HDU統計問題
4426 ワード
とうけいてきもんだい
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 137 Accepted Submission(s): 94
Problem Description
無限大の2 D平面では、次のように仮定します.
1、 毎回1つしか移動できません.
2、 後ろに歩いてはいけません(目的地が「上へ」だと仮定すると、左に歩いてもいいし、右に歩いてもいいし、上へ歩いてもいいですが、下へ歩いてはいけません).
3、 通り過ぎた格子はすぐに陥没して二度と歩けない.
nステップの異なるシナリオ数を求める(2つのステップが1ステップ異なる限り,異なるシナリオと考えられる).
Input
まず、Cグループのテストデータがあることを示す正の整数Cを与える.
次のC行は、各行に整数n(n<=20)が含まれ、nステップを進むことを示す.
Output
nステップの異なるシナリオの総数をプログラミングして出力してください.
各グループの出力は1行を占めます.
Sample Input
Sample Output
再帰式は、a[n]=2*a[n-1]+a[n-2]
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 137 Accepted Submission(s): 94
Problem Description
無限大の2 D平面では、次のように仮定します.
1、 毎回1つしか移動できません.
2、 後ろに歩いてはいけません(目的地が「上へ」だと仮定すると、左に歩いてもいいし、右に歩いてもいいし、上へ歩いてもいいですが、下へ歩いてはいけません).
3、 通り過ぎた格子はすぐに陥没して二度と歩けない.
nステップの異なるシナリオ数を求める(2つのステップが1ステップ異なる限り,異なるシナリオと考えられる).
Input
まず、Cグループのテストデータがあることを示す正の整数Cを与える.
次のC行は、各行に整数n(n<=20)が含まれ、nステップを進むことを示す.
Output
nステップの異なるシナリオの総数をプログラミングして出力してください.
各グループの出力は1行を占めます.
Sample Input
2
1
2
Sample Output
3
7
再帰式は、a[n]=2*a[n-1]+a[n-2]
#include <iostream> using namespace std; int main() { int a[21];
a[0] = 0;
a[1] = 3;
a[2] = 7; for(int i = 3;i < 21; i++)
a[i] = 2*a[i-1]+a[i-2]; int T,n;
cin>>T; while(T--) {
cin>>n;
cout<<a[n]<<endl; } return 0; }