Числа Фибоначчи Pascal(Паскаль)

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

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

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. 

Поиск чисел Фибоначчи с помощью рекурсивных вызовов очень не эффективно. Дело в том, что для вычисления каждого элемента необходимо сначала вычислить значения двух предыдущих, а для каждого из них — двух предыдущих, и так далее. Получаем дерево рекурсивных вызовов. Для оптимизации алгоритма, достаточно запоминать два предыдущих элемента ряда Фибоначчи.

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

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. 

Программа вычисления чисел ряда Фибоначчи по рекуррентной формуле без запоминания членов

Program Pr39(Input, Output);
Var 
N : Integer;
X1, X2, Y : LongInt; 
i : Integer;
 
Begin
 
WriteLn ('PASCAL: Вычисление чисел Фибоначчи '); 
WriteLn ('по рекуррентной формуле без запоминания членов.'); 
Write ('Введите количество членов (3<=N<=50):N = '); 
ReadLn (N); 
WriteLn ('Ваши ', N, ' членов:');
Write ('1 1 ');
X1 := 1; 
X2 := 1; 
 
For i := 3 To N Do
Begin
Y := X1 + X2; 
Write (Y); 
Write (' '); 
X1 := X2;
X2 := Y; 
End;
 
ReadLn;
End. 

Программа вычисления чисел ряда Фибоначчи по рекуррентной формуле с запоминанием членов

Program pr40 (Input, Output); 
Var 
X : Array [1..50] Of Integer;
N : Integer;
i : Integer;
 
Begin
 
Write ('PASCAL: Вычисление чисел Фибоначчи ');
WriteLn ('по рекуррентной формуле c запоминанием членов.'); 
Write ('Введите количество членов (3<=N<=50):N = '); 
ReadLn (N); 
 
X [1] := 1; 
X [2] := 1; 
 
WriteLn ('Вычисленные члены:'); 
Write ('1 1 ');
For i := 3 To N Do
Begin
X [i] := X [i - 2] + X [i - 1]; 
Write (X [i]);
Write (' '); 
End;
 
ReadLn;
End. 

Leave a Comment