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