当前位置:网站首页>有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
2022-07-07 13:04:00 【乐乐~LL】
输入
输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<55),n的含义如题目中描述。
n=0表示输入数据的结束,不做处理。
输出
对于每个测试实例,输出在第n年的时候母牛的数量。
每个输出占一行。
样例输入复制
2 4 5 0
样例输出复制
2 4 6
代码如下:
两种思路,递归和动态规划
1,递归
递归先考虑递归结束条件--》为当 n==1 的时候 只有一头牛,,return 1
其他情况下:第n年 的牛的数量为:n-1年的数量和 今年新出生的牛的数量
,今年新出生的牛的数量 --就是在今年有生育能力的牛的数量--就是n-3年 时牛的数量
所以又要讨论 n---当 n<=3的时候 有生育能力的牛只有一头,
伪代码:
if (n == 1)
{
return 1;
}
if (n <= 3)
{
return number(n - 1) + 1;
}
else
{
return number(n - 1) + number(n - 3);
}
这个代码没问题但是 容易超时
我们继续考虑
第一年 1头
第二年 2头
第三年 3头
前三年来说都没有新的牛出生,且牛的头数和年份数相等
改进:
if (n <= 3)
{
return n;
}
else
{
return number(n - 1) + number(n - 3);
}
代码如下:
#include<stdio.h>
int number(int n)
{
/*if (n == 1)
{
return 1;
}*/
if (n <= 3)
{
//return number(n - 1) + 1;
return n;
}
else
{
return number(n - 1) + number(n - 3);
}
}
int main()
{
int arr[1000]={0};
int n = 0;
int i = 0;
scanf("%d", &n);
while (n != 0)
{
arr[i] = n;
i++;
scanf("%d", &n);
}
for (i = 0; arr[i] != '\0'; i++) {
printf("%d\n", number(arr[i]));
}
return 0;
}
第二种方法:动态规划---就是找规律
一样--这种比较抽象的题不要去 找 N年对应的牛的个数,,,这样会比较困难,,我们引入一个数组,,存放每年的牛的个数,横向找规律,,本质思路和递归同,
代码如下:
#include<stdio.h>
int main()
{
int arr[1000]={0};
int n = 0;
int i = 1;
scanf("%d", &n);
int max = n;
while (n != 0)
{
arr[i] = n;
i++;
if (n >= max)
{
max = n;
}
scanf("%d", &n);
}
int number[1000] = { 0 };//对应年份牛的个数
for (i = 1; i <= max; i++)
{
if (i <= 3)
{
number[i] = i;
}
else
{
number[i] = number[i - 1] + number[i - 3];
}
}
for (i = 1; arr[i] != '\0'; i++)
{
printf("%d\n", number[arr[i]]);
}
return 0;
}
来看看两个代码的速度(上面的是用 动态规划求解
显然 -----动态规划 ----还是 要快呀
快去用动态规划试试 斐波那契数列吧~!@#¥%……&*(
边栏推荐
- MySQL installation configuration 2021 in Windows Environment
- 微信小程序 01
- 一文读懂数仓中的pg_stat
- FFmpeg----图片处理
- Niuke real problem programming - Day9
- Bye, Dachang! I'm going to the factory today
- Ctfshow, information collection: web9
- Discussion on CPU and chiplet Technology
- Ctfshow, information collection: web14
- Pandora IOT development board learning (HAL Library) - Experiment 12 RTC real-time clock experiment (learning notes)
猜你喜欢
"July 2022" Wukong editor update record
微信小程序 01
Protection strategy of server area based on Firewall
【深度学习】图像超分实验:SRCNN/FSRCNN
CTFshow,信息搜集:web2
Ctfshow, information collection: web5
【搞船日记】【Shapr3D的STL格式转Gcode】
CTFshow,信息搜集:web5
With 8 modules and 40 thinking models, you can break the shackles of thinking and meet the thinking needs of different stages and scenes of your work. Collect it quickly and learn it slowly
Today's sleep quality record 78 points
随机推荐
8大模块、40个思维模型,打破思维桎梏,满足你工作不同阶段、场景的思维需求,赶紧收藏慢慢学
Ctfshow, information collection: web10
什麼是數據泄露
摘抄的只言片语
缓冲区溢出保护
Lidar Knowledge Drop
IDA pro逆向工具寻找socket server的IP和port
【服务器数据恢复】戴尔某型号服务器raid故障的数据恢复案例
2. 堆排序『较难理解的排序』
What is the process of ⼀ objects from loading into JVM to being cleared by GC?
Stm32f103c8t6 PWM drive steering gear (sg90)
Used by Jetson AgX Orin canfd
Promoted to P8 successfully in the first half of the year, and bought a villa!
数学建模——什么是数学建模
Niuke real problem programming - day18
最安全的证券交易app都有哪些
拜拜了,大厂!今天我就要去厂里
Pinduoduo lost the lawsuit, and the case of bargain price difference of 0.9% was sentenced; Wechat internal test, the same mobile phone number can register two account functions; 2022 fields Awards an
Mathematical modeling -- what is mathematical modeling
CTFshow,信息搜集:web8