Динамічне програмування (одновимірний підхід)

Покликання для онлайн-уроку (Google Meet)

Гімнастика для очей

Відеоінструкція (1 хв)

Тест містить 8 питань. Час виконання тесту 10 хв.

Задача "Числа Фібоначчі"

Описати рекурсивну функцію Fib(N) цілого типу, яка обчислює N-й елемент послідовності чисел Фібоначчі (N - ціле число):F₁ = F₂ = 1, F_N = F_N-2 + F_N-1, N = 3, 4, ...

Відповіді (приклади, як можна було б подати код):

Рекурсивний запис

Рекурсія з запам'ятовуванням (довжину масива залежить від контексту задачі, тому в цьому завдання її можна було вибрати довільною, наприклад, 100).

Табуляція

Задача "Сума цифр"

Скласти рекурсивну функцію S(N), яка повертає суму цифр у заданому натуральному числі N (N>=0)

Рекурсивний запис

Рекурсія з запам'ятовуванням

Табуляція

Задача. "Створи паліндром".

Паліндром – це послідовність символів, яка зліва-направо та справа-наліво пишеться однаково. Наприклад, «АБА» або «АББ ББА».

Задано послідовність символів (рядок) х. Яку мінімальну кількість символів потрібно вилучити з х, щоб отримати паліндром?

Приклад. Вхідні дані «і розморозь зором зорі». Відповідь: 3 (пропуски між словами).

х – рядок символів, який можна подати у вигляді LаR, де L – перший символ зліва, R – останній символ рядка х, а – підрядок, решта символів рядка (між першим та останнім, можливо – порожній). S(x) – функціz, що обчислює мінімальну кількість символів, які потрібно вилучити з рядка х, щоб решта символів утворювали паліндром.

Рекурсивний запис

Задача "Біномінальні коефіцієнти"

1. Умова задачі (vpn)
   

2. Розв'язок (використано масив типу vector, як один із варіантів опису масиву на мові С++)
   

Повторити як описуються вектори, що презентують матриці масиви. Користуватись вказаними прикладами можна як "словничком" програмного коду. (Документ)

Задача "Фібоначчі"

1. Умова задачі

2. Розв'язок
   

Задача. Степінь числа

1. Умова
   Підказка: подати у вигляді рекурсії
   

2. Розв'язати. Надіслати скріншот коду та результатів тестування

Задача. Піднесення до степеня

1. Умова
   Підказка: подати у вигляді рекурсії
   

2. Розв'язати. Надіслати скріншот коду та результатів тестування

Задача. Проста послідовність

1. Умова
   Підказки. Формули, які задані в умові задачі можна подати у вигляді рекурсії:
   
   
   
   
   
   Самостійно підібрати підхід до реалізації ДП: рекурсія, рекурсія із запам'ятовуванням чи табуляція.

2. Розв'язати. Надіслати скріншот коду та результатів тестування

Задача. Коник

1. Умова

2. Пояснення до задачі (Підказка: уважно подивитись на формулу та початкові значення - базу рекурсії; пригадати для якої числової послідовності були схожі записи).

3. Надіслати скріншоти програмного коду та результатів тестування

Задача. М'ячик на сходах

1. Умова1, умова2

2. Пояснення до задачі. Задача подібна до попередньої, тільки коника замінили на м'яч та дозволили стрибати на 3 кроки замість двох.
   У рекурентному співвідношенні додасться ще один доданок: k(n) = k(n − 1) + k(n − 2) + k(n − 3). І початкові значення для обчислення тепер повинні складатися із трьох чисел: k(0), k(1), k(2).
   Розв'язати задачу ітераційним підходом. Для масиву використати статичний масив long long arr[71].

3. Надіслати скріншоти програмного коду та результатів тестування

Контейнери STL

Послідовний контейнер vector

Реалізація лінійного масиву

Клас vector (або просто «вектор») — це динамічний масив, здатний збільшуватися в міру необхідності для утримання всіх своїх елементів. Клас vector забезпечує довільний доступ до своїх елементів через оператор індексації [], а також підтримує додавання і видалення елементів.

Прочитати як описуються вектори, що презентують лінійні масиви. Ознайомитись з прикладами кодів, що показують використання vector. Користуватись вказаними прикладами можна як "словничком" програмного коду. (Документ)