求斐波那契数列log(n) pascal算法程序
来源:学生作业帮 编辑:神马作文网作业帮 分类:综合作业 时间:2024/09/20 11:54:32
求斐波那契数列log(n) pascal算法程序
如题,注意是Log(n)
如题,注意是Log(n)
用矩阵加速
[ f(n+1) ] [1 1] [ f(n) ]
=
[ f(n) ] [1 0] [ f(n-1)]
不停的迭代就行了
递归求解,log(n)的
program fibonacci;
type
matrix=array[1..2,1..2] of qword;
var
c,cc:matrix;
n:integer;
function multiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
function getcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
if n=1 then exit(c);
t:=n div 2;
temp:=getcc(t);
temp:=multiply(temp,temp);
if odd(n) then exit(multiply(temp,c))
else exit(temp);
end;
procedure init;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
if n=1 then
begin
writeln(1);
halt;
end;
if n=2 then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procedure work;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
[ f(n+1) ] [1 1] [ f(n) ]
=
[ f(n) ] [1 0] [ f(n-1)]
不停的迭代就行了
递归求解,log(n)的
program fibonacci;
type
matrix=array[1..2,1..2] of qword;
var
c,cc:matrix;
n:integer;
function multiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
function getcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
if n=1 then exit(c);
t:=n div 2;
temp:=getcc(t);
temp:=multiply(temp,temp);
if odd(n) then exit(multiply(temp,c))
else exit(temp);
end;
procedure init;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
if n=1 then
begin
writeln(1);
halt;
end;
if n=2 then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procedure work;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
求斐波那契数列log(n) pascal算法程序
用递归算法编写求斐波那契数列前n项和的程序
Pascal:用递归函数求斐波那契数列的第n项·
求斐波那契数列的第N项VFP程序
pascal程序:数列
VB:斐波那契数列第一项是1,第二项是1,用递归算法编写一个程序,求数列前N项的和
Pascal 斐波那契数列求和
输入斐波那契数列的第N项的位置PASCAL
pascal高精度的斐波那契数列的第n项?
斐波那契数列的算法设{fn}是斐波那契数列,则F1=F2=1,Fn=Fn-1=Fn-2(n>=3).画出程序框图,表示输
斐波那契数列求和1 pascal语言
求各种斐波那契数列的pascal题目!