Динамічне програмування: способи реалізації, рекурсія

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

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

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

Динамічне програмування як метод розв'язування задач

Ознайомитись з описом методу та підходами до його реалізації (документ)

1. Вивчити означення "динамічного програмування", "рекурсія".

2. Вивчити поняття "гранична умова", "база", крок рекурсії.

3. Вміти пояснювати три підходи до реалізації динамічного програмування: рекурсія, мемоїзація, табуляція.

4. Ознайомитись з прикладами розв'язання задачі трьома підходами.

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

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

1. Написати програмний код у вигляді рекурсивної функції, рекурсії з запам'ятовуванням, у вигляді ітерацій.

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

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

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

1. Написати програмний код у вигляді рекурсивної функції, рекурсії з запам'ятовуванням, у вигляді ітерацій.

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

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

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

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

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

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

Для розв'язання скористатись функціями для типу string

1. Написати програмний код у вигляді рекурсивної функції.

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

Стандартна бібліотека шаблонів (STL)

Прочитати про призначення бібліотеки STL.

Контейнери STL

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

Реалізація лінійних масивів

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

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

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

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

2. Розв'язати задачу за допомогою рекурсії з запам'ятовуванням. Для запам'ятовування використати vector (двовимірий масив):
   vector< vector<unsigned long long> > FibMemo;
   FibMemo.assign(N+1, vector<unsigned long long>(M+1, 0));
   
   Кількість способів - це комбінаторна формула:
   
   Під час розв'язування на С++ правильно вибирати тип результату

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

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

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

2. Розв'язати задачу за допомогою рекурсії з запам'ятовуванням.
   Підказка: потрібно правильно вибрати підхід до реалізації ДП
   Під час розв'язування на С++ правильно вибирати тип результату

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