Запам’ятовуємо позицію найкращого кандидата
Кандидат є елементом, який поки що має найкраще знайдене значення. Для мінімуму це найменше число серед уже переглянутих, для максимуму найбільше.
У змінній minIndex або maxIndex зберігаємо індекс кандидата. Його значення читаємо як arr[minIndex] або arr[maxIndex].
У непорожньому масиві завжди є мінімум і максимум. При пошуку лише серед елементів з певною ознакою може не бути жодного кандидата: тоді повертаємо −1.
Індекс 0 є правильною відповіддю. Індекс −1 означає відсутність результату. Не звертаємося до arr[−1].
Приклад 1
Індекс першого мінімального елемента
int IndMin(int arr[], int n) {
if (n == 0) return -1;
int minIndex = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[minIndex]) minIndex = i;
}
return minIndex;
}Якщо елементів немає, повертаємо −1. Інакше перший елемент стає початковим кандидатом. Тому minIndex = 0, а цикл починаємо з i = 1.
Порівнюємо саме arr[i] < arr[minIndex], а не індекси i та minIndex. Якщо число менше, запам’ятовуємо його позицію.
Для 7 5 8 5 9 6 кандидат зміниться з індексу 0 на 1. Друга п’ятірка не менша за першу, тому індекс залишиться 1.
Повна програма з RandArr та PrintArr
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
int IndMin(int arr[], int n) {
if (n == 0) return -1;
int minIndex = 0;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[minIndex]) minIndex = i;
}
return minIndex;
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cin >> n >> a >> b;
if (n < 1 || n > capacity || a < -100 || a > 100 ||
b < -100 || b > 100 || a > b) {
cout << "Incorrect data\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int index = IndMin(mass, n);
if (index == -1) cout << "Not found\n";
else cout << "Index=" << index << " Value=" << mass[index] << "\n";
}
return 0;
}Введіть n, a, b. Межі навчального прикладу: 1 ≤ n ≤ 100, −100 ≤ a ≤ b ≤ 100. Випадковий набір може відрізнятися між запусками.
Однакові значення: перший чи останній?
Під час руху зліва направо результат залежить від знака порівняння:
| Що шукаємо | Коли оновлюємо індекс |
|---|---|
| Перший мінімум | arr[i] < arr[index] |
| Останній мінімум | arr[i] <= arr[index] |
| Перший максимум | arr[i] > arr[index] |
| Останній максимум | arr[i] >= arr[index] |
Строге порівняння зберігає першого кандидата за рівних значень. Порівняння з рівністю дозволяє замінити його пізнішим.
«Перший мінімум» не означає найменший індекс серед усіх елементів. Спочатку знаходимо мінімальне значення, потім обираємо його перше входження.
Приклад 2
Останній максимум серед парних чисел
int IndMax(int arr[], int n) {
int maxIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) {
if (maxIndex == -1) {
maxIndex = i;
} else if (arr[i] >= arr[maxIndex]) {
maxIndex = i;
}
}
}
return maxIndex;
}Спочатку maxIndex = −1. Перший парний елемент стає кандидатом незалежно від його значення. Так правильно обробляються й від’ємні парні числа.
Лише після появи кандидата порівнюємо з arr[maxIndex]. Умова >= вибирає останній індекс за однакових максимальних значень.
arr: 3 8 5 2 8 7 індекс: 0 1 2 3 4 5 Відповідь: індекс 4, значення 8
Для −6 −2 −4 −2 відповідь: індекс 3, значення −2. Для 3 7 5 9 1 результат −1, бо парних немає. Нуль є парним.
Повна програма з RandArr та PrintArr
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
int IndMax(int arr[], int n) {
int maxIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) {
if (maxIndex == -1) {
maxIndex = i;
} else if (arr[i] >= arr[maxIndex]) {
maxIndex = i;
}
}
}
return maxIndex;
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cin >> n >> a >> b;
if (n < 1 || n > capacity || a < -100 || a > 100 ||
b < -100 || b > 100 || a > b) {
cout << "Incorrect data\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int index = IndMax(mass, n);
if (index == -1) cout << "Not found\n";
else cout << "Index=" << index << " Value=" << mass[index] << "\n";
}
return 0;
}Введіть n, a, b. Межі навчального прикладу: 1 ≤ n ≤ 100, −100 ≤ a ≤ b ≤ 100. Випадковий набір може відрізнятися між запусками.
Приклад 3
Останній мінімум серед чисел Фібоначчі
Використаємо послідовність 0, 1, 1, 2, 3, 5, 8, 13, 21…. Кожне наступне число є сумою двох попередніх. Від’ємні числа не належать цій послідовності.
bool IsFib(int x) {
if (x < 0) return false;
long long previous = 0, current = 1;
while (current < x) {
long long next = previous + current;
previous = current;
current = next;
}
return x == 0 || current == x;
}Поки current менше за x, обчислюємо наступне число. Коли досягли x або перевищили його, перевіряємо рівність. Нуль враховуємо окремо.
long long є ширшим цілим типом: проміжне наступне число може перевищити діапазон int. Для аргументу x типу int цього запасу достатньо в звичних навчальних середовищах.
int IndMin(int arr[], int n) {
int minIndex = -1;
for (int i = 0; i < n; i++) {
if (IsFib(arr[i])) {
if (minIndex == -1) {
minIndex = i;
} else if (arr[i] <= arr[minIndex]) {
minIndex = i;
}
}
}
return minIndex;
}Умова <= зберігає останнє входження найменшого відповідного значення. Перший відповідний елемент, як і в прикладі 2, стає кандидатом без порівняння.
| Масив для перевірки | Правильна відповідь |
|---|---|
| 1 8 13 5 21 2 3 4 | Індекс 0, значення 1 |
| 6 7 8 9 10 | Індекс 2, значення 8 |
| 1 1 2 3 5 1 8 | Індекс 5, значення 1 |
| 4 6 7 9 10 | −1, відповідних чисел немає |
Це фіксовані набори для перевірки функції, а не гарантований вивід rand(). У початковій версії перші два результати були неправильними: 1 і 8 теж є числами Фібоначчі.
Повна програма з RandArr та PrintArr
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void RandArr(int arr[], int n, int a, int b) {
for (int i = 0; i < n; i++) arr[i] = a + rand() % (b - a + 1);
}
void PrintArr(int arr[], int n) {
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\n";
}
bool IsFib(int x) {
if (x < 0) return false;
long long previous = 0, current = 1;
while (current < x) {
long long next = previous + current;
previous = current;
current = next;
}
return x == 0 || current == x;
}
int IndMin(int arr[], int n) {
int minIndex = -1;
for (int i = 0; i < n; i++) {
if (IsFib(arr[i])) {
if (minIndex == -1) {
minIndex = i;
} else if (arr[i] <= arr[minIndex]) {
minIndex = i;
}
}
}
return minIndex;
}
int main() {
const int capacity = 100;
int mass[capacity];
int n, a, b;
cin >> n >> a >> b;
if (n < 1 || n > capacity || a < -100 || a > 100 ||
b < -100 || b > 100 || a > b) {
cout << "Incorrect data\n";
} else {
srand(time(0));
RandArr(mass, n, a, b);
PrintArr(mass, n);
int index = IndMin(mass, n);
if (index == -1) cout << "Not found\n";
else cout << "Index=" << index << " Value=" << mass[index] << "\n";
}
return 0;
}Введіть n, a, b. Межі навчального прикладу: 1 ≤ n ≤ 100, −100 ≤ a ≤ b ≤ 100. Випадковий набір може відрізнятися між запусками.
Стеж за індексом кандидата
Від 1 до 10 цілих чисел від −100 до 100. Параметри застосовуються після натискання кнопки.
Індекс кандидата
Значення кандидата
Рамка позначає щойно перевірений елемент, зелений фон поточного кандидата. Модель починає з відсутності кандидата для всіх режимів; у прикладі 1 без відбору перший елемент одразу обраний до циклу.
Варіанти для учнів
Усі 17 варіантів збережено. Обирайте стандартний масив зі сталою місткістю, перевіряйте 1 ≤ n ≤ 100 та використовуйте RandArr і PrintArr. Для навчальних запусків підходять межі −100 ≤ a ≤ b ≤ 100.
У прототипах int* arr та int arr[] означають той самий тип параметра. У варіантах 14, 15 та 17 потрібні саме значення, а не індекси.
Варіант 1
Напишіть функцію, яка знаходить індекс першого максимального елемента серед усіх елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 2
Напишіть функцію, яка знаходить індекс останнього максимального елемента серед від’ємних елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 3
Напишіть функцію, яка знаходить індекс першого мінімального елемента серед додатних елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 4
Напишіть функцію, яка знаходить індекс першого максимального елемента серед однозначних елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Однозначні числа мають модуль від 0 до 9, двозначні від 10 до 99. Мінус не є цифрою.
↑ До вибору варіантаВаріант 5
Напишіть функцію, яка знаходить індекс останнього мінімального елемента серед двозначних елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Однозначні числа мають модуль від 0 до 9, двозначні від 10 до 99. Мінус не є цифрою.
↑ До вибору варіантаВаріант 6
Напишіть функцію, яка знаходить індекс останнього максимального елемента серед непарних елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 7
Напишіть функцію, яка знаходить індекс першого мінімального елемента серед парних елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 8
Напишіть функцію, яка знаходить індекс першого максимального елемента серед чисел, кратних 3 елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 9
Напишіть функцію, яка знаходить індекс останнього мінімального елемента серед чисел, кратних 5 елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
↑ До вибору варіантаВаріант 10
Напишіть функцію, яка знаходить індекс останнього максимального елемента серед чисел, що закінчуються цифрою 3 елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Останню цифру перевіряємо без знака числа: наприклад, −13 закінчується цифрою 3.
↑ До вибору варіантаВаріант 11
Напишіть функцію, яка знаходить індекс першого мінімального елемента серед чисел, що закінчуються цифрою 5 елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Останню цифру перевіряємо без знака числа: наприклад, −13 закінчується цифрою 3.
↑ До вибору варіантаВаріант 12
Напишіть функцію, яка знаходить індекс першого максимального елемента серед чисел, що починаються цифрою 2 елементів масиву.
int IndMax(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMax. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Для першої цифри використайте функцію FirstDig. Знак мінус не враховуємо: перша цифра −21 є 2.
↑ До вибору варіантаВаріант 13
Напишіть функцію, яка знаходить індекс останнього мінімального елемента серед чисел, що починаються цифрою 1 елементів масиву.
int IndMin(int* arr, int n);Програма заповнює масив через RandArr, виводить його через PrintArr та викликає IndMin. Виведіть знайдений елемент і його індекс. Якщо відповідних елементів немає, поверніть −1 та виведіть повідомлення.
Для першої цифри використайте функцію FirstDig. Знак мінус не враховуємо: перша цифра −21 є 2.
↑ До вибору варіантаВаріант 14
Напишіть Min, яка знаходить мінімальне значення в непорожньому масиві, та NumMin, яка рахує елементи, що дорівнюють x.
int Min(int* arr, int n);
int NumMin(int* arr, int n, int x);Заповніть і виведіть масив через RandArr та PrintArr. Знайдіть і виведіть мінімальне значення функцією Min. Передайте його як x у NumMin і виведіть кількість таких елементів.
Тут Min повертає саме значення, а не індекс.
↑ До вибору варіантаВаріант 15
Напишіть Max, яка знаходить максимальне значення в непорожньому масиві, та NumMax, яка рахує елементи, що дорівнюють x.
int Max(int* arr, int n);
int NumMax(int* arr, int n, int x);Заповніть і виведіть масив через RandArr та PrintArr. Знайдіть і виведіть максимальне значення функцією Max. Передайте його як x у NumMax і виведіть кількість таких елементів.
Тут Max повертає саме значення, а не індекс.
↑ До вибору варіантаВаріант 16
Напишіть функції для індексів першого мінімального та першого максимального елементів:
int IndMin(int* arr, int n);
int IndMax(int* arr, int n);Заповніть і виведіть масив через RandArr та PrintArr. Знайдіть обидва індекси, виведіть значення й індекси та визначте, який індекс менший. Якщо індекси однакові, повідомте про це.
↑ До вибору варіантаВаріант 17
Напишіть функції для мінімального та максимального значень:
int Max(int* arr, int n);
int Min(int* arr, int n);Заповніть і виведіть масив через RandArr та PrintArr. Знайдіть і виведіть мінімальне й максимальне значення, потім обчисліть їхнє середнє арифметичне. Використайте ділення на 2.0, щоб не втратити дробову частину.
↑ До вибору варіантаПеревір себе
Що зберігає minIndex: число чи позицію?
Позицію. Значення отримуємо через arr[minIndex].
Чому не починаємо мінімум зі значення 0?
Мінімум може бути додатним. Потрібен справжній кандидат із масиву, а не довільне число.
Як перейти від першого максимуму до останнього?
Під час руху зліва направо замінити порівняння > на >=.
Коли можна читати arr[index]?
Після перевірки, що індекс знайдено й він не дорівнює −1.
Що робити, якщо всі значення однакові?
Перший мінімум і перший максимум мають індекс 0. Останні мають індекс n − 1.