Помощь - Поиск - Пользователи - Календарь
Полная версия: Фибоначчи
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Самара
Требуется найти n-ое число Фибоначчи. Напомним, что последовательность Фибоначчи это:
F(1) = 1; F(2) = 1; F(n) = F(n - 1) + F(n - 2);

на вход n. при том ,что n до 15000
volvo
Цитата
при том ,что n до 15000

Уууу, да тут без длинной арифметики не обойтись... При таких значениях N тип LongInt переполнится однозначно...

FAQ: Длинная арифметика
Ирочка
А как приблизительно будет выглядеть код???
volvo
Цитата
А как приблизительно будет выглядеть код?
Примерно вот так:
const
_maxdig = 1000;
_osn = 10000;

type
Tlong = array[0.._maxdig]of integer;
Plong = ^Tlong;

Procedure InitOne(a: PLong);
Begin
a^[1] := 1; inc(a^[0]);
End;

procedure SumLongTwo(a,b,c:Plong);
var i,k:integer;
begin
fillchar(c^,sizeof(c^),0);
if a^[0]>b^[0] then k:=a^[0] else k:=b^[0];
for i:=1 to k do
begin
c^[i+1]:=(c^[i]+a^[i]+b^[i]) div _osn;
c^[i]:=(c^[i]+a^[i]+b^[i]) mod _osn;
end;
if c^[k+1]=0 then c^[0]:=k else c^[0]:=k+1;
end;

procedure WriteLong(var f:text;a:Plong);
var ls,s:string;
i:integer;
begin
str(_osn div 10,ls);
write(f,a^[a^[0]]);
for i:=a^[0]-1 downto 1 do
begin
str(a^[i],s);
while length(s)<length(ls) do s:='0'+s;
write(f,s);
end;
writeln(f);
end;

var
Great_1, Great_2, Great_3: TLong;
first, second, next: PLong;
n, max: integer;
begin
Write('n = '); ReadLn(max);

first := @Great_1;
second := @Great_2;
next := @Great_3;

InitOne(First); { First := 1 }
InitOne(Second); { Second := 1 }
n := 2;
repeat
Inc(n);
SumLongTwo(First, Second, Next); { next := first + second }

First^ := Second^;
Second^ := Next^;

until n >= max;

Write('n = ', n, ' : ');
WriteLong(Output, Next);
end.

А вот как будет выглядеть результат при n = 15000 я не берусь тебе сказать... При n = 2000 получается вот такое число:
Цитата
4224696333392304878706725602341482782579852840250681098010280137
3143085843701307072241235996391415110884460875389096036076401947
1164359602927198331259873732625355580260699158591522949245390499
8722256795316982874482472992263901833716778060607011615497886719
8798583114688708762645973690867228840236544222952433479644801395
1534956297208765265606952980649984197744872015561280266540455417
1717881930324025204312082516817125
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.