C++ • Алгоритми пошуку

Тема 4 • Перша й остання знахідка

Знайти число
і запам’ятати його номер

Пошук першого та останнього числа із заданою властивістю

Числа: 13, 8, 7, −12

Шукаємо однозначні

Перше: 8, номер 2

Останнє: 7, номер 3

«Перше» й «останнє» означає порядок введення, а не розмір числа

Запам’ятовуємо дві речі

На попередніх сторінках ми відбирали числа, рахували їх або перевіряли їхню наявність. Тепер потрібно зберегти конкретне число й місце, на якому його ввели.

  • a: поточне введене число.
  • i: його порядковий номер, починаючи з 1.
  • value: запам’ятоване число.
  • position: запам’ятований номер.

Тип value такий самий, як у введених чисел. Тип position завжди цілий.

int position = 0;
int value = 0;

position == 0 означає «ще не знайдено». Номери починаються з 1, тому 0 зручно використати як ознаку відсутності знахідки. Саме число 0 при цьому може бути правильною знахідкою.

Початкове значення value = 0 лише задає стан змінної. Наявність результату перевіряємо за position, а не за value.

Перше зберігаємо, останнє оновлюємо

Перше число

Якщо число підходить і ще нічого не знайдено, запам’ятовуємо його. Далі знахідку не змінюємо.

if (a >= -9 && a <= 9 && position == 0) {
    value = a;
    position = i;
}

Останнє число

Якщо число підходить, щоразу запам’ятовуємо його. Нова знахідка замінює попередню.

if (a >= -9 && a <= 9) {
    value = a;
    position = i;
}

Серед усіх цілих однозначними вважаємо числа від −9 до 9 включно. Знак мінус не є цифрою. Наприклад, −7 і 0 однозначні, а −12 та 10 ні.

Масив не потрібний: у цих прикладах читаємо по одному числу й зберігаємо тільки поточну знахідку.

Три приклади з повними програмами

Спочатку вводимо n, потім рівно n чисел. Для роботи використовуй n від 1 до 1000.

Приклад 1. Останнє однозначне число

За кожного однозначного числа оновлюємо і значення, і номер. У кінці залишиться остання знахідка.

#include <iostream>
using namespace std;

int main() {
    int n, position = 0;
    int a, value = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (a >= -9 && a <= 9) {
            value = a;
            position = i;
        }
    }
    if (position == 0) {
        cout << "NO";
    } else {
        cout << value << " " << position;
    }
    return 0;
}

Введення

4
13 8 7 -12

Виведення

7 3

Приклад 2. Перше однозначне число

Додаємо перевірку position == 0. Запам’ятовуємо число лише тоді, коли знахідок ще не було.

#include <iostream>
using namespace std;

int main() {
    int n, position = 0;
    int a, value = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (a >= -9 && a <= 9 && position == 0) {
            value = a;
            position = i;
        }
    }
    if (position == 0) {
        cout << "NO";
    } else {
        cout << value << " " << position;
    }
    return 0;
}

Введення

4
13 8 7 -12

Виведення

8 2

Приклад 3. Перше від’ємне дійсне число

Алгоритм той самий. Змінюємо властивість на a < 0, а для самих чисел використовуємо double. Номер залишається цілим.

#include <iostream>
using namespace std;

int main() {
    int n, position = 0;
    double a, value = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (a < 0 && position == 0) {
            value = a;
            position = i;
        }
    }
    if (position == 0) {
        cout << "NO";
    } else {
        cout << value << " " << position;
    }
    return 0;
}

Введення

4
8.1 -3.2 7.3 -2.5

Виведення

-3.2 2

Якщо потрібних чисел немає, програми виводять NO. Наприклад, серед 81, 57, 322 однозначних немає.

Одна послідовність, дві знахідки

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

Перша знахідка

Остання знахідка

Що перевірити у своїй програмі

  • Значення й номер запам’ятовуємо разом.
  • Для першої знахідки додаємо перевірку position == 0.
  • Для останньої знахідки цю перевірку не додаємо.
  • Якщо число не підходить, попередню знахідку не скидаємо.
  • У цих програмах цикл читає всі n чисел, навіть якщо перше потрібне число вже знайдено.
  • Після циклу спочатку перевіряємо номер і лише потім виводимо знайдене значення.

Порядковий номер не є кількістю потрібних чисел. Наприклад, у 13, 8, 7, −12 є два однозначні числа, але номер останнього з них дорівнює 3.

Варіанти для самостійної роботи

У кожному варіанті два пункти. Усі числа вводимо в заданому порядку; порядкові номери починаються з 1. Для кратності b ≠ 0. Для діапазону [x; y] вважаємо x ≤ y та включаємо обидві межі.

Як перевіряти цифри від’ємних чисел

Знак мінус не враховуємо. Наприклад, −16 є двозначним і закінчується цифрою 6. Для звичайних невеликих цілих чисел можна спочатку отримати невід’ємне значення:

int t = a;
if (t < 0) {
    t = -t;
}

Далі перевіряємо цифри t. Остання цифра: t % 10; дві останні: t % 100. «Закінчується на 00» означає наявність двох нулів у кінці запису, наприклад 100 або −200, але не 0. Для цього підійде t >= 100 && t % 100 == 0.

Варіант 1

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше від’ємне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке кратне 10 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 2

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке кратне 5 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, що дорівнює 0 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 3

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке кратне 3 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке закінчується цифрою 1 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 4

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше додатне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке закінчується цифрою 2 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 5

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше додатне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке кратне 4 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 6

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке закінчується цифрою 0 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє парне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 7

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке закінчується на 33 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке кратне 7 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 8

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше додатне однозначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке кратне b та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 9

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше двозначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє двозначне число, яке закінчується на 6 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 10

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке закінчується цифрою 3 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє двозначне від’ємне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 11

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке закінчується цифрою 5 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє додатне тризначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 12

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше двозначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке закінчується на 00 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 13

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше двозначне число, яке складається з однакових цифр та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке кратне b та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 14

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке належить інтервалу [x; y] та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє тризначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 15

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше тризначне число та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє від’ємне число, яке закінчується на 55 та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 16

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше число, яке належить інтервалу [x; y] та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє додатне тризначне число, яке складається з різних цифр та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта

Варіант 17

  1. Дано n цілих чисел. Знайдіть серед цих чисел перше двозначне число, яке складається з різних цифр та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
  2. Дано n цілих чисел. Знайдіть серед цих чисел останнє число, яке належить інтервалу [x; y] та кратне b та його порядковий номер. Якщо таких чисел немає, то виведіть NO.
↑ До вибору варіанта