Вивести на екран n-ну кількість чисел Фібоначчі

Формулювання. 

Дано натуральне n (яке також може бути дорівнює 0). Вивести на екран n-ну кількість Фібоначчі.

Примітка: послідовність чисел Фібоначчі задається наступною рекурентною формулою:

Тобто, нульовий член послідовності - це число 0, 1-й член - число 1, а будь-який інший член, починаючи з 2-го, є сумою двох попередніх. Наприклад, F2 = F1 + F0 = 1 + 0 = 1, F3 = F2 + F1 = 1 + 1 = 2 і т. Д.

Рішення. 

Знайдемо кілька перших чисел Фібоначчі:

F2 = F1 + F0 = 1 + 0 = 1;
F3 = F2 + F1 = 1 + 1 = 2;
F4 = F3 + F2 = 2 + 1 = 3;
F5 = F4 + F3 = 3 + 2 = 5;

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

Так як нульовий і перший члени послідовності НЕ обчислюються і даються як частина визначення, будемо вважати їх заздалегідь відомими. Позначимо їх ідентифікаторами fib0 і fib1. За прикладом знаходження перших членів послідовності порахуємо кількість операцій, необхідних для обчислення кожного члена (вважаючи, що попередні члени невідомі). Легко побачити, що для обчислення 2-го члена (при відомому 1-му та нульовому членах) необхідна одна операція додавання, 3-го - дві операції додавання і т. д. Видно, що за цими ж правилами для обчислення n- ного члена необхідно виконати (n - 1) операцій.

Тепер можна почати писати програму. Спочатку нам необхідно ввести значення n і виконати ініціалізацію значень нульового та першого чисел Фібоначчі, так як ми вважаємо їх заздалегідь відомими:

readln (n); fib0: = 0; fib1: = 1;

Далі нам необхідно організувати цикл, в якому на кожному кроці змінні fib0 і fib1 отримуватимуть наступні значення в послідовності чисел Фібоначчі. Тобто, наприклад, якщо в fib0 і fib1 знаходитимуться значення, відповідно, (n - 2) -го і (n - 1) -го членів послідовності Фібоначчі, то після одного кроку циклу вони будуть містити значення (n - 1 ) -го і n-го членів. Для цього можна створити якусь допоміжну змінну fib, в яку помістити результат складання fib0 і fib1, після чого в fib0 у нас буде значення (n - 2) -го члена, в fib1 - (n - 1) -го, а в fib - n-го. Тепер потрібно тільки скопіювати значення fib1 в fib0 і fib в fib1, після чого значення змінної fib на цьому кроці вже не має значення. З урахуванням того, що ми вже порахували необхідну кількість повторень для отримання необхідного результату, цикл буде виглядати так:

for i: = 1 to n - 1 do begin   fib: = fib1 + fib0;   fib0: = fib1;   fib1: = fib end;

Такий метод вирішення загальної задачі, що базується на використанні в ній рішень задач з меншою розмірністю вихідних даних (в даному випадку під розмірністю розуміється вели-чину n), називається динамічним програмуванням.

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

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

Інший приклад спадного динамічного програмування - обчислення факторіала 

Щоб обчислити n !, необхідно обчислень (n - 1)! і т.д.

Отже, повернемося до поточної задачі. Раніше було сказано, що після вичерпання n - 1 кроків циклу в змінній fib1, яка піде на виведення в програмі, буде зберігатися значення Fn. Перевіримо коректність обробки граничних значень (зокрема, коли n = 0, 1, 2):

1) При n = 0 границі циклу будуть у відрізку [1, 0 - 1]. При цьому значення правої межі залежить від типу змінної i, так як компілятор, щоб уникнути помилок, при обчисленні «розширює» тип виразів, що означають межі циклу.

Якщо буде оголошено тип byte, то вираз 0 - 1 дасть в результаті 255 (так як всі числові типи в мові Pascal більшість компіляторів вважає кільцевими), що викличе довгий ланцюжок обчислень, а це невірно.

Звичайно, можна оголосити тип integer, і тоді границі циклу будуть у відрізку [1, -1] 

Так як при обчисленні важливо лише кількість повторень, ми можемо розширити відрізок [1, n - 1] на одну позицію правіше на числовій прямій, і тоді цикл буде проходити від 2 до n.

Однак тоді ми зіткнемося з іншою проблемою: при введенні 0 буде виведено значення fib1, якій було присвоєно число 1 при ініціалізації. Справитися з проблемою можна, присвоївши fib1 значення 0, якщо n = 0:

if n = 0 then fib1: = 0;

2) При n = 1 (з урахуванням прийнятих в попередньому пункті змін) входу в цикл не буде, і на екран виведеться незмінне значення fib1, рівне 1;

3) При n = 2 відбудеться вхід в цикл, де i буде змінюватися від 2 до 2 (тобто, в цьому випадку буде виконаний єдиний крок), в якому буде обчислено значення fib = fib1 + fib0 = 1 + 0 = 1, яке буде скопійовано в fib1 і виведено на екран. Неважко зрозуміти, що подальша підстановка значень не потрібна, так як коректність циклічної конструкції ми вже довели.

Верхні значення ми не перевіряємо, оскільки не існує найбільшого номера в послідовності чисел Фібоначчі (хоча зрозуміло, що коректність обчислень обмежена «місткістю» типу integer, і при його перевищенні в обчисленнях числа вже будуть неправильними).

program FibonacciNumbers;
var
fib0, fib1, fib: integer;
i, n: byte;
begin
readln(n);
fib0 := 0;
fib1 := 1;
for i := 2 to n do begin
fib := fib1 + fib0;
fib0 := fib1;
fib1 := fib
end;
if n = 0 then fib1 := 0;
writeln(fib1)
end.