Знаходимо N’е число Фібоначчі трьома способами за прийнятний час: засади динамічного програмування


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Задача: порахувати N’e число послідовності, в якій кожен елемент дорівнює сумі двох попередніх. Така послідовність називається послідовністю Фібоначчі: 1, 1, 2, 3, 5, 8.

Дуже часто на різноманітних олімпіадах пропонуються задачі на зразок цієї, які, як видається на перший погляд, можна розв’язати за допомогою простого перебору. Проте якщо ми підрахуємо кількість можливих варіантів, то відразу переконаємося в неефективності такого підходу: наприклад, проста рекурсивна функція, наведена нижче, споживатиме істотні ресурси вже на 30-му числі Фібоначчі, тоді як на олімпіадах час розв’язання часто обмежений 1-5 сек.

int fibo (int n){ if (n == 1 || n == 2) { return 1; } else { return fibo (n - 1)  + fibo (n - 2); }}

Давайте подумаємо, чому так відбувається. Наприклад, для обчислення fibo (30) ми спочатку обчислюємо fibo (29) і fibo (28). При цьому наша програма “забуває”, що fibo (28) ми вже обчислювали при пошуку fibo (29).

Основна помилка такого підходу “в лоб” в тому, що однакові значення аргументів функції обчислюються багаторазово, це ресурсоємні операції. Позбавитися від повторних обчислень нам допоможе метод динамічного програмування – це прийом, при використанні якого задача розбивається на загальні підзадачі, що повторюються, кожна з яких вирішується тільки 1 раз – це значно підвищує ефективність програми. Цей метод детально описаний у нашій статті, там також наведені приклади розв’язання інших задач.

Варіант поліпшення нашої функції – запам’ятовувати, які значення ми вже обчислювали. Для цього треба ввести додатковий масив, який служитиме ніби “кешем” для наших обчислень: перед обчисленням нового значення ми перевірятимемо, чи не обчислювали його раніше. Якщо обчислювали, то братимемо з масиву готове значення, а якщо не обчислювали – доведеться обчислювати його на основі попередніх і запам’ятовувати на майбутнє:

int cache[100];int fibo (int n){ if (cache[n] == 0) { if (n == 1 || n == 2) { cache[n] = 1; } else { cache[n] = fibo (n - 1)  + fibo (n - 2); } } return cache[n];}

Оскільки в даній задачі для обчислення N-го значення нам гарантовано знадобиться (N-1)-е, то не становить труднощів переписати формулу в ітераційний вид – просто заповнюватимемо наш масив підряд до тих пір, поки не дійдемо до потрібного осередку:

cache[0] = 1;cache[1] = 1;for (int i = 2; i <= n; i++) { cache[i] = cache[i - 1] + cache[i - 2];}cout << cache[n - 1];

Тепер ми можемо помітити, що коли обчислюємо значення F (N), то значення F (N-3) нам вже гарантовано ніколи не знадобиться, тобто нам достатньо зберігати в пам’яті лише два значення – F (N-1) і F (N-2). Причому, щойно ми обчислили F (N), зберігання F (N-2) втрачає будь-який сенс. Спробуємо записати ці роздуми у вигляді коду:

//Два попередні значення: int cache1 = 1;int cache2 = 1;//Нове значення int cache3;for (int i = 2; i <= n; i++) { cache3 = cache1 + cache2; // Обчислюємо нове значення // Абстрактний cache4 буде дорівнювати cache3+cache2 // Означає cache1 нам вже не потрібний?. // Відповідно, означає cache1 -- те значення, яке втратить актуальність на наступній ітерації. //cache5 = cache4 - cache3 => через ітерацію втратить актуальність cache2, тобто він і повинен стати cache1 // Іншими словами, cache1 -- f (n - 2), cache2 -- f (n - 1), cache3 -- f (n). // Нехай N=n+1 (номер, який ми обчислюємо на наступній ітерації). Тоді n - 2=N - 3, n - 1=N - 2, n=N - 1. // Відповідно до нових реалій ми і переписуємо значення наших змінних: cache1 = cache2; cache2 = cache3;}cout << cache3;

Досвідченому програмістові зрозуміло, що  вищий код є нісенітницею, оскільки cache3 ніколи не використовується (він відразу записується в cache2), і всю ітерацію можна переписати, використовуючи один вираз:

cache[0] = 1;cache[1] = 1; for (int i = 2; i <= n; i++) { cache[i%2] = cache[0] + cache[1]; //При i=2 застаріє 0-й елемент //При i=3 в 0 буде свіжий елемент (оновили його на попередній ітерації), а в 1 -- ще старий //При i=4 останнім елементом ми оновлювали cache[1], означає непотрібну старизну зараз в cache[0] //Інтуїтивно зрозуміло, що так триватиме і далі} cout << cache[n%2];

Для тих, хто не може зрозуміти, як працює магія із залишком від ділення, або просто хоче побачити неочевидну формулу, є ще одне розв’язання:

int x = 1;int y = 1;for (int i = 2; i < n; i++) { y = x + y; x = y - x;}cout << "Число Фібоначчі: " << y;

Спробуйте простежити за виконанням цієї програми: Ви переконаєтеся в правильності алгоритму.


P.S. Єдина формула для обчислення будь-якого числа Фібоначчі, що не потребує жодних ітерацій або рекурсії:

const double SQRT5 = sqrt (5);const double PHI =  (SQRT5 + 1)  / 2;int fibo (int n){ return int (pow (PHI, n)  / SQRT5 + 0.5);}

Як можете здогадатися, каверза в тому, що ціна обчислення ступенів нецілих чисел достатньо велика, як і їх похибка.

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *