C++ • Мінімум та максимум

Тема 8 • Шукаємо індекс екстремального значення

Де стоїть найменше
або найбільше число?

Порівнюємо значення, запам’ятовуємо індекс

Масив: 7 5 8 5 9 6

Мінімальне значення: 5

Його перший індекс: 1

Його останній індекс: 3

Значення одне, позицій може бути кілька.

Запам’ятовуємо позицію найкращого кандидата

Кандидат є елементом, який поки що має найкраще знайдене значення. Для мінімуму це найменше число серед уже переглянутих, для максимуму найбільше.

У змінній 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.