菲布纳计数Pascal语言详解 [复制链接]

急寻菲布纳计数Turbo Pascal语言详解
especially 逻辑过程详解

Fibonacci?
可以用数列的知识推导出公式。
Ai+2=Ai+1 +Ai(i>=1)

然后用特征方程特征根就可以求出。

斐波纳契， 不是菲布纳， delphinus

是斐波纳契， 不是菲布纳计

就用矩阵乘法吧
const
        maxk=20;
        max=7777777;

var
        t,ans:array[1..maxk] of qword;
        d:array[1..maxk,1..maxk] of qword;
        now:array[boolean,1..maxk,1..maxk] of qword;
        k,n,i,j,l,p:longint;

procedure f(v:longint);
var
        i,j,r:longint;
        s:qword;
begin
        for i:=1 to k do
        for j:=1 to k do begin
                s:=0;
                for r:=1 to k do inc(s,now[odd(v),i,r]*now[odd(v),r,j]);
                now[not odd(v),i,j]:=s mod max;
        end;
end;

procedure g;
var
        i,j:longint;
        s:qword;
begin
        for i:=1 to k do begin
                s:=0;
                for j:=1 to k do inc(s,ans[j]*now[odd(l),j,i]);
                t:=s mod max;
        end;

        ans:=t;
end;

begin

        fillchar(d,sizeof(d),0);
        fillchar(ans,sizeof(ans),0);

   
        k:=2;
        readln (n);

        for i:=1 to k-1 do d[i+1,i]:=1;
        for i:=1 to k do d[i,k]:=1;

        for i:=1 to k do ans:=1;
        for i:=1 to k do
                for j:=i+1 to k do inc(ans[j],ans);

        if n<=k then begin writeln (ans[n]);halt;end
                else dec(n,k);

        while n>0 do begin

                now[odd(1)]:=d;l:=1;p:=1;
                while n-p*2>=0 do begin
                        f(l);
                        inc(l);p:=p*2;
                end;

                g;dec(n,p);
        end;

        writeln (ans[k]);

end.

矩阵连乘太麻烦！！！
read(n);
A[1]=1;A[2]=1;
for (i:=3;i<=n;i++)
A=a[i-1]+a[i-2];
writeln(a[n])
end.

乱七八糟的，用数组+递归。