Числа Фибоначчи — это значения числовой последовательности, в которой, первые два числа равны единице, а каждый последующий элемент равен сумме предыдущих двух чисел.
Последовательность Фибоначчи имеет вид:
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.