HDU 母牛的故事

題目

思路

fn代表前n年母牛的數目，先寫出前幾年的母牛數，試着找出規律：

第n年： n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9

fn頭牛？f1=1 f2=2 f3=3 f4=4 f5=6 f6=9 f7=13 f8=19 f9=28

我們可以得出這樣一個公式：

fn=fn-1+fn-3

再了解一下，fn-1是前一年的牛，第n年仍然在，fn-3是前三年那一年的牛，但換句話說也就是第n年具有生育能力的牛，也就是第n年能生下的小牛數。

代碼

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    
    int n;
    while (cin >> n, n)
    {
    	int f1 = 1, f2 = 2, f3 = 3, fn;
	    if (n == 1) cout << f1 << endl;
	    else if (n == 2) cout << f2 << endl;
	    else if (n == 3) cout << f3 << endl;
	    else 
	    {
	        for (int i = 4; i <= n; i++)
	        {
	            fn = f1 + f3;
	            f1 = f2;
	            f2 = f3;
	            f3 = fn;
	        }
	        cout << fn << endl;
	    }
    }
    return 0;
}
           

另解(遞歸)

缺點： 效率低，容易爆棧！

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int f(int n)
{
    if (n < 4) return n;
    return f(n - 1) + f(n - 3);
}

int main()
{
    int n;
    while (cin >> n, n)
    {
    	cout << f(n) << endl;
    }
    return 0;
}