C++經典算法題

1.一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

假設f(n)是n個台階跳的次數。

1. f(1) = 1
2. f(2) 會有兩個跳得方式，一次1階或者2階，這回歸到了問題f(1),f(2) = f(2-1) + 1 =2

3. f(3) 會有三種跳得方式，1階、2階、3階，那麼就是第一次跳出1階後面剩下：f(3-1);第一次跳出2階，剩下f(3-2)；第一次3階，那麼剩下f(3-3).是以結論是

   f(3) = f(3-1)+f(3-2)+1=4

4. f(n)時，會有n中跳的方式，1階、2階...n階，得出結論：

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + 1 

=> f(n-1)=f(n-2)+...+f(n-(n-1)) + 1 

=>f(n) = 2*f(n-1)     (n>=3)   f(2)=2f(1)同樣成立，是以

f(n) = 2*f(n-1)     (n>=2) 

是以，可以得出結論

代碼如下(遞歸實作)：

int func(int target)
{
    if(target<=0){ 
        return 0;
    }
    if(1==target){
        return 1;
    }
    return 2*func(target-1);
}
           

2、一個台階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有 多少總跳法。

思路：

如果隻有1 級台階，那顯然隻有一種跳法；

如果有2 級台階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1 級；另外一種就是一次跳2 級。

一般情況：把n 級台階時的跳法看成是n 的函數，記為f(n)。

    當n>2 時，第一次跳的時候就有兩種不同的選擇：

    一是第一次隻跳1 級，此時跳法數目等于後面剩下的n-1 級台階的跳法數目，即為f(n-1)；

    另外一種選擇是第一次跳2 級，此時跳法數目等于後面剩下的n-2 級台階的跳法數目，即為f(n-2)。

是以n 級台階時的不同跳法的總數f(n) = f(n-1) + f(n-2)。

用一個公式表示：

       /  1  (n=1)

f(n) =  2  (n=2)

       \  f(n-1) + (f-2)  (n>2)

咦，這不是Fibonacci數列嗎！

時間複雜度：O(n)

第一個方法：遞歸

int jump(int n)
{
    if(n<=0) 
        return 0;
    if(1==n||2==n)
        return n;
    return jump(n-1)+jump(n-2);
}
           

第二種方法：循環

int jump(int n)
{
    if(n<=0) 
        return 0;
    if(1==n||2==n){
        return n;
    }
    else{
        prepre=1; 
        pre=2;
        res=0;
        for(i=3;i<=n;i++){
            res=prepre+pre;
            prepre=pre;
            pre=res;
        }
    return res;
    }
}