解题思路:
审清题干,养成习惯。
有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。是不是有点似曾相识?没错,这道题和斐波那契数列很相似,只不过递增的规律稍微变了一些。
一个输入,一个输出,多组测试用例,输入0结束,这是首先要明确的,所以要用到循环,并且输入0时结束循环。
我们先来分析一下这道题的规律吧。
这里简单地列一个表格:
年份 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
母牛数量 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 | 28 |
有没有看出一些端倪?没错,fn=fn-1+fn-3(n>3)。记不记得斐波那契数列的公式?fn=fn-1+fn-2(n>2)。说到这里,想必大家都会做了吧?
注意,这里题目明确要用递归的方法,所以大家尽量还是用递归来做,虽说用数组的方法也能提交。。。
既然是递归,那就离不开三点:找重复、找变化、找边界。
(1)找重复:就是递归时重复操作的部分,详见上面的公式;
(2)找变化:就是递归时参数的变化,上面的公式一起囊括了;
(3)找边界:就是递归脱出的条件,这里很明显是n<=3,因为此时上面的公式不适用了。
写成分段函数的形式就是:
n ,n<=3
f(n)= (没法打大括号,各位将就看)
f(n-1)+f(n-3) ,n>3
注意事项:
(1)注意测试用例是多组,要想办法循环输入并输出;
(2)注意程序运行结束的条件是输入0时结束;
(3)注意递归方法的脱出条件是n<=3;
参考代码:
# include<stdio.h> int fun(int n) { if(n<=3) return n; else return fun(n-1)+fun(n-3); } int main() { int n; while(scanf("%d",&n) && n) printf("%d\n",fun(n)); return 0; }
如有裨益,吾之幸也。祝大家编程进步。
0.0分
940 人评分
运行错误 0 ,这是什么错误理由 #include <stdio.h> int factor( int n ) { if (n<5) return n; else return factor(n-3)+factor(n-1); } int main() { int year,s; printf("请输入第n年:"); scanf("%d",&year); s=factor (year); printf("母牛的数量:%d\n",s); }
#include<iostream> using namespace std; int fn(int num) { int sum = 0; if(num<3||num == 3){ sum = num; } else { sum = fn(num - 1) + fn(num - 3); } return sum; } int main() { int n; while (cin >> n && n!=0) { int sum = fn(n); cout<<sum<<endl; } } 结果的是时间超时,该怎么改进,救命救命!
李白 2022-02-08 12:32:07 |
用scanf读入试试
#include <stdio.h> #include <stdlib.h> int mcd(int a); int main() { int a; while(scanf("%d",&a)&&(0<a&&a<55)) { if(a==0) return 0; else printf("%d\n",mcd(a)); } return 0; } int mcd(int a) { if(a<=4) return a; else return mcd(a-1)+mcd(a-3); }
为啥我枚举到第八年是18头,想不通哪里出错了。。
while(scanf("%d",&n) && n) printf("%d\n",fun(n)); 啥意思
/*有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。 请编程实现在第n年的时候,共有多少头母牛?*/ #include <stdio.h> int main() { int cows[55] = { 0, 1, 2, 3, 4 }; int n, i; for (i = 5; i < 55; i++) cows[i] = cows[i - 1] + cows[i - 3]; while (scanf("%d", &n),n) { if (n == 0) break; printf("%d\n", cows[n]); } return 0; }
2108syx 2022-03-17 15:12:22 |
while(n!=0) { scanf("%d",&n); printf("%d ",fun(n)); 为什么这样就不对?
CCK 2022-03-20 13:12:04 |
当输入n为0或者复数时直接跳出循环