Перейти до змісту

ЛР13. Лінійний пошук: контракт і підрахунок операцій

Коротко про роботу

Потрібно знайти першу позицію цільового значення у невпорядкованій послідовності. Варіант визначає STUDENT_X.

Відкрити робочий зошит Як виконувати лабораторні

1. Умова

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

Усі обчислення виконуйте з даними свого STUDENT_X. Значення варіанта друкує перша комірка зошита.

2. Що треба знати

Робота виконується після Л1–Л7. Потрібні поняття:

  1. лінійний пошук
  2. умова функції
  3. операція порівняння
  4. O(n)

Межа матеріалу

Використовуйте поняття, вивчені до Л1–Л7. Не сортуйте дані перед пошуком. Це змінило б початкову умову задачі.

3. Варіант, вхідні дані та результат

У зошиті заповніть STUDENT_NAME, STUDENT_GROUP і STUDENT_X від 1 до 30.

Вхідні дані

Поле Зміст
values невпорядкована послідовність
target цільове значення

Поля результату

Поле Зміст
found_index перша позиція або -1
comparisons кількість порівнянь із цільовим значенням
found ознака успішного пошуку

Назви полів результату не змінюйте.

4. Терміни і правила

Терміни

  • лінійний пошук — послідовна перевірка елементів від початку до першого збігу.
  • порівняння — одна перевірка element == target; саме такі перевірки треба рахувати.

Правила

  1. found_index — нульовий індекс першого елемента, рівного target; для відсутньої цілі використовуйте -1.
  2. comparisons рахує лише перевірки виду «поточний елемент дорівнює target».
  3. Пошук завершується після першого збігу або після перевірки останнього елемента.
  4. found має бути true рівно тоді, коли found_index не дорівнює -1.

5. Завдання

Завдання 1

Реалізуйте лінійний пошук першого target. Запишіть found_index, found і кількість порівнянь у comparisons.

Завдання 2

Запустіть пошук для першого елемента, початкового target і відсутнього значення. Для кожного випадку виведіть індекс, кількість порівнянь і результат пошуку.

Завдання 3

Для трьох перевірок запишіть очікувано → отримано. Після цього знову обчисліть контрольні поля для початкового target.

6. Перевірка і здача

  1. Запустіть самоперевірку та виправте помилки.
  2. Перезапустіть ядро і виконайте роботу ще раз від початку.
  3. Збережіть .ipynb і PDF з кодом та результатами.

Назва PDF: LR13_Прізвище_Група_VNN.pdf.