《C++经典算法》由会员分享，可在线阅读，更多相关《C++经典算法（53页珍藏版）》请在金锄头文库上搜索。
1、分治算法的基本思想是将一个规模为N 的问题分解为K 个规模较小的子问题，这些子问题相互独立且与原问，性质相同。求出子问题的解，就可得到原问题的解。分治法解题的般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题：（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。例 1、比赛安排（noipl996）设有2n（n=6）个球队进行单循环比赛,计划在2勾-1 天内完成,每个队每天进行一场比赛。设计一个比赛的安排，使在2人 止 1 天内每个队都与不同的对手比赛。例如n=2时的比赛安排为:队 12 34比 赛 1-2 3-4
2、第一天1-3 2-4 第二天1-4 2-3 第三天算法分析：此题很难直接给出结果，我们先将问题进行分解，设 m=2M,将规模减半，如果 n=3（即 m=8）,8 个球队的比赛，减半后变成4 个球队的比赛（m=4）,4 个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛（m=2）,两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可：1221分析两个球队的比赛的情况不难发现，这是一个对称的方阵,我们把这个方阵分成4 部分（即 右 下 右 上 部 分 可 由 左 上 部 分 加1（即 加m2）得到，而右上与左下濡 可 然：X黑别相察因此我们也可以把这个方阵看作是由M E的方阵所
3、成生的,123421433412432同理可由M=4方阵生成M=8的方阵:2345678143658741278563218765*67812345872143*856341287654321这样就构成了整个比赛的安排表。在算法设计中，用数组a 记录2人 n 个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，直到生成出整个循环比赛表为止。变量 h 表示当前方阵的大小，也就是要生成的下一个方阵的一半。源程序：i,jzhzmzn:integer;a:array1.32,l.32of integer;beginreadln(n);m:=l;al,l:
4、=l;h:=l;for i:=l to n do m:=m*2;repeatfor i:=l to h dofor j:=l to h do beginai,j+h:=ai,j+h;构造右上角方阵ai+h,j:=ai,j+h;构造左下角方阵ai+h,j+h:=ai,j;构造右下角方阵end;h:=h*2;until h=m;for i:=l to m dobeginfor j:=l to m do write(ai,j:4);writein;end;end.在分治算法中，若将原问题分解成两个较小的子问题，我们称之为二分法，山于二分法划分简单，所以使用非常广泛。使用二分法与使用枚举法求解问题相比
5、较，时间复杂度由o(N)降到O(lo g2N),在很多实际问题中，我们可以通过使用二分法，达到提高算法效率的目的,如下面的例子。例 2-一 元三次方程求解(noip2001tg)题目大意：给出一个一元三次方程f(x)=ax3+bx2+cx+d=0，求它的三个根。所有的根都在区间1100,100中，并保证方程有三个实根，且它们之间的差不小于1。算法分析：在讲解枚举法时，我们讨论了如何用枚举法求解此题，但如果求解的精度进一步提高，使用枚举法就无能为力了，在此我们再一次讨论如何用二分法求解此题。由题意知(i,i+l)中若有根，则只有一个根，我们枚举根的值域中的每一个整数x(-100 xW100),设
6、定搜索区间xl,x 2,其中xl=x,x2=x+l若：f(xl)=0,则确定x l 为 f(x)的根；(2)f(xl)*f(x2)0,则确定根x 不在区间 xl,x2 内，设定 x2,x2+l 为下一个搜索区间：若确定根x 在区间 xl,x2 内，采用二分法，将区间 xl,X2 分成左右两个子区间：左子区间 xl,x 和右子区间 x,x2(其中x=(xl+x2)/2)。如果f(xl)*f(x)W O,则确定根在左区间 xl,x 内，将 x 设为该区间的右界值(x 2=x),继续对左区间进行对分；否则确定根在右区间 x,X2 内，将 x 设为该区间的左界值(x l=x),继续对右区间进行对分；上
7、述对分过程一直进行到区间的间距满足精度要求为止(即x2-xl0.005)此时确定x l 为f(x)的根。源程序：$N+varx:integer;a,b,c,d,xl,x2,xx:extended;function f(x:extended):extended;beginf:=(a*x+b)*x+c)*x+d;end;beginread(a,b/c,d);for x:=-100 to 100 dobeginxl:=x;x2:=x+l;if f(xl)=0 then write(xl:0:2/)else if f(xl)*f(x2)=0.005 dobeginxx:=(xl+x2)/2;if f(
8、xl)*f(xx)a2-ar;(2)其中第i 位数(l=ir-i;我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数,否则返回到上一个数,改变上一个数的值按此规则不断循环搜索,直到找出r个数的组合，这种求解方法就是回溯法。如果按以上方法生成了第i位数a i,下一步的的处理为：(1)若air-i且i=r,则输出这r个数并改变a i的值:ai=ai-1;(2)若air-i且iW r,则继续生成下一位ai+l=ai-l;(3)若ai=r-i,则回溯到上一位，改变上一位数的值
9、:算法实现步骤：第一步：输入n,r的值，并初始化；i:=l;al:=n;第二步：若则重复：若若i=r,则输出解,并且若 i o r,则继续生成下一位：ai+l:=ai-l;i:=i+l;若 air-i then 符合条件if i=r then 输出beginfor j:=l to r do write(aj:3);writein;ai:=ai-l;endelse 继续搜索begin ai+l:=ai-l;i:=i+l;endelse 回溯begin i:=i-l;ai:=ai-l;end;until al=r-l;end.下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。例 2 数的划分(
10、noip2001tg)问题 描 述 整 数 n 分成k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7,k=3,下面三种分法被认为是相同的。1,1,5;1,5,1;5,1,1;问有多少种不同的分法。输入：n,k(6n=200,2=k=6)输出：一个整数，即不同的分法。样例输入：7 3输出：4 四种分法为：1,1,5;1,2,4;1,3,3;2,2,3；）算法分析：此题可以用回溯法求解，设自然数n 拆分为al,a2,ak,必须满足以下两个条件:(1)n=al+a2+ak；(2)al=a2=-=ak(避免重复计算)；现假设己求得的拆分数为al,a2,ai,且都满足以上两个条件，设
11、 sum=n-al-a2-ai,我们根据不同的情形进行处理：(1)如果i=k,则得到一个解，则计数器t 加 1,并回溯到上一步，改变ai-1的值；(2)如果i=ai,则添加下一个元素ai+1；(3)如果ik且 sumai,则说明达不到目标，回溯到上一步，改变ai-1的值；算法实现步骤如下：第一步：输入自然数 n,k 并初始化；t:=0;i:=l;ai:=l;sum:=n-l;nk:=n divk;第二步：如果al=ai则继续搜索；若 sum=ai then 判断是否回溯begin inc(i);ai:=ai-l;sum:=sum-ai;end 继续搜else begin dec(i);inc(
12、ai);sum:=sum+ai+l-l;end;回溯end;until alnk;writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在 N O IP 中有许多涉及搜索问题的题目都可以用回溯法来求解递归算法算法递归算法的定义：如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。我们先来看看大家熟知的一个的故事：从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说上面的故事本身是递归的，用递归算法描述：procedure bonze-tell-story
13、；begini f 讲话被打断then故事结束else begin从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事：bonze-tell-story；endend;从上面的递归事例不难看出，递归算法存在的两个必要条件：(1)必须有递归的终止条件；(2)过程的描述中包含它本身；在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；例 1：汉诺塔问题，如下图，有 A、B、C 三根柱子。A 柱子上按从小到大的顺序堆放了 N 个盘子，现在要把全部盘子从A 柱移动到C 柱，移动过程中可以借助B 柱。移动时有如下要求：(1)一
14、次只能移动一个盘子;(2)不允许把大盘放在小盘上边；(3)盘子只能放在三根柱子上；算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：如果只有一个盘子，只需一步，直接把它从A 柱移动到C 柱；如果是二个盘子，共需要移动3 步：(1)把 A 柱上的小盘子移动到B 柱；(2)把 A 柱上的大盘子移动到C 柱；(3)把 B 柱上的大盘子移动到C 柱；如 果 N比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A 柱上最大的盘子移动到C 柱上去，必须先把上面的N-1个盘子从A柱移动到B 柱上暂存，按这种思路，就可以把N 个盘子的移动过程分作3
15、大步：(1)把 A 柱上面的N-1个盘子移动到B 柱；(2)把 A 柱上剩下的一个盘子移动到C 柱；(3)把 B 柱上面的N-1个盘子移动到C 柱；其 中 N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。递归过程：procedure Hanoi(N,A,B,C:integer;)；以 B 柱为中转柱将N 个盘子从A 柱移动到C 柱beginif N=1 then w rite(A ,C)把盘子直接从A 移动到Celse beginHanoi(N-l,A,C,B)；以 C 柱为中转柱将N-1个盘
16、子从A 柱移动到B 柱write(A,-,C)；把剩下的一个盘子从A 移动到CHanoi(N-l,BAC):以A 柱为中转柱将N-1个盘子从B 柱移动到C 柱end;end;从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。例 2 求先序排列(N O IP 2001pj)问题描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度W8)。样例输入：BADC BDCA 输出：ABCD算法分析：我们先看看三种遍历的定义：先序遍历是先访问根结点，再遍历左子树，最后遍历右子树；中序遍历是先遍历左子树，再访问根结点，最后遍历右子树；后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；从遍历的定义可知，后序排列的最后个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可
