Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

Послідовність чисел 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.