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

Числа Фибоначчи - это значения числовой последовательности, в которой, первые два числа равны единице, а каждый последующий элемент равен сумме предыдущих двух чисел.

Последовательность Фибоначчи имеет вид:
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.

Смотрите также: