迭代与递推
米奇温馨圣诞夜-
迭代与递推
1
）
迭
代法
也称
“
辗转法
”
，是一种不断用变量的
旧值递推出新值
< br>的
解决问题的方法。
迭代算法一般用于数值计算。迭代法
应该是我们早已
熟悉的算法策略，
程序设计语言课程中所学的累
加、累乘都是迭代算法
策略的基础应用。例如：斐波那契数列
例子：兔子繁殖问题
一对兔子从出生后第三个月开始
，每月生一对小兔子。小兔
子到第三个月又开始生下一代小兔子。
假若兔子只生不死，
一月份抱来
一对刚出生的小兔子，问一年
中每个月各有多少只兔子。
•
问题分析
因为一对兔子从出生后第三个月
开始每月生产一对小兔子，
则每月新下生的小兔子的对儿数显然由前两个月的小兔子的对
儿数决
定。则繁殖过程如下：
一月
二月
三月
四月
五月
六月
……
1
1 1+1=2
2+1=3
3+2=5
5+3=8
……
•
数学建模（斐波那契数列）
y1=y2=1
，
yn=yn-1+yn-2
，
< br>n=3
，
4
，
< br>5
，
……
2
）倒推法的概念
•
倒推法：是对某些特殊问题所采用的违反通常习惯的，从
后向前推解问题的方法。例如，在不知前提条件的情况下，由结果倒过
来推解它的前提条件，从而求解问题。又如，由于存储的要求，而必须
从后向前进行推
算。另外，在对一些问题进行分析或建立数学模型时，
从前向后分析问题感到比较棘手，
而采用倒推法，
则问题容易理解和解
决
。
例子：穿越沙漠问题
用一辆吉普车穿越
1000
公里的沙漠。吉普车的总装油量为<
/p>
500
加仑，耗油率为
1
加仑
/
公里。由于沙漠中没有油库，必须先用这辆车在
沙漠中建立临时油库。该吉普车以
最少的耗油量穿越沙漠，应在什么地方建油库，以及各
处的贮油量。
•
问题分析
贮油点问题要求要以最少的耗油
量穿越沙漠，
即到达终点时，
沙漠中的各临时油
库和车的装油量均为
0
。这样只能从终点开始向前倒着
推解贮油点和贮油量。
•
数学模型
根据耗油量最少目标的分析，下面从后向前分段讨论。
第一段长度为
500
公里且第一个加油点贮油为
500
加仑。
第二段中为了贮备油，吉普车在这段的行程必须有往返。
下面讨论怎样走效率高：
1
）首先不计方向这段应走奇数次（保证最后向前走）。
2
）
每次向前行进时吉普车是满载
。
3
）要能贮存够下一加油点的贮油
量，路上耗油又最少。
•
综上分析
从终点开始分别间隔
500
，
500/3
，
500/5
，
500/7
，
……
（公里）设立贮油
点，直到总距离超过
1000
公里。每个贮油点的油量为
500
，
1000
，
1500
，
……
。
•
终极解释：
1
）从终点推，到终点必须正好没油，且中途加油站
也耗光。所以距离终点
500
公里有一个
500
加仑
储油点
2
）第二个，要想把第一个储油点，储
500
加仑，最
少需要三次，且汽车需要满载油，则距离为<
/p>
500*2 - 3X=500
得距离
X=500/3
储油量：
500*2=1000
3
）第三个，距离计算公式：
500*3 -5x
=1000
-->x=500/7
储油量：
3*500=1500
二，分治与递归
1
）
分治法在每一层递归上都有三个步骤：
（
1<
/p>
）
划分：
把输入的问题实例划分为若干子
问题，
尽量使子问题的规模大致相同。
（
2<
/p>
）求解：若子问题规模较小而容易被解决则直接解，否则，当问题的规模大于
某个预定义的阀值时，求解步骤由个递归调用组成。
（
3<
/p>
）合并：将各个子问题的解合并为原问题的解。
分治和递归的关系
分
治与递归像一对孪生兄弟，
经常同时应用在算法设计之中。
因为
从分治法的算
法框架中可以看出，分治法设计出的算法一般是一个递归过程。
2
）二分治的基本思想
在算法设计中每次一个问题分
解成的子问题个数一般是固定的，每个子问题的
规模也是平均分配的。
< br>当每次都将问题分解为原问题规模的一半时，
称为二分治法。
二分法
是分治法较常用的分解策略，
数据结构课程中的折半
查找、
归并排序等算法都是采用此策略
实现的。
例题：二分治法求最大、最小值
[html]
view
plaincopy
1.
#include
2.
using
namespace std;
3.
void
FindMaxAndMin(int a[], int begin, int end, int*
pmax,int* pmin)
4.
{
5.
if(end-
begin
<
=1)
//
递归出口
6.
{
7.
if(a[begin]
<
= a[end])
8.
{
9.
*
pmax
=
a
[end];
10.
*
pmin
=
a
[begin];
11.
return;
12.
}
13.
else
14.
{
15.
*
pmin
=
a
[end];
16.
*
pmax
=
a
[begin];
17.
return;
18.
}
19.
}
20.
int min1, min2, max1, max2;
21.
int
mid
= (begin+end)/2;
22.
FindMaxAndMin(a, begin, mid, &max1, &min1);
23.
FindMaxAndMin(a,mid+1, end,&max2, &min2);
24.
*
pmin
=
min1
<
min2
? min1 : min2;
25.
*
pmax
=
max1
<
max2
? max2 : max1;
26.
}
27.
int main()
28.
{
29.
int a[] = {1,2,3,4,5,9,41,8,12,20,98};
30.
int max,min;
31.
FindMaxAndMin(a,0,10,&max,&min);
32.
cout
<<
， <
br>O
<
，
the min num
is:
<
;
33.
return 0;
34.
}
35.
例题：线性时间求数组，第
k
小元素
•
问题分析
这
个问题可以通过排序来解决，最好的排序算法的
复杂性是
O
（
n*log(n)
）
下面我们要利用分治法，
找到复杂性为
（
n
）
的算法。
但这个问题不能用简单的二分法分解成完全独立、
相
似的两个
子问题。
因为在选出分解后第一组的第
k
小的数据和第二组的第
k
小
的
数据，不能保证在这两个数据之一是原问题的解。
•
例如：
米奇温馨圣诞夜-
米奇温馨圣诞夜-