date: 2024-06-10
title: 递推
status: DONE
author:
  - AllenYGY
tags:
  - Algorithm
  - Share
  - Recursion
created: 2024-06-10T14:23
updated: 2024-06-22T16:18
publish: True

递推

什么是递推?

递推是按照一定的规律来求序列中的每一项,一般是通过计算前面的一些项来得出序列中的指定项。
其思想是把一个复杂的庞大的计算过程转化为对简单过程的多次重复,该算法利用了计算机运算速度快和不知疲倦的机器特点。

采用数组实现递推算法的三要素

将问题用数组形式表达
求解递推关系,列出递推表达式
寻找边界值

递推算法实现方法

首先知道小规模的数列
求解递推关系,列出递推表达式

兔子的故事

🐰的故事

已知一对兔子，每个月可以生一对小兔子，小兔子出生后的第二个月会变成成年兔子，会继续生小兔子。
第一个月，我们有1对小兔子。
第二个月，我们有1对成年兔子的兔子。
第三个月，我们有1对成年兔子的兔子，有1对小兔子，共2对。
第四个月，我们有2对成年兔子的兔子，有1对小兔子，共3对。
第五个月，我们有3对成年兔子的兔子，有2对小兔子，共5对。
现在我们希望知道第n个月，一共有多少只兔子。

题解

假设：第个月的大兔为幼兔为,总数.

已知：一对成年兔每个月可以生一对小兔子

已知：下个月的成年兔是由上个月的成年兔和幼兔组成的

CODE

#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

Output

2
4
6

题解

第n年的牛的数量为：n-1年的数量和今年新出生的牛的数量
今年新出生的牛的数量为 n-3 年前牛的数量

CODE

#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

Output

题解

Success

表示走到第级台阶的走法

Why？

要上第级楼梯
可以从级楼梯一次走一步上去
可以从级楼梯一次性走两步上去
可以从级楼梯一次性走三步上去

CODE

#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种铺法.如图：

]表示铺满的长方形方格，一共有多少方案数

铺到最后要么剩或者
表示前已铺满，剩最后只能竖着放
为铺满网格的方案数
(如果前面的2*(n-2)的网格已经铺满, 那么最后的只能是横着放两块,否则会与重复).

CODE

#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

Output

题解

$$f(n)=\begin{cases}

\ 1 & n= 1\
\ 2 & n= 2\
d[i-1]+2\times d[i-2] \ &n>2
\end{cases}$d[i]$ 表示江面宽度为时铺设方案的数

Why

当宽度是二的时候，有两种排列方法

CODE

#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

Output

题解

$$f(n)=\begin{cases}

\ 2 & n= 1\
\ 2 & n= 2\
d(i-1)+d(i-2) \ &n>2
\end{cases}$d[i]$ 表示当橱窗宽度是时，彩带放置方案数

Why ?

假设一共有条彩带，当前条彩带排好后，则最后一条彩带
- 一定只能是红色或者只能是白色
对于第条彩带存在两种可能
蓝色或者不是蓝色
- 当为蓝色时第条彩带也必然是确定的
- 不为蓝色时第条彩带不能确定

CODE

#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;
}

最短距离

问题描述

桂林的景点很多，为了让更多的游客可以顺利游玩。在不影响游览品质的前提下，旅游公司决定通过改变路线的方法分流游客。方案是：每个旅行团都跳过其中的一个景点（但是不能跳过号和号景点），使得它从号景点开始，到达号景点所经过的总距离最小。假设每一个景点i都有一个坐标，从的景点到的景点的距离为：

输入格式

第1行1个正整数n，表示城市个数。

接下来的n行，每行2个数x_i和y_i,表示城市i的坐标。

输出格式

一行一个数，使得它从1号城市开始，跳过某一个城市，到达n号城市所经过的最小总距离。

样例

Input

Output

题解

先计算出总距离S (每个景点之间的曼哈顿距离总和)
逐个跳过景点维护最小距离

Success

初始化为
表示跳过景点的总距离
表示不跳过任何一个景点的总距离
表示从景点到景点的距离
表示两景点之间的曼哈顿距离

曼哈顿距离

假设 A, B两点坐标分别为，
从到的曼哈顿距离为:

int manhattandist(int x1, int y1, int x2, int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}

CODE

#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;
}

猴子吃桃子

题目描述

猴子吃桃子问题：猴子第一天摘下若干个桃子，当即吃了一半还不过瘾，又多吃了一个；第二天又将剩下的桃子吃掉一半又多吃了一个；以后每天早上都吃了前一天剩下的一半零一个。到了第十天想再吃时，见只剩下一个桃子，求第一天共摘了多少个桃子？

输入格式

无

输出格式

一个整数，第一天共有多少个桃子

CODE

#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

OutPut

CODE

#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 数列

题目描述

Pell数列的定义是这样的，，。给出一个正整数k，要求Pell数列的第项模上是多少。

输入格式

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

输出格式

n行，每行输出对应一个输入。输出应是一个非负整数。

样例

Input

2
1
8

Output

1
408

CODE

#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

Output

CODE

#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;
}