笔考试题中考到：斐波那契数列的快速实现方法

笔试题中考到：斐波那契数列的快速实现方法
如题！
望大家指教 谢谢
------解决方案--------------------
利用特征方程
线性递推数列的特征方程为：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2
C1*X1^2 + C2*X2^2
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】


方法二:
考虑矩阵 A
1 1
0 1,
你求A^n试试

方法三:
递归(非常慢)

方法四:
用两个数a,b,然后一个for循环,你懂的
------解决方案--------------------

#include <stdio.h>


unsigned int fib(unsigned int x)

{

        if (x <= 1)

                return x;


        return fib(x - 1) + fib(x - 2);

}


int main(int argc, char *argv[])

{

        unsigned i;


        for (i = 0; i <= 20; i++)

                printf("%u ", fib(i));

        printf("\n");


        return 0;

}

------解决方案--------------------
尾部递归或循环

这是动态规划的思想

long long fib(unsigned int n, long long acc1, long long acc2)

{   

	if(n == 0)

		return acc2;

	return fib(n-1, acc1+acc2, acc1);

}


long long Fibonacci(unsigned int n)

{

	long long  fibNMinusOne = 1;

	long long  fibNMinusTwo = 0;

	long long  fibN = 0;

	unsigned int i = 0;

	if(n < 2)

		return n;


	for(i=2; i<=n; ++i)

	{

		fibN = fibNMinusOne + fibNMinusTwo;

		fibNMinusTwo = fibNMinusOne;

		fibNMinusOne = fibN;

	}


	return fibN;

}

------解决方案--------------------
标准做法就是矩阵的N次幂, 用快速幂运算, 用公式稍微处理下也可以, 过程中不会出现任何浮点运算, 复杂度也相当, 都是 O( lnN ), 速度好像我也试过差不多.

说递归或者递推快的, 给出 Fib( 1E8 ) 的结果和运行时间...
我这试了下, 不输出结果在 T410s 上单线程运行时间 2.5 秒, 输出结果时间 20 秒,  优化余地应该还很大, 用上多线程, 优化下输出应该能在3秒内得结果...

结果应该是 20,898,766 位, 前后应该是: 473710347345633696254897131 ... 83606082642167760546875