算法设计与分析第2版王红梅胡明习题答案

1、精心整理习题 11. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（ LeonhardEuler ，17071783）提出并解决了该问题。七桥问题是这样描述 的：一个人是否能在一次步行中穿越哥尼 斯堡（现在叫加里宁格勒，在波罗的海南 岸）城中全部的七座桥后回到起点，且每 座桥只经过一次，图 1.7 是这条河以及河 上的两个岛和七座桥的草图。请将该问题 的数据模型抽象出来，并判断此问题是否有解七桥问题属于一笔画问题。输入：一个起点输出：相同的点1，一次步行2，经过七座桥，且每次只经历过一次3，回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2在

2、欧几里德提出的欧几里德算法中（即最初的欧几里德算法 ）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2. 循环直到 r=02.1?m=n2.2?n=r2.3?r=m-n3?输出 m3设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C+描述。/ 采用分治法/ 对数组先进行快速排序/ 在依次比较相邻的差#includeusingnamespacestd; intpartions(intb,intlow,inthigh) intprvotkey=blow; b0=blow;while(lowhigh)while(low=prvotkey) -hi

3、gh;blow=bhigh; while(lowhigh&blow=prvotkey) +low;bhigh=blow;精心整理blow=b0; returnlow; voidqsort(intl,intlow,inthigh) intprvotloc; if(lowhigh) prvotloc=partions(l,low,high);/ 将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1);/ 递归调用排序由 low 到 prvotloc-1 qsort(l,prvotloc+1,high);/ 递归调用排序由 prvotloc+1 到 high voidquicks

4、ort(intl,intn)qsort(l,1,n);/ 第一个作为枢轴，从第一个排到第 n 个intmain() inta11=0,2,32,43,23,45,36,57,14,27,39; intvalue=0;/ 将最小差的值赋值给 value for(intb=1;b11;b+) coutab;coutendl; quicksort(a,11); for(inti=0;i!=9;+i) if(ai+1-ai)=(ai+2-ai+1) value=ai+1-ai;else value=ai+2-ai+1; coutvalueendl;return0;4设数组 an 中的元素均不相等，设计

5、算法找出 an 中一个既不是最大也不是最小的元素，并说明最坏情 况下的比较次数。要求分别给出伪代码和C+描述。#include usingnamespacestd; intmain() inta=1,2,3,6,4,9,0;intmid_value=0;/ 将“既不是最大也不是最小的元素”的值赋值给它 for(inti=0;i!=4;+i) if(ai+1ai&ai+1ai+2)精心整理mid_value=ai+1;coutmid_valueendl;break;elseif(ai+1ai+2)mid_value=ai+1;coutmid_valueendl;break;/forreturn0

6、;5. 编写程序，求 n 至少为多大时， n个“ 1”组成的整数能被#includeusingnamespacestd;intmain()doublevalue=0;for(intn=1;n=10000;+n)value=value*10+1;if(value%2013=0)coutn 至少为 :nendl;break;/forreturn0;6. 计算 值的问题能精确求解吗？编写程序，求解满足给定精度要求的#includeusingnamespacestd;intmain()doublea,b;doublearctan(doublex);/ 声明a=16.0*arctan(1/5.0);b=

7、4.0*arctan(1/239);coutPI=a-b1e-15)/ 定义精度范围 f=e/i;/f 是每次 r 需要叠加的方程 r=(i%4=1)?r+f:r-f;e=e*sqr;/e 每次乘于 x 的平方 i+=2;/i 每次加 2/while returnr; 7. 圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么是 6 天呢？任何一个自然数的因数中 都有 1 和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等 于它本身，这个自然数称为完美数。例如， 6=1+2+3，因此 6 是完美数。神 6 天创造世界，暗示着 该创造是完美的。设计算法，判断给定的

8、自然数是否是完美数 #include usingnamespacestd;intmain() intvalue,k=1; cinvalue; for(inti=2;i!=value;+i) while(value%i=0) k+=i;/k 为该自然数所有因子之和 value=value/i; /for if(k=value) cout 该自然数是完美数 endl;elsecout 该自然数不是完美数 endl;return0;8. 有 4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是 在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一

9、个人 将手电筒带回来。每个人走路的速度是不同的：甲过桥要用 1 分钟，乙过桥要用 2 分钟，丙过桥 要用 5 分钟，丁过桥要用 10 分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是 他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来 第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥 一共用时 19 小时9欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行精心整理 动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是 新的，也就是

10、说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就 输了。请问，你是选择先行动还是后行动？为什么？设最初两个数较大的为 a, 较小的为 b，两个数的最大公约数为 factor 。则最终能出现的数包括 :factor,factor*2,factor*3,.,factor*(a/factor)=a.一共 a/factor个。如果 a/factor 是奇数，就选择先行动；否则就后行动。习题 21如果 T1( n)= O( f ( n) ，T2( n)= O( g( n) ，解答下列问题：(1) 证明加法定理： T1(n) T2( n)=max O( f ( n), O( g(

11、n) ；(2) 证明乘法定理： T1( n) T2( n)= O( f ( n) O( g( n) ；(3) 举例说明在什么情况下应用加法定理和乘法定理 。, ( 1 )(2)(3)比如在for (f(n) )for(g(n)中应该用乘法定理 如果在“讲两个数组合并成一个数组时” ，应当用加法定理2考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执 行了多少次？算法的时间复杂性是多少？1()1)in完tSt成er的y(i是ntn)1 -n 的平方和( 2) intQ(intn)基本 语句： s+=i*i ，执行了 n次intS=0; 时间复杂度 O(n)if(n=

12、1)2) fo(r(i2nt)i=完1;i成=的n;是i+)n 的平方return1;S=基S本+i*语i; 句： returnQ(n -1)+2*n 1，els执e 行了 n 次returnS;时 间复杂度 O(n)returnQ(n - 1)+2*n - 1;3. 分析 以下程序段中基本语句的执行次数是多 少，要求列出计算公式。(2)m=0;次 for(i=1;i=n;i+) 2/n 次for(j=1;j=2*i;j+) (n)m=m+1;( 1) for(i=1;i=n;i+)2+)1) 基本if语(2*句i=2n*)i n 执行了 n/2 基本f语or(句j=2y*=i;jy+=i*n

13、j;j+执行了 一共f执or(行j=次2*数i;j1) return3*T(n-1);前as精心整理(2)intT(intn)if(n=1)return1;elseif(n1)return2*T(n/3)+n;5. 求下列问题的平凡下界，并指出其下界是否紧密。 (1)求数组中的最大元素； (2)判断邻接矩阵表示的无向图是不是完全图； (3)确定数组中的元素是否都是惟一的； (4)生成一个具有 n 个元素集合的所有子集(1)(n) 紧密？(2)( n*n)(3)( logn+n ) (先进行快排，然后进行比较查找)(4)(2n)7画出在三个数 a, b,是c 中求a中b值问题的否判定树。习题 3

14、1 假设在文本 ababcabccabccacbab 中查找模式 abccac ，写出分别采用 BF算法和 KMP算法的 串匹配过/BF 算法 #include usingnamespacestd; intBF(charS,charT)return0;？ bcaCbabc8国际象棋是是很久 就许诺可以给a这bc个 发明人任个印度人 的奖赏b。ac Shashi 个方格内只放 1粒麦粒是，第 2格 2粒否，第 3格 4 格全部放满。这个奖赏a的c最b 终结果会C是a什b 么样呢？ #include usingnamespacestd;intmain() longdoubleresult=1; d

15、oublej=1; for(inti=1;i=64;+i) j=j*2; result+=j; j+;coutresultendl;，当他把该发明献给国王时， 国王很高兴， 求以这种方式给他一些粮食：棋盘的第 1 ，第 4 格 8否粒，以此类推，直到 64 个方精心整理intindex=0;inti=0,j=0;while(Si!=0)&(Tj!=0) if(Si=Tj)i+;j+;else+index; i=index; j=0;if(Tj=0)returnindex+1;elsereturn0;intmain() chars119=ababcabccabccacbab; chars27=a

16、bccac;coutBF(s1,s2)endl;return0;/KMP 算法#include usingnamespacestd;next0=-1;for(j=1;Tj!=0;j+)/for(len=j-1;len=1;len-)/for(i=0;ilen;i+)/if(Ti!=Tj-len+i)break;if(i=len)voidGetNext(charT,intnext)/ 求模式 T 的 next 值 inti,j,len;依次求 nextj相等子串的最大长度为 j-1依次比较 T0Tlen-1 与 Tj-lenTj-1nextj=len;break;/forif(len1)精心整理

17、nextj=0;/ 其他情况，无相等子串/for intKMP(charS,charT)/求 T 在 S中的序号inti=0,j=0;intnext80;/ 假定模式最长为 80 个字符GetNext(T,next); while(Si!=0&Tj!=0)if(Si=Tj)i+;j+;elsej=nextj;if(j=-1)i+;j+;if(Tj=0)return(i-strlen(T)+1);/ 返回本趟匹配的开始位置elsereturn0;intmain() chars1=ababcabccabccacbab; chars2=abccac;coutKMP(s1,s2)endl;return

18、0;2. 分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将 6/8 化简为 3/4 #include usingnamespacestd;intmain()intn;/ 分子intm;/ 分母intfactor;/ 最大公因子intfactor1;cout 输入一个真分数的分子与分母： nm;intr=m%n; / 因为是真分数所以分母一定大于分子 factor1=m;factor=n;while(r!=0)factor1=factor;精心整理factor=r;r=factor1%factor;cout 输出该真分数的最简分数： (n/factor)/(m/factor)e

19、ndl; return0;3./ 将一个大整数看成一个数组/ 数组的奇数位对应数的 10 倍加上数组偶数对应数的本身/ 验证结果能否被 11 整除 #include usingnamespacestd; intmain()inta9=5,6,2,8,4,3,7,4,8;intresult=0;/result 为题目要求的各位之和for(inti=0;i!=9;+i)if(i%2=0)result+=ai;/i 为偶数位时，结果加上其对应数组数的本身 elseresult+=ai*10;/i为奇数位时，结果加上对应数组数的 10 倍 if(result%11=0)cout 该整数能被 11 整除

20、endl;elsecout 该整数不能被 11 整除endl;return0;4. 数字游戏 。把数字 1,2, ,9 这 9 个数字填入以下含有加、减、乘、除的四则运算式中，使 得该等式成立。要求 9 个数字均出现一次且仅出现一次，且数字 1 不能出现在乘和除的一位数中 (即排除运算式中一位数为 1 的平凡情形)。 =05. 设计算法求解 anmodm，其中 a、n 和 m均为大于 1 的整数 。(提示：为了避免 an 超出 int 型 的表示范围，应该每做一次乘法之后对 n 取模)#include usingnamespacestd; intsquare(intx)returnx*x;/

21、用递归思想intresultmod(inta,intn)if(n=0)return1;if(n%2=0)精心整理returnsquare(resultmod(a,n/2); /n 为偶数的时，取 n 的一半防止溢出 elsereturna*resultmod(a,n-1); /n 为奇数时，取 n-1 ； intmain() inta,n,m; cout 请输入 a，n,m:anm;coutendl; intresult=resultmod(a,n); coutanmodm 的结果为： result%mendl;return0;6. 设计算法，在数组 r n中删除所有元素值为 x 的元素，要求

22、时间复杂性为 O( n) ，空间复杂 性为 O(1) 。7. 设计算法，在数组 rn 中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相 对次序保持不变。#include usingnamespacestd; voiddeletere(inta,intN)intb100=0;inti,k;k=0;staticintj=0;for(i=0;iN;i+)bai+;for(i=0;i100;i+)if(bi!=0)if(bi=2)k+;aj=i;j+;for(i=0;iN-k;i+) coutaiendl;intmain()inta=1,2,1,3,2,4;deletere(a,6);精心整

23、理return0;/ 在数组查找相同的元素/ 把其中一个相同的数值的元素位置设成一个“特殊数值”/ 输出所求函数#includeusingnamespacestd;intmain()inta=1,2,1,5,3,2,9,4,5,5,3,5;inti,j;for(i=0;i12;i+)for(j=0;ji;j+)if(aj=ai)/forfor(i=0;i12;i+)coutai;coutendl;return0;8. 设表A=a1, a2, , an ，将A拆成 B和C两个表，使A中值大于等于 0的元素存入表 B，值小 于 0 的元素存入表 C，要求表 B 和 C不另外设置存储空间而利用表 A

24、的空间。/ 先对 A 进行快排/ 将大于 0的元素给 B，小于 0 的元素给 C#includeusingnamespacestd;intpartions(intl,intlow,inthigh)intprvotkey=llow;l0=llow;while(lowhigh)while(low=prvotkey)-high;llow=lhigh;while(lowhigh&llow=prvotkey)+low;lhigh=llow;llow=l0;精心整理 returnlow; voidqsort(intl,intlow,inthigh) intprvotloc; if(lowhigh) prv

25、otloc=partions(l,low,high);/ 将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1);/ 递归调用排序由 low 到 prvotloc-1 qsort(l,prvotloc+1,high);/ 递归调用排序由 prvotloc+1 到 highvoidquicksort(intl,intn)qsort(l,1,n);/ 第一个作为枢轴，从第一个排到第 n 个intmain() inta11=-2,2,32,43,-23,45,36,-57,14,27,-39;quicksort(a,11); for(inti=1;i11;i+)if(ai0)co

26、utC:ai;else coutB:ai;coutendl;return0;9. 荷兰国旗问题。要求重新排列一个由字符 R, W, B( R代表红色， W代表白色， B代表兰色， 这都是荷兰国旗的颜色)构成的数组，使得所有的 R都排在最前面， W排在其次， B 排在最后。为 荷兰国旗问题设计一个算法，其时间性能是 O(n) 。/0 代表红； 1 代表白； 2 代表蓝 #include usingnamespacestd;constintN=20; voidswap_ab(int*p,int*q)inttmp=*p;*p=*q;*q=tmp; voidprocess(inta,intn) int

27、*p,*q; p=q=a;精心整理while(p!=a+n-1)/p 向前遍历，直到便利完毕if(*(p+1)*p)q=p+1;while(*q*(q-1)swap_ab(q,q-1);-q;/q 指针后移/if+p;/whileintmain()intaN=0,2,1,2,0,1,0,2,2,1,0,1,2,1,1,0,0,1,1,2;/ 待处理的数组cout 处理后的数组序列 :endl; process(a,N);for(inti=0;iN;+i)coutai;coutendl;return0;10. 设最近对问题以 k维空间的形式出现， k维空间的两个点 p1=(x1,x2, xk)和

28、p2=(y1,y2,yk)的欧几里德距离定义为： d(p1,p2)k (yi-xi)2 。对 k维空间的最近对问题设计蛮力算法，并分析其i1时间性能。11设计蛮力算法求解小规模的线性规划问题。假设约束条件为： (1)x+y4；( 2)x+3y6； (3) x0 且 y0；使目标函数 3x+5y 取得极大值。#includeusingnamespacestd;intmain()intx,y,x0,y0;intsummax=0,temp=0;for(x0=0;x0=4;+x0)for(y0=0;(x0+y0=4)&(x0+3*y0=summax)summax=temp;x=x0;/ 符合 sum最

29、大值的 xy=y0;/ 符合 sum最大值得 y精心整理/forcoutx=xy=ysummax=summax0 的元素进行判断1.1 循环变量 i 从 1n 重复进行下述操作：1.1.1 计算矩阵 i 次方，如果矩阵对角线上有 0 的元素，则跳转到 1.21.1.2 否则 +i;1.2 如果矩阵对角线有 0 的元素，则输出该回路2 输出无解信息； 13找词游戏。要求游戏者从一张填满字符的正方形表中，找出包含在一个给定集合中的所有单 词。这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个蛮力算法14. 变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相

30、同， 只是位置有所不同，则这两个单词称为变位词。例如， eat 和 tea 是变位词。/ 判断 qwer 和 rewq 是否是变位词#include#include usingnamespacestd; intmain()chars5=qwer;chart5=rewq;for(inti=0;i!=4;+i)if(si!=t3-i)coutqwer 和 rewq 不是变位词 endl;return0;break;coutqwer 和 rewq 是变位词 endl;return0;15在美国有一个连锁店叫 7-11 店，因为这个商店以前是早晨 7 点开门，晚上 11 点关 门。有一天，一个顾客在这

31、个店挑选了四样东西， 然后到付款处去交钱。 营业员拿起计算器， 按了一些键，然后说：“总共是 $7.11 。”这个顾客开了个玩笑说： “哦？难道因为你们的店名 叫 7-11 ，所以我就要付 $7.11 吗？”营业员没有听出这是个玩笑，回答说： “当然不是，我 已经把这四样东西的价格相乘才得出这个结果的！ ”顾客一听非常吃惊，“你怎么把他们相乘 呢？你应该把他们相加才对！ ”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错 了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为 吃惊的是总和也是 $7.11 。设计蛮力算法找出这四样东西的价格各是多少？精心整理该算

32、法为：int$7.11(floata,floatb,floatc,floatd,intn)for(inti=0;i!=n;+i)for(intj=0;j!=n;+j) for(intk=0;k!=n;+k) for(intm=0;m!=n;+m) if(ai+bj+ck+dm)=7.11&ai*bj*ck*dm=7.11) coutaibjckdmendl;return0;return0;习题 41. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有 关，试说明这几个参数与分治法时间复杂性之间的关系 。2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的

33、规模之和小于原问题的规 模时，算法的时间复杂性可达到 O(n) 。O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a*O(N/2)+(a+1)*x 由此可知，时间复杂度可达到 O(n);3. 分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例 子，并阐述这种分治和包含递归的分治的主要不同。不一定导致递归。 如非递归的二叉树中序遍历。这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。4. 对于待排序序列 (5,3,1,9) ，分别画出归并排序和快速排序的递归运行轨迹。 归

34、并排序：第一趟 第二趟 第三趟：(5,3)(1,9 )；：(3,5,1,9 )；：(1,3,5,9 )；快速排序：第一趟：5(,3,1,9)；/5 为哨兵，比较 9和 5第二趟：5(1,3,9)；/ 比较 1和 5，将 1挪到相应位置；第三趟：5(1,3,9);/ 比较 3和 5；第四趟：(1,3,5,9);5. 设计分治算法求一个数组中的最大元素，并分析时间性能/ 简单的分治问题/ 将数组均衡的分为“前” ，“后”两部分/ 分别求出这两部分最大值，然后再比较这两个最大值#include usingnamespacestd;externconstintn=6;/ 声明精心整理intmain()

35、intan=0,6,1,2,3,5;/ 初始化intmid=n; intnum_max1=0,num_max2=0;for(inti=0;inum_max1) num_max1=ai;for(intj=n+1;jnum_max2) num_max2=aj; if(num_max1=num_max2) cout 数组中的最大元素： num_max1endl;elsecout 数组中的最大元素： num_max2endl;return0;时间复杂度： O(n)6. 设计分治算法，实现将数组 A n中所有元素循环左移 k 个位置,要求时间复杂性为 O(n)， 空间复杂性为 O(1) 。例如，对 ab

36、cdefgh 循环左移 3 位得到 defghabc 。/ 采用分治法/ 将数组分为 0-k-1 和 k-n-1 两块/ 将这两块分别左移/ 然后再合并左移#include usingnamespacestd;voidLeftReverse(char*a,intbegin,intend) for(inti=0;i(end-begin+1)/2;i+)/ 交换移动 inttemp=abegin+i; abegin+i=aend-i;aend-i=temp; voidConverse(char*a,intn,intk)LeftReverse(a,0,k+1);LeftReverse(a,k,n+1

37、);LeftReverse(a,0,n-1);for(inti=0;in;i+) coutai;coutendl;精心整理intmain() chara7=a,b,c,d,e,f,g;Converse(a,7,3);return0;7. 设计递归算法生成 n 个元素的所有排列对象。#include usingnamespacestd; intdata100;/ 在 m个数中输出 n 个排列数( n=m) voidDPpl(intnum,intm,intn,intdepth) if(depth=n)for(inti=0;in;i+) coutdatai; coutendl;for(intj=0;

38、jm;j+)if(num&(1j)=0)datadepth=j+1;DPpl(num+(1j),m,n,depth+1);/forintmain()DPpl(0,5,1,0);DPpl(0,5,2,0);DPpl(0,5,3,0);DPpl(0,5,4,0);DPpl(0,5,5,0);return0;8. 设计分治算法求解一维空间上 n 个点的最近对问题。参见 4.4.1 最近对问题的算法分析及算法实现9. 在有序序列( r 1, r 2, , r n)中，存在序号 i(1in)，使得 ri =i 。请设计一个分治算法找到 这个元素，要求算法在最坏情况下的时间性能为 O(log 2n) 。/

39、 在有序数组中/ 采用二分法查找符合条件的元素#include usingnamespacestd;voidFindnum(int*a,intn)精心整理intlow=0;inthigh=n-1;while(low=high)intmid=(low+high)/2;if(amid=mid)cout 这个数是： amidmid)high=mid-1;elselow=mid+1;intmain()inta7=1,0,2,5,6,7,9;Findnum(a,7);return0;时间复杂度为 O(log 2n) 。10. 在一个序列中出现次数最多的元素称为众数。 请设计算法寻找众数并分析算法的时间复

40、杂 性。/ 先对序列进行快速排序/ 再进行一次遍历/ 输出众数的重复次数#includeusingnamespacestd;intpartions(intb,intlow,inthigh)intprvotkey=blow;b0=blow;while(lowhigh)while(low=prvotkey)-high;blow=bhigh;while(lowhigh&blow=prvotkey)+low;bhigh=blow;blow=b0;returnlow;voidqsort(intl,intlow,inthigh)精心整理intprvotloc;if(lowhigh)prvotloc=par

41、tions(l,low,high);/ 将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1);/ 递归调用排序由 low 到 prvotloc-1qsort(l,prvotloc+1,high);/ 递归调用排序由 prvotloc+1 到 highvoidquicksort(intl,intn)qsort(l,1,n);/ 第一个作为枢轴，从第一个排到第 n 个intmain()inta10=1,2,3,5,3,3,3,2,5,1;inti=0;intcount=0;intmax=0;/max 表示出现的次数qsort(a,0,10);while(i10)intj;j=i

42、+1;if(ai=aj&imax)max=count;count=0;/whilecout 重复次数： maxendl;return0;时间复杂度 nlog(n)11. 设M是一个 nn的整数矩阵，其中每一行(从左到右)和每一列(从上到下)的元素都 按升序排列。设计分治算法确定一个给定的整数 x 是否在 M中，并分析算法的时间复杂性。12. 设 S是 n(n为偶数)个不等的正整数的集合，要求将集合 S划分为子集 S1和 S2，使得 | S1|=| S2|= n/2 ，且两个子集元素之和的差达到最大。/ 先用快速排序进行一趟排序/ 如果 s1(大的数集)的的个数大于 n/2/ 将( i=n/2-

43、low-1 )个最小的数排到后面/ 如果 s1(大的数集)的的个数小于 n/2精心整理/ 将 s2(小的数集) n/2-low-1 排到前面/ 将排好的数组的前 n/2 个数赋值给 s1/ 将排好的数组的后 n/2 个数赋值给 s2 #include usingnamespacestd;constintn=8; voidpartions(inta,intlow,inthigh)/ 进行一趟快排intprvotkey=alow;a0=alow;while(lowhigh) while(lowhigh&ahigh=prvotkey) -high;alow=ahigh;while(low=prvot

44、key)+low;ahigh=alow;alow=prvotkey;/ 如果 s1(大的数集)的的个数大于 n/2 if(low=n/2)for(inti=0;i=n/2-low-1;+i)for(intj=0;jn-i;+j) if(ajaj+1) inttemp=aj;aj=aj+1;aj+1=temp;/for/if/ 如果 s1(大的数集)的的个数小于 n/2 elsefor(inti=0;i=n/2-low-1;+i)for(intk=n-1;kak-1) inttemp1=ak;ak=ak-1;精心整理ak-1=temp1;/forintmain() intan=1,3,5,9,6

45、,0,-11,-8; partions(a,0,n-1);for(inti=0;in;+i)if(i4)cout 属于子集 s1 的： endl;coutaiendl;elsecout 属于子集 s2 的： endl;coutaiendl;return0;13. 设 a1, a2, , an是集合1,2, , n的一个排列，如果 iaj ，则序偶 ( ai, aj )称为该排 列的一个逆序。例如， 2,3,1 有两个逆序： (3,1) 和(2,1) 。设计算法统计给定排列中含有逆序的个 数。/ 用归并进行排序/ 当一个子集的一个数大于第二个子集的一个数，为逆序，即aiaj/ 则逆序数为 end

46、-j+1; #include usingnamespacestd; intcount;voidMerge(inta,inta1,intbegin,intmid,intend)/ 合并子序列 inti=begin,j=mid+1,k=end; while(i=mid&j=end) if(ai=aj)a1k+=ai+;/ 取 ai 和 aj 中较小者放入 r1kelsea1k+=aj+;count+=(end-j+1); while(i=mid)精心整理a1k+=ai+;while(j=end)a1k+=aj+;voidMergeSort(inta,intbegin,intend)intmid,a11000; if(begin=end)return;elsemid=(begin+end)/2;MergeSort(a,begin,mid);MergeSort(a,mid+1,end);Merge(a,a1,begin,mid,end);intmain()inta6=6,5,4,3,2,1;count=0;MergeSort(a,0,6);coutcountendl;return0;14. 循环赛日程安排问题。设有 n=2k 个选手要进行网球循环赛，要求设计一个满足以下要求的 比赛日程表：