本文主要是介绍蓝桥杯备赛day02:递推,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
斐波那契数列
#include <bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;int dp[n+1];dp[1]=1;dp[2]=1;for(int i = 3;i <= n;i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[n];return 0;
}
n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
if n > 1:dp[2] = 1
for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]print(dp[n])
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] dp = new int[n + 1];dp[1] = 1;if (n > 1) {dp[2] = 1;}for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}System.out.println(dp[n]);scanner.close();}
}
养牛场
题目描述
现有一养殖场培育母牛。假设一头母牛名叫 M,每年春季生一头小母牛,小母牛经历两年的成长可以成熟,从成熟的这一年开始,每年春季生一头小母牛,那么在第 n 年春季的时候,母牛 M 共有多少头后代母牛呢?(注意:第一年母牛 M,不产小牛,从第二年开始产小牛)
输入描述
一个整数 n,表示年数。
输出描述
一个整数,表示统计结果。
样例输入
5
样例输出
7
提示
数据范围与提示
1≤n≤20
方法一:递推
询问是“母牛 M 共有多少头后代母牛”,第一年不生产小牛,后代母牛个数为0,第二年生产一头小牛,后代母牛个数为1,第三年生成一头小牛,后代母牛个数为2,第四年,母牛M生产一头小牛,第二年生产的小牛已经长大也生产一头小牛,总共生产2头小牛,后代母牛个数为4,第五年,母牛M生产一头小牛,第二年生产的小牛生产一头小牛,第三年生产的小牛生产一头小牛,总共生产3头小牛,后代母牛个数为7。这就是样例的过程,输入再大一点,手推就有点累了,那么怎么转化成递推公式,让电脑帮我们推呢?
用dp[n]表示第 n 年春季的时候,母牛 M 拥有后代母牛的个数。第 n 年春季的时候,母牛 M 拥有后代母牛的个数等于第 n-1 年拥有后代母牛的个数加上第 n 年生产的小牛。第n年生产的小牛等于第n年成熟的母牛的个数,关键点在于这个怎么表示,成熟的母牛个数等于早就成熟的母牛以及在第n年刚成熟的母牛,第n-2年的所有后代母牛(包括第n-2年之前出生的小牛以及第n-2年刚出生的小牛)在第n年肯定已经成熟,所以第n-2年的所有牛的个数+1就是第 n 年生产的小牛,加1加的是最初的母牛,它也要生产小牛,但是不被记录在dp数组里面。
d p [ n ] = d p [ n − 1 ] + d p [ n − 2 ] + 1 dp[n]=dp[n-1]+dp[n-2]+1 dp[n]=dp[n−1]+dp[n−2]+1
因为这里出现了n-2,所以dp[1]=0,dp[2]=1后面就for循环递推即可。
#include <bits/stdc++.h>
using namespace std;
int dp[21];
int main(){int n;cin>>n;dp[1]=0,dp[2]=1;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+1;}cout<<dp[n];return 0;
}
n = int(input())
dp = [0] * (n + 1)
dp[1] = 0
if n > 1:dp[2] = 1for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2] + 1print(dp[n])
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] dp = new int[n + 1];dp[1] = 0;if (n > 1) {dp[2] = 1;}for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2] + 1;}System.out.println(dp[n]);scanner.close();}
}
昆虫繁殖
题目描述
科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵,每对卵要过两个月长成成虫。假设每个成虫不死,第一个月只有一对成虫,且卵长成成虫后的第一个月不产卵(过X个月产卵),问过Z个月以后,共有成虫多少对?0≤X≤20,1≤Y≤20,X≤Z≤50。
输入
x,y,z的数值。
输出
过Z个月以后,共有成虫对数。
样例
输入数据 1
1 2 8
输出数据 1
37
方法一:递推
询问是过Z个月以后,共有成虫多少对。第1个月只有一对成虫,第2个月产了2对卵,第3个月产了2对卵,第4个月产了2对卵,共有3对成虫,第5个月产了6对卵,共有5对成虫,第6个月产了10对卵,共有7对成虫,第7个月产了14对卵,共有13对成虫,第8个月产了26对卵,共有23对成虫,第9个月产了46对卵,共有37对成虫。
以上是样例的递推过程,令c[n]表示第n个月的成虫数量,r[n]表示第n个月的卵数量,则c[n]=c[n-1]+r[n-2],r[n]=y*c[n-x]。
注意这里出现了n-x,那么从1到x的值应该被初始化,1到x只有一对成虫且还没有产卵,所以c[i]=1,r[i]=0。
#include<bits/stdc++.h>
using namespace std;
long long c[100]={};
long long r[100]={};
int main() {long long x,y,z;cin>>x>>y>>z;for(int i=1;i<=x;i++){c[i]=1;r[i]=0;}for(int i=x+1;i<=z+1;i++){c[i]=c[i-1]+r[i-2];r[i]=c[i-x]*y;}cout<<c[z+1]; return 0;
}
x, y, z = map(int, input().split())c = [0] * (z + 2)
r = [0] * (z + 2)for i in range(1, x + 1):c[i] = 1r[i] = 0
for i in range(x + 1, z + 2):c[i] = c[i - 1] + r[i - 2]r[i] = c[i - x] * yprint(c[z + 1])
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long x = scanner.nextLong();long y = scanner.nextLong();long z = scanner.nextLong();long[] c = new long[(int) (z + 2)];long[] r = new long[(int) (z + 2)];for (int i = 1; i <= x; i++) {c[i] = 1;r[i] = 0;}for (int i = (int) (x + 1); i <= z + 1; i++) {c[i] = c[i - 1] + r[i - 2];r[i] = c[i - (int) x] * y;}System.out.println(c[(int) (z + 1)]);scanner.close();}
}
这篇关于蓝桥杯备赛day02:递推的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!