作业帮输入斐波那契数列的第N项的位置PASCAL
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/03 04:24:18
输入斐波那契数列的第N项的位置PASCAL
输入斐波那契数列的第N项的位置PASCAL
输入斐波那契数列的第N项的位置PASCAL
(*基本算法*)
var a,b,t,n:longint;
begin
readln(n);
a:=1;
for i:=1 to n do begin
t:=a; a:=a+b; b:=t;
end;
writeln(a);
end.
(*基于矩阵的快速幂*)
var
n:longint;
t,mat,ans:array[0..1,0..1] of longint;
begin
readln(n);
mat[0,1]:=1; mat[1,0]:=1; mat[1,1]:=1;
ans[0,0]:=1; ans[1,1]:=1;
while n>0 do begin
if n and 1=1 then begin
t:=ans;
ans[0,0]:=t[0,0]*mat[0,0]+t[0,1]*mat[1,0];
ans[0,1]:=t[0,0]*mat[1,0]+t[0,1]*mat[1,1];
ans[1,0]:=ans[0,1]; ans[1,1]:=ans[0,0]+ans[0,1];
end;
t:=mat; n:=n>>1; if n=0 then break;
mat[0,0]:=t[0,0]*t[0,0]+t[0,1]*t[1,0];
mat[0,1]:=t[0,0]*t[1,0]+t[0,1]*t[1,1];
mat[1,0]:=mat[0,1]; mat[1,1]:=mat[0,0]+mat[0,1];
end;
writeln(ans[0,1]);
end.