HDU 2018雌牛の物語

Problem Description

1頭の雌牛がいて、毎年年の初めに1頭の子牛を産んでいます.子牛は4年目から毎年年初にも子牛を産む.プログラミングして実現してn年目の時、何頭の雌牛がありますか?

Input

入力データは複数のテストインスタンスからなり、各テストインスタンスは1行を占め、1つの整数n(0 n=0は入力データの終了を表し、処理しない.

Output

各試験例について、n年目の雌牛の数を出力した.出力ごとに1行を占めます.

Sample Input

2 4 5 0

Sample Output

2 4 6

ぶんせき

タイトルの既知に基づいて、表をリストします.
n年目
成年牛
幼牛1
幼牛2
幼牛3
合計
1
1
1
2
1
1
2
3
1
1
1
3
4
1
1
1
1
4
5
2
2
1
1
6
6
3
3
2
1
9
7
4
4
3
2
13
8
6
6
4
3
19
9
9
9
6
4
28
…
…
…
…
…
…
表を見て、フィボナッチの数列を連想すると、次の式が得られます.
fn = fn-1 + fn-3

問題解

// 1
#include
using namespace std;
int main() 
{	
	int n;
	while(cin>>n&&n!=0)
	{
		int a[56];
		a[0] = 1;a[1] = 2;a[2] = 3;a[3] = 4;
		for(int i=4;i<56;i++)
			a[i] = a[i-1] + a[i-3];	
		cout << a[n-1] << endl;	
	} 
 	return 0;
}

// 2— 
#include 
using namespace std;
int fun(int n)
{
	if(n<5) return n;
	else return fun(n-1)+fun(n-3);
}
int main() 
{	
	int n;
	while(cin>>n&&n!=0)
	{
		cout << fun(n) << endl;
	} 
 	return 0;
}