关于斐波那契数列的引申

迈不过友情╰ 2022-04-23 07:26 94阅读 0赞

**最基本的函数模型是：**

/  0                             n=0  
f(n)=      1                             n=1  
          \\ f(n-1)+(f-2)              n>1

**1.我们一般的解法是：**

int fun( int n )
    {      
            if ( 0 == n )
            {
                   return0;
            }
            elseif ( 1 == n )
            {
                   return1;
            }
            else
            {
                   returnfun(n - 1) + fun(n - 2);
            }
    }

**2.但是递归在大的数据的情况下可能超时( 特别是在OJ上的时候 )**

**那么我们想想还可以用：**

#include <stdio.h>
     
    int main()
    {
       long long f[51] = { 0, 1 };
       long long n, a0 = 0, a1 = 1;
       int i;
     
       for( i = 2; i <= 50 ; i++ )
       {
                f[i] = a0 + a1;    // 此处只要遍历一次就ok
                a0 = a1;
                a1 = f[i];
       }
       while( scanf("%d", &n) != EOF )   // 我们可以得到任意的n的 Fibonacci 结果
       {
               printf("%lld\n", f[n]);
       }
       return 0;
    }

**3.算法导论上的Naive recursive squaring method 方法：其实也就是将其化成数学问题解决！**

**   Fibonacci的一条性质是：求N项的公式是有的，即：黄金比Q的N次方/根号5 即： pow( Q, N )/sqrt( 5 )  
                                                   得到最近的一个整数，那么就是第N项的 Fibonacci 数值！ ( Q = ( sqrt(5) + 1 ) / 2 是黄金比  )**

**   那么求前15项的代码如下：**

#include <stdio.h>
    #include <math.h>
    
    int main()
    {
        int i;
        double Q = 1.0 * ( 1 + sqrt( 5 ) ) / 2.0, t;
        
        for( i = 1; i < 15; i++ )
        {
             t = pow( Q, i )/sqrt(5);   // 取最近的整数就是第你项的fibonacci元素 
             
             if( (t - (int)t) < ( ( (int)t + 1 ) - t ) )  // 这个if是判断到底是那个整数近( 例如：1.3 离1近呢还是离2近 )
             { 
                 printf("%d ", int(t));
             }
             else
             {
                 printf("%d ", int(t) + 1);
             }
        }
        getchar();
        return 0;
    }

**实际我们知道，由于计算机的浮点数的位置限制，那么我们在做上面的算式时候，当N很大的时候，很多的位可能会丢失，那么所求的结果就是不准确的，所以理论上的意义会更大！实际编程时候，当N很大的时候实不可取的~**

**那么下面的办法就很重要了~**

**4.此处还要介绍一个非常好的办法：利用矩阵**

**Fibonacci 说白了就是一个递推序列，f( n ) = f( n - 1 ) + f( n - 2 );**

**变形一下有： f( n )  =  1 \*f( n - 1 )  + 1 \*  f( n - 2 );**

**那么使用矩阵表示就是：( 注意：下面表示的不好看，其实是矩阵表示，见谅！ )**

**|  f( n )     |        |  1 1  |          |  f( n-1 ) |**

**|  f( n-1 )  |   =   |  1 0  |     \*    |  f( n-2 )  |  **

**即：**

|  f( n )     |     |  1 1  |                   |  f( 1 )  |

|  f( n-1 ) |  = |  1 0  | ^( n-1 )  \*  |  f( 0 )  |

**就是那个| 1 1 |**

**                | 1 0 |    的n-1次方后 乘以 初始化的两个数就是！**

#include <stdio.h>
     
    long long all[71];
     
    void fun( int n )
    {
        int i;
        long long mat[2][2] = { 1, 0, 0, 1 };      // 单位矩阵
        long long tmp[2][2];
       
        for( i = 2; i <= n; i++ )
        {
             tmp[0][0] = mat[0][0];
             tmp[0][1] = mat[0][1];
             tmp[1][0] = mat[1][0];
             tmp[1][1] = mat[1][1];
            
             mat[0][0] = tmp[0][0] + tmp[0][1];
             mat[0][1] = tmp[0][0];
             mat[1][0] = tmp[1][0] + tmp[1][1];
             mat[1][1] = tmp[1][0];
            
             all[i] = mat[0][0] * all[1] +mat[0][1] * all[0];
        }
    }
     
    int main()
    {
        int n;
     
        all[0] = 0;
        all[1] = 1;
        fun( 70 );
     
        while( scanf("%d", &n) != EOF)
        {
               if( n == 0  )
               {
                   printf("0\n");
               }
               else if( n == 1 )
              {
                   printf("1\n");
               }
               else
               {
                   printf("%lld\n",all[n]);
               }
        }
       
        return 0;
    }

**关于 Fibonacci  的变体：**

**1》[青蛙跳台阶问题][Link 1]:**

**      一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。**

**分析：**

**    当n =1， 只有1中跳法；当n =2时，有2种跳法；当n = 3 时，有3种跳法；当n = 4时，有5种跳法；当n = 5时，有8种跳法**

**    所以还是Fibonacci 序列，只不过初始化为：f(1) = 1; f(2) = 2;**

#include <stdio.h>
     
    long long all[71];
     
    void fun( int n )
    {
        int i;
        long long mat[2][2] = { 1, 0, 0, 1 };      // 单位矩阵
        long long tmp[2][2];
       
        for( i = 3; i <= n; i++ )
        {
             tmp[0][0] = mat[0][0];
             tmp[0][1] = mat[0][1];
             tmp[1][0] = mat[1][0];
             tmp[1][1] = mat[1][1];
            
             mat[0][0] = tmp[0][0] + tmp[0][1];
             mat[0][1] = tmp[0][0];
             mat[1][0] = tmp[1][0] + tmp[1][1];
             mat[1][1] = tmp[1][0];
            
             all[i] = mat[0][0] * all[2] +mat[0][1] * all[1];
        }
    }
     
    int main()
    {
        int n;
     
        all[0] = 0;
        all[1] = 1;
        all[2] = 2;
        fun( 70 );
     
        while( scanf("%d", &n) != EOF)
        {
               if( n == 0 || n == 1 )
               {
                   printf("1\n");
               }
               else
               {
                   printf("%lld\n",all[n]);
               }
        }
       
        return 0;
    }

**或者代码为：**

**（ 下面的代码计算大的数的时候可能超时，不建议 ）**

#include <stdio.h>
     
    int count;
     
    void fun( int s, int i, int n )
    {    
          s += i;
         
          if( s == n )
          {
              count++;
              return;
          }
          else if( s > n )
          {
               return;
          }
          else        // 此处分叉
          {  
              fun( s, 1, n );  
              fun( s, 2, n );
          }
    }
     
    int main()
    {
        int n;
       
        while( scanf("%d", &n) != EOF)
        {
               count = 0;
               fun( 0, 0, n );
              
               printf("%d\n", count);
        }
       
        return 0;
    }

**2》 [ 跳台阶问题（变态跳台阶）][Link 2]**

**    一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法**

**分析：**

** **

**             / 1                        n=1  
f(n)=   2                             n=2  
          \\ f(n-1)+(f-2)            n>2**

#include <stdio.h>
     
    int main()
    {
       long long f[51] = { 0, 1, 2 };
       long long n = 3, sum = 3;
       int i;
     
       for( i = 3; i <= 50 ; i++ )
       {
               f[i] = sum + 1;
               sum += f[i];
       }
     
       while( scanf("%d", &n) != EOF )
       {
              printf("%lld\n", f[n]);
       }
     
       return 0;
    }

**3》 矩形覆盖**

**      我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？**

**分析：**

**      同上!（ 说到底还是其变形 ）**

#include <iostream>
     using namespace std;
      
     int main()
     {
         long long f[71];
         int i;
         int n;
      
         f[0] = 1;
         f[1] = 1;
          
         for(  i = 2; i <= 70; i++ )
         {
             f[i] = f[i-1] + f[i-2];
         }
      
         while( cin >> n )
         {
             cout << f[n] << endl;
         }
         
         return 0;
     }

[Link 1]: http://blog.csdn.net/silenough/article/details/7184784
[Link 2]: http://blog.csdn.net/martin_liang/article/details/8661083