剣指offer面接問題9——変態階段

1378 ワード

タイトル1389:変態ステップ
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:2296
解決:1308
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
 
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=50)を含む.
 
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
 
サンプル入力:
6

サンプル出力:
32

質疑応答:
この問題はf(n)=2^n-1を採用している.
ここで注意が必要なデータ型は、Intでは通じませんが、long long intが必要です
本を読んだばかりの頃、このような表タイプ名バイト数の取値範囲signed char 1-128~+127 short int 2-32768~+32767 int 4-2174438648~+2174438647 long int 4-2174438647 long long int 8-9223372036854775808~+9223372036854775807


#include<iostream>

using namespace std;

 

#define LINT long long

 

LINT fbi(LINT n)

{

    if(n==0)

        return 0;

    if(n==1)

        return 1;

    LINT v=n-1;

    LINT re=1;

    while(v--)

    {

        re*=2;

    }

    return re;

}

int main()

{

    LINT n;

    while(cin>>n)

        cout<<fbi(n)<<endl;

    return 0;

}

/**************************************************************

    Problem: 1389

    User:  12138

    Language: C++

    Result: Accepted

    Time:10 ms

    Memory:1520 kb

****************************************************************/