SDUT-1243 母牛的故事

母牛的故事

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic Discuss

Problem Description

有一对夫妇买了一头母牛，它从第2年起每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0< n< 55)，n的含义如题目中描述。 n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。

Example Input

2

4

5

Example Output

2

4

6

递推问题，关键在于找到递推公式，我们可以这样想，求某一年（n）的牛的数量，因为每一头牛是第四个年头才会生小母牛的，所以第n年的母牛数量 f(n) 中有一部分肯定等于 f(n-3)的二倍，因为所有 第 n-3 年的牛在第n年都可以生小母牛了（这自 n-3 算起，n是第四年），除了这一部分之外，还有一部分是没有成熟的母牛的数量，这个计算我们需要借助 n-1 年的母牛数量，即 f(n-1)-f(n-3) 就是未成熟的母牛的数量，综合起来：

f(n) = f(n-3) * 2 + ( f(n-1) - f(n-3) ) = f(n-3) + f(n-1)

拿到这个递推公式，简单编程即可：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

int main(){
   int s[];
   s[]=;
   s[]=;
   s[]=;
   for(int i=;i<;i++){
    s[i]=s[i-]+s[i-];
   }
   int n;
   while(cin>>n&&n){
    cout<<s[n]<<endl;
   }
}
           

当然也可以使用递归函数的方式，这道题的数据量不大，所以就直接全部计算了，如果使用递归函数的话，可以结合动态规划的思想，计算更少一点。

end~