为了设计出解决问题的好算法,除了要掌握常用的数据结构工
具外,还需要掌握算法设计方法,算法设计与分析课程主要讨论分治
法、回溯法、分支限界法、贪心法和动态规划,称为五大算法策略。在
学习这些算法策略之前必须具有一定的算法设计基础,本章讨论穷
举法、归纳法、迭代法和递归法等基本算法设计方法及其递推式的计
算,学习要点和学习目标如下:
(1)掌握穷举法的原理和算法框架。
(2)掌握归纳法的原理和从求解问题找出递推关系的方法。
(3)掌握迭代法的原理和实现迭代算法的方法。
(4)掌握递归法的原理和实现递归算法的方法。
(5)掌握递推式的各种计算方法。
(6)综合运用穷举法、归纳法、迭代法和递归法解决一些复杂的
实际问题。
3.1穷举法
3.1.1穷举法概述
1.什么是穷举法
穷举法又称枚举法或者列举法,是一种简单而直接地解决问题的方法。其基本思想是
先确定有哪些穷举对象和穷举对象的顺序,按穷举对象的顺序逐一列举每个穷举对象的所
有情况,再根据问题提出的约束条件检验哪些是问题的解,哪些应予排除。
在用穷举法解题时,针对穷举对象的数据类型而言,常用的列举方法如下。
①顺序列举:是指答案范围内的各种情况很容易与自然数对应甚至就是自然数,可以
按自然数的变化顺序去列举。
②排列列举:有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排
列为排列列举。
③组合列举:当答案的数据形式为一些元素的组合时,往往需要用组合列举。组合是
无序的。
穷举法的作用如下:
①理论上讲穷举法可以解决可计算领域中的各种问题,尤其是处在计算机的计算速度
非常快的今天,穷举法的应用领域是非常广阔的。
②在实际应用中,通常要解决的问题规模不大,用穷举法设计的算法的运算速度是可
以接受的,此时设计一个更高效率的算法不值得。
③穷举法算法一般逻辑清晰,编写的程序简洁明了。
④穷举法算法一般不需要特别证明算法的正确性。
⑤穷举法可作为某类问题时间性能的底限,用来衡量同样问题的更高效率的算法。
穷举法的主要缺点是设计的大多数算法的效率都不高,主要适合规模比较小的问题的
求解。为此在采用穷举法求解时应根据问题的具体情况分析归纳,寻找简化规律,精简穷举
循环,优化穷举策略。
2.穷举法算法框架
穷举法算法一般使用循环语句和选择语句实现,其中循环语句用于枚举穷举对象所有
可能的情况,而选择语句判定当前的条件是否为所求的解。其基本流程如下:
①根据问题的具体情况确定穷举变量(简单变量或数组) 。
②根据确定的范围设置穷举循环。
③根据问题的具体要求确定解满足的约束条件。
④设计穷举法程序,并执行和调试,对执行结果进行分析与讨论。
假设某个问题的穷举变量是
x
和y,穷举顺序是先
x
后y,均为顺序列举,它们的取值
范围分别是x∈(x1,xn
y∈(ym
约束条件为p(xi,对应穷举法
x2,…,),y2,…,), yj
),
算法的基本框架如下:
y1,
70
71
void Exhaustive(x,n,y,m) { //穷举法框架
for(int i=1;i<=n;i++) { //枚举x 的所有可能的值
for(int j=1;j<=m;j++) { // 枚 举 y 的所有可能的值
…
if(p(x[i],y[j]))
输出一个解;
…
}
}
}
从中看出,x 和y 所有可能的搜索范围是笛卡儿积,即([x1,y1],[x1,y2],…,[x1,ym ],…,
[xn ,y1],[xn,y2],…,[xn,ym ]),这样的搜索范围可以用一棵树表示,称为解空间树,它包含
求解问题的所有解,求解过程就是在整个解空间树中搜索满足约束条件p(xi,yj)的解。
【例3-1】 鸡兔同笼问题。现有一个笼子,里面有鸡和兔子若干只,数一数,共有a 个
头、b 条腿。设计一个算法求鸡和兔子各有多少只。
解:由于有鸡和兔两种动物,每只鸡有2条腿,每只兔有4条腿,设置两个循环变量,x
表示鸡的只数,y 表示兔的只数,那么穷举对象就是x 和y,假设穷举对象的顺序是先x 后
y(在本问题中也可以先y 后x)。
图3.1 a=3,b=8的解空间树
显然,x 和y 的取值范围都是0~a,约束条件p(x,y)=(x+y==b)&& (2x+4y=b)。
以a=3,b=8为例,对应的解空间树如图3.1所示,根结点是分支对应x 的各种取值,第二
层结点的分支为y 的各种取值,其中“×”结点是不满足约束条件的结点,带阴影的结点是
满足约束条件的结点,所以结果是x=2/y=1。对应的算法如下:
void solve1(int a,int b) {
for(int x=0;x<=a;x++) {
for(int y=0;y<=a;y++) {
if(x+y==a && 2*x+4*y==b)
System.out.printf("x=%d,y=%d\n",x,y);
}
}
}
扫一扫
视频讲解
72
从图3.1中看到,解空间树中共21个结点,显然结点个数越多时间性能越差,可以稍做
优化,鸡的只数最多为min(a,b/2),兔的只数最多为min(a,b/4),仍以a=3,b=8为例,x
的取值范围是0~3,y 的取值范围是0~2。对应的解空间树如图3.2所示,共17个结点。
图3.2 a=3,b=8的优化解空间树
对应的优化算法如下:
void solve2(int a,int b) {
for(int x=0;x<=Math.min(a,b/2);x++) {
for(int y=0;y<=Math.min(a,b/4);y++) {
if(x+y==a && 2*x+4*y==b)
System.out.printf("x=%d,y=%d\n",x,y);
}
}
}
所以尽管穷举法算法通常性能较差,但可以以它为基础进行优化继而得到高性能的算
法,优化的关键是能够找出求解问题的优化点,不同的问题优化点是不相同的,这就需要读
者通过大量实训掌握一些基本算法设计技巧。3.1.2节和3.1.3节通过两个应用讨论穷举法
算法设计方法以及穷举法算法的优化过程。
3.1.2 最大连续子序列和
1.问题描述
给定一个含n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。例如,序列
(-2,11,-4,13,-5,-2)的最大子序列和为20,序列(-6,2,4,-7,5,3,2,-1,6,-9,
10,-2)的最大子序列和为16。规定一个序列的最大连续子序列和至少是0,如果小于0,
其结果为0。
2.问题求解1
对于含有n 个整数的序列a[0..n-1],其中任何连续子序列为a[i..j](i≤j,0≤i≤
n-1,i≤j≤n-1),求出它的所有元素之和cursum,并通过比较将最大值存放在maxsum
中,最后返回maxsum。这种解法是通过穷举所有连续子序列(一个连续子序列由起始下标
扫一扫
视频讲解
73
i 和终止下标j 确定)来得到结果,是典型的穷举法思想。
例如,对于a[0..5]={-2,11,-4,13,-5,-2},求出的a[i..j](0≤i≤j≤5)的所有
元素之和如图3.3所示(行号为i,列号为j),其过程如下:
图3.3 所有a[i..j]子序列(0≤i≤j≤5)的元素和
(1)i=0,依次求出j=0,1,2,3,4,5的子序列和分别为-2,9,5,18,13,11。
(2)i=1,依次求出j=1,2,3,4,5的子序列和分别为11,7,20,15,13。
(3)i=2,依次求出j=2,3,4,5的子序列和分别为-4,9,4,2。
(4)i=3,依次求出j=3,4,5的子序列和分别为13,8,6。
(5)i=4,依次求出j=4,5的子序列和分别为-5,-7。
(6)i=5,求出j=5的子序列和为-2。
其中20是最大值,即最大连续子序列和为20。
对应的算法如下:
int maxSubSum1(int a[]) { //解法1
int n=a.length;
int maxsum=0,cursum;
for(int i=0;i<n;i++){ //两重循环穷举所有的连续子序列
for(int j=i;j<n;j++) {
cursum=0;
for(int k=i;k<=j;k++)
cursum+=a[k];
maxsum=Math.max(maxsum,cursum); //通过比较求最大值maxsum
}
}
return maxsum;
}
【算法分析】 maxSubSum1(a,n)算法中用了三重循环,所以有:
T(n)=Σn-1
i=0Σn-1
j=iΣj
k=i1=Σn-1
i=0Σn-1
j=i(j-i+1)=12
Σn-1
i=0(n -i)(n -i+1)=O(n3)
74
3.问题求解2
采用前缀和方法,用Sum(i)表示子序列a[0.. i-1]的元素和,即a 中前i 个元素的和,
显然有如下递推关系:
Sum(0)=0
Sum(i)=Sum(i-1)+a[i-1] 当i >0时
假设j≥i,则有:
Sum[i]=a[0]+a[1]+ …a[i-1]
Sum[j]=a[0]+a[1]+ …a[i-1]+a[i]+ …a[j-1]
两式相减得到Sum[j]-Sum[i]=a[i]+…a[j-1],这样i 从0到n-1、j-1从i
到n-1(即j 从i+1到n)循环可以求出所有连续子序列a[i..j]之和,通过比较求出最大
值maxsum 即可。对应的算法如下:
static int maxSubSum2(int a[]) { //解法2
int n=a.length;
int Sum[]=new int[n+1];
Sum[0]=0;
for(int i=1;i<=n;i++)
Sum[i]=Sum[i-1]+a[i-1];
int maxsum=0,cursum;
for(int i=0;i<n;i++) {
for(int j=i+1;j<=n;j++) {
cursum=Sum[j]-Sum[i];
maxsum=Math.max(maxsum,cursum); //通过比较求最大值maxsum
}
}
return maxsum;
}
【算法分析】 maxSubSum2(a,n)算法中主要是两重循环,所以有:
T(n)=Σn-1
i=0 Σn
j=i+11=Σn-1
i=0(n -i)=n(n +1)
2 =O(n2)
4.问题求解3
对前面的解法1进行优化。当i 取某个起始下标时,依次求j=i,i+1,…,n-1对应
的子序列和,实际上这些子序列是相关的。用Sum(a[i..j])表示子序列a[i..j]的元素和
(即表示以a[i]为起始元素的前缀和),显然有如下递推关系:
Sum(a[i..j])=0 当j <i 时
Sum(a[i..j])=Sum(a[i..j-1])+a[j] 当j ≥i 时
这样在连续求a[i..j]子序列和(j=i,i+1,…,n-1)时没有必要使用循环变量为k 的
第3重循环,优化后的算法如下:
75
int maxSubSum3(int a[]) { //解法3
int n=a.length;
int maxsum=0,cursum;
for(int i=0;i<n;i++) {
cursum=0;
for(int j=i;j<n;j++) {
cursum+=a[j];
maxsum=Math.max(maxsum,cursum); //通过比较求最大值maxsum
}
}
return maxsum;
}
【算法分析】 maxSubSum3(a,n)算法中只有两重循环,所以有:
T(n)=Σn-1
i=0Σn-1
j=i1=Σn-1
i=0(n -i)=n(n +1)
2 =O(n2)
5.问题求解4
对前面的解法2继续优化。将maxsum和cursum初始化为0,用i 遍历a,置cursum+=
a[i],也就是说cursum 累计到a[i]时的元素和,分为两种情况:
① 若cursum≥maxsum,说明cursum 是一个更大的连续子序列和,将其存放在
maxsum 中,即置maxsum=cursum。
② 若cursum<0,说明cursum 不可能是一个更大的连续子序列和,从下一个i 开始继
续遍历,所以置cursum=0。
在上述过程中先置cursum+=a[i],后判断cursum 的两种情况。a 遍历完后返回
maxsum 即可。对应的算法如下:
int maxSubSum4(int a[]) { //解法4
int n=a.length;
int maxsum=0,cursum=0;
for(int i=0;i<n;i++) {
cursum+=a[i];
if(cursum>=maxsum) / /通 过 比 较 求 最大值maxsum
maxsum=cursum;
if(cursum<0) // 若 c ur su m <0 ,最 大连续子序列从下一个位置开始
cursum=0;
}
return Math.max(maxsum,0);
}
【算法分析】 maxSubSum4(a,n)算法中只有一重循环,所以时间复杂度为O(n)。
从中看出,尽管仍采用穷举法思路,但可以通过各种优化手段降低算法的时间复杂度。
76
解法2的优化点是采用前缀和数组,解法3的优化点是找出a[i..j-1]和a[i..j]子序列的
相关性,解法4的优化点是进一步判断cursum 的两种情况。
思考题:对于给定的整数序列a,不仅要求出其中最大连续子序列的和,还需要求出这
个具有最大连续子序列和的子序列(给出其起始和终止下标),如果有多个具有最大连续子
序列和的子序列,求其中任意一个子序列。
3.1.3 实战———最大子序列和(LeetCode53★)
1.问题描述
给定一个含n(1≤n≤105)个整数的数组nums,设计一个算法找到一个具有最大和的
连续子数组(子数组最少包含一个元素),返回其最大和。例如,nums={-2,1,-3,4,-1,
2,1,-5,4},答案为6,对应的连续子数组是{4,-1,2,1}。要求设计如下方法:
public int maxSubArray(int[]nums) { }
2.问题求解
本题是求nums的最大连续子序列和,但该序列至少包含一个元素,也就是说最大连续
子序列和可能为负数,因此不能简单采用3.1.2节中解法4的优化点,需要做两点修改:
(1)将表示结果的maxsum 初始化为nums[0]而不是0。
(2)在求当前以nums[i]结尾的最大连续子序列和cursum 时分为两个部分,一是
cursum+nums[i],另外一部分是只有nums[i](即无论nums[i]是否小于0,它都有可能
构成一个仅含一个元素的最大连续子序列),然后在这样的两个部分中取最大值得到
cursum,即cursum=max(cursum+nums[i],nums[i])。
在每次得到一个连续子序列和时通过比较将最大值存放到maxsum 中。对应的程序
如下:
class Solution {
public int maxSubArray(int[]nums) {
int n=nums.length;
if(n==1) return nums[0];
int maxsum=nums[0],cursum=0;
for(int i=0;i<n;i++) {
cursum=Math.max(cursum+nums[i],nums[i]);
maxsum=Math.max(maxsum,cursum);
}
return maxsum;
}
}
上述程序提交时通过,运行时间为1ms,内存消耗为48.7MB。
扫一扫
视频讲解
3.归法
2
纳
3.2.1
归纳法概述
1.
什么是数学归纳法
谈到归纳法很容易想到数学归纳法,数学归纳法是一种数学证明方法,典型地用于确定
一个表达式在所有自然数范围内是成立的,分为第一数学归纳法和第二数学归纳法两种。
(1)第一数学归纳法的原理:若{P(1),P(2),P(3),P(4),…} 是命题序列且满足以下
两个性质,则所有命题均为真。
①P(1)为真。
②任何命题均可以从它的前一个命题推导得出
n
。
(
例如,采用第一数学归纳法证明1+2+…+n=n+1)/2成立的过程如下
:
当n=1时,左式=1,右式=(1×2)/2=1,左、右两式相等,等式成立
。
假设当n=k-有1+2+…+(1)k(1)/2
。
1时等式成立, k-=k
当n=
k
时, 1+2+…+(1)+k=k-k(等式成立。
左式=k-k(1)/2+k=k+1)/2,
即证
(
。
2)第二数学归纳法的原理:若{P(1),P(2),P(3),P(4),…} 是满足以下两个性质的
命题序列,则对于其他自然数,该命题序列均为真。
①P(1)为真。
②任何命题均可以从它的前面所有命题推导得出
。
用数学归纳法进行证明主要是两个步骤
:
①证明当取第一个值时命题成立。
②假设当前命题成立,证明后续命题也成立。
数学归纳法的独到之处便是运用有限个步骤就能证明无限多个对象,而实现这一目的
的工具就是递推思想。第①步是证明归纳基础成立,归纳基础成为后面递推的出发点,没有
它递推成了无源之水;第②步是证明归纳递推成立,借助该递推关系,命题成立的范围就能
从开始向后面一个数一个数地无限传递到以后的每一个正整数,从而完成证明,因此递推是
实现从有限到无限飞跃的关键。
【例3-2】给定一棵非空二叉树,采用数学归纳法证明如果其中有
n
个叶子结点,则双
分支结点个数恰好为n-即P(1。
1, n)=n
证明:当n=1时,这样的二叉树恰好只有一个结点,该结点既是根结点又是叶子结点,
没有分支结点,则P(1)=0成立。
k-k--1=k假设叶子结点个数为k-1时成立,即P(1)=(1)2。由二叉树的结构
可知,想要在当前的二叉树中增加一个叶子结点,对其中某种类型的结点的操作如下。
①双分支结点:无法增加孩子结点,不能达到目的。
②单分支结点:可以增加一个孩子结点(为叶子结点), 此时该单分支结点变为双分支
结点,也就是说叶子结点和双分支结点均增加一个, k)k-=2+1
这样P(=P(1)+1k-=
77
k-1,结论成立。
③叶子结点:增加一个孩子结点,总的叶子结点个数没有增加,不能达到目的。
④叶子结点:增加两个孩子结点(均为叶子结点), 此时该叶子结点变为双分支结点,
也就是说叶子结点和双分支结点均增加一个,这样P(k)=P(k-1)+1=k-2+1=k-1,
结论成立。
凡是能够达到目的的操作都会使结论成立,根据第一数学归纳法原理,问题即证。
2.什么是归纳法
从广义上讲,归纳法是人们在认识事物的过程中所使用的一种思维方法,通过列举少量
的特殊情况,经过分析和归纳推理寻找出基本规律。归纳法比枚举法更能反映问题的本质,
但是从一个实际问题中总结归纳出基本规律并不是一件容易的事情,而且归纳过程通常也
没有一定的规则可供遵循。归纳法包含不完全归纳法和完全归纳法,不完全归纳法是根据
事物的部分特殊事例得出的一般结论的推理方法,即从特殊出发,通过实验、观察、分析、综
合和抽象概括出一般性结论的一种重要方法。完全归纳法是根据事物的所有特殊事例得出
的一般结论的推理方法。
在算法设计中归纳法常用于建立数学模型,通过归纳推理得到求解问题的递推关系,也
就是采用递推关系表达寻找出的基本规律,从而将复杂的运算化解为若干重复的简单运算,
以充分发挥计算机擅长重复处理的特点。在应用归纳法时一般用n表示问题规模(n为自
然数), 并且具有这样的递推性质———能从已求得的问题规模为1~n-1或者n/2等的一
系列解构造出问题规模为n的解,前者均称为“小问题”,后者称为“大问题”,而大、小问题
的解法相似,只是问题规模不同。利用归纳法产生递推关系的基本流程如下:
①按推导问题的方向研究最初、最原始的若干问题。
②按推导问题的方向寻求问题间的转换规律,即递推关系,使问题逐步转化成较低层
级或简单的且能解决的问题或者已解决的问题。
递推算法根据推导问题的方向分为顺推法和逆推法两种。所谓顺推法是从已知条件出
发逐步推算出要解决问题的结果,如图3.4(a)所示。所谓逆推法是从已知问题的结果出发
逐步推算出问题的开始条件,如图3.4(b)所示。
图3.4顺推法和逆推法
前面讨论的数学归纳法和归纳法有什么关系呢? 实质上数学归纳法与归纳法没有逻辑
联系,按著名数学家波利亚的说法是数学归纳法这个名字是随便起的。数学归纳法虽不是
归纳法,但它与归纳法有着一定程度的关联,在结论的发现过程中,往往先对大量个别事实
进行观察,通过不完全归纳法归纳形成一般性的结论,最终利用数学归纳法对结论的正确性
予以证明。3.2节~4节通过几个示例讨论归纳法在算法设计中的应用。
2.3.
2.
78
79
3.2.2 直接插入排序
1.问题描述
有一个整数序列R[0..n-1],采用直接插入排序实现R 的递增有序排序。直接插入排
序的过程是,i 从1到n-1循环,每次循环时将R[i]有序插入R[0.. i-1]中。
2.问题求解
采用不完全归纳法产生直接插入排序的递推关系。例如R=(2,5,4,1,3),这里n=5,
用[]表示有序区,各趟的排序结果如下:
初始:([2],5,4,1,3)
i=1:([2,5],4,1,3)
i=2:([2,4,5],1,3)
i=3:([1,2,4,5],3)
i=4:([1,2,3,4,5])
设f(R,i)用于实现R[0.. i](共i+1个元素)的递增排序,它是大问题;f(R,i-1)实
现R[0.. i-1](共i 个元素)的排序,它是小问题。对应的递推关系如下:
f(R,i)≡ 不做任何事情当i=1时
f(R,i)≡f(R,i-1);将R[i]有序插入R[0.. i-1]中; 其他
显然f(R,n-1)用于实现R[0..n-1]的递增排序。这样采用不完全归纳法得到的结
论(直接插入排序的递推关系)是否正确呢? 采用数学归纳法证明如下:
① 证明归纳基础成立。当n=1时直接返回,由于此时R 中只有一个元素,它是递增
有序的,所以结论成立。
② 证明归纳递推成立。假设n=k 时成立,也就是说f(R,k-1)用于实现R[0..k-1]
的递增排序。当n=k+1时对应f(R,k),先调用f(R,k-1)将R [0..k-1]排序,再将
R[k]有序插入R[0..k-1]中,这样R[0..k]变成递增有序序列了,所以f(R,k)实现R[0..k]
的递增排序,结论成立。
根据第一数学归纳法的原理,问题即证。按照上述直接插入排序的递推关系得到对应
的算法如下:
void Insert(int R[],int i) { //将R[i]有序插入R[0..i-1]中
int tmp=R[i];
int j=i-1;
do{ //找R[i]的插入位置
R[j+1]=R[j]; //将关键字大于R[i]的元素后移
j--;
} while(j>=0 && R[j]>tmp); / /直 到R[j]<=tmp 为止
R[j+1]=tmp; // 在 j +1 处插入R[i]
}
void InsertSort1(int R[]) { // 迭 代算法: 直接插入排序
int n=R.length;
80
for(int i=1;i<n;i++) {
if(R[i]<R[i-1]) //反序时
Insert(R,i);
}
}
在实际中有一些采用不完全归纳法得到的结论明显是正确的,或者已经被人们证明是
正确的,可以在算法设计中直接使用这些结论。
3.2.3 实战———不同路径(LeetCode62★★)
1.问题描述
一个机器人位于一个m ×n(1≤m ,n≤100)网格的左上角(起始点标记为“Start”)。机
器人每次只能向下或者向右移动一步。设计一个算法求机器人到达网格的右下角(标记为
“Finish”)总共有多少条不同的路径。例如,m =3,n=3,对应的网格如图3.5所示,答案为
6。要求设计如下方法:
public int uniquePaths(int m, int n) {}
2.问题求解
在从左上角到右下角的任意路径中,一定是向下走m -1步、向右走n-1步,不妨置
x=m -1,y=n-1,路径长度为x+y。例如对于图3.5,这里x=2,y=2,所有路径长度为
4,6条不同的路径如下:
图3.5 3×3的网格
① 右右下下
② 右下右下
③ 右下下右
④ 下右右下
⑤ 下右下右
⑥ 下下右右
归纳起来,不同路径条数等于从x+y 个选择中挑选x 个“下”或者y 个“右”的组合数,
即Cxx+y 或者Cyx+y (实际上从数学上推导有Cxx+y =Cyx+y ),为了方便,假设x ≤y,结果
取Cxx+y 。
Cxx+y = (x +y)!
x!y! = (x +y)(x +y -1)…(y -1)y!
x!y!
= (x +y)× … × (y -1)
x × (x -1)× … ×2×1
上式中分子、分母均为x 个连乘,可以进一步转换为:
x +y
x ×x +y -1 x -1 × … ×y -1
1
由于除法的结果是实数,而不同的路径数一定是整数,所以最后需要将计算的结果向上
取整得到整数答案。对应的程序如下:
扫一扫
视频讲解
81
class Solution {
public int uniquePaths(int m, int n) { //求解算法
return comp(m-1,n-1);
}
int comp(int x,int y) {
int a=x+y,b=Math.min(x,y);
double ans=1.0;
while(b>0)
ans*=(double)(a--)/(double)(b--);
ans+=0.5;
return (int)ans;
}
}
上述程序提交时通过,运行时间为0ms,内存消耗35.1MB。
说明:在求Cxx+y 时如果先计算(x+y)!,再计算x!y!,最后求二者相除的结果,当x、
y 较大时会发生溢出。
3.2.4 猴子摘桃子问题
1.问题描述
猴子第1天摘下若干个桃子,当即吃了一半又一个。第2天又把剩下的桃子吃了一半
又一个,以后每天都吃前一天剩下的桃子的一半又一个,到第10天猴子想吃的时候,只剩下
一个桃子。求猴子第1天一共摘了多少桃子。
2.问题求解
采用归纳法中的逆推法。设f(i)表示第i 天的桃子数,假设第n(题目中n=10)天只剩
下一个桃子,即f(n)=1。另外题目中隐含前一天的桃子数等于后一天桃子数加1的两倍:
f(10)=1
f(9)=2(f(10)+1)
f(8)=2(f(9)+1)
…
即f(i)=2(f(i+1)+1)。这样得到递推关系如下:
f(i)=1 当i=n 时
f(i)=2(f(i+1)+1) 其他
其中f(i)是大问题,f(i+1)是小问题。最终结果是求f(1)。对应的算法如下:
int peaches(int n) { //第n 天的桃子数为1,求第1 天的桃子数
int ans=1;
for(int i=n-1;i>=1;i--)
ans=2*(ans+1);
return ans;
}
82
上述算法求出f(1)为1534。
3.3 迭 代 法
3.3.1 迭代法概述
迭代法也称辗转法,是一种不断用变量的旧值推出新值的过程。通过让计算机对一组
指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时都从变量的原值推
出它的一个新值。
如果说归纳法是一种建立求解问题数学模型的方法,则迭代法是一种算法实现技术。
一般先采用归纳法产生递推关系,在此基础上确定迭代变量,再对迭代过程进行控制,基本
的迭代法算法框架如下:
void Iterative() { //迭代法框架
迭代变量赋初值;
while(迭代条件成立) {
根据递推关系式由旧值计算出新值;
新值取代旧值,为下一次迭代做准备;
}
}
实际上3.2节中所有的算法均是采用迭代法实现的。
如果一个算法已经采用迭代法实现,那么如何证明算法的正确性呢? 由于迭代法算法
包含循环,对循环的证明引入循环不变量的概念。所谓循环不变量是指在每轮迭代开始前
后要操作的数据必须保持的某种特性(例如在直接插入排序中,排序表前面的部分必须是有
序的)。循环不变量是进行循环的必备条件,因为它保证了循环进行的有效性,有助于用户
理解算法的正确性。如图3.6所示,对于循环不变量必须证明它的3个性质。
初始化:在循环的第一轮迭代开始之前,应该是正确的。
保持:如果在循环的第一次迭代开始之前正确,那么在下一次迭代开始之前它也应该
保持正确。
终止:当循环结束时,循环不变量给了用户一个有用的性质,它有助于表明算法是正
确的。
图3.6 利用循环不变量证明算法的正确性
这里的推理与数学归纳法相似,在数学归纳法中要证明某一性质是成立的,必须首先证
明归纳基础成立,这里就是证明循环不变量在第一轮迭代开始之前是成立的。证明循环不
变量在各次迭代之间保持成立,就类似数学归纳法中证明归纳递推成立。循环不变量的第
三项性质必须成立,与数学归纳法不同,在归纳法中归纳步骤是无穷地使用,在循环结束时
才终止“归纳”。
【例3-3】采用循环不变量方法证明3.2.2节中直接插入排序算法的正确性。
证明:直接插入排序算法中循环不变量为R[0..i-1]是递增有序的。
初始化:循环时i从1开始,循环之前R[0..0]中只有一个元素,显然是有序的。所以
循环不变量在循环开始之前是成立的。
保持:需要证明每一轮循环都能使循环不变量保持成立。对于R[i]排序的这一趟,之
前R[0..i-1]是递增有序的:
①如果R[i]≥R[i-1],即正序,则该趟结束,结束后循环不变量R[0..i]显然是递增
有序的。
②如果R[i]<R[i-1],即反序,则在R[0..i-1]中从后向前找到第一个R[j]≤R[i],
将R[j+1..i-1]均后移一个位置,并且将原R[i]放在R[j+1]位置,这样结束后循环不变
量R[0..i]显然也是递增有序的。
终止:循环结束时i=n,在循环不变量中用i替换n,就有R[0..n-1]包含原来的全部
元素,但现在已经排好序了,也就是说循环不变量也是成立的。
这样证明了上述直接插入排序算法的正确性。
3.3.2节~3.3.5节将重点放在迭代法算法的设计上而不是算法的正确性证明上,通过
几个经典应用予以讨论。
3.3.2简单选择排序
1.问题描述
有一个整数序列R[0..n-1],采用简单选择排序实现R的递增有序排序。简单选择排
序的过程是,i从0到n-2循环,R[0..i-1]是有序区,R[i..n-1]是无序区,并且前者的所
有元素均小于或等于后者的任意元素,每次循环在R[i..n-1]无序区采用简单比较找到最
小元素R[minj],通过交换将其放在R[i]位置。
2.问题求解
采用不完全归纳法产生简单选择排序的递推关系。例如R=(2,5,4,1,3),这里n=5,
用[]表示有序区,各趟的排序结果如下:
初始:([]2,5,4,1,3)
i=0:([1],5,4,2,3)
i=1:([1,2],4,5,3)
i=2:([1,2,3],5,4)
i=3:([1,2,3,4],5)
设f(R,用于实现R[1]( i个元素) 它是大问题, R,
i) i.
n-共n-的递增排序, 则f(i+1)
i+1.
n-i
实现R[1](共n-1个元素)的排序,它是小问题。对应的递推关系如下:
f(R,i)≡不做任何事情当i=n-1时
f(R,i.
i]位置
i)
≡
在R[n-1]中选择最小元素交换到R[其他
f(i+1)
R,
83
84
显然f(R,0)用于实现R[0..n-1]的递增排序。对应的算法如下:
void Select(int R[],int i) { //在R[i..n-1]中选择最小元素交换到R[i]位置
int minj=i; //minj 表示R[i..n-1]中最小元素的下标
for(int j=i+1;j<R.length;j++) { // 在 R[ i. . n- 1] 中找最小元素
if(R[j]<R[minj]) minj=j;
}
if(minj!=i) { //若最小元素不是R[i]
int tmp=R[minj]; //交换
R[minj]=R[i]; R[i]=tmp;
}
}v
oid SelectSort1(int R[]) { // 迭 代 法 : 简 单选择排序
for(int i=0;i<R.length-1;i++) //进行n-1 趟排序
Select(R,i);
}
3.3.3 实战———多数元素(LeetCode169★)
1.问题描述
见2.12.3节,这里采用迭代法求解。
2.问题求解
依题意nums中一定存在多数元素。通过观察可以归纳出这样的结论,删除nums中
任意两个不同的元素,则删除后多数元素依然存在且不变。假设nums中的多数元素为c,
即c出现的次数cnt大于n/2,现在删除nums中任意两个不同的元素得到nums1(含n-2
个元素):
① 若两个元素均不是c,则c在nums1中出现的次数仍然为cnt,由于cnt>n/2>
(n-2)/2,所以c是nums1中的多数元素。
② 若两个元素有一个是c,则c在nums1中出现的次数为cnt-1,由于(cnt-1)/(n-2)>
(n/2-1)/(n-2)=1/2,也就是说c在nums1中出现的次数超过一半,所以c是nums1中
的多数元素。
既然上述结论成立,设候选多数元素为c=nums[0],计数器cnt表示c出现的次数(初
始为1),i 从1开始遍历nums,若两个元素(nums[i],c)相同,cnt增1,否则cnt减1,相当
于删除这两个元素(nums[i]删除一次,c也只删除一次),如果cnt为0说明前面没有找到
多数元素,从nums[i+1]开始重复查找,即重置c=nums[i+1],cnt=1。遍历结束后c就
是nums中的多数元素。对应的迭代法算法如下:
class Solution {
public int majorityElement(int[]nums) {
int n=nums.length;
if(n==1) return nums[0];
扫一扫
视频讲解
85
int c=nums[0],cnt=1;
int i=1;
while(i<n) {
if(nums[i]==c) //选择两个元素(nums[i],c)
cnt++; //相同时累加次数
else
cnt--; //不相同时递减cnt,相当于删除这两个元素
if(cnt==0) { //cnt 为0 时对剩余元素从头开始查找
i++;
c=nums[i];
cnt++;
}
i++;
}
return c;
}
}
上述程序提交时通过,运行时间为1ms,内存消耗为44.3MB。对应算法的时间复杂度
为O(n),空间复杂度为O(1)。
说明:与2.12.3节的程序相比,上述程序的时间性能得到大幅度提高。
3.3.4 求幂集
1.问题描述
给定正整数n(n≥1),请给出求{1~n}的幂集的递推关系和迭代算法。例如,n=3时,
{1,2,3}的幂集为{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}(子集的顺序任意)。
2.问题求解
以n=3为例,求1~3的幂集的过程如图3.7所示。
图3.7 求{1,2,3}的幂集的过程
扫一扫
视频讲解
86
对应的步骤如下:
① {1}的幂集M1={{},{1}}。
② 在M1 的每个集合元素的末尾添加2得到A2={{2},{1,2}},将M1 和A2 的全部
元素合并起来得到M2={{},{1},{2},{1,2}}。
③ 在M2 的每个集合元素的末尾添加3得到A3={{3},{1,3},{2,3},{1,2,3}},将
M2 和A3 的全部元素合并起来得到M3={{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,
3}}。
归纳起来,设Mi 表示{1~i}(i≥1,共i 个元素)的幂集(是一个两层集合),为大问题,
则Mi-1是{1~i-1}(共i-1个元素)的幂集,为小问题。显然有M1={{},{1}}。
考虑i>1的情况,假设Mi-1已经求出,定义运算appendi(Mi-1,i)返回在Mi-1中每
个集合元素的末尾添加整数i 的结果,即:
appendi(Mi-1,i)= ∪ s∈Mi-1add(s,i)
则:
Mi =Mi-1 ∪Ai
其中Ai=appendi(Mi-1,i)。
这样求{1~n}的幂集的递推关系如下:
M1 ={{},{1}}
Mi =Mi-1 ∪Ai 当i >1时
幂集是一个两层集合,采用List<List<Integer> > 类对象存放,其中每个List
<Integer>元素表示幂集中的一个集合。大问题即求{1~i}的幂集,用Mi 变量表示,小问
题即求{1~i-1}的幂集,用Mi_1变量表示,首先置Mi_1={{},{1}}表示M1,迭代变量i
从2到n 循环,每次迭代将完成的问题规模由i 增加i+1。对应的迭代法算法如下:
class Solution {
List<List<Integer>>deepcopy(List<List<Integer>>A) { //返回A 的深复制
List<List<Integer>>B=new ArrayList<>();
for(List<Integer>x: A)
B.add(new ArrayList<>(x));
return B;
}
List<List<Integer>>appendi(List<List<Integer>>Mi_1,int e) {
//向Mi_1 中每个集合元素的末尾添加e
List<List<Integer>>Ai=Mi_1; //浅复制
for(List<Integer>x: Ai)
x.add(e);
return Ai;
}
public List<List<Integer>>subsets(int n ) { // 迭代法: 求1 到n 的幂集
List<List<Integer>>Mi=new ArrayList < >( ); / /存 放 幂 集
List<List<Integer>>Mi_1=new ArrayList<>();
Mi_1.add(new ArrayList<>()); / / 添 加 一 个 {}
ArrayList<Integer>tmp=new ArrayList<>();
tmp.add(1);
87
Mi_1.add(tmp); //再添加一个{1},即Mi_1={{},{1}}
if(n==1) return Mi_1; //处理特殊情况
for(int i=2;i<=n;i++) {
Mi=deepcopy(Mi_1);
List<List<Integer>>Ai=appendi(Mi_1,i);
for(List<Integer>x: Ai) //将Ai 中的所有集合元素添加到Mi 中
Mi.add(x);
Mi_1=deepcopy(Mi); //用新值替换旧值
}
return Mi;
}
}
3.3.5 实战———子集(LeetCode78★★)
1.问题描述
给定一个含n(1≤n≤10)个整数的数组nums,其中所有元素互不相同。设计一个算法
求该数组的所有可能的子集(幂集),结果中不能包含重复的子集,但可以按任意顺序返回幂
集。例如,nums={1,2,3},结果为{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}。要求
设计如下方法:
public List<List<Integer>>subsets(int[]nums) { }
2.问题求解
将数组nums看成一个集合(所有元素互不相同),求nums的所有可能的子集就是求
nums的幂集,与3.3.4节的思路完全相同,仅需要将求1~n 的幂集改为求nums[0..n-1]
的幂集。定义运算appendi(Mi-1,nums[i])返回在Mi-1中每个集合元素的末尾插入元素
nums[i]的结果,即:
appendi(Mi-1,nums[i])= ∪ s∈Mi-1push_back(s,nums[i])
则:
Mi =Mi-1 ∪Ai
其中Ai=appendi(Mi-1,nums[i])。
这样求nums的幂集的递推关系如下:
M0 ={{},{nums[0]}}
Mi =Mi-1 ∪Ai 当i >0时
对应的迭代法算法如下:
class Solution {
public List<List<Integer>>subsets(int[]nums) { //迭代法: 求nums 的幂集
List<List<Integer>>Mi=new ArrayList<>(); / /存 放 幂 集
List<List<Integer>>Mi_1=new ArrayList<>();
扫一扫
视频讲解
88
Mi_1.add(new ArrayList<>()); //添加一个{}
ArrayList<Integer>tmp=new ArrayList<>();
tmp.add(nums[0]);
Mi_1.add(tmp); //再添加一个{nums[0]}
if(nums.length==1) return Mi_1; //处理特殊情况
for(int i=1;i<nums.length;i++) {
Mi=deepcopy(Mi_1);
List<List<Integer>>Ai=appendi(Mi_1,nums[i]);
for(List<Integer>x: Ai) //将Ai 中的所有集合元素添加到Mi 中
Mi.add(x);
Mi_1=deepcopy(Mi); //用新值替换旧值
}
return Mi;
}
List<List<Integer>>appendi(List<List<Integer>>Mi_1,int e) {
//向Mi_1 中每个集合元素的末尾添加e
List<List<Integer>>Ai=Mi_1; //浅复制
for(List<Integer>x: Ai)
x.add(e);
return Ai;
}
List<List<Integer>>deepcopy(List<List<Integer>>A) { //返回A 的深复制
List<List<Integer>>B=new ArrayList<>();
for(List<Integer>x: A)
B.add(new ArrayList<>(x));
return B;
}
}
上述程序提交时通过,执行用时为1ms,内存消耗为38.5MB。
3.4 递 归 法
3.4.1 递归法概述
1.什么是递归
递归算法是指在算法定义中又调用自身的算法。若p算法定义中调用p算法,称为直
接递归算法;若p算法定义中调用q算法,而q算法定义中又调用p算法,称为间接递归算
法。任何间接递归算法都可以等价地转换为直接递归算法,所以本节主要讨论直接递归
算法。