当前位置:网站首页>There is a cow, which gives birth to a heifer at the beginning of each year. Each heifer has a heifer at the beginning of each year since the fourth year. Please program how many cows are there in the
There is a cow, which gives birth to a heifer at the beginning of each year. Each heifer has a heifer at the beginning of each year since the fourth year. Please program how many cows are there in the
2022-07-07 15:13:00 【Lele ~ll】
Input
The input data consists of multiple test cases , One line per test instance , Include an integer n(0<n<55),n The meaning of is described in the title .
n=0 Indicates the end of the input data , Don't deal with it .
Output
For each test case , The output is in the second n The number of cows in the year .
One line per output .
Sample input copy
2 4 5 0
Sample output copy
2 4 6
The code is as follows :
Two ways of thinking , Recursion and dynamic programming
1, recursive
Recursion first considers the end condition of recursion --》 Serve as n==1 When Only one cow ,,return 1
In other cases : The first n year The number of cattle is :n-1 Number of years and The number of new cows born this year
, The number of new cows born this year -- Is the number of fertile cows this year -- Namely n-3 year Number of cows per hour
So we have to discuss n--- When n<=3 When There is only one fertile cow ,
Pseudo code :
if (n == 1)
{
return 1;
}
if (n <= 3)
{
return number(n - 1) + 1;
}
else
{
return number(n - 1) + number(n - 3);
}
This code is OK, but It's easy to time out
Let's continue to consider
First year 1 head
In the second year 2 head
The third year 3 head
No new cows have been born in the past three years , And the number of cows is equal to the number of years
improvement :
if (n <= 3)
{
return n;
}
else
{
return number(n - 1) + number(n - 3);
}
The code is as follows :
#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;
}
The second method : Dynamic programming --- It's about finding the rules
equally -- Don't go to this more abstract problem look for N The number of cattle corresponding to the year ,,, This will be more difficult ,, We introduce an array ,, Number of cattle stored every year , Horizontal law finding ,, The essential idea is the same as recursion ,
The code is as follows :
#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 };// The number of cows in the corresponding year
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;
}
Take a look at the speed of two codes ( The top one is for Dynamic programming solution
obviously ----- Dynamic programming ---- still Be quick
Try dynamic programming Fibonacci sequence ~!@#¥%……&*(
边栏推荐
- Ctfshow, information collection: web12
- Novel Slot Detection: A Benchmark for Discovering Unknown Slot Types in the Dialogue System
- @ComponentScan
- 13 ux/ui/ue best creative inspiration websites in 2022
- 什麼是數據泄露
- TypeScript 发布 4.8 beta 版本
- 全日制研究生和非全日制研究生的区别!
- CTFshow,信息搜集:web7
- CTFshow,信息搜集:web14
- Ctfshow, information collection: Web3
猜你喜欢
How to enable radius two factor / two factor (2fa) identity authentication for Anheng fortress machine
MySQL bit类型解析
Change win10 Screensaver
Unity's ASE achieves full screen sand blowing effect
Unity之ASE实现卡通火焰
#yyds干货盘点# 解决名企真题:交叉线
Summer safety is very important! Emergency safety education enters kindergarten
Unity's ASE realizes cartoon flame
【跟着江科大学Stm32】STM32F103C8T6_PWM控制直流电机_代码
Notes HCIA
随机推荐
Ascend 910 realizes tensorflow1.15 to realize the Minist handwritten digit recognition of lenet network
【跟着江科大学Stm32】STM32F103C8T6_PWM控制直流电机_代码
【深度学习】图像超分实验:SRCNN/FSRCNN
Protection strategy of server area based on Firewall
Ctfshow, information collection: web5
Read PG in data warehouse in one article_ stat
13 ux/ui/ue best creative inspiration websites in 2022
众昂矿业:萤石继续引领新能源市场增长
Integer learning
Niuke real problem programming - day15
[today in history] July 7: release of C; Chrome OS came out; "Legend of swordsman" issued
A need to review all the knowledge, H5 form is blocked by the keyboard, event agent, event delegation
防火墙基础之服务器区的防护策略
Niuke real problem programming - Day17
Today's sleep quality record 78 points
asp.netNBA信息管理系统VS开发sqlserver数据库web结构c#编程计算机网页源码项目详细设计
Andriod --- JetPack :LiveData setValue 和 postValue 的区别
Ctfshow, information collection: web4
数学建模——什么是数学建模
有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?