题目九：斐波那契数列

怼烎@ 2021-11-02 01:02 274阅读 0赞

/  
// 13.题目九：斐波那契数列  
/\*写一个函数，输入N,求斐波那契(Fibonacci)数列的第N项.  
F(n) = \{0    n == 0;  
         1    n == 1;  
         F(n -1) + F(n -2) n > 1;  
         \}

\*/

static int s_RunTime = 0;
    void CalcFbio(int iNum)
    {
        printf("N(%d) --> F(%d) + F(%d)\n", iNum, iNum - 1, iNum - 2);
        s_RunTime++;
    }
    
    int Fbio_1(int iNum)
    {
        if (iNum <= 1)
        {
            return iNum;
        }
    
        CalcFbio(iNum);
        return Fbio_1(iNum - 1) + Fbio_1(iNum - 2);
    }
    
    // 优化版 --> 去掉重复计算项
    //时间复杂度O(n)
    int Fbio_2(int iNum, vector<int>& vect)
    {
        // 1.循环退出条件
        if (iNum <= 1)
        {
            return iNum;
        }
    
        // 如果该项F(n)已经计算过，直接返回结果
        if (vect[iNum - 1] > 0)
        {
            return vect[iNum - 1];
        }
    
        // 3.存储对应项结果
        vect[iNum - 1] = Fbio_2(iNum - 1, vect) + Fbio_2(iNum - 2, vect);
        CalcFbio(iNum);
        return vect[iNum - 1];
    }
    
    // 非递归解法 时间复杂度O(n)
    int Fbio_3(int iNum)
    {
        int iRes = 0;
        if (iNum <= 1)
        {
            return 1;
        }
    
        int iSum = 0;
        int iOne = 1;
        int iTwo = 0;
        for (int i = 2; i <= iNum; i++)
        {
            iSum = iOne + iTwo;
            iTwo = iOne;
            iOne = iSum;
            printf("Fbio: N = %d, Value = %d\n", i, iSum);
        }
    
        return iSum;
    }
    
    //
    // 类似题目：一只青蛙一次可以跳上一级台阶，也可以跳上2级，求该青蛙跳上一个N级的台阶总共有多少种跳法？
    int JumpStep_1(int iNum)
    {
        if (iNum <= 2)
        {
            return iNum;
        }
    
        CalcFbio(iNum);
        return JumpStep_1(iNum - 1) + JumpStep_1(iNum - 2);
    }
    
    int JumpStep_2(int iNum)
    {
    #if 0
        //int iSumStep = 0;
        int iStep1 = 1;
        int iStep2 = 2;
    
        while (iNum-- > 1)
        {
            iStep2 += iStep1;
            iStep1 = iStep2 - iStep1;
            printf("JumpStep: N = %d, Value = %d\n", iNum, iStep1);
        }
    
        return iStep1;
    
    #else 
    
    #endif
    
        if (iNum <= 2)
        {
            return iNum;
        }
    
        int iRes = 0;
        int iOne = 1;
        int iTwo = 2;
    
        for (int i = 3; i <= iNum; i++)
        {
            iRes = iOne + iTwo;
            iOne = iTwo;
            iTwo = iRes;
            printf("JumpStep: N = %d, Value = %d\n", i, iRes);
        }
    
        return iRes;
      
    }
    
    void FiboTestFunc()
    {
        cout << "\n\n --------------- FiboTestFunc Start -------------->" << endl;
    
        //for (int i = 0; i < 20; i++)
        //{
        //    printf("斐波那契数列: N = %d, Value = %d\n", i, Fbio(i));
        //}
        
        int iNum = 10;
        printf("斐波那契数列: N = %d, Value = %d\n", iNum, Fbio_1(iNum));
        printf("方法一运行次数: %d\n", s_RunTime);
    
        cout << "========================>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
        vector<int> vect(iNum, 0);
        s_RunTime = 0;
        printf("斐波那契数列: N = %d, Value = %d\n", iNum, Fbio_2(iNum, vect));
        printf("方法二运行次数: %d\n", s_RunTime);
    
        cout << "========================>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
        printf("斐波那契数列: N = %d, Value = %d\n", iNum, Fbio_3(iNum));
    
        cout << "========================>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
        s_RunTime = 0;
        printf("青蛙跳台阶: N = %d, Value = %d\n", iNum, JumpStep_1(iNum));
        printf("方法一运行次数: %d\n", s_RunTime);
    
        cout << "========================>>>>>>>>>>>>>>>>>>>>>>>>>>>>" << endl;
        printf("青蛙跳台阶: N = %d, Value = %d\n", iNum, JumpStep_2(iNum));
    
        cout << "\n\n --------------- FiboTestFunc End -------------->" << endl;
    
    }

转载于:https://www.cnblogs.com/yzdai/p/11258630.html