大家好，欢迎来到IT知识分享网。
目录
递推算法概述
- 递推/递归既可以理解成是一种算法思想，也可以理解成是一种算法的实现方式
- 分治算法策略主要通过递归实现，大规模问题分解成小规模问题；动态规划算法主要通过递推实现
- 递归和递推的核心其实都是递推式
- 递归：从上到下 从未知到已知解决问题
- 递推：从下到上 从已知到未知解决问题
（1）算法特点：
- 一个问题的求解需一系列的计算
- 在已知条件和所求问题之间总存在着某种相互联系的关系
- 找到前后过程之间的数量关系（即递推式），分为顺推和逆推。
- 无论顺推还是逆推，其关键是要找到递推式
（2）关键：
用递推算法解决问题时，关键是找到递推式以及边界条件（临界条件）
（3）顺推、逆推
（4）使用递推方法解决：菲波那契数列、汉诺塔移动次数、猴子吃桃、数字三角形（顺推法）、骨牌铺满方格、蜜蜂路线、吃糖果、昆虫繁殖、位数问题、分苹果、踩方格、爬楼梯（openjudge题目）
一、求菲波那契数列
(Fibonacci)数列的前40个数。这个数列有如下特点：第1、2两个数为1、1。从第3个数开始，该数是其前面两个数之和。即:
#include<iostream> using namespace std; int main() { int f[101],n; cin>>n; f[1]=1;f[2]=1; for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; for(int i=0;i<n;i++) { if(i%5==0)//5个数一行 cout<<endl; cout<<f[i]<<'\t'; } cout<<endl; return 0; }二、汉诺塔(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; }四、数字三角形（顺推法）
请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。
- 一步可沿左斜线向下或右斜线向下走；
- 三角形行数小于等于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]} 递推式
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
#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; }五、骨牌铺满方格
有 2*n 的一个长方形方格，用一个1*2 的骨牌铺满方格。
编写一个程序，试对给出的任意一个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] 递推式
#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; } 【代码实际与上一题骨牌铺满方格完全一致】七、蜜蜂路线
一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问：蜜蜂从蜂房m开始爬到蜂房n，m<n，有多少种爬行路线？
设f[i]表示蜜蜂爬到i位置的爬行路线数
例如蜜蜂爬到4只有可能从3来，或者从2来
故f[4]=f[3]+f[2]
即f[i]=f[i-1]+f[i-2] 递推式
f[m]=1,f[m+1]=1 临界值
【代码都是大同小异】
#include <iostream> using namespace std; int main(){ int m,n;//代表有几列 cin>>m>>n; int f[101]; f[m]=1;f[m+1]=1; for(int i=m+2;i<=n;i++) f[i]=f[i-1]+f[i-2]; cout<<f[n]<<endl; }八、昆虫繁殖【这题有点点难哦】
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。
每对成虫过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;
}
九、位数问题
在所有的n位数中，有多少个数中有偶数个数字3 ？ （说明，0是偶数）
f[i][0]表示前i位中有偶数个3的数目
前i-1位有偶数个3，第i位不能为3
前i-1为有奇数的3，第i位是3
故f[i][0]=f[i-1][0]*9+f[i-1][1]【乘以9是因为，第i位除了3以外的每一个数字】
f[i][1]表示前i位中有奇数个3的数目
同理，f[i][1]=f[i-1][1]*9+f[i-1][0]
f[1][1]=1;f[1][0]=9;//1位数中有偶数个3的有9个，有奇数个3的1个
#include <iostream> using namespace std; int main(){ int n,x=9;//n位数 cin>>n; int f[101][2]; f[1][1]=1;f[1][0]=9;//f[1][0]表示有偶数个3的数目 for(int i=2;i<=n;i++) { if(i==n)//i是最高位 x--;//最高位不能是0 f[i][0]=f[i-1][0]*x+f[i-1][1]; f[i][1]=f[i-1][1]*x+f[i-1][0]; } cout<<f[n][0]<<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; }十一、踩方格
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、只能向北、东、西三个方向走；
b、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
c、走过的格子立即塌陷无法再走第二次；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案
分析：
走到第i步的时候可能是从左边来的，也可能从右边来的，也可能从上面来的
用up[i], l[i]和 r[i]分别代表第 i 步是向上走,向左走和向右走的不同方案数
我们要求的结果便是：up[i]+ l[i]+r[i]
递推关系：
up[i]=up[i-1]+l[i-1]+r[i-1]
l[i]=up[i-1]+l[i-1]
r[i]=up[i-1]+r[i-1]
初始值
up[1]=1 l[1]=1 r[1]=1
十二、爬楼梯（openjudge题目)
小明爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。【和吃糖果一样】
大家一起加油 ！！！
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/123194.html
