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

Числа Фібоначчі – це значення числової послідовності, в якій перші два члени рівні одиниці, а кожен наступний елемент рівний сумі двох попередніх чисел.

Послідовність Фібоначчі має вигляд:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610…

Функціонально послідовність можна записати як:

  • fib0 = 1
  • fib1 = 1
  • fibn = fibn-1 + fibn-2

Програма для рекурсивного обчислення та виводу N перших членів послідовності Фібоначчі

{$CODEPAGE UTF8}
program FibonacciNumbers;
var
  N, i, f : integer;

function FibonacciNumber(number : integer) : integer;
begin
  if (number = 0) or (number = 1) then
    FibonacciNumber := 1
  else
    FibonacciNumber := FibonacciNumber(number - 1) + FibonacciNumber(number - 2);
end;

begin
  write('N = ');
  readln(N);

  writeln(N, ' перших чисел Фібоначчі');
  for i := 0 to N - 1 do
    begin
      f := FibonacciNumber(i);
      write(f);
      if i < N - 1 then
        write(', ');
    end;
  readln;
end.

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

Оптимізована програма пошуку чисел Фібоначчі

{$CODEPAGE UTF8}
program FibonacciNumbers;
var
  N, i, f : integer;

function FibNum(num : integer) : integer;
var
  nm1 : integer; {fib(n-1)}
  nm2 : integer; {fib(n-2)}
begin
  nm1 := 1;
  nm2 := 1;
  if (num = 0) or (num = 1) then
    FibNum := 1
  else
    for i := 2 to num do
      begin
        FibNum := nm1 + nm2;
        nm2 := nm1;
        nm1 := FibNum;
      end;
end;

begin
  write('N = ');
  readln(N);

  writeln(N, ' перших членів послідовності Фібоначчі');
  for i := 0 to N - 1 do
    begin
      f := FibNum(i);
      writeln('fib(', i:2,') = ', f:8);
    end;
  readln;
end.

Дивіться також: