早教吧作业答案频道 -->其他-->
求斐波那契数列log(n) pascal算法程序如题,注意是Log(n)
题目详情
求斐波那契数列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) ...的网友还看了以下:
(1)特例导航:请根据所给的运算程序完成填空.(2)探索与归纳:运算程序例如按左侧的形式完成你的举 2020-04-07 …
朱熹的《四书章句集注》里经常出现的“反”是什么意思,比如“澳,于六反.”...诗云:“瞻彼淇澳,菉 2020-06-10 …
数论中的那些数列有何意义?比如说一个叫斐波那契数列. 2020-07-23 …
我在少年宫附近住.改变词序,不改变句意1他的话没有完全错.改变词序,不改变句意.2忽如夜春来,树树梨 2020-11-25 …
我想请问一下,就是我用PB写一个程序.例如,单行编辑框里的任意一个数,如果在5一下,就提示节约了例如 2020-11-28 …
INT21是什么意思我刚学汇编语言,程序段里老是出现INT21,我知道INT是中断的意思.但这个IN 2020-12-03 …
下面说法有误的一项是A.“序”有两种,一是书序,如《<指南录>后序》《<黄花岗七十二烈士事略>序》; 2020-12-05 …
斐济由300多个岛屿组成,多为珊瑚礁环绕的火山岛;河流多而短小,海洋渔业资源丰富.读“斐济示意图”( 2020-12-16 …
阮籍的《咏怀诗》内涵幽愤,情寄八荒,李白《古风》每得其意放诣.如阮“东园桃与李”,李“桃花开东园”; 2021-01-18 …
意识的本质是什么?人怎样样产生的意识?为什么大脑中的细胞这样排列就能产生意识?分子原子以特定的方式和 2021-02-05 …