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

ЛР36. Рекурсія і повторна робота

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

Функція рахує кількість способів дійти до позиції n, використовуючи кроки 1 або 2. Варіант визначає STUDENT_X.

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

1. Умова

Функція рахує кількість способів дійти до позиції n, використовуючи кроки 1 або 2.

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

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

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

  1. рекурсія
  2. базовий випадок
  3. кількість викликів
  4. ітеративне порівняння

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

Використовуйте поняття, вивчені до Л1–Л14. Не використовуйте мемоізацію в основному завданні. Мета — побачити повторну роботу наївної рекурсії.

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

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

Вхідні дані

Поле Зміст
n цільова позиція
probe_n малий контрольний приклад трасування для ручної перевірки

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

Поле Зміст
ways_result кількість способів
probe_ways результат малого контрольного прикладу
recursive_calls кількість викликів наївної рекурсії
iterative_steps кількість ітеративних оновлень після базових значень

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

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

Терміни

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

Правила

  1. Використовуйте рекурентне правило ways(0) = 1, ways(1) = 1, ways(n) = ways(n-1) + ways(n-2) для n >= 2.
  2. recursive_calls рахує кожний вхід у рекурсивну функцію, включно з базовими випадками.
  3. probe_ways — результат тієї самої рекурентне правило для probe_n.
  4. iterative_steps рахує переходи ітеративної версії від стану для n = 1 до стану для заданого n; для n >= 1 це n - 1.

5. Завдання

Завдання 1

Реалізуйте ways(n) за наведеним правилом. Запишіть ways_result і probe_ways.

Завдання 2

Порахуйте всі виклики рекурсивної функції та запишіть їх у recursive_calls.

Завдання 3

Реалізуйте ітеративне обчислення. Запишіть iterative_steps і коротко порівняйте кількість роботи.

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

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

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