1、第二章常用算法2.12.1递归法递归法2.22.2分治法分治法2.32.3贪心法贪心法2.42.4搜索法与回溯法搜索法与回溯法【2.1.12.1.1递归的概念与基本思想递归的概念与基本思想】递归（Recursion）即是一个函数直接或间接调用自己本身的过程。使用递归时必须符合以下三个条件：可将一个问题转化为新问题，而新问题的解决方法仍然与原问题的方法相同，只不过所处理的对象不同而已，即它们只是规律的递增和递减。可以通过转化过程使问题回到对原问题的求解。必须要有一个明确的递归结束条件，否则递归会无休止地进行下去。递归的思想就是把复杂的问题层层分解成简单的问题去解决。我们用几个经典例子说明递归的思
2、想。阶乘函数 f（n）=n！按照递归的思想可以定义为f(0)=1,n=0f(n)=f(n1)n,n0对应的递归函数：int f(int n)if(n=0)return 1；2.1递归法elsereturn f(n1)*n；斐波那契数列按照递归的思想可以定义为：f(1)=1，n=1f(2)=1，n=2f(n)=f(n1)f(n2),n2对应的递归函数：int f(int n)if(n=1)return 1；if(n=2)return 1；elsereturn f(n1)+f(n2)；2.1递归法【2.1.22.1.2递归法的应用递归法的应用】【例例 2.12.1】计算两个数的最大公约数。【算法分
3、析算法分析】我们用gcd（n，m）来表示两个数的最大公约数，那么我们有公式 gcd（n，m）=gcd（m，nm）进而我们可以按照递归的思想写出新的公式gcd(n,m)=gcd(m,n%m)有了这个公式我们就可以写出程序了。【设计技巧设计技巧】可以利用?表达式来简化程序。【程序实现程序实现】下面是用 if 语句完成的程序。/*prog:gcd lang c*/#includeiostreamusing namespace std；int gcd（int a,int b）2.1递归法if（b=0）return a；else return gcd（b，a%b）；int main（）int a，b；c
4、inab；coutgcd（a，b）endl；return 0；2.1递归法下面是用？：表达式完成的程序。/*prog：gcdlang：c*/#includeiostreamusing namespace std；int gcd（int a，int b）return b=0？a：gcd（b，a%b）；int main（）int a，b；cinab；coutgcd（a，b）endl；return 0；2.1递归法【例2.2】将十进制正整数n转化为m进制数。2m20。【算法分析】连续除以m直到商为0，从底向上记录余数即可得到结果。如图2.1所示，将12转化为2进制数，（12）10=（1100）2观察
5、这个过程，它就是一个递归的过程，递归的边界条件是当前数为0，只需按照上图的思路设计程序即可。【设计技巧】需要注意n=0时是特殊情况，需要特殊处理保证程序的正确性。可以提前存储代码，减少程序代码量。在递归更深层结束后再将这一层对应的余数加入答案，即回溯时再将这一层的余数加人答案。【程序实现】/*prog：进制转换lang：c*/#includeiostreanmusing namespace std；string Num20；string S；void PreWork（void）2.1递归法图图2.1 122.1 12转换为转换为2 2进制数进制数for（int i=0；i20；i）Numi=.
6、for（int i=0；i10；iNumi0=（char）（0i）；for（int i=10；i20；i）Numi0=（char）（Ai10）；void NemberConver（int n，int m）if（n=0）return；NumberConver（n/m，m）；S=Numn%m；int main（）int n，m；cinnm；id（n=0）cout0endl；elsePreWork（）；NumberConver（n，m）；coutSendl；return 0；2.1递归法【2.2.12.2.1分治的概念与基本思想分治的概念与基本思想】分治法是一种很重要的算法。字面上的解释是“分而治之
7、”，其基本思想就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好顺序；n=3时只要作三次比较即可。而当n较大时，问题就不那么容易处理了，要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想
8、：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。2.2分治法分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决。（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解。（4）该问题所分解出的各个子问
9、题是相互独立的，即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提它也是 大多数问题可以满足的，此特征反映了递归思想的应用;第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。分治法的基本步骤。分治法在每一层递归上都有三个步骤：（1）分解：将原问题分
10、解为若干个规模较小、相互独立并且与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。它的一般的算法设计模式如下：DivideandConquer（P）if|P|n0；2.2分治法then return（ADHOC（P）；将P分解为较小的子问题P1，P2，Pk；for i1 to k；do yiDivideandConquer（Pi）；递归解决PiTMERGE（y1，y2，yk）；合并子问题return（T）。其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，
11、不必再继续分解。ADHOC（P）是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC（P）求解。算法MERGE（y1，y2，yk）是该分治法中的合并子算法，用于将P的子问题P1，P2，Pk的相应的解yl，y2，yk合并为P的解。分治法的过程如图2.2所示。2.2分治法图图2.2 2.2 分治法的过程分治法的过程实际中分治法的应用很广泛，信息学竞赛中有很多经典的应用。例如，归并排序算法、快速排序算法和二分查找算法。下面我们介绍归并排序算法和二分查找算法来更详细的解释分治法。1.1.归并排序算法归并排序算法归并排序是一种利用了分治法的排序算法。其可以
12、分为三个步骤：将序列分为规模相等的两部分。对两部分分别进行排序。将已经排过序的两部分整合起来得到有序的原序列。其中可以继续递归下去处理，整个递归树只有O（lnn）层，故如果我们能在O（n）时间复杂度内完成，则整个算法时间复杂度为O（nlnn）。归并排序非常巧妙的应用了分治法，将原序列排序这个大问题，层层分治最后变成容易解决的小规模问题。归并排序是分治法的经典应用之一。下面给出归并排序算法的程序：/*prog：merge sortlang：c*/#includeiostream#includecstdiousing namespace std；2.2分治法const int maxn=10000
13、5；int n，Amaxn，tmp_Amaxn；void MergeSort（int 1，int r）if（1=r）return；int mid=（1+r）1；MergeSort（1，mid）；MergeSort（mid+1，r）；int p1=1，p2=mid+1；for（int i=1；i=r；i+）if（p1mid）tmp_Ai=Ap2，p2+；else if（p2r）tmp_Ai=AP1，p1+；else if（Ap1Ap2）tmp_Ai=Ap1，p1+；else tmp_Ai=Ap2，p2+；2.2分治法 for（int i=1；i=r；i+）Ai=tmp_Ai；int main（）
14、cinn；for（int i=0；in；i+）scanf（%d，&Ai）；MergeSort（0，n1）；for（int i=0；in；i+）printf（%d%c，Ai，i=n1？n：）；return 0；2.2分治法2.2.二分查找算法二分查找算法现在有一个严格单调递增数列，要求在其中查找元素X（保证X一定存在）。数列中有n个数。我们把数列从头到尾查找一遍，时间复杂度O（n）。但是没有用到严格单调递增这个 条件，利用二分查找算法可以在时间复杂度O（lnn）内解决问题。二分查找算法可以分为三个部分：如果当前区间只有一个数，那么必然是要查找的数。将要查找的数与区间最中间的数进行比较，根据区间单
15、调性可以确定要查找的数在 左半部分区间还是在右半部分区间。在新的区间内继续查找。下面给出二分查找算法的程序：2.2分治法2.2分治法【2.2.22.2.2分治法的应用分治法的应用】【例例2.42.4】比赛安排（NOIP1996提高组）。设有2n（n6）个球队进行单循环比赛，计划在2n一1天内完成，每个队每天进行一场比赛，且在2n一1天内每个队都与不同的对手比赛。请编写程序设计比赛安排表并按下表的格式输出。例如下面是n=2时的比赛安排表，见表2.1。表表2.1 n=22.1 n=2时的比赛安排表时的比赛安排表【算法分析算法分析】题目貌似很难下手，我们不妨尝试一下找规律。下面是n=1时的比赛安排表
16、，见表2.2。2.2分治法表表2.2 n=12.2 n=1时的比赛安排表时的比赛安排表对比两个表，我们容易发现规律：表2.1的左上角与右下角和表2.2一样。表2.1的左下角和右上角一样，且是表2.2每个值均加上2得到。按照这两个规律我们可以构造出n=3时的比赛安排表，注意这里要加上2，见表2.3。表表2.3 n=32.3 n=3时的比赛安排表时的比赛安排表2.2分治法2.2分治法2.2分治法【2.3.12.3.1贪心的概念与基本思想贪心的概念与基本思想】贪心法是解决一类最优问题的策略。这种算法只选择当前局部看起来的最佳策略，而不去考虑整体来讲是否是最佳策略。正确的贪心算法应保证贪心策略的无后效
17、性（即某个状态以后的过程不影响以前的状态，只和当前状态有关）。贪心法不能保证对所有问题均适用，但对很多最优解的问题适用。可以应用贪心法的题目必须具备贪心选择和最优子结构两种性质。所谓贪心选择性质，是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心选择是贪心法的核心，我们求整体最优解的时候可以通过一系列局部最优的选择来达到，即我们可以迭代的选择局部最优选择来得到全局最优解。怎么去设计贪心选择是贪心法的关键。最优子结构性质，是指一个问题的最优解包含其子问题的最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。程序设计中，贪心算法的问题枚不胜数，且问题类型变化也
18、很多，是信息学竞赛的一个难点。贪心算法的经典应用有单源最短路径的Dijkstra算法（我们将在第5章介绍这种算法）、求解最小生成树的Prim算法及Kruskal算法（我们将在第5章介绍这种算法）。很多时候贪心算法并不能保证正确性，但往往通过与随机算法的结合可以得到靠近最优解的近似算法，例如遗传算法、模拟退火算法。对于这一类问题，通过一定的数学推导之后可以用贪心算法解决，这是贪心算法和数学的结合。贪心算法类型繁多，我们主要通过例题来说明贪心算法的应用。2.3贪心法【2.3.22.3.2贪心法的应用贪心法的应用】【例例2.72.7】背包问题。给定背包的容量为W，给定n（n105）件物品，第i件物品
19、的体积是wi，问背包至多能装多少件物品?【算法分析算法分析】显然，背包的剩余的容量越大能装的物品数越多。根据题意，每个物品除了体积以外没有区别。那么我们可以得到以下贪心策略。（1）将物品按体积从小到大排序。（2）从体积最小的开始依次放入背包，直到背包不再能装物品为止。【设计技巧设计技巧】排序可以应用algorithm库中的sort函数。【程序实现程序实现】/*prog：背包问题lang：c+*/#includeiostream#includecstdio#includealgorithm2.3贪心法using namespace std；const int maxn=100005；int wm
20、axn；int main（）int n，W；cinnW；for(int i=0；in；i+)scanf(%d，&wi)；sort（w，w+n）；int res=0；for(int i=0；in&W=wi；i+)res+，W=wi；coutresendl；return 0；2.3贪心法【例例2.82.8】线段。在数轴上有n（n105）个线段，编号从0到n1，第i条线段的左端点坐标为Li、右端点坐标为Ri，且满足对于任意的i，j0，n1，ij都不满足LiLj且RiRj（即不存在两个线段满足包含关系）。要求在数轴上选择尽量少的点使得这个线段每个线段内均有被选择的点。即求最小的K满足Kn且存在b1，b
21、2，bk使得对于任意i0，n1均存在j1，K使得LibjRi，输出最少要用多少个点即可。【算法分析算法分析】将n个线段按照左端点坐标升序排序，下面证明这时右端点坐标为升序。证明我们利用反证法来证明这个结论。若排序后存在i，j0，n1且ij，RiRj。即存在i，j0，n1且LiLj，RiRj。矛盾。故排序后右端点坐标也为升序。证毕。这时我们得到了n个左右端点都升序的线段，如图2.8所示：图图2.82.8线段线段2.3贪心法设fi为最少需要多少个点才能覆盖第i条线段到第n一1条线段（这里的编号是排序之后的编号）。那么f0就是我们要求的答案。如果我们要求fi，那么先选择Ri这个点，如果此时编号从i到
22、n一1的线段均被覆盖则fi=1。否则找到编号最小的不被覆盖的线段j，那么fi=fj1。这样我们在贪心策略的基础上得到了递推式。下面我们来证明这样的贪心策略是正确的。证明证明如果选择Ri这个点编号从i到n1的线段均被覆盖，那么这一定是最优方案。我们只需讨论不能全部被覆盖的情况。显然，fi是不下降的序列，那么我们只需要证明选择Ri这个点能使得递推式中的j最小即可。因为这n条线段左右端点均单调递增。显然选择Ri这个点能使得递推式中的j最小。证毕。因为数据规模较大，这里的值要用二分法求出。总时间复杂度O（nlnn）。【设计技巧设计技巧】我们需要倒着去求f数组。排序可以用algorithm库中sort函
23、数。【程序实现程序实现】/*prog：segmemtlang：c+*/2.3贪心法2.3贪心法2.3贪心法【2.4.12.4.1搜索与搜索与回溯的概念与基本思想回溯的概念与基本思想】搜索算法如同其字面意思，即穷举所有的可能情况去解决问题，搜索算法的复杂度往往是指数级，数据规模稍大运算时间可能就会是天文数字，但搜索算法往往是解决问题最直接的方式。有些问题没有更优秀的方法只能应用搜索算法解决问题。搜索算法往往也用作和其他算法相互配合解决问题。搜索算法的实质就是构造一个“搜索树”，这个“搜索树”表达了整个搜索算法的过程。搜索算法从一个初始状态出发根据一定的扩展规则来进行搜索过程，最后形成的整个过程就
24、是一个“搜索树”。也就相当于我们将一个问题的解决过程已经抽象成了图论中的模型树，即我们的搜索算法相当于在这个树上进行某种形式的遍历，如图2.9所示。图图2.92.9搜索树搜索树2.4搜索法与回溯法一种搜索算法相当于树的遍历，通常我们有两种实现方式，深度优先搜索（简称DFS）和广度优先搜索（简称BFS）。回溯算法的基本思想是：为了求得待解问题的解，我们先选择一种可能的情况向前搜索，一旦发现原来的选择是错误（也就是这种选择会导致问题无解）就退回来重新选择，如此反复进行。直到得到问题的解，或者在穷举完所有情况后，判断原问题无解。下面我们来介绍深度优先搜索和广度优先搜索：（1）深度优先搜索。顾名思义，
25、深度优先搜索即是深度优先的搜索算法，即在搜索树上优先深度遍历。深度优先搜索通常用递归法的方法实现。（2）广度优先搜索。对比深度优先搜索，广度优先搜索是以广度优先的搜索算法，即在搜索树上一层层遍历，第0层和第1层全部遍历完才会遍历第2层，广度优先搜索通常用循环结构就可以实现。对比这两种搜索算法，我们发现深度优先搜索是以栈结构为基础的搜索算法，而广度优先搜索是以队列结构为基础的搜索算法。2.4搜索法与回溯法【2.4.22.4.2搜索法与回溯法的应用搜索法与回溯法的应用】【例例2.112.11】跳马。如图2.10所示的55的棋盘上，从左下角的方格出发，按照日字跳马，要求不重复地跳过所有方格。输出方案
26、数。【算法分析算法分析】用窗口坐标系表示棋盘上的每个格子，那么我们从（x，y）只能跳往（x2，y1）、（x2，y1）、（x1，y2）、（x1，y2）、（x1，y2）、（x1，y2）、（x2，y1）和（x2，y1）这八个格子。我们采用深度优先搜索，状态表示为当前所在格子的坐标。那么初始状态为（1，1），那么每个状态可以扩展的状态最多只有八个。题目还要求不能重复经过。我们需要加一个标志数组，标志哪些格子已经经过了，继续往下搜的时候加标志搜完了退回来去掉标志即可。一直重复这个过程直至所有状态均已搜索出来。【设计技巧设计技巧】标志数组必须是全局变量。【程序实现程序实现】/*Prog：跳马lang：c*
27、/2.4搜索法与回溯法图图2.102.10棋盘棋盘#includeiostream#includecstring using namespace std；const int dir_x8=2,2,1,1,2,2,1,1；const int dir_y8=1,1,2,2,1,1,2,2；bool vis55；int ans=0；void DFS(intx,int y,int deep)if(deep=24)ans；return；2.4搜索法与回溯法 for(int i=0；i8；i)if(xdir_xi=0&xdir_xi5)if(ydir_yi=O&ydir_yi5)if(！visxdir_x
28、iydir_yi)visxdir_xiydir_yi=true；DFS(xdir_xi,ydir_yi,deep1)；visxdir_xiydir_yti=false；int main（）memset(vis,false,sizeof(vis)；vis00=true；DFS(0,0,0)；coutansendl；2.4搜索法与回溯法【例例2.122.12】哈密顿回路。给一个无向图，从1号点开始不重复的经过所有点后再回到1号点，这样的回路称之为哈密顿回路。对于一个无向图，求有多少个哈密顿回路。【算法分析算法分析】哈密顿回路是典型的NP完全问题，没有多项式复杂度的解法。考虑使用深度优先搜索的方法解
29、决问题。和上例很类似，但是本题要求的是回路，其实方法一样，判断下走到的最后一个点和1号点是否联通即可。【设计技巧设计技巧】采用邻接矩阵存储图，标志数组必须是全局变量。【程序实现程序实现】/*prog：哈密顿回路lang：c*/#includeiostream#includecstringusing namespace std；bool vis10；int G1010，n，m，ans=0；2.4搜索法与回溯法void DFS(int p,int deep)if(deep=n-1)if(Gp1)ans;return;for(int i=1;i=n;i)if(Gpi&！visi)visi=true;DFS(i,deep1);visi=false;int main（）2.4搜索法与回溯法memset(G,0,sizeof(G)；cinnm；for(int i=0；im；i)int pl,p2；cinplp2；Gp1p2=Gp2p1=1；memset(vis,false,sizeof(vis)；vis1=true；DFS(1,0)；coutansendl；return O；2.4搜索法与回溯法
