为了设计出解决问题的好算法,除了要掌握常用的数据结构工 具外,还需要掌握算法设计方法,算法设计与分析课程主要讨论分治 法、回溯法、分支限界法、贪心法和动态规划,称为五大算法策略。在 学习这些算法策略之前必须具有一定的算法设计基础,本章讨论穷 举法、归纳法、迭代法和递归法等基本算法设计方法及其递推式的计 算,学习要点和学习目标如下: (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;i0时 假设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=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=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;i0) 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]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(i1的情况,假设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 元素表示幂集中的一个集合。大问题即求{1~i}的幂集,用Mi 变量表示,小问 题即求{1~i-1}的幂集,用Mi_1变量表示,首先置Mi_1={{},{1}}表示M1,迭代变量i 从2到n 循环,每次迭代将完成的问题规模由i 增加i+1。对应的迭代法算法如下: class Solution { List>deepcopy(List>A) { //返回A 的深复制 List>B=new ArrayList<>(); for(Listx: A) B.add(new ArrayList<>(x)); return B; } List>appendi(List>Mi_1,int e) { //向Mi_1 中每个集合元素的末尾添加e List>Ai=Mi_1; //浅复制 for(Listx: Ai) x.add(e); return Ai; } public List>subsets(int n ) { // 迭代法: 求1 到n 的幂集 List>Mi=new ArrayList < >( ); / /存 放 幂 集 List>Mi_1=new ArrayList<>(); Mi_1.add(new ArrayList<>()); / / 添 加 一 个 {} ArrayListtmp=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>Ai=appendi(Mi_1,i); for(Listx: 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>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>subsets(int[]nums) { //迭代法: 求nums 的幂集 List>Mi=new ArrayList<>(); / /存 放 幂 集 List>Mi_1=new ArrayList<>(); 扫一扫 视频讲解 88 Mi_1.add(new ArrayList<>()); //添加一个{} ArrayListtmp=new ArrayList<>(); tmp.add(nums[0]); Mi_1.add(tmp); //再添加一个{nums[0]} if(nums.length==1) return Mi_1; //处理特殊情况 for(int i=1;i>Ai=appendi(Mi_1,nums[i]); for(Listx: Ai) //将Ai 中的所有集合元素添加到Mi 中 Mi.add(x); Mi_1=deepcopy(Mi); //用新值替换旧值 } return Mi; } List>appendi(List>Mi_1,int e) { //向Mi_1 中每个集合元素的末尾添加e List>Ai=Mi_1; //浅复制 for(Listx: Ai) x.add(e); return Ai; } List>deepcopy(List>A) { //返回A 的深复制 List>B=new ArrayList<>(); for(Listx: A) B.add(new ArrayList<>(x)); return B; } } 上述程序提交时通过,执行用时为1ms,内存消耗为38.5MB。 3.4 递 归 法 3.4.1 递归法概述 1.什么是递归 递归算法是指在算法定义中又调用自身的算法。若p算法定义中调用p算法,称为直 接递归算法;若p算法定义中调用q算法,而q算法定义中又调用p算法,称为间接递归算 法。任何间接递归算法都可以等价地转换为直接递归算法,所以本节主要讨论直接递归 算法。