Що саме ми шукаємо
Функція отримує масив і кількість елементів n. Вона повертає індекс елемента з потрібною ознакою: наприклад, від’ємного чи простого числа.
| Результат функції | Що означає |
|---|---|
| 0…n − 1 | Індекс знайденого елемента |
| −1 | Потрібного елемента немає |
−1 не є допустимим індексом масиву. Тому його зручно використати як ознаку відсутності. Значення самого елемента при цьому цілком може дорівнювати −1.
Індекс починається з нуля. Знайдений індекс 0 означає успішний пошук першого елемента, а не відсутність.
Приклад 1
Перший від’ємний: знайшли й завершуємо
int FindFirst(int arr[], int n) {
for (int i = 0; i < n; i++) {
if (arr[i] < 0) return i;
}
return -1;
}Переглядаємо індекси від 0. Щойно arr[i] < 0, команда return i; завершує всю функцію. Решту елементів не переглядаємо.
return -1; стоїть після циклу. Він виконається лише тоді, коли цикл завершився без збігу.
arr: 4 −1 0 −3 7 −1 індекс: 0 1 2 3 4 5 Відповідь: індекс 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 FindFirst(int arr[], int n) {
for (int i = 0; i < n; i++) {
if (arr[i] < 0) return i;
}
return -1;
}
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 = FindFirst(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. Випадкові елементи можуть відрізнятися між запусками.
Приклад 2
Останній від’ємний: запам’ятовуємо кожний збіг
int FindLast(int arr[], int n) {
int lastIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) lastIndex = i;
}
return lastIndex;
}Початково lastIndex = −1: ще нічого не знайдено. При кожному збігу записуємо новий індекс. Він розташований правіше від попереднього, бо i зростає.
У масиві 4 −1 0 −3 7 −1 lastIndex змінюється так:
−1 → 1 → 3 → 5
Повертаємо lastIndex після всього циклу. Якщо від’ємних немає, він так і залишиться −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 FindLast(int arr[], int n) {
int lastIndex = -1;
for (int i = 0; i < n; i++) {
if (arr[i] < 0) lastIndex = i;
}
return lastIndex;
}
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 = FindLast(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. Випадкові елементи можуть відрізнятися між запусками.
Додатково: можна шукати справа наліво
int FindLast(int arr[], int n) {
for (int i = n - 1; i >= 0; i--) {
if (arr[i] < 0) return i;
}
return -1;
}Починаємо з n − 1. Перший збіг під час руху справа наліво є останнім у звичайному порядку масиву. Це альтернативний опис FindLast, його не треба вставляти поруч із попереднім описом тієї самої функції.
Приклад 3
Змінимо умову: останнє просте число
Схема пошуку та сама. Замість arr[i] < 0 перевіряємо IsPrime(arr[i]). Прості числа більші за 1 й мають рівно два натуральні дільники.
bool IsPrime(int x) {
if (x < 2) return false;
for (int d = 2; d <= x / d; d++) {
if (x % d == 0) return false;
}
return true;
}Якщо знайдено дільник d, число не просте. Умова d <= x / d для додатного x перевіряє дільники до квадратного кореня включно, не використовуючи sqrt та множення d · d.
int FindLastPrime(int arr[], int n) {
int lastIndex = -1;
for (int i = 0; i < n; i++) {
if (IsPrime(arr[i])) lastIndex = i;
}
return lastIndex;
}Наприклад, для 4 −1 0 −3 7 −1 відповідь 4, бо arr[4] = 7. Нуль, одиниця та від’ємні числа не є простими.
Повна програма з 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 IsPrime(int x) {
if (x < 2) return false;
for (int d = 2; d <= x / d; d++) {
if (x % d == 0) return false;
}
return true;
}
int FindLastPrime(int arr[], int n) {
int lastIndex = -1;
for (int i = 0; i < n; i++) {
if (IsPrime(arr[i])) lastIndex = i;
}
return lastIndex;
}
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 = FindLastPrime(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. Випадкові елементи можуть відрізнятися між запусками.
Спочатку перевіряємо індекс, потім читаємо елемент
int index = FindFirst(mass, n);
if (index == -1) {
cout << "Not found\n";
} else {
cout << "Index=" << index << " Value=" << mass[index] << "\n";
}Не можна звертатися до mass[index] до перевірки: за відсутності збігу це було б mass[−1], вихід за межі масиву.
Для самоперевірки повних програм можна задати однакові межі генерації:
| Ввід n, a, b | FindFirst | FindLast | FindLastPrime |
|---|---|---|---|
| 3 −2 −2 | Index=0 Value=−2 | Index=2 Value=−2 | Not found |
| 3 2 2 | Not found | Not found | Index=2 Value=2 |
Порівняй перший та останній збіг
Від 1 до 10 цілих чисел від −100 до 100. Умову й масив застосовуємо після натискання кнопки.
Знайдений індекс
Значення елемента
Рамка виділяє щойно перевірений елемент. Зелений фон позначає збережений збіг. До завершення пошуку останнього елемента результат ще може змінитися.
Варіанти для учнів
Збережено всі 17 варіантів, імена функцій та допоміжних перевірок. Програма кожного варіанта має однакову послідовність: RandArr, PrintArr, пошук індексу, перевірка результату й виведення.
Використовуйте масив зі сталою місткістю 100, n від 1 до 100 і для навчальних запусків −100 ≤ a ≤ b ≤ 100. У параметрах функцій int* arr та int arr[] тут означають той самий тип. Індекс повертається як int.
Варіант 1
Напишіть функцію, яка знаходить індекс першого парного числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
↑ До вибору варіантаВаріант 2
Напишіть функцію, яка знаходить індекс останнього непарного числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
↑ До вибору варіантаВаріант 3
Напишіть функцію, яка знаходить індекс першого числа, кратного 3 у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Нуль кратний 3: 0 % 3 дорівнює 0. Від’ємні кратні теж враховуємо.
↑ До вибору варіантаВаріант 4
Напишіть функцію, яка знаходить індекс останнього числа, кратного 5 у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Нуль та від’ємні кратні 5 теж підходять.
↑ До вибору варіантаВаріант 5
Напишіть функцію, яка знаходить індекс першого числа, що закінчується цифрою 0 у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Нуль закінчується цифрою 0. Від’ємні числа на зразок −20 також підходять.
↑ До вибору варіантаВаріант 6
Напишіть функцію, яка знаходить індекс останнього числа, що закінчується цифрою 5 у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Останню цифру розглядаємо без знака: 15 і −15 закінчуються цифрою 5.
↑ До вибору варіантаВаріант 7
Напишіть функцію, яка знаходить індекс першого однозначного числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Однозначними вважаємо цілі числа від −9 до 9 включно. Знак мінус не є цифрою.
↑ До вибору варіантаВаріант 8
Напишіть функцію, яка знаходить індекс останнього двозначного числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Двозначними вважаємо числа, модуль яких від 10 до 99 включно.
↑ До вибору варіантаВаріант 9
Напишіть функцію, яка знаходить індекс першого числа, що починається цифрою 1 у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Для перевірки використайте функцію FirstDig для першої цифри.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
FirstDig визначає першу цифру без знака числа. Наприклад, для −123 це 1, а для 0 це 0.
↑ До вибору варіантаВаріант 10
Напишіть функцію, яка знаходить індекс останнього числа, що починається цифрою 7 у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Для перевірки використайте функцію FirstDig для першої цифри.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
FirstDig визначає першу цифру без знака числа. Наприклад, для −72 це 7.
↑ До вибору варіантаВаріант 11
Напишіть функцію, яка знаходить індекс першого простого числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Для перевірки використайте функцію IsPrime.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
↑ До вибору варіантаВаріант 12
Напишіть функцію, яка знаходить індекс останнього непростого числа у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Для перевірки використайте функцію IsPrime.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Тут «непросте» означає !IsPrime(x). Отже, підходять також 0, 1 та від’ємні числа. Це не те саме, що складене натуральне число.
↑ До вибору варіантаВаріант 13
Напишіть функцію, яка знаходить індекс першого числа Фібоначчі у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Для перевірки використайте функцію IsFib.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Домовимося використовувати послідовність 0, 1, 1, 2, 3, 5, 8… Від’ємні числа не належать їй.
↑ До вибору варіантаВаріант 14
Напишіть функцію, яка знаходить індекс останнього числа Фібоначчі у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Для перевірки використайте функцію IsFib.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Домовимося використовувати послідовність 0, 1, 1, 2, 3, 5, 8… Від’ємні числа не належать їй.
↑ До вибору варіантаВаріант 15
Напишіть функцію, яка знаходить індекс першого числа з парною сумою цифр у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Для перевірки використайте функцію SumDig для суми цифр.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
SumDig обчислює суму цифр без знака числа. Для −24 результат 6, для 0 результат 0. Сума 0 парна.
↑ До вибору варіантаВаріант 16
Напишіть функцію, яка знаходить індекс останнього числа з непарною сумою цифр у масиві. Якщо такого елемента немає, поверніть −1.
int FindLast(int* arr, int n);Для перевірки використайте функцію SumDig для суми цифр.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindLast та виводить знайдений елемент і його індекс або повідомлення про відсутність.
SumDig обчислює суму цифр без знака числа. Наприклад, для −25 результат 7.
↑ До вибору варіантаВаріант 17
Напишіть функцію, яка знаходить індекс першого числа-паліндрома у масиві. Якщо такого елемента немає, поверніть −1.
int FindFirst(int* arr, int n);Для перевірки використайте функцію IsPal.
Програма заповнює масив функцією RandArr, виводить його через PrintArr, викликає FindFirst та виводить знайдений елемент і його індекс або повідомлення про відсутність.
Для цієї вправи паліндромами вважаємо невід’ємні числа, запис яких однаковий зліва направо та справа наліво. Нуль і всі однозначні невід’ємні числа підходять; від’ємні не підходять.
↑ До вибору варіантаПеревір себе
Чим return i відрізняється від lastIndex = i?
return i одразу завершує функцію та повертає індекс. Присвоювання лише запам’ятовує індекс, і перебір триває.
Чому пошук може повернути 0?
Тому що потрібний елемент може стояти на індексі 0, на самому початку.
Чи може знайдений елемент дорівнювати −1?
Так. Функція повертає його індекс, наприклад 1. Це не те саме, що повернений індекс −1 за відсутності збігу.
Що робити, якщо функція повернула −1?
Вивести повідомлення. Не звертатися до елемента з таким індексом.
Чи є 1 простим числом?
Ні. Прості числа більші за 1.