[算法]Fibonacci数列

dskongenius 发表于 2007/12/20 22:38:07

快速Fibonacci数算法(Fib_Quick)在非递归的Fibonacci程序中，在算f(n)的时候最多不超过n-2个加法，请编写一个更快的程序，或许可以用乘法。如果每一个乘法用m单位时间，每一个加法用p单位时间，于是非递归的写法因为最多有n-2个加法，因此最多用(n-2)×p的时间。请问，改良程序要用多少时间？假设只考虑加法和乘法。解答：考虑：f(n) = f(n-1) + f(n-2) = 1×f(n-1) + 1×f(n-2)f(n-1) = f(n-1) = 1×f(n-1) + 0×f(n-2)可以用矩阵乘法来表示两个式子：|f(n)   | = | 1 1 | ×|f(n-1)||f(n-1)|    | 1 0 |   |f(n-2)| 　Fibonacci数列非递归解(Fib_Iteration)Fibonacci数列f1，f2，...，fn的定义如下：                fn =    1            n = 1                fn =    1            n = 2                fn = fn-1+fn-2   n > 2    请不要用递归方法，也不用数组，写一个函数，它接受n的值，传回fn。解答：这个问题比较简单，如果已经有fi-1和fi-2，那么fi = fi-1 + fi-2，下次计算fi+1时需要fi和fi-1，保留fi-1和fi的值，丢弃fi-2的值即可。代码：long int fib_iter(int n){    long int f1 = 1, f2 = 1;    long int temp;    int i;    if(n <= 2) return 1;    else    {        for(i = 3; i <= n; i++)        {           temp = f1 + f2;           f2 = f1;           f1 = temp;        }       return temp;    }}思考问题：(1)如果用传统的递归办法，程序如下所示long int fibonacci(int n){    if(n <= 2)   return 1;    else return fibonacci(n-1)+fibonacci(n-2);}请用n=13做输入，用手算方式看看有哪些计算是重复做过的。n = 13：1次；n = 12：1次；n = 10：2次；n = 9：3次；n = 8：5次；n = 7：8次；n = 6：13次；n = 5：21次；n = 4：34次；n = 3：55次；n = 2：88次；n = 1：143次；呈一个fibonacci数列的规律。(2)请问算fn时一共用了多少个加法？请导出一个公式。(3)k阶的Fibonacci数列问题：前k个数值=1，fi(k) = fi-1(k) + fi-2(k) + ... + fi-k+1(k)(i > k)，当k=2时就是一般的Fibonacci数列。请不要用递归，或许可用数组，写一个函数fibK(n,k)，接收n与k，算出fj(k)。(4)为什么函数要用unsigned long而不用int？