递推算法
递推算法能通过已知某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法“聪明”，它不会"一根筋"的寻找每一种可能方案。
（1）顺推法：从已知条件出发，逐步推算出要解决的方法。例如裴波那契数列就可以通过顺推法不断推算出新的数据。
（2）逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。
无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
一、斐波那契问题
数学里面的斐波那契数列便是一个使用递推算法的经典例子。13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题，其大意如下:如果一对两个月大的兔子以后每-一个月都可以生一对小兔子，而一对新生的兔子出生两个月后才可以生小兔子。也就是说，1月份出生，3月份才可产仔。那么假定一年内没有产生兔子死亡事件，那么1年后共有多少对兔子呢?
分析：我们先来分析一下兔子产仔问题。我们来逐月看一次每月的兔子对数:
第一个月: 1对兔子;
第二个月: 1对兔子;
第三个月: 2对兔子;
第四个月: 3对兔子;
第五个月: 5对兔子;
从上面可以看出，从第个3月开始，每个月的兔子总对数等于前两个
月兔子数的总和。相应的计算公式如下:
第n个月兔子总数F=Fn-1+Fn-2
这里，初始第一个月的兔子数为F1=1,第二个月的兔子数为F2=1.
二、汉诺塔(Tower of Hanoi)问题
移动规则：
每次只能移动一个圆盘；圆盘可以插在X、 Y和Z中的任何一个塔座上；任何时刻都不能将一个较大的圆盘压在较小的圆盘之上
假设移动n个盘子从A到C需要移动的次数为f(n)
f(0)=0
f(1)=1 临界条件
f(n)=f(n-1)+1+f(n-1)=2*f(n-1)+1 递推式【把n-1从A->B ,把第n个从A->C,把n-1从B->C】
#include<iostream>
using namespace std;
int main()
{
int f[101],n;
cin>>n;
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++)
f[i]=2*f[i-1]+1 ;
cout<<f[n]<<endl;
return 0;
}
三、猴子吃桃
猴子第一天采摘了一些桃子，第二天吃了第一天的一半多一个，第三天吃了第二天的一半多一个...直到第十天就剩下一个。问：猴子第一天摘了多少桃子？
f[n]代表第n天剩余的桃子的个数
f[n]=f[n-1]*1/2-1 -> f[n-1]=(f[n]+1)*2 递推式 、逆推
f[10]=1 临界条件
#include<iostream>
using namespace std;
int main()
{
int f[101];
f[10]=1;
for(int i=9;i>=1;i--)
f[i]=(f[i+1]+1)*2;
cout<<f[1]<<endl;
return 0;
}
上台阶
楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
n:4
共7种走法
#include<cstdio>
long long d[110]= {0};
int main()
{
d[1]=1;
d[2]=2;
d[3]=4;
for(int i=4; i<=100; i++)
d[i]=d[i-1]+d[i-2]+d[i-3];
int n;
cin>>n;
cout<<d[n]<<endl;
return 0;
}
四、数字三角形（顺推法）
请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
一步可沿左斜线向下或右斜线向下走；
三角形行数小于等于100；
三角形中的数字为0，1，…，99；
二维数组存储，格式如右图
f[x][y]表示从(1,1)到(x,y)的路径的最大权值和
f[1][1]=a[1][1] 临界条件
f[x][y]=max{f[x-1][y]，f[x-1][y-1]} 递推式
#include <iostream>
using namespace std;
int a[101][101]={0}; //注意此时二维数组的初值为0
int f[101][101],n;
int max(int a,int b){
if(a>b)
return a;
return b;
}
int main() {
cin >> n;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= i;j ++)
cin >> a[i][j];
f[1][1] = a[1][1];
//求出f[2][1],f[2][2]......f[5][5]
for(int i = 2;i <= n;i ++)
for(int j = 1;j <= i;j ++)
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
int ans =0;
//这个循环求f[5][1]......f[5][5]的大小
for(int i = 1;i <= n;i ++)
ans = max(ans,f[n][i]);
cout << ans << endl;
return 0;
}
五、骨牌铺满方格
有 2n 的一个长方形方格，用一个12 的骨牌铺满方格。
编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
算法分析：
（1）当n=1时，
只能是一种铺法，铺法总数有示为x1=1。
（2）当n=2时，
骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2；
当n=3时，如上图
当n=4时，如下图
算法分析：
推出一般规律：对一般的n，xn可以这样来考虑
若第一个骨牌是竖排列放置
剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；
若第一个骨牌是横排列放置
整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2
假设f(n)表示n列的铺发总数
F(1)=1
F(2)=2
F(n)=f(n-1)+f(n-2)
#include <iostream>
using namespace std;
int main(){
int n;//代表有几列
cin>>n;
int f[101];
f[1]=1;f[2]=2;
for(int i=3;i<=n;i++)
f[i]=f[i-1]+f[i-2];
cout<<f[n]<<endl;
}
六、吃糖果
名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。
妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。
分析：
每天只有两个选择，吃1块或者吃2块
f[n]: 表示吃完 n 块巧克力的方案数
n=1,1种方案 f[1]=1
n=2,2种方案 则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块, f[2]=2
.......
如果n= i，第一天要么吃掉1块，要么吃掉2块，所以剩余 i-1 块或者 i-2 块，因此，
f[i] = f[i - 1] + f[i - 2] 递推式
七、蜜蜂路线
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问：蜜蜂从蜂房m开始爬到蜂房n，m<n，有多少种爬行路线？
需要注意，斐波那契额数列是从1开始进的，现在是从m开始进，到n点。相当于走了 n-m 个点 f[n-m] ,本题涉及高精度算法
#include <cstdio>
using namespace std;
int n,m,len=1;
int f[1005][1005];
void plus(int x)
{
for(int i=1;i<=len;i++)
f[x][i]=f[x-1][i]+f[x-2][i];
for(int i=1;i<=len;i++)
if(f[x][i]>9)
{
f[x][i+1]+=f[x][i]/10;
f[x][i]%=10;
}
if(f[x][len+1]) len++;
}
int main ()
{
scanf("%d%d",&m,&n);
f[1][1]=1,f[2][1]=2;
for(int i=3;i<=n-m;i++) plus(i);
for(int i=len;i;i--) printf("%d",f[n-m][i]);
return 0;
}
八、昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。
每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。
假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月内不产卵(过X个月产卵).
问过Z个月以后，共有成虫多少对？1=<x<=20,1<=y<=20,x=<z<=50
本月成虫的数量=前2个月卵的数量+前1个月成虫的数量
本月卵的数量=前x月成虫的数量*y
设f[i]表示第 i 月昆虫成虫的数量，b[i]表示第 i 月的新虫卵的数目
b[i] = f[ i - x] * y; （成虫经过x月产卵 y对）
f[i] = f[ i - 1] + b[ i - 2]; （卵经过2个月长成成虫）
F[1]=1 b[1]=0
#include <iostream>
using namespace std;
int main(){
int x,y,z;
cin>>x>>y>>z;
int f[101],b[101];
//在x个月之内成虫都是，都不产卵，所以赋初值一定是用循环
for(int i=1;i<=x;i++){
f[i]=1;
b[i]=0;
}
for(int i=x+1;i<=z+1;i++)
//因为要统计到第z个月后，所以要for到z+1
{
b[i]=y*f[i-x];
f[i]=f[i-1]+b[i-2];
}
cout<<f[z+1]<<endl;
return 0;
}
九、分苹果
把 m 个同样的苹果放在 n 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
说明：5，1，1和1，5，1 是同一种分法。
【输入格式】一行，包含二个整数 m 和 n，以空格分开。1<=m，n<=10。
【输出格式】用一行输出相应的K。
设f(m,n) 为m个苹果，n个盘子的放法数目
当n>m：至少有n-m个盘子永远空着 即f(m,n) = f(m,m)
当n<=m：
有盘子空着，至少一个盘子空着 f(m,n) = f(m,n-1)
所有盘子都有苹果，多出m-n个苹果，拿走不影响放法的个数 f(m,n)=f(m-n,n)
故当n<=m时，f(m,n)=f(m,n-1)+f(m-n,n)
当没有苹果可放时，即m=0时，定义为１种放法；
边界条件： f[m,1]=1 f[i,0]=0 f[0][n]=1
#include <iostream>
using namespace std;
int main(){
int m,n,f[11][11];//第一维表示苹果个数，第二维表示盘子个数
cin>>m>>n;
//初始化如果盘子n的个数是0或1时初始化
for(int i=0;i<=m;i++)
{
f[i][0]=0;
f[i][1]=1;
}
//初始化如果苹果个数为0
for(int i=0;i<=n;i++)
f[0][i]=1;
for(int i=1;i<=m;i++)//i是苹果个数
{
for(int j=1;j<=n;j++)//j是盘子个数
{
if(i<j)
f[i][j]=f[i][i];
else
f[i][j]=f[i][j-1]+f[i-j][j];
}
}
cout<<f[m][n]<<endl;
}
十、台阶问题
题目描述
有$N$级的台阶，你一开始在底部，每次可以向上迈最多$K$级台阶（最少$1$级），问到达第$N$级台阶有多少种不同方式。
输入格式
两个正整数N，K。
输出格式
一个正整数，为不同方式数，由于答案可能很大，你需要输出$ans \bmod 100003$后的结果。
样例 #1
样例输入 #1
5 2
样例输出 #1
8
提示
对于$20%$的数据,有$N ≤ 10, K ≤ 3$;
对于$40%$的数据，有$N ≤ 1000$;
对于$100%$的数据，有$N ≤ 100000,K ≤ 100$。
#include<iostream>
using namespace std;
int main()
{
int a[1000001]={1},i,j,n,k;
cin>>n>>k;
for(i=1;i<=n;i++)
for(j=1;j<=k&&(i-j)>=0;j++)
{
a[i]=(a[i]+a[i-j])%100003;
}
cout<<a[n]<<endl;
return 0;
}
十一、数的计算
题目描述
给出自然数 $n$，要求按如下方式构造数列：
- 只有一个数字 $n$ 的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个自然数，但是这个自然数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你求出，一共有多少个合法的数列。两个合法数列 $a, b$ 不同当且仅当两数列长度不同或存在一个正整数 $i \leq |a|$，使得 $a_i \neq b_i$。
输入格式
输入只有一行一个整数，表示 $n$。
输出格式
输出一行一个整数，表示合法的数列个数。
样例 #1
样例输入 #1
6
样例输出 #1
6
提示
样例 1 解释
满足条件的数列为：
- $6$
- $6, 1$
- $6, 2$
- $6, 3$
- $6, 2, 1$
- $6, 3, 1$
数据规模与约定
对于全部的测试点，保证 $1 \leq n \leq 10^3$。
#include<bits/stdc++.h>//万能头文件
using namespace std;
int n;
int f[1001];//存每一位数的种类
int main(){
cin>>n;
for(int i=1;i<=n;i++){ //1-n的递推
for(int j=1;j<=i/2;j++){
f[i]+=f[j]; //每一位叠加，递推走起
}
f[i]++; //加上本身
}
cout<<f[n];//输出n的种类
return 0;
}
十二、旅行
题目描述
你要进行一个行程为7000KM的旅行，现在沿途有些汽车旅馆，为了安全起见，每天晚上都不开车，住在汽车旅馆，你手里现在已经有一个旅馆列表，用离起点的距离来标识，如下：
0， 990， 1010， 1970， 2030， 2940， 3060
3930， 4060， 4970， 5030， 5990， 6010， 7000
但在出发之前可能还要增加一些旅馆。
现在旅行社为了节约成本，要求每天至少行驶A公里，国家旅行社为了安全起见，要求每天最多只能行驶B公里。
你想知道一共有多少种旅行方案。
输入格式
第一行输入A，第二行输入B，第三行输入N（0≤N≤20），表示在出发之前又新增N个汽车旅馆；接下来N行，每行一个整数m，表示旅馆离起点的距离（0<m<7000）。注意：没有任意两个旅馆在同一位置。
输出格式
输出一共有多少种旅行方案。
样例 #1
样例输入 #1
500
1500
0
样例输出 #1
64
#include<bits/stdc++.h>
using namespace std;
int a,b,n,ans[40],r[40]={0,990,1010,1970,2030,2940,3060,3930,4060,4970,5030,5990,6010,7000};
//旅馆初始化
int main(){
scanf("%d %d %d",&a,&b,&n);
for (int i=14;i<14+n;i++) cin>>r[i];//输入
sort(r,r+14+n);//排序
ans[0]=1; //起始点默认一套方案
for (int i=1;i<14+n;i++){//枚举所有点
for (int j=0;j<i;j++){//枚举这个点之前的点
if (r[i]-r[j]>=a&&r[i]-r[j]<=b){//如果这两个点之间的距离符合要求
ans[i]+=ans[j];//这个点可以获得前面那个点的所有可能
}
}
}
cout<<ans[13+n]<<endl;//输出到终点时的所有可能
return 0;
}
十三、 踩方格
题目描述
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
输入
允许在方格上行走的步数n(n≤20)。
输出
计算出的方案数量。
样例
输入数据 1
2
输出数据 1
7
其中f[i]表示的是走在方格上走i步的方法数；那么我们要怎么求f[n]呢，题目要求只能向北、东、西三个方向走（不能向南走，感觉这才是题目的关键）并且走过的格子立即塌陷无法再走第二次
解释：向北走后，格子塌陷，仍有三个方向选择；向东西方向走后，格子坍塌，只有两种选择（无法回头走）
第n-1步向北走的方法数（记为North[n-1]），那么North[n-1]其实就是在走了n-2步的情况下再向北走一步的的情况数，
所以North[n-1]=f[n-2]，
有了North[n-1]，那么第n-1步向东或西走的方法数也就有了（因为这两种情况加起来就是f[n-1]），既f[n-1]-f[n-2]；
将这些数带入上图中得f[n]=f[n-2]* 3+(f[n-1]-f[n-2])* 2，化简得f[n]=f[n-1]*2+f[n-2]
十四、 数列
题目描述
用以下方式构造数列 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。 给出一个正整数a，要求数列中第a个数对1000取模的结果是多少。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，为数列中第a个数对1000取模得到的结果。
样例
输入复制
4
5
2
19
1
输出复制
5
1
181
1
#include<iostream>
using namespace std;
#define SIZEN 1000000
int arr[SIZEN+9];//全局变量,默认初始化
int main() {
int n,x,i;
arr[1]=1;//第1项
arr[2]=1;//第2项
for(int i=3; i<=SIZEN; i++)
arr[i]=(arr[i-1]+arr[i-2])%1000;//取模
cin>>n;
for(int i=1; i<=n; i++) {
cin>>x;
cout<<arr[x]<<endl;
}
return 0;
}
十五、装信问题
问题 ：
某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封，共有多少种不同情况？
对n封信以及n个信封各自按照从1到 n 进行编号，当 n 个编号的信放在 n 个编号位置的信封时，信的编号与信封位置编号 各不对应 的方法数用 f[n] 表示，那么 f[n - 1] 就表示 n - 1个编号的信放在 n - 1个编号位置的信封，各不对应的方法数，其他类推。
第一步，把第n封信放在一个信封，比如第k个信封 (k ≠ n) ，一共有 n - 1种方法。
第二步，放编号为 k 的信，这时有两种情况：
(1) 把它放到第 n 个信封，那么，对于剩下的 n - 2 封信，需要放到剩余的 n - 2个信封且各不对应，就有 f[n - 2]种方法。
(2) 不把它放到位置 n，这时，对于这 n - 1 封信，放到剩余的 n - 1个信封且各不对应（此时假设第k封信与位置n为对应关系），有 f[n - 1]种方法。
由于(1)与(2)是同一步骤的两种不同情况，所以第二步放法总数即为(1)与(2)这同一步骤的两种情况放法之和，即为 f[n - 2] + f[n - 1]。
归纳：
由以上分析可知，由于整个过程是由上述第一步、第二步两个步骤实现，因此 n 封信放到 n 个信封全部放错的方法就是上述第一步与第二步方法之积，即
｛ 递推关系式 f[n] = (n - 1) * ( f[n - 1] + f[n - 2] ) (n > 2)
{ 递推边界 f[1] = 0, f[2] = 1
#include <stdio.h>
#define N 50
int main()
{
int i, n;
long long int f[N + 1];
f[1] = 0;
f[2] = 1;
scanf("%d", &n);
for(i = 3; i < n; i++)
{
f[i] = (n - 1) * (f[i - 1] + f[i - 2]);
}
printf("%lld\n", f[n]);
return 0;
}
评论区