Create Time: 10th June 2024
Title: "[[递推]]"
status: DONE
Author:
- AllenYGY
tags:
- Algorithm
- Share
- Recursion
created: 2024-06-10T14:23
updated: 2024-06-22T16:18
递推是按照一定的规律来求序列中的每一项,一般是通过计算前面的一些项来得出序列中的指定项。
其思想是把一个复杂的庞大的计算过程转化为对简单过程的多次重复,该算法利用了计算机运算速度快和不知疲倦的机器特点。
已知一对兔子,每个月可以生一对小兔子,小兔子出生后的第二个月会变成成年兔子,会继续生小兔子。
第一个月,我们有1对小兔子。
第二个月,我们有1对成年兔子的兔子。
第三个月,我们有1对成年兔子的兔子,有1对小兔子,共2对。
第四个月,我们有2对成年兔子的兔子,有1对小兔子,共3对。
第五个月,我们有3对成年兔子的兔子,有2对小兔子,共5对。
现在我们希望知道第n个月,一共有多少只兔子。
假设:第
已知:一对成年兔每个月可以生一对小兔子
已知:下个月的成年兔是由上个月的成年兔和幼兔组成的
#include <bits/stdc++.h>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
const int MOD = 1000;
const int MAXN = 1000000;
int val[MAXN] = {0};
val[1]=1, val[2]=1;
signed main() {
int n;
cin >> n;
if(val[n]!=0){
cout << val[n] << endl;
return 0;
}
for(int i=3;i<=x;i++){
val[i]=(val[i-1]+val[i-2])%MOD;
}
cout << val[x] << endl;
return 0;
}
有一头母牛,从第二年起,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?
输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<55),n的含义如题目中描述。
n=0表示输入数据的结束,不做处理。
对于每个测试实例,输出在第n年的时候母牛的数量。每个输出占一行。
Input
2
4
5
0
Output
2
4
6
第n年的牛的数量为:n-1年的数量和今年新出生的牛的数量
今年新出生的牛的数量为 n-3 年前牛的数量
#include <bits/stdc++.h>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
const int MOD = 1000;
const int MAXN = 1000000;
int val[MAXN] = {0};
void solve(int x)
{
if(val[x]!=0){
cout << val[x] << endl;
return;
}
val[1]=1;
val[2]=2;
val[3]=3;
for(int i=4;i<=x;i++){
val[i]=(val[i-1]+val[i-3]);
}
cout << val[x] << endl;
}
signed main()
{
int x;
cin >> x;
while (x)
{
solve(x);
cin >> x;
}
return 0;
}
楼梯有
编程计算共有多少种不同的走法。
输入的每一行包括一组测试数据,即为台阶数n。最后一行为0,表示测试结束。
每一行输出对应一行输入的结果,即为走法的数目。
Input
1
2
3
4
0
Output
1
2
4
7
要上第
可以从
可以从
可以从
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
int a[101]={0};
signed main() {
a[1]=1;
a[2]=2;
a[3]=4;
int n;
cin >> n;
while(n){
for(int i=4;i<=n;i++){
a[i]=a[i-1]+a[i-2]+a[i-3];
}
cout << a[n] << endl;
cin >> n;
}
return 0;
}
在2×n的一个长方形方格中,用一个1×2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格,骨牌的铺放方案有三种,如下图:
输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0< n<=50)。
对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。
Input
1
3
2
Output
1
3
2
为了使方格铺满,每次要么铺一个2×1的骨牌,要么铺两个1×2的骨牌,要么铺两个2×1的骨牌首先,分析边界值:2×1方格只有1种铺法,2×2方格只有2种铺法.如图:
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
int a[51]={0};
signed main() {
a[1]=1, a[2]=2;
int n=0;
while(cin>>n){
for(int i=3;i<=n;i++){
a[i]=a[i-1]+a[i-2];
}
cout << a[n] << endl;
}
return 0;
}
桂林山水甲天下,漓江更是美不胜收。 漓江上竹筏整齐排列,形成了美丽的风景线,津津、菲菲和皮皮决定乘坐竹筏游览漓江景色。 已知竹筏有2种规格:一种是单人竹筏,长度为1,宽度为1;另一种是双人竹筏,长度为 2,宽度为2。假设漓江江面的面积是n*3,请问多少种不同的竹筏安排方案?
一行一个整数n,0<n<1000.
一行一个整数,为铺设方案的数量模12345的结果。
Input
2
Output
3
\ 1 & n= 1\
\ 2 & n= 2\
d[i-1]+2\times d[i-2] \ &n>2
\end{cases}$
当宽度是二的时候,有两种排列方法
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n';
using namespace std;
const int MOD=12345;
int f(int n){
if(n==1) return 1;
if(n==2) return 3;
return f(n-1)+2*f(n-2);
}
signed main(){
int n;
cin>>n;
int d[n+1];
d[0]=0,d[1]=1,d[2]=3;
for(int i=3;i<=n;i++){
d[i]=(d[i-1]+2*d[i-2])%MOD;
}
cout<<d[n]<<endl;
return 0;
}
桂林为了欢迎广大游客,决定在桂林的各大街道上布置迎宾彩带。 目前有白色、蓝色和红色的彩带,并满足以下两个条件:
一行一个整数n,表示橱窗的宽度(或者说彩带数目)。
一行一个整数,表示装饰橱窗的彩带放置方案数。
Input
3
Output
4
\ 2 & n= 1\
\ 2 & n= 2\
d(i-1)+d(i-2) \ &n>2
\end{cases}$
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n';
using namespace std;
signed main(){
int n;
cin>>n;
int a[n+1]={0};
a[1]=2,a[2]=2;
for(int i=3;i<=n;i++){
a[i]=a[i-2]+a[i-1];
}
cout<<a[n]<<endl;
return 0;
}
桂林的景点很多,为了让更多的游客可以顺利游玩。在不影响游览品质的前提下,旅游公司 决定通过改变路线的方法分流游客。 方案是:每个旅行团都跳过其中的一个景点(但是不能跳过
第1行1个正整数n,表示城市个数。
接下来的n行,每行2个数x_i和y_i,表示城市i的坐标。
一行一个数,使得它从1号城市开始,跳过某一个城市,到达n号城市所经过的最小总距离。
Input
4
0 0
8 3
11 -1
10 0
Output
14
假设 A, B两点坐标分别为
从
int manhattandist(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
#include <bits/stdc++.h>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
int n, m, b, s, a[100005], x[100005], y[100005];
int manhattandist(int x1, int y1, int x2, int y2){
return abs(x1 - x2) + abs(y1 - y2);
}
int dist(int i, int j){
return manhattandist(x[i], y[i], x[j], y[j]);
}
signed main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
if (i > 1)
a[i] = dist(i, i - 1);
s += a[i];
}
m = s;
for (int i = 2; i <= n - 1; i++){
b = s - a[i] - a[i + 1] + dist(i - 1, i + 1);
m = min(m, b);
}
cout << m << endl;
return 0;
}
猴子吃桃子问题:猴子第一天摘下若干个桃子,当即吃了一半还不过瘾,又多吃了一个;第二天又将剩下的桃子吃掉一半又多吃了一个;以后每天早上都吃了前一天剩下的一半零一个。到了第十天想再吃时,见只剩下一个桃子,求第一天共摘了多少个桃子?
无
一个整数,第一天共有多少个桃子
#include <iostream>
using namespace std;
int peaches_2(int day) {
if (day == 10) {
return 1;
} else {
return (peaches_2(day + 1) + 1) * 2;
}
}
int peaches_1(int day) {
int total_peaches = 1;
for (int i = 10; i > 1 ; --i) {
total_peaches = (total_peaches + 1) * 2;
}
return total_peaches;
}
int main() {
int day = 1;
int total_peaches = peaches_1(day);
cout << total_peaches << endl;
return 0;
}
有1×n(n<=50)的一个长方形,用1×1、1×2和1×3的骨牌铺满方格,请问有多少种铺法? 例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格,共有四种铺法。如下图:
一个整数n(n<=50)
骨牌的铺法
Input
3
OutPut
4
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
signed main(){
int n=0;
cin>>n;
int dp[52];
dp[0]=0;
dp[1]=1;
dp[2]=2;
dp[3]=4;
for(int i=4;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
}
cout<<dp[n]<<endl;
return 0;
}
Pell数列
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。
n行,每行输出对应一个输入。输出应是一个非负整数。
Input
2
1
8
Output
1
408
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
int a[1000001]={0};
void solve(int n){
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++){
a[i]=(2*a[i-1]+a[i-2])%32767;
}
}
signed main() {
int T=0;
cin>>T;
while(T--){
int n=0;
cin>>n;
if(a[n]!=0)
cout<<a[n]<<endl;
else{
solve(n);
cout<<a[n]<<endl;
}
}
return 0;
}
请编程求出所有的n位数中,有多少个数中有偶数个数字3.结果模12345。(1<=n<=1000)
一行一个正整数n,0<n<1000.
一行一个正整数,表示n位数中有多少个数有偶数个3.
input
2
Output
73
#include<bits/stdc++.h>
#include<iostream>
#define int long long
#define endl '\n'
using namespace std;
signed main(){
int f[1001][2],n,i,x=9;
cin>>n;
f[1][1]=1;f[1][0]=9;
for(i=2;i<=n;i++) {
if(i==n) // i是最高位
x-=1;
f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;
f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;
}
cout<<f[n][0];
return 0;
}