2020/6/21
-
题目描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
-
输入
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。 -
输出
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。 -
样例输入
2
4
5
0 -
样例输出
2
4
6 -
要求
时间限制: 1Sec 内存限制: 128MB
心路历程：
- 通过列举第5、6、7年的母牛数6、9、13，想当然的以为母牛数cows = n + (n - 4) + (n - 3) + ... + 1，于是有：
#include<iostream>
using namespace std;
int sum1(int n) {
int s = 0;
for (int i = 1; i <= n; i++)
s += i;
return s;
}
int sum(int n) {
if (n <= 4)
return n;
else
return n + sum1(n - 4);
}
int main(){
int n;
while (cin >> n && n)
cout << sum(n) << endl;
return 0;
}
- 被退回后发现算法过于头脑简单，因为没有考虑到小母牛所生的小母牛也有繁育能力，导致第8年以后的数据不再满足上述算法，需要在上述程序中引入函数递归的算法，可是思索许久，无从下手，于是查看解题思路，发现竟然有着很简单的隐藏函数关系！
-
列举有：
第n年 ：1 2 3 4 5 6 7 8
f(n)头牛：1 2 3 4 6 9 13 19
-
得函数关系：
- f(n) = f(n-1) + f(n-3) , n>=4;
- f(1) = 1 , f(2) = 2 , f(3) = 3
-
于是有：
#include<iostream>
using namespace std;
int sum(int n) {
if (n <= 3)
return n;
else
return sum(n - 1) + sum(n - 3);
}
int main(){
int n;
while (cin >> n && n)
cout << sum(n) << endl;
return 0;
}
- 提交后报错：时间超限。仔细思索，题目规定n<55，也就是说n最大可取54，由于函数的反复递归调用很费时间，当n超过50时，运行速度是极慢的(约5~20秒)。因此，不能够采用函数的方式进行递归，由于公式已得出，所以可以采用数组进行1-55递归数据的存储，由于只在主函数内作简单的算式递归，所以运行时间短到可以忽略不计。
最终答案：
#include<iostream>
using namespace std;
int main() {
int n, i;
int f[55] = { 0,1,2,3 }; //f[0]=0,f[1]=1,f[2]=2,f[3]=3
for (i = 4; i < 55; i++)
f[i] = f[i - 1] + f[i - 3];
while (cin >> n && n)
cout << f[n] << endl;
return 0;
}
总结与收获：
- 一开始想当然的认为是简单的公式算法，没有列举更多的情况，也没有深入思考问题，以后需要细心全面看待问题；
- 一般采用递归算法的题目都能总结出相应的递归公式，且该递归公式往往不是能够直观反映问题的公式，例如此题中的f(n) = f(n-1) + f(n-3)是通过前几项的列举所直接推导出来的，因此利用递归算法解题时往往采取利用已知条件推导递归公式的方法；
- 递归算法不一定就是递归函数，当递归量很大时，采用函数的方式递归往往会使运行量变得极大，此时可以采用数组储存或进行新旧值的反复替换来完成高效率递归。
