shijilin1


私信TA

用户名:Fl1ui

访问量:8149

签 名:

等  级
排  名 359
经  验 3868
参赛次数 0
文章发表 1
年  龄 99
在职情况 学生
学  校 望子成龙小学
专  业

  自我简介:

TA的其他文章

解题思路:

打表理清思路先,把牛家分大牛、三岁牛宝、两岁牛宝、一岁牛宝(虚岁,出生就是一岁啦)

2.png

在第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分

95 人评分

  评论区

那个大佬能给我讲一下递归公式的for循环是什么意思
2021-11-13 21:50:42 | |
这个for循环i定义的是什么意思
2021-11-13 21:48:24 | |
厉害啊
2021-11-08 21:48:10 | |
2021-11-06 22:32:10 | |
有个问题,为什么数组长度是56呢,不应该是循环输入的吗,怎么做到循环输入直到输入0呢
2021-11-06 15:34:21 | |
#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;
}
能跑出来就是时间超了
2021-10-08 15:50:19 | |
可以nice
2021-10-03 15:28:58 | |
出生即一岁,第一年不应该是老牛+一岁牛宝宝两只牛吗?
2021-09-25 12:02:02 | |