解题思路:
打表理清思路先,把牛家分大牛、三岁牛宝、两岁牛宝、一岁牛宝(虚岁,出生就是一岁啦)
在第5年时,牛宝开始陆续长成大牛,三岁牛宝就变成了大牛
同理,两岁牛宝变三岁牛宝,一岁牛宝变两岁牛宝
而新的一岁牛宝则是去年的大牛跟三岁牛宝的总牛数(三岁牛宝今年长成大牛也开始生小牛宝了)
思路理清后,就要求递推公式了,把4种牛分别用字母标记:
大牛a[]、三岁牛宝b[]、两岁牛宝c[]、一岁牛宝d[]以及牛头数s[]
可以得出第n年的各个公式:
a[n] = a[n-1]+b[n-1]
b[n] = c[n-1]
c[n] = d[n-1]
d[n] = a[n-1]+b[n-1] = a[n]
则总牛数 s[n]=a[n]+b[n]+c[n]+d[n]
= a[n-1]+b[n-1]+c[n-1]+d[n-1]+a[n-1]+b[n-1]
= s[n-1]+a[n-2]+b[n-2]+c[n-2]
= s[n-1]+a[n-3]+b[n-3]+c[n-3]+d[n-3]
= s[n-1]+s[n-3]
根据递推公式可以写出基本的递归函数如下:
int fab(int month) { if(month < 4) { return month; } else { return fab(month-1)+fab(month-3); } }
但递归在月份大的时候空间复杂度跟时间复杂度都特别高,故需再用动态规划思路,在递归的过程中不断记录计算过的月份的牛头数,需要的时候可以直接调用
参考代码:
应题目要求使用递归:
#include<iostream> using namespace std; long long cow[56] = {0,1,2,3,4}; // 在main函数外定义的数组会全部自动初始化为0 long long fab(int month) { if(cow[month] == 0) { // 没有算过的月份,数组内存的是0 cow[month] = fab(month-1) + fab(month-3); return cow[month]; } else { return cow[month]; } } int main () { int n; while(scanf("%d", &n) && n) cout << fab(n) << endl; return 0; }
或者直接用递推公式:
#include<iostream> using namespace std; int main () { int cow[56] = {0,1,2,3,4}; for(int i = 4; i < 55; i ++) cow[i] = cow[i-1] + cow[i-3]; int n; while(scanf("%d", &n) && n) cout << cow[n] << endl; return 0; }
0.0分
246 人评分
#include<stdio.h> int nun(int n); int main() { int n; while(scanf("%d",&n)&&nun(n)>0) printf("%d\n",nun(n)); return 0; } int nun(int n) { if(n>=4) return nun(n-1)+nun(n-3); return n; } 能跑出来就是时间超了
出生即一岁,第一年不应该是老牛+一岁牛宝宝两只牛吗?
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:722 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1048 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:732 |
不容易系列 (C语言代码)浏览:664 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:742 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:517 |
简单的a+b (C语言代码)浏览:335 |
WU-格式化数据输出 (C++代码)浏览:1194 |
WU-格式化数据输出 (C语言代码)浏览:1741 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:522 |
Sato 2021-11-12 08:55:51 |
可以用链表,每次都进行尾插入来储存数据,这样可以输入无限多个数。最后再输出就行啦。
边城 2021-11-21 19:45:44 |
while(t)cin>>t;
Yeah 2022-01-09 21:40:31 |
int in;cin>>in;while(in!=0){cin>>in;}
盘旋 2022-02-22 18:27:37 |
while(scanf("%d",&n)!=EOF&&n!=0)