算法设计与分析(第2版)-王红梅-胡明-习题答案文档格式.doc

1、&bhigh=prvotkey） -high; blow=bhigh;blow=prvotkey） +low; bhigh=blow;blow=b0;return low;void qsort（int l,int low,int high）int prvotloc;if（low prvotloc=partions（l,low,high）; /将第一次排序的结果作为枢轴 qsort（l,low,prvotloc-1）; /递归调用排序 由low 到prvotloc-1 qsort（l,prvotloc+1,high）; /递归调用排序 由 prvotloc+1到 highvoid quickso

2、rt（int l,int n）qsort（l,1,n）; /第一个作为枢轴 ，从第一个排到第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 ;endl;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;valuereturn 0;4 设数组an中的元素均不相等，设计算法找出an中一个既

3、不是最大也不是最小的元素，并说明最坏情况下的比较次数。#includeai&ai+1ai+2） mid_value=ai+1; coutmid_valuebreak;else if（ai+1 cout /for 5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。 double value=0; for（int n=1;n=10000 ;+n） value=value*10+1; if（value%2013=0）n至少为: break; /for return 0;6. 计算值的问题能精确求解吗？编写程序，求解满足给定精度要求的值int main （） double a,b

4、; 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 /while return r;7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6

5、=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 int value, k=1; cinvalue; for （int i = 2;=value; while （value % i = 0 ） k+=i;/k为该自然数所有因子之和 value = value/ i; if（k=value） cout该自然数是完美数 else该自然数不是完美数return 0;8. 有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带

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

7、了。请问，你是选择先行动还是后行动？为什么？设最初两个数较大的为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）=maxO（f （n）, O（g（n）；（2）证明乘法定理：T1（n）T2（n）=O（f （n）O（g（n）；（3）举例说明在什么情况下应用加法定理和乘法

8、定理。,（1）（2）（3）比如在 for（f（n）for（g（n）中应该用乘法定理如果在“讲两个数组合并成一个数组时”，应当用加法定理（1）int Stery（int n） int S = 0; for （int i = 1; i = n; i+） S = S + i * i; return S;（2）int Q（int n） if （n = 1） return 1; else return Q（n-1） + 2 * n - 1;2考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本语句执行了多少次？算法的时间复杂性是多少？（1） 完成的是1-n的平方和基本语句：s+=i

9、*i，执行了n次时间复杂度O（n）（2） （2）完成的是n的平方return Q（n-1） + 2 * n 1，执行了n次3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。（1）for （i = 1;if （2*i = n） for （j = 2*i; j j+） y = y + i * j；（2）m = 0;for （i = 1; for （j = 1;= 2*i; m=m+1; （1） 基本语句2*i1）return 3*T（n-1）;int T（int n） return 2*T（n/3）+n;5. 求下列问题的平凡下界，并指出其下界是否紧密。（1）求数组中的最大元素；

10、（2）判断邻接矩阵表示的无向图是不是完全图；（3）确定数组中的元素是否都是惟一的；（4）生成一个具有n个元素集合的所有子集（1） （n） 紧密？（2） （n*n）（3） （logn+n）（先进行快排，然后进行比较查找）（4） （2n）7画出在三个数a, b, c中求中值问题的判定树。abc是否Cac8国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢

11、？ long double result=1; double j=1; for（int i=1;i=64; j=j*2; result+=j; j+; coutresult习题31 假设在文本ababcabccabccacbab中查找模式abccac，写出分别采用BF算法和KMP算法的串匹配过/BF算法int BF（char S, char T） int index = 0; int i = 0, j = 0; while （Si != 0） & （Tj !） if （Si = Tj） i+; j+; else +index; i = index; j = 0; if （Tj = ） retu

12、rn index + 1; else return 0;char s119=char s27= cout BF（ s1, s2） = 1; len-） /相等子串的最大长度为j-1 for （i = 0; len; i+） /依次比较T0Tlen-1与Tj-lenTj-1 if （Ti != Tj-len+i） break;if （i = len） nextj = len; break;/forif （len 1） nextj = 0; /其他情况，无相等子串int KMP（char S , char T ） /求T在S中的序号int next80; /假定模式最长为80个字符 GetNext

13、（T, next）; while （Si ! & Tj !）if （Si = Tj） i+; j+; else j = nextj; if （j = -1） i+; ） return （i - strlen（T） +1）; /返回本趟匹配的开始位置else char s1=char s2=KMP（s1,s2）m; int r = m % n;/因为是真分数 所以分母一定大于分子 factor1=m;factor=n;while （r != 0） factor1 =factor; factor = r; r = factor1% factor;输出该真分数的最简分数：（n/factor）/（m/

14、factor）3. 设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数的十进制表示从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。例如，将562843748分割成5,62,84,37,48，然后判断（5+62+84+37+48）能否被11整除/将一个大整数看成一个数组/数组的奇数位对应数的10倍加上数组偶数对应数的本身/验证结果能否被11整除 int a9=5,6,2,8,4,3,7,4,8;int result=0; /result为题目要求的各位之和for（int i=0; if（i%2=0） result+=ai; /i 为偶数位时，结果加上其

15、对应数组数的本身 else result+=ai*10; /i 为奇数位时，结果加上对应数组数的10倍 if（result%11=0）该整数能被11整除else coutacout int result = resultmod（a, n）;an mod m的结果为： result % m return 0;6. 设计算法，在数组rn中删除所有元素值为x的元素，要求时间复杂性为O（n），空间复杂性为O（1）。7. 设计算法，在数组rn中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。void deletere（int a,int N）int b100=0;int i,k;k=0;static int j=0;for（i=0;N;i+）bai+;100; if（bi!=0）if（bi=2）k+;aj=i;j+;N-k;aiint a=1,2,1,3,2,4;deletere（a,6）;/在数组查找相同的元素/把其中一个相同的数值的元素位置设成一个“特殊数值”/输出所求函数i