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

ЛР18. Порівняння алгоритмів і рефакторинг

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

Одне підсумкове значення обчислюється ітеративно та рекурсивним методом «поділяй і володарюй». Варіант визначає STUDENT_X.

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

1. Умова

Одне підсумкове значення обчислюється ітеративно та рекурсивним методом «поділяй і володарюй».

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

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

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

  1. ітеративний алгоритм
  2. рекурсія і метод «поділяй і володарюй»
  3. порівняння роботи
  4. рефакторинг зі збереженням поведінки

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

Використовуйте поняття, вивчені до Л1–Л8. Не робіть висновок про ефективність лише з часу одного запуску. Використовуйте структуру роботи й кількість операцій.

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

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

Вхідні дані

Поле Зміст
values послідовність чисел

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

Поле Зміст
iterative_result ітеративний результат
recursive_result рекурсивний результат
equivalent збіг двох результатів
iterative_steps кількість опрацьованих елементів

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

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

Терміни

  • еквівалентність — два алгоритми дають однаковий результат для тих самих допустимих даних.
  • рефакторинг — зміна структури коду зі збереженням результату.

Правила

  1. Обидві реалізації обчислюють суму всіх елементів values.
  2. Ітеративна версія опрацьовує кожний елемент один раз; iterative_steps дорівнює кількості елементів.
  3. Рекурсивна версія ділить діапазон на дві частини, доки піддіапазон не стане порожнім або одноелементним.
  4. equivalent підтверджує рівність двох агрегатів на даних варіанта.

5. Завдання

Завдання 1

Обчисліть суму values циклом. Запишіть iterative_result і iterative_steps.

Завдання 2

Обчисліть ту саму суму рекурсивно через поділ діапазону навпіл. Запишіть recursive_result.

Завдання 3

Запишіть у equivalent, чи збігаються результати. Змініть структуру коду без зміни результату та перевірте ще раз.

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

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

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