孟习笔谈
10 算法-递推
发布时间:
一、递 推 基 础
1、什么是递推
递推算法是一种用 若干步可重复运算来描述复杂问题 的方法，递推法是一种重要的数 学方法，也是编程中解决问题的一个重要方法。
这种算法特点是： 一个问题的求解需一系列的计算，在已知条件和所求问题之间总存 在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系(即递推式),那么，从问题出发逐步推到已知条件。
无论顺推还是逆推，其 关键是要找到递推式。这种处理问题的方法能使复杂运算化为 若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系(即递推关系)。递推算法避开了求 通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。 一般说来，可以将递推算法看成是一种特殊的迭代算法。
二、递推问题训练
例1 【【入门】统计每个月兔子的总数
分析：
第 1 个 月 ：a 1
第 2 个 月 ：a 1
第 3 个 月 ：ab 2
第 4 个 月 ：abc 3
第 5 个 月 ：abcde 5
请问，数列的规律是什么?
规 律 ：a(n)=a(n-1)+a(n-2) (斐波拉契数列)
注 意 交 代 2 个 起 始 项 ( 第 1 项 和 第 2 项 )
代码：
js
#include<bits/stdc++.h>
using namespace std;
int getTotal(int n){
if(n>2){
return getTotal(n-1)+getTotal(n-2);
}else {
return 1;
}
}
int main(){
int n;
cin>>n;
cout<<getTotal(n);
return 0;
}
注意：递归存在的问题
由于递归是函数对于自己的调用，因此在 n 的值比较大时，存在太多的重复求解的过程， 而且这些重复求解的过程都必须等所有项计算完毕，才能汇总出总解；因此效率很低。
改进：使用数组和递推的方法来提高递归的效率
改进方案一：采用数组来记录每个月兔子的数量，这样的话，如果要知道 a[n-1]和 a[n-2]就 不需要再次求解了，而是直接从数组中获取。
| 1 | 1 | 2 | 3 | 5 |
|---|
js
#include <bits/stdc++.h>
using namespace std;
long long a[60],i,n;
int main() {
cin>>n;
a[0]=1;
a[1]=1;
//从第3个月开始求解
for(int i=2; i<n; i++) {
a[i]=a[i-1]+a[i - 2];
}
cout<<a[n-1]<<endl;
return 0;
}
3、课堂练习
1、数数小木块
分析：自上而下
1层 1
2层 3 比上一层多2
3层 6 比上一层多3
4成 10 比上一层多4
5层 15 比上一层多5
2、 【基础】数塔问题（选做）
3、 【基础】数塔的行走路径（选做）
4、 【提高】过河卒（选做）
5、 Pell 数 列（选做）
4、作业
1、 【基础】摘花生问题
2、【基础】摘花生问题(2)（选做）
3、【提高】蜜蜂路线（选做）
4、【入门】骨牌铺方格（选做）
5、【入门】小X 放骨牌（选做）
6、【入门】平面分割问题（选做）