Fibonacci 通项公式 Pascal

上面说的不错,但忽略了一个问题,实数运算是有微小误差的,所以取整可能大数据会有误差.你试试就知道了.
要解决这个问题,可以通过矩阵运算解决.
F(n)=[0,1]^n (那个2*2的矩阵的n次方) 的左上角的数字
[1,1]
另外,可以通过二分快速求幂法使时间复杂度降到O(log(2,n))

通项公式是：an=1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)

var n:longint;
function sq(a:real;x:longint):real;{自定义求幂函数，a为底数，x为指数}
var i:longint;
s:real;
begin
s:=1;
for i:=1 to x do
s:=s*a;
sq:=s;
end;
begin
read(n);
writeln(1/sqrt(5)*(sq(((1+sqrt(5))/2),n)-sq(((1-sqrt(5))/2),n)):0:0);
end.

用矩阵快速幂可以优化到O(lg n),顶楼上