Числа Фібоначчі

Відомим прикладом рекурентної послідовності є послідовність чисел Фібоначчі.

Послідовність чисел 1, 1, 2, 3, 5, 8, 13,..., де f₁=f₂=1, а кожний наступний член дорівнює сумі двох попередніх, називається послідовністю чисел Фібоначчі. Таким чином, усі члени послідовності чисел Фібоначчі, починаючи з третього, задаються рекурентним співвідношенням f_n=f_n-2+f_n-1. Числа Фібоначчі мають декілька цікавих властивостей. Зокрема, сусідні числа Фібоначчі є взаємно простими; найбільшим спільним дільником двох чисел Фібоначчі є число Фібоначчі; число Фібоначчі парне тоді і тільки тоді, коли його номер кратний трьом.

Розробимо програму, що генерує послідовність n перших чисел Фібоначчі. Нам знадобиться змінна fi для зберігання значення поточного члена послідовності та змінні f₁ і f₂ для зберігання значень двох попередніх членів. Значення f₁ модифікуватиметься оператором fi :=f₁+f₂ , який увійде до складу циклу з лічильником. Після виконання цього оператора слід переприсвоїти значенням змінних f₁ та f₂ так, щоб вони містили нову пару чисел Фібоначчі. Це можна здійснювати операторами f₁:=f₂ та f₂:=fi.

Програма, що генерує послідовність чисел Фібоначчі:

program fibonachi;

var f1,f2,fi:integer; {два попередніх та поточний член послідовності}

i,n:integer; {лічильник і загальна кількість членів послідовн.}

begin

write('Enter the length of Fibonacci sequence');

readln (n); {ввести кількість членів}

f1:=1; f2:=1; {ініціалізувати два перших члени}

if n>0 then write (f1); {якщо у послідовності принаймні один член}

if n>1 then write (' ',f2); {якщо у послідовності принаймні два члени}

for i:=3 to n do {цикл обчислення наступних членів}

begin

fi:=f1+f2; {обчислити поточний член послідовності}

f1:=f2; {сформувати нову пару доданків}

f2:=fi;

write (' ',fi); {вивести чергове число Фібоначчі}

end;

end.