Фибоначчи Опции

[Самара]

Требуется найти 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