九度OJ-テーマ1389:変態階段

タイトルリンクアドレス:
九度OJ-テーマ1389:変態階段
1匹のカエルは一度に1段の階段を跳ぶことができて、2段に跳ぶことができて......それはn段に跳ぶことができます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
入力:入力には複数のテストサンプルが含まれる場合があります.入力には、各テストケースに対して整数n(1<=n<=50)が含まれます.
出力:各テストケースに対応して、カエルがn段の階段を飛び上がるのに合計何種類のジャンプ法があるかを出力します.
サンプル入力:6
サンプル出力:32
問題解決の考え方:
"変态が阶段を跳ぶ"というテーマを见た时、私の心の中はまだ少し怖くて、囧..しかしよく分析してみると、この問題は少しも「変態」ではないことが分かった.O(∩∩)O~カエルがn級の階段を飛び上がる踊りの数をf(n)と仮定し、カエルは一度に1級の階段を飛び上がることができ、2級に飛び上がることもできる......n級に飛び上がることもできる.したがって、(1)カエルが1段の階段を飛び上がることを選択した場合、残りの階段数はn−1であり、1つのn−1段の階段を飛び上がるジャンプ数はf(n−1)である.(2)カエルが2段の階段を飛び上がることを選択した場合、残りの階段数はn−2であり、1つのn−2段の階段を飛び上がるジャンプ数はf(n−2)である.(3)カエルが3段の階段を飛び上がることを選んだ場合、残りの階段の数はn-3であり、1つのn-3段の階段を飛び上がるジャンプの数はf(n-3)......(n−1)カエルがn−1段の階段をジャンプすることを選択すると、残りの階段数は1であり、1段の階段をジャンプするジャンプ数はf(1)である.(n)カエルがn段の階段を飛び上がることを選択すると、残りの階段数は0であり、0段の階段を飛び上がるジャンプ数はf(0)である.従って、f(n)=f(n−1)+f(n−2)+…+f(2) + f(1) + f(0)                                                           [1] f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)                                                                 [2] ……                                                                                                                     ...... f(2) = f(1) + f(0)                                                                                                     [n-2] f(1) = f(0)                                                                                                              [n-1] f(0)=1[n]は、式[1]および式[2]によって、f(n)=f(n−1)+f(n−1)=2*f(n−1)を押し出すことができる.式[n]:f(0)=1については,カエルが1段しかない階段を飛び上がる場合,1段しか飛び上がる選択がなく,残りの階段数は0であるため,f(1)=f(0)=1となるので,以下の式を出すことができる.
MACコードは以下の通りである.

#include<stdio.h>
 
/**
*  n 
* f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1) + f(0) ---->  f(n) = 2*(f(n-1))   // n >= 2
* @param jumpMethods   
* @return void
*/
void getNumberOfSuperJumpSteps(long long * jumpMethods)
{
    int i;
    jumpMethods[1] = 1;
    for(i = 2;i <= 50;i++)
    {
       jumpMethods[i] = 2 * jumpMethods[i - 1];
    }
}
 
int main()
{
    int n;
    long long jumpMethods[51];               //  
    getNumberOfSuperJumpSteps(jumpMethods);
    while(EOF != scanf("%d",&n))
    {
        printf("%lld
",jumpMethods[n]);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1389
    User: blueshell
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:912 kb
****************************************************************/