剣指offerの踊り場&変態踊り場

階段を跳ぶ
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
ぶんせき
本題は簡単なフィボナッチ数列問題です.
コード#コード#

class Solution {
public:
    int jumpFloor(int n) {
       /* //    int prev = 0; int cur = 1; for(int i = 1; i <= n ; ++i){ int tmp = cur; cur = prev + cur; prev = tmp; } return cur; */
       //   ：          
        double s = sqrt(5);
        return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);  
    }
};

へんたいステップ
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
方法一分析
ステップ数nの場合、1回目のジャンプのステップ数をs、ステップ数Tとすると、(1)s=1の場合、T(n)=T(n-1)(2)s=2の場合、T(n)=T(n-2)となる.(n)s=nの場合、T(n)=T(0)=1であるので、全体のステップ飛び方式数Tは、
T(n)=T(0)+T(1)+T(2)+…+T(n−1)
によって
T(0)=T(1)=1なので、
T(n)=2(n−1)
コード#コード#

class Solution {
public:
    int jumpFloorII(int number) {
     long long result=(long long)pow(2,number-1);
    return result;
    }
};

方法二分析
1、n=1の場合、1次ジャンプ:Fib(1)=1しかない.2、n=2の場合、1次ジャンプと2次ジャンプの2種類があります.
Fib(2)=Fib(1)+Fib(0)=2
3、当
n=3の場合、3種類の踊り方があり、初めて1階を飛び出した後、後ろに
Fib(3−1)中跳法;初めて2階を飛び出した後、後ろには
Fib(3−2)中跳法;初めて3階を飛び出した後、後ろには
Fib(3−3)中跳び
Fib(3)=Fib(2)+Fib(1)+Fib(0)=4
n、当
n=nの場合、全部でn種類の踊り方があり、初めて1階を飛び出した後、後ろに
Fib(n−1)中跳法;初めて2階を飛び出した後、後ろには
Fib(n−2)でのジャンプ・・・初めてn階を飛び出した後、後ろに
Fib(n-n)中跳法
Fib(n)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n−1)
また
Fib(n−1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n−2)
2つの式の減算:
Fib(n)−Fib(n−1)=Fib(n−1)
Fib(n)=2∗Fib(n−1)   n>=2
コード#コード#

class Solution {
public:
    int jumpFloorII(int number) {
     if(number<= 0)
        return 0;
    if(number==1)
        return 1;
    long long FibN = 1; 
    for(int i=2;i<=number;i++)
    {
        FibN *= 2;
    }
    return FibN;      
    }
};

注:コードは牛客網プラットフォームでデバッグされました.デバッグプラットフォーム:リンクりんく
参考資料:
1、http://www.acmerblog.com/offer16-jiudu-1389-4082.html 2、https://leetcode.com/discuss/16866/basically-its-a-fibonacci