蓝桥杯备赛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] = 1
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + 1
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] = 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] = 1
r[i] = 0
for i in range(x + 1, z + 2):
c[i] = c[i - 1] + r[i - 2]
r[i] = c[i - x] * y
print(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();
}
}