算法设计与分析习题答案1 6章

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

2、算法)用得不就是除法而就是减法。请用伪代码描述这个版本得欧几里德算法1、r=m-n2、循环直到r=0123 输出1.2、2、2、3m=nn=rr=m-n(Leonhard Euler ,1707 1783)3 .设计算法求数组中相差最小得两个元素(称为最接近数)得差。要求分别给出伪代 码与C+描述。/采用分治法/对数组先进行快速排序 /在依次比较相邻得差#i nclude using n ames pace std; int p arti on s(i nt b,i nt low,i nt high) int p rvotkey=blow; b0=blow; while (lowvhigh)

3、while (low=p rvotkey) -high; blow=bhigh; while (lowhigh&blow=p rvotkey) +low;bhigh=blow; blow=b0; return low;void qsort(int l,int low,int high)int prvotloc; if(lowhigh)将第一次排序得结果作为枢轴 递归调用排序 由 low 到 prvotloc-1 递归调用排序 由 prvotloc+1 到 high/ prvotloc=partions(l,low,high); qsort(l,low,prvotloc-1); / qsort(

4、l,prvotloc+1,high); /void quicksort(int l,int n)第一个作为枢轴，从第一个排到第 n 个qsort(l,1,n); /int main()int a11=0,2,32,43,23,45,36,57,14,27,39;int value=0;/将最小差得值赋值给 valuefor (int b=1;b11;b+) coutab ; coutendl;quicksort(a,11);for(int i=0;i!=9;+i)if( (ai+1-ai)=(ai+2-ai+1) ) value=ai+1-ai;else value=ai+2-ai+1;cou

5、tvalueendl;return 0;4 设数组 an 中得元素均不相等， 设计算法找出 an 中一个既不就是最大也不就是最 小得元素，并说明最坏情况下得比较次数。要求分别给出伪代码与C+描述。#include using namespace std; int main()int a=1,2,3,6,4,9,0;int mid_value=0;/将“既不就是最大也不就是最小得元素”得值赋值给它for(int i=0;i!=4;+i)if(ai+1ai&ai+1ai+2)mid_value=ai+1;coutmid_valueendl;break;else if(ai+1ai+2)mid_va

6、lue=ai+1;coutmid_valueendl; break;/forreturn 0;n 至少为多大时， n 个“ 1 ”组成得整数能被 2013 整除。5、编写程序，求 #include using namespace std;int main()double value=0;for(int n=1;n=10000 ;+n)value=value*10+1;if(value%2013=0)coutn 至少为 :nendl; break;/forreturn 0;6、计算n值得问题能精确求解吗？编写程序，求解满足给定精度要求得 #include using namespace std;

7、int main ()double a,b;double arctan(double x);/ 声明 a = 16 、 0*arctan(1/5 、 0);b = 4 、 0*arctan(1/239);cout PI= a-b 1e-15)/ 定义精度范围f = e/i;/f 就是每次 r 需要叠加得方程r = (i%4=1)?r+f:r-f;e = e*sqr;/e 每次乘于 x 得平方i+=2;/i 每次加 2/whilereturn r;7、圣经上说：神 6 天创造天地万有，第 7 日安歇。为什么就是 6天呢？任何一个自然 数得因数中都有 1 与它本身，所有小于它本身得因数称为这个数得

8、真因数，如果一个自然 数得真因数之与等于它本身， 这个自然数称为完美数。 例如， 6=1+2+3 ，因此 6 就是完美数。 神 6 天创造世界，暗示着该创造就是完美得。设计算法，判断给定得自然数就是否就是完 美数#includeusing namespace std;int main()int value, k=1;cinvalue;for (int i = 2;i!=value;+i)while (value % i = 0 )k+=i;/k 为该自然数所有因子之与 value = value/ i;/for if(k=value) cout 该自然数就是完美数 endl;elsecout

9、该自然数不就是完美数 endl;return 0;8、有 4 个人打算过桥， 这个桥每次最多只能有两个人同时通过。她们都在桥得某一端，并且就是在晚上，过桥需要一只手电筒，而她们只有一只手电筒。这就意味着两个人过桥 后必须有一个人将手电筒带回来。每个人走路得速度就是不同得：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路得速度等于乙过桥且甲回来 丙过桥且甲回来 丁过桥甲,甲,甲,其中较慢那个人得速度，问题就是她们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电得工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟： 第二趟： 第一趟：

10、 一共用时19小时9 欧几里德游戏：开始得时候，白板上有两个不相等得正整数，两个玩家交替行动， 每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上得数字得差，而且这 个数字必须就是新得，也就就是说，与白板上得任何一个已有得数字都不相同，当一方再 也写不出新数字时，她就输了。请问，您就是选择先行动还就是后行动？为什么？ 设最初两个数较大得为a,较小得为b,两个数得最大公约数为factor 。则最终能出现得数包括 ：factor, factor*2, factor*3, 、, factor*(a/factor)=a 共 a/factor 个。如果a/factor就是奇数，就选择先行动；否

11、则就后行动。习题21.如果 Ti(n) =O(f (n), T2(n)=O(g(n)，解答下列问题： (1 )证明加法定理：Ti(n)+ T2(n)=max O(f (n), O(g(n);(2) 证明乘法定理：T1(n)x T2(n)=O(f (n)x O(g(n);(3) 举例说明在什么情况下应用加法定理与乘法定理,1 (1)(2) I(3) 比如在for (f(n)for(g( n)中应该用乘法定理如果在“讲两个数组合并成一个数组时”，应当用加法定理(2)int Q(int n)if (n = 1)return 1;2 考虑下面得算法，回答下列问题：算法完成什么功能？算法得基本语句就是什

12、么？基 本语句执行了多少次？算法得时间复杂性就是多少？(1)(1) int完成得就是1-n得平方与 基本语句：s+=i*i，执行了 n次时间复杂度O (n)forint完成得就是n; iffl+得平方基本语S： + i return Q(n -1) + 2 * n - 1，执行了else 次时t间间复杂度 O (n)return Q(n-1) + 2 * n - 1;分析以下程序段中基本语句得执行次数就是多少，要求列出计算公式。3、(1) for (i = 1; i = n; i+)if (2*i = n)for (j = 2*i; j = n; j+)y = y + i * j ；(2) m

13、 = 0;for (i = 1; i = n; i+)for (j = 1; j = 2*i; j+) m=m+1;(1) 基本语句2*i1)return 3*T( n-1);int T(i nt n)if(n=1)return 1;else if(n 1)return 2*T( n/3)+n;、求下列问题得平凡下界，并指出其下界就是否紧密。(1) 求数组中得最大元素；(2) 判断邻接矩阵表示得无向图就是不就是完全图；(3) 确定数组中得元素就是否都就是惟一得；(4) 生成一个具有n个元素集合得所有子集Q( n)紧密？Q(n*n)Q(logn+n )(先进行快排，然后进行比较查找)Q(2n)(

14、1)(2)(3)(4)7.画出在三个数a, b, cc合这个发achi发明得,SS&国际象棋就是很久以前由一个印度人 王很高兴，就 粮食：棋盘得第1个方格内只放想要得b赏。1粒麦粒否第2格2粒就以此类推，直到64个方格全部放满。这个奖赏得最终结果会就是什么样呢bn#in cludeusing n ames pace std;int mai n()long double result=1;double j=1;for(i nt i=1;i=64;+i)哋把该发明献给国王时，国求以这种方式给她一些4粒，否第4格8粒，j=j*2; result+=j; j+;coutresultendl; retu

15、rn 0;习题 31 假设在文本 ababcabccabccacbab 中查找模式 abccac ，写出分别采用 BF 算法与 KMP 算法得串匹配过/BF 算法#includeusing namespace std;int BF(char S, char T)int index = 0;int i = 0, j = 0;while (Si != 0) & (Tj != 0)if (Si = Tj)i+; j+;else +index; i = index; j = 0;if (Tj = 0)return index + 1;elsereturn 0;int main()char s119=a

16、babcabccabccacbab;char s27=abccac;cout BF( s1, s2) endl;return 0;/KMP 算法#include using namespace std; void GetNext(char T , int next ) int i, j, len;next0 = -1;for (j = 1; Tj!=0; j+)for (len = j - 1; len = 1; len-)for (i = 0; i len; i+)if (Ti != Tj-len+i) break; if (i = len)/求模式 T 得 next 值/ 依次求 next

17、j/ 相等子串得最大长度为 j-1/ 依次比较 T0Tlen-1 与 Tj-lenTj-1nextj = len; break;/forif (len 1) nextj = 0;/for/其她情况，无相等子串int KMP(char S , char T )int i = 0, j = 0;int next80;GetNext(T, next);while (Si != 0 & Tj != 0)if (Si = Tj)i+; j+;else j = nextj;if (j = -1) i+; j+;if (Tj = 0) return (i - strlen(T) +1); else retu

18、rn 0;int main()/求 T 在 S 中得序号/假定模式最长为 80 个字符/返回本趟匹配得开始位置char s1=ababcabccabccacbab;char s2=abccac; coutKMP(s1,s2)endl;return 0;6/8 化简为2、分式化简。设计算法，将一个给定得真分数化简为最简分数形式。例如，将 3/4。#include using namespace std; int main() int n;/ 分子int m;/ 分母int factor;/ 最大公因子int factor1;endl;coutnm;int r = m % n; /因为就是真分数

19、所以分母一定大于分子 factor1=m;factor=n; while (r != 0) factor1 =factor; factor = r;r = factor1% factor;cout 输出该真分数得最简分数： (n/factor)/(m/factor)endl;return 0;3. 设计算法，判断一个大整数能否被11 整除。可以通过以下方法：将该数得十进制表示从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其与能否被 11 整除。 例如，将 562843748 分割成 5,62,84,37,48，然后判断 (5+62+84+37+48) 能否被 11 整除/将一个大整

20、数瞧成一个数组/数组得奇数位对应数得 10 倍加上数组偶数对应数得本身/验证结果能否被 11 整除#includeusing namespace std;int main()int a9=5,6,2,8,4,3,7,4,8;int result=0; /result 为题目要求得各位之与for(int i=0;i!=9;+i)if(i%2=0)result+=ai; /i 为偶数位时，结果加上其对应数组数得本身elseresult+=ai*10;/i 为奇数位时，结果加上对应数组数得10 倍11 整除e ndl;11 整除e ndl; if(result%11=0) cout 该整数能被els

21、ecout 该整数不能被return 0;4、 数字游戏 。把数字 式中，使得该等式成立。要求 与除得一位数中(即排除运算式中一位数为1,2,9这9个数字填入以下含有加、减、乘、除得四则运算9 个数字均出现一次且仅出现一次，且数字 1 不能出现在乘1 得平凡情形) 。X +-= 05、设计算法求解an mod m,其中a、n与m均为大于1得整数。(提示：为了避免 an 超出 int 型得表示范围，应该每做一次乘法之后对 n 取模)#include using namespace std; int square(int x) return x*x;/用递归思想int resultmod(int

22、a, int n)if(n= 0)return 1;if(n%2 = 0)return square(resultmod(a, n/2);/n 为偶数得时,取 n 得一半防止溢出 elsereturn a*resultmod(a, n-1); /n 为奇数时,取 n-1 ；int main()int a, n, m;cout请输入 a，n, m:anm;coutendl;int result = resultmod(a, n);coutaAn mod m 得结果为： result % mendl; return 0;6、 设计算法，在数组rn中删除所有元素值为 x得元素，要求时间复杂性为0(n

23、),空 间复杂性为 O(1)。7. 设计算法，在数组rn中删除重复得元素，要求移动元素得次数较少并使剩余元素间得相对次序保持不变。#include using namespace std; void deletere(int a,int N) int b100=0;int i,k;k=0;static int j=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;int main()int a=1,2,1,3,2,4; deletere(a,6); re

24、turn 0;/在数组查找相同得元素/把其中一个相同得数值得元素位置设成一个“特殊数值” /输出所求函数#includeusing namespace std;int main()int a=1,2,1,5,3,2,9,4,5,5,3,5;int i,j;for( i=0;i12;i+)for(j=0;ji;j+) if(aj=ai) ai=64787250;/ 设一个数组不存在得数值IIforfor(i=0;i12;i+)if(ai!=64787250)coutai ;coutendl;return 0;8、设表A=ai, a2,an，将A拆成B与C两个表，使A中值大于等于0得元素存 入表B

25、,值小于0得元素存入表 C,要求表B与C不另外设置存储空间而利用表 A得空间。 /先对 A 进行快排II将大于0得元素给B,小于0得元素给C#include using namespace std;int partions(int l,int low,int high)int prvotkey=llow; l0=llow;while (lowhigh)while (low=prvotkey)-high;llow=lhigh;while (lowhigh&llow=prvotkey) +low;lhigh=llow;llow=l0;return low;void qsort(int l,int

26、low,int high)int prvotloc;if(lowhigh)prvotloc=partions(l,low,high);/ 将第一次排序得结果作为枢轴qsort(l,low,prvotloc-1); / 递归调用排序 由 low 到 prvotloc-1 qsort(l,prvotloc+1,high); / 递归调用排序 由 prvotloc+1 到 high void quicksort(int l,int n)qsort(l,1,n); /第一个作为枢轴，从第一个排到第n个int main()int a11=-2,2,32,43,-23,45,36,-57,14,27,-3

27、9; quicksort(a,11);for(int i=1;i11;i+)if(ai0)coutC: ai ;elsecoutB: ai ;coutendl;return 0;9、荷兰国旗问题。要求重新排列一个由字符 R, W, B ( R代表红色，W代表白色，B 代表兰色，这都就是荷兰国旗得颜色)构成得数组，使得所有得R都排在最前面， W排在其次， B 排在最后。为荷兰国旗问题设计一个算法，其时间性能就是O(n)。/0 代表红； 1 代表白； 2 代表蓝#include using namespace std;const int N = 20;void s ( int *p , int *

28、q )int tmp = *p; *p = *q;*q = tmp;void process ( int a, int n )int *p, *q; p = q = a;while ( p != a+n-1 ) /p 向前遍历，直到便利完毕if ( *(p+1) *p )q = p+1;while ( *q *(q-1) )s ( q, q-1 );-q; /q指针后移 /if+P； /whileint mai n()int aN = 0, 2, 1,2, 0, 1,0, 2, 2, 1,0, 1,2, 1, 1, 0, 0, 1, 1,2; / 待处理得数组cout 处理后得数组序列:end

29、l; p rocess ( a, N );for (i nt i=0; i N; +i )cout ai ;cout en dl;return 0;10、设最近对问题以k维空间得形式出现，k维空间得两个点P1=(X1, X2,Xk)与p2=(y1, y2,yk)得欧几里德距离定义为：。对k维空间得最近对问题设计蛮力算法，并分析其时间性能。(1) x+yw 4; (2)11设计蛮力算法求解小规模得线性规划问题。假设约束条件为： x+3y 0且y0;使目标函数3x+5y取得极大值。#in clude using n ames pace std;int mai n()int x,y,xO,yO;in

30、t summax=0,te mp=0;for(x0=0;x0=4;+x0)for(y0=0;(x0+y0=4) &(x0+3*y0=summax)summax=te mp;x=x0;/符合sum最大值得xy=y0;/符合sum最大值得y/forcoutx= x y= y summax= summax0得元素进行判断1、11、1、循环变量i从1 n重复进行下述操作：1、1计算矩阵i次方，如果矩阵对角线上有0得元素，则跳转到1、21、2 否则 +i;1、2如果矩阵对角线有0得元素，则输出该回路2输出无解信息；13找词游戏。要求游戏者从一张填满字符得正方形表中，找出包含在一个给定集合中得 所有单词。

31、这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个 蛮力算法14、变位词。给定两个单词，判断这两个单词就是否就是变位词。如果两个单词得字母完全相同，只就是位置有所不同，则这两个单词称为变位词。例如，eat与tea就是变位词。/判断qwer与rewq就是否就是变位词#in clude#in cludeusing n ames pace std;int mai n()char s5=qwer; char t5=rewq; for(i nt i=0;i!=4;+i) if(si!=t3-i)coutqwer 与 rewq 不就是变位词endl; return 0;break;cou

32、tqwer 与 rewq 就是变位词endl; return 0;15.在美国有一个连锁店叫7-11店，因为这个商店以前就是早晨7点开门，晚上11点关门。有一天，一个顾客在这个店挑选了四样东西，然后到付款处去交钱。营业员拿起计算器，按了一些键，然后说：“总共就是$7、11。”这个顾客开了个玩笑说：“哦？难道因为您们得店名叫7-11,所以我就要付$7、11吗？”营业员没有听出这就是个玩笑，回答说：“当然不就是，我已经把这四样东西得价格相乘才得出这个结果 得！”顾客一听非常吃惊，“您怎么把她们相乘呢？您应该把她们相加才对！”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将

33、结果重算了一遍，将这四样东西得价格加在一起，然而，令她俩更为吃惊得就是总与也就是11”设计蛮力算法找出这四样东西得价格各就是多少？ 该算法为：int $7 、 11(float a,float b,float c,float d,int n)for(int i=0;i!=n;+i)for(int j=0;j!=n;+j)for(int k=0;k!=n;+k)for(int m=0;m!=n;+m)if(ai+bj+ck+dm)=7 、11 & a i*bj*ck*dm=7、11)coutaibjckdmendl;return 0;return 0;习题 41、 分治法得时间性能与直接计算最小

34、问题得时间、合并子问题解得时间以及子问题得个数有关，试说明这几个参数与分治法时间复杂性之间得关系 。O(n)。2、证明：如果分治法得合并可以在线性时间内完成，则当子问题得规模之与小于原 问题得规模时，算法得时间复杂性可达到O(N)=2*O(N/2)+x O(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、分治策略一定导致递归吗？如果就是，请解释原因。如果不就是，给出一个不包含 递归得分治例子，并阐述这种分治与包含递归得分治得主要不同。不一定导致递归。 如非递归得二叉树中序遍

35、历。 这种分治方法与递归得二叉树中序遍历主要区别就是：应用了栈这个数据结构。5,3)(1,9)；3,5,1,9)；1,3,5,9)；4、对于待排序序列 (5, 3, 1, 9) ，分别画出归并排序与快速排序得递归运行轨迹。 归并排序： 第一趟： 第二趟： 第三趟：快速排序：5( ,3,1,9)； /5为哨兵，比较 9与 55(1,3, ,9)；/比较 1与 5，将 1挪到相应位置；1,3, ,9) ;/比较 3 与 5；51,3,5,9);5、 设计分治算法求一个数组中得最大元素，并分析时间性能。 /简单得分治问题/将数组均衡得分为“前” ，“后”两部分 /分别求出这两部分最大值，然后再比较这

36、两个最大值 #include第一趟：第二趟：第三趟：第四趟：using namespace std; extern const int n=6;/ 声明 int main()int an=0,6,1,2,3,5;/ 初始化int mid=n/2;int num_max1=0,num_max2=0; for(int i=0;inum_max1) num_max1=ai;for(int j=n/2+1;jnum_max2)num_max2=aj; if(num_max1=num_max2) cout 数组中得最大元素： else cout 数组中得最大元素： return 0;时间复杂度： O(

37、n)6、设计分治算法，实现将数组An中所有元素循环左移 k个位置，要求时间复杂性为 0(n),空间复杂性为 0(1)。例如，对 abcdefgh循环左移3位得到defghabc。/ 采用分治法 / 将数组分为 0-k-1 与 k-n-1 两块 / 将这两块分别左移 / 然后再合并左移 #include using namespace std;void LeftReverse(char *a, int begin, int end)num_max1endl;num_max2endl;for(int i=0;i(end-begin+1)/2;i+)/int temp=abegin+i;abegin

38、+i=aend-i;aend-i=temp;交换移动void Converse(char *a,int n,int k)LeftReverse(a, 0, k-1);LeftReverse(a, k, n-1);LeftReverse(a, 0, n-1);for(int i=0;in;i+) coutai ; coutendl;int main()char a7=a,b,c,d,e,f,g;Converse(a,7,3);return 0;7、设计递归算法生成 n 个元素得所有排列对象。 #include using namespace std;int data100;/在 m 个数中输出

39、n 个排列数( n=m ) void DPpl(int num,int m,int n,int depth) if(depth=n)for(int i=0;in;i+) coutdatai ; coutendl;for(int j=0;jm;j+)if(num&(1j)=0) datadepth=j+1; DPpl(num+(1j),m,n,depth+1);/for int main() 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); return 0;8、 设计分治算法求解一维空间上 n 个点得最

40、近对问题。 参见 4、4、1 最近对问题得算法分析及算法实现9、在有序序列(门，2,rn)中，存在序号i ( K i n),使得ri=i。请设计一个分治算 法找到这个元素，要求算法在最坏情况下得时间性能为O(log2n)。/ 在有序数组中/ 采用二分法查找符合条件得元素#include using namespace std; void Findnum(int *a,int n) int low=0;int high=n-1; while(low=high)int mid=(low+high)/2; if(amid=mid) cout 这个数就是： amidmid) high=mid-1;el

41、se low=mid+1;int main()int a7=1,0,2,5,6,7,9;Findnum(a,7);return 0;时间复杂度为 O(log 2n)。10、 在一个序列中出现次数最多得元素称为众数。请设计算法寻找众数并分析算法得 时间复杂性。/ 先对序列进行快速排序/ 再进行一次遍历/ 输出众数得重复次数#include using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (lowhigh)while (low=prvotkey) -high;blow=b

42、high;while (lowhigh&blow=prvotkey) +low;bhigh=blow;blow=b0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh)prvotloc=partions(l,low,high); / 将第一次排序得结果作为枢轴 qsort(l,low,prvotloc-1); / 递归调用排序 由 low 到 prvotloc-1 qsort(l,prvotloc+1,high); / 递归调用排序 由 prvotloc+1 到 high void quicksort(in

43、t l,int n)qsort(l,1,n); / 第一个作为枢轴 ，从第一个排到第 n 个int main()int a10=1,2,3,5,3,3,3,2,5,1;int i=0;int count=0;int max=0;/max 表示出现得次数qsort(a,0,10);while(i10)int j;j=i+1;if(ai=aj&imax)max=count;count=0;/while cout 重复次数： maxendl;return 0;时间复杂度 nlog（n）11、设M就是一个n X n得整数矩阵，其中每一行（从左到右）与每一列（从上到下） 得元素都按升序排列。设计分治算法

44、确定一个给定得整数 x 就是否在 M 中，并分析算法得 时间复杂性。S 划分为子集 S1 与12 、 设 S 就是 n （ n 为偶数）个不等得正整数得集合，要求将集合S2,使得I Si|=| S2|= n/2,且两个子集元素之与得差达到最大。/先用快速排序进行一趟排序n/2 n/2-low-1 排到前面 n/2 个数赋值给 s1 n/2 个数赋值给 s2如果si （大得数集）得得个数大于 n/2 /将（ i=n/2-low-1 ）个最小得数排到后面 如果si （大得数集）得得个数小于/将s2 （小得数集）/将排好得数组得前 /将排好得数组得后#include using namespace

45、std;const int n=8;void partions（int a,int low,int high）/进行一趟快排int prvotkey=alow; a0=alow; while （lowhigh）while (lowhigh&ahigh=prvotkey) -high;alow=ahigh;while (low=prvotkey) +low;ahigh=alow;alow=prvotkey;如果s1 (大得数集)得得个数大于 n/2if(low=n/2)for(int i=0;i=n/2-low-1;+i)for(int j=0;jn-i;+j)if(ajaj+1)/forint

46、 temp=aj; aj=aj+1; aj+1=temp;/ifs1 (大得数集)得得个数小于n/2/如果elsefor(int i=0;i=n/2-low-1;+i)for(int k=n-1;kak-1)int temp1=ak;ak=ak-1; ak-1=temp1;/forint main()int an=1,3,5,9,6,0,-11,-8; partions(a,0,n-1);for(int i=0;in;+i)if(i4)cout 属于子集 s1 得： endl; coutaiendl;elsecout属于子集 s2 得：endl; coutaiendl;13 、return 0;设ai, 32,an就是集合1,2,n得一个排列，如果ia