Последовательность Фибоначчи определяется так: а (0) = 1, а (1) = 1, а (к) = а (к-1) + а (к-2) при к>2. Дано n, вычислить а (n) (в паскале)

1) Решение методом рекурсии.

Программа проста в понимании, но неэффективна при больших значениях

var

n: integer;

function f (i: integer) : longint;

begin

if i < 2 then

f : = 1

else

f : = f (i - 1) + f (i - 2) ;

end;

begin

read (n) ;

writeln (f (n)) ;

end.

2) Решение методом динамического программирования. Намного быстрее метода с рекурсией.

var

i, n: integer;

f: array[0 ... 50] of longint;

begin

read (n) ;

f[0] : = 1;

f[1] : = 1;

for i : = 2 to n do

f[i] : = f[i - 1] + f[i - 2];

writeln (f[n]) ;

end.

3) Решение методом моделирования. Использует меньше памяти.

var

n, a, b, i: integer;

begin

read (n) ;

if n < 2 then

a : = 1

else

begin

a : = 0;

b : = 1;

for i : = 0 to n do

begin

b : = a + b;

a : = b - a;

end;

end;

writeln (a) ;

end.