母牛的故事
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 120200 Accepted Submission(s): 58541
Problem Description
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
Input
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
n=0表示输入数据的结束，不做处理。
Output
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
每个输出占一行。
Sample Input
2
4
5
0
4
5
0
Sample Output
2
4
6
4
6
这道题涉及的内容是递归化成递推，这类型的题以后会演化成动态规划，重在练习和思考！！
首先拿到题目想到的就是动物繁殖典型例子斐波那契数列，fn=f(n-1)+f(n-2)
同样的，本题可以枚举他前十个数来观察，很多题目都可以这么做，ACM一部分感觉就是在玩小学找规律T T
回到正题··然后得到fn=f(n-1)+f(n-3)
有了这个就可以直接递归了AC了~~
再深入一些学习这道题，把繁琐的递归转成迭代，我个人是用两个概念来引导自己思考
首先拿到题目想到的就是动物繁殖典型例子斐波那契数列，fn=f(n-1)+f(n-2)
同样的，本题可以枚举他前十个数来观察，很多题目都可以这么做，ACM一部分感觉就是在玩小学找规律T T
回到正题··然后得到fn=f(n-1)+f(n-3)
有了这个就可以直接递归了AC了~~
再深入一些学习这道题，把繁琐的递归转成迭代，我个人是用两个概念来引导自己思考
1.有所有状态的状态方程
2.找出各个状态的转换式
状态方程即是 fn=f(n-1)+f(n-3)
转换式可以这么尝试，举个例子吧~
如：
2.找出各个状态的转换式
状态方程即是 fn=f(n-1)+f(n-3)
转换式可以这么尝试，举个例子吧~
如：
假如每年的牛数量都是已知的
第四年的牛等于第三年的牛加第一年的牛
第五年的牛等于第四年的牛加第二年的牛
fn=f1+f3; 这里完成了fn的状态转化
第五年的牛等于第四年的牛加第二年的牛
fn=f1+f3; 这里完成了fn的状态转化
第一年的牛过了一年成了第二年的牛
f1=f2; 这里完成了f1的状态转化
第三年的牛过了一年成了第四年的牛
f2=f3; 这里是记录第二年过了一年成第三年没用上的
f3=fn; 这里完成了f2的状态转化
然后就可以有以下代码
#include<stdio.h>
//递归
int sum(int n)
{
if (n <= ) return n;
else return (sum(n-) + sum(n - ));
}
int main()
{
int n;
while (~scanf("%d", &n) != EOF&&n!=)
printf("%d\n", sum(n));
getchar();
return ;
}
#include<stdio.h>
//迭代
int main()
{
int f1,f2,f3,fn,i,n;
while(~scanf("%d",&n)&&n!=)
{
if(n==)fn=;
else if(n==)fn=;
else if(n==)fn=;
else
{
f1=;
f2=;
f3=;
for(i=;i<=n;i++)
{
fn=f1+f3;
f1=f2;
f2=f3;
f3=fn;
}
}
printf("%d\n",fn);
}
return ;
}