ЛР13. Порівняння пошуків і проєктування тестів

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

Є два сценарії: багато запитів до вже впорядкованих даних та один запит до невпорядкованої послідовності. Варіант визначає STUDENT_X.

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

1. Умова

Є два сценарії: багато запитів до вже впорядкованих даних та один запит до невпорядкованої послідовності.

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

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

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

1. лінійний і двійковий пошук
2. значення n
3. підрахунок операцій
4. проєктування тестів

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

Використовуйте поняття, вивчені до Л1–Л7. Не включайте в одноразовий пошук у невпорядкованих даних окрему сортировку: її прямо виключає умова цієї задачі.

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

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

Вхідні дані

Поле	Тип	Зміст
sorted_values	std::vector<int>	впорядкований набір даних для повторних запитів
unsorted_values	std::vector<int>	невпорядкований набір даних для одного запиту
target_sorted	int	ціль у першому сценарії
target_unsorted	int	ціль у другому сценарії

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

Поле	Зміст
choice_sorted	binary або linear для впорядкованих даних
choice_unsorted	вибір для одноразового пошуку в невпорядкованих даних
linear_comparisons	порівняння у другому сценарії
binary_iterations	ітерації у першому сценарії

Назви полів результату не змінюйте. Перша комірка лише показує значення варіанта і не оголошує предметні змінні. Перед розв’язанням кожного завдання самостійно оголосіть потрібні вхідні змінні з показаними значеннями. Власні та результуючі змінні також оголошуйте звичайно, як у лекційних прикладах. Обчислення виконуйте у блоці { ... }; код над блоком використовуйте лише там, де це позначено. Наприкінці блока вже є службовий рядок самоперевірки для контрольних полів — його не потрібно писати або змінювати. Формат std::cout обирайте за змістом завдання: спеціального формату для самоперевірки немає.

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

Терміни

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

Правила

1. Для sorted_values дані вже впорядковані та передбачають багато пошукових запитів.
2. Для unsorted_values передбачений один пошуковий запит; попереднє сортування у цьому сценарії заборонене умовою.
3. linear_comparisons рахує порівняння з target_unsorted до першого збігу.
4. binary_iterations рахує перевірені середини під час пошуку target_sorted.

5. Завдання

Завдання 1

Виберіть пошук для впорядкованих і невпорядкованих даних. Запишіть назви у choice_sorted і choice_unsorted та коротко поясніть вибір.

Завдання 2

Порахуйте linear_comparisons для unsorted_values і binary_iterations для sorted_values.

Завдання 3

Перевірте лінійний пошук на відсутньому значенні, а двійковий — на останньому елементі. Виведіть результати обох тестів.

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

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

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