计算机算法设计与分析(第三版)课后习题答案详解

1、第1章算法概述习题1-1函数的浙近表达式求下列蚩数的渐近表达式二3z?- + 10m;?/104-2,i： 21 + 1/小 lag/-; lOzgS*。分析与解答：3/+ 1(加亠(J(沪片,r/104 2-=(.)(20:21 -p l y m < K1)；logji5 =( Kk】R?);I()lcg3n=( SA习题1-2 XI)和()(2)的区别 试论OC打和CX2)的区别.分析与解答：根据符号Q的定义易知O(1)=CX2)。用CX1或0(2表示同一个函数时，差别仅在于习題V4按渐近阶排列表达式按照渐近阶从低到高的順序排列以F表达式,4r?, logn> 3".

2、 20,i, 2严乂刃!应该排在哪一位？分析与解答：函数排列颐序如下< 2. og,按渐近阶从低到高.习题1-5 算法效率(1)假没某算法柱加人规模为刃时的计算时间为T(K)=3X2住某台计算机上实现并 U成该算汰的时间为f秒。现有另一台计算机，其运行速度为第一台的64倍，那么玄这点新机器卜用同一铤決在t秒内能常输人规模为名大的问題？亡)若上述尊法的计算时间改进为Tu) = nS其余条件不变，两在新机器上用上秒时间能解输人规模为务大的问顾？估)若上述算法的计算时间进一步改进为T(»)-8,其余条舛不变，那么在新机器上用 t秒时I可能解输人规模为多大的问题？分析与解答： 设新机器

3、用同 簧法在，抄内能解输入规模为以的冋题。因此£ 3X2=3X2f64解得川一界十6。(2) nY? =64?f刃1 = 8”。 由丁丁5)常数丙此算法可解任意规模的问J8L习题卜6 硬件效率硬件厂言XYZ公司宣称他们最新研制的徴处理器运行速度为其竞争对手ABC公司同类 产品的1G0倍&对于计算复杂性分别为和打！的各算迭，若用ABC公司的计算机在 !小时内能解输入规模为兀的问題.那么用XYZ公司的计算机在1小时内分别能解愉人規 模为多大的问題？分析与解答:moo打LOOrP">r/r 100 = 4. 6lwn l(X)n!>Vn+k)R103=72+6

4、 64习题17 函数渐近阶对于下列各组函数/（Q和gM,确定/（n）=O（K（n）或/"）«（*（”）或g5) = lo* 卄 5f(n)&(gCn)9并简述理由o(«)=log?r jgn)/n心=1。刊(4)f(n) noRnni£（=1OR 力/<77)= 10|/(n) = loK10于(?1) = 1姑小g(n) = k>M<7)f(n) = 2f(n)=2Sg(Q = 3”(1) f(刃)To品分析与解答：(1) kgT=Q(logn+5)(2) Iogn:=O(6t>(3> n=fl(o(frO(4)

5、nogn 卜并=Q()ogn)(5) 10=0怙 glO) <6) leg2 猝=O(!cgn)(7) 2*n(100n2)(8) 2* =0(3")习题1-川的阶还明 t«! =o(w*)o 分析与解答：.Slidingapproximation：”!=厉住）屮（訂习题1-9 3刃+1问題下两的算法段用于确定”的初始值，试分析该算迭段所需计算时间的上界和下界°whi |p(n>*l)ii (ocd(n)n 3*n + l;n=n/2;分析与解答:该算法表述的是著名的：5卜1问題.在最坏悄况 厂 该算法的计算时间F界显然为/2(!ogF7)c算法的计算

6、时问卜界至今未知“算法足否在冇限时间内结.来.至今还足一个思而未决的 问題.h本学者米田信夫曾对内的所有自然数验证f.述算法均在右限步结束。人们猎 测对所仃自然数上述算法均在有限步结束.但无法给出理论证明.因此也无法分析上述 算法的计算时间上界.这个猜测就成为著名的前+】猜想.也称为Collacz 想，习题1-10平均情况下的计算时间复杂性证明；如果一个算法在平均情况下的计算时间复杂忤为&(/(Q),则该算法衣最坏情况 下所需的计算时问为f2<y(n)0ft 1 r*tees分析与解答：T/N)-另八<52 P(f) maxT(N.r) 緘5= T(NJa)工卩(门= 7X

7、W)= TQN)闵此 九(N) =0( T郴(N» =C(& /Xn) ) =C( fin).算沬实现超M 统计数字问题问题描述：一本书的页码从白然数1开始顺序编码直到自然数札书的贞码按照通常的习惯编排. 毎个页码都不含多余的前毘数字0。例如.第6页用数字6我示.而不是06或C0£等"数字 il数何题要求对给定书的总页码m计算岀书的仝部页码中分别用到多少次数字0.L2.-.9.编程任务：给定表示书的总页码的十进制解数”(1WM1()9)c编稈卄算书的全部页码中分别用到 3 八ilO/fn-n + K1 71 >1/M1 =1由此可知丿（托）=讥（）1

8、。r据此，町从高位向低位进行统計再滅去多余的0的个数即可.算法实现题12 字典序问题问题描述:在数据加密和数据压缩中営需耍对特殊的字符圉进行編码。给定的宇母衷A由滋个小写英文字母组成人=Sh“儿 该字母衣产生的升序字符申是指宇符串中字僚从左到右出 现的次字与字母在字母表中出现的次序相同月每个字符最多出现：乃次.例如触bxb.bc xyz等字符串都是升序字符串.现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。12 26 |272RI -Pb 一一乙1叫1 对于任意长度不趨过6的升序字符串.迅速计算出它在上述字典中的编码。细程任务'肘于给定的K度不超过6的升序字符

9、串编程计算出它在JL述字典中的編码。散据输入:输入数据由文件名为input, txt的文本文件提供.文件的第1行足个止鹤数乞表示 接下来共有&行，在接下来的&行中，每行给岀一个字符串。结果输出：称序运行结束&仁 将计算结果编出到丈件OUtiMH.txt中.文件共行.侮行对应于 个字符半的编码。输人文件示例揄出文件示例input txroutput txt21a*2b分析弓解答：序察一般情况下长度不超过k的升序字符串。设以第2个字符打头的长度不崔过怡的升序字符串个数为长盛不超过七的斧序 字符申总个数为以怡儿则肛切=刀/（八小，易知=1g（l） =- 26/（八2）=工 f

10、 （j 1） = 36 i 一般情况下右昭此町计算小毎个升序字符申的编码.2S2$02）=/（八2）=工（26 ？）= 325冰小=£于（讥 =工£ fd、k 1）211 /e| 1算法实现题1-3 最多约数问题问题描述：正鞋数J的约数浪能整除/的止整数，止建数/的约数个数记为div©）。便如，1,2, 510都是止整数10的约数.且div（2OJ-4c设n和”是2个正整数.a© 找出a和b之 间约数个数協多的数文.编袴任务： 对干给定的2个正鞘数a<b.编稈计算a和b之间约数个数最多的数“数据输入：输入数据苗文件名为input, txt的文本文件

11、提供。文件的第1行有2个正整数o和以结果输出：程序运行结束时若找到的"和之间约数个数最多肮数是八 则将山V©）输岀到文件 OUtpUt.【XI 中 °输入文件示例 inpu:, txt1 36输出文件示例 output, txt9.分析与解答:设正整数工的质因子分解为，则diY(D =M+l)(M, + l)(N»+l)捜索区间sQl中数的质因子分解。primes产生质数。void rimcsObool getLWAKP+ 1J :for(ini 1«2; 1<=HAXP;t +) gcti = true;for (i a«2:

12、i<MAXP:i + + )if(80ti)int j=i-Fi；while(j<CHAXP' glLj=fal$e； j +二 i JIfor(int I i 2. j 0; i i V=MAXP： i i+>if(getriil) prio*+j=ii:search搜索最多约数。search捜索最多约数。void 6«arch(inl from, ini lol. ini duil ini low, incp)(if (nun> = l)if (tot>max) I (tot = - max) && (num<numb)

13、 (' *max = tot .numb二num;1 i f (lowup)M(lovii ju)search(froanuoilow. 1,1);fg(irrt i=from；i<=PCCOn；i + + )、. if(prl®jJ>up) return;.° u .elseint jpr imi 1 x = lo 一 l9 y up. n nim, i ioi. wl ； while(true)if(x=y) break;search (i+Lxr n. xT, y):I»=1<Z<P；if(tot<Dax/m) retu

14、rn:实现算法的主函数如下。 6 int awinOJorimesO : cin»3»u;1) fmnx :nunbI; els；o3ax=2rnunb=】:search(1, b hD ： cout<?<*inax<r<*Ardl :return 0;算法实现题1-4金币阵列问题问题描述：有mXwCwClOO,w'Cl00）枚金币在桌面上井成一个也行n列的金币阵列每一枚金币 或正面朝上,或背面朝上'用数字表示金币状态，C表示金币正面朝上，1表示金币背面朝上C金币阵列游戏的规则是；<1）每次町将任一行金币翻过来放在原来的位置上；

15、（2）每次町仕选2列，交换这2列金帀的位置。编程任铸：给定金币阵列的初始状态和目标状态.編程汁算按金币游戏规则.将金币阵列从初始状 态变换到目标状态所需的最少变换次数C数据输入：由文件.nput. txt给出输人数据.文件中有多组数据。文件的第1行有1个正整数冷. 表示有上组数据< 每组数摇的第I行右Z个正幣数加和".以下的皿行是金币阵列的初始状 态，毎行有"个数字表示该行金币的状态.0表示止面朝上1表示背面朝上.接着的加行 是金币阵列的冃标状态。结果输出:瑜出文件示例将计算出的最少变换次数按照输入数据的次序输出到文件nurpiit. txt,相应数据尢解时input

16、 txtOutpuL txt294 3-11 0 10 0 0输入文件示例1 1 01 0 I1 0 11 110 1 11 0 14 31 0 10 0 31 0 9111】1 0111Oil1 G 1分析与解答：枚举初始状态每一列变换为标状态第刃的情况。算法描述如下。int k> n> mr count, best;int b0Size+1 | Size十 1 L bl|_Size+ lSize+ l,bSize十lSize十 1;fbool found:int main ()I< cin>>k;for(int il;i<=k;l + +) (1cin&

17、#187;n»fn;：mi k. n. couot. tsi:li t UfSite4-lXSiw4-门,bPSixe FlCSii+.b：Si“+lSizQ+ Ij; bool found;int nminO1 ” cin»k;for(int i-l;i<-k；i + )l八*八ci «»«»for(int x=l；M<=rii;x I 4)for(lr)t y= l;y<=；y+-)oix)»bOxJLyJ;.forfi,l;x<n；x+ 十)efor(int y=l：y<=o：y-b+&g

18、t;cin»blxyl：acpy(b.bl) ibesxD-Hn+l;for(int J=1；J< = m:j-h+H *八 *：；ncpy (bl, h);count =0; t.mrnlld, j);for(int p=l;pV=口;p+)?； :if(b® p 13! = b 1d 1 )trmsI (p>: for(p = l;p<=m;p十+)( fnund=false：4for(int qbp：q<y;q+ +),if(saoe (p, q) Hr»ns2(pr q ;foan<l = i rue;brt«ak:

19、 if (1 found) brk;.jif (found && count<best)best»count;if (b<«st<a+ n-hl cuutVVbe<tVOndl;else cmt<V_ Kendl;icturn fl.其中山皿1模槪行劃转变换uransZ繼拟列交换变换void i ransl Cmt k)foi <ieil l=1; i<n：l 4-Fbir> irtl bCrJLiJ 1:count t :1：vnlrt rran<>2<itit 儿 int y)Ifor (

20、ini 1= I i<=n; t Swaptbluilij. blCllfy):if b! yjcount 4-：1buul sanr (in X, i口I yJrfor (im i - I ： i<=n; i - I ) if (bOCiTxj! -blLiJLyl) return flse; return true:IvcmH acpyCiai aSize- lJLSiwlt int bCSiwei 叮Sf“十门)4%for(int J = l< j< = o:J丄算法实規题15最大间陳问也问題描述:最人间附问题：给定刃个实數rj £八求这n个数在实轴上相

21、邻2个数之间的展 大塔偵傀设对任何实数的下取整函数怀时。（八设汁輛垠大间原问通的线件时问许法.缩程任务： 对干给定的n个实数q入编程计篩它们的最大间隙数据输入：握人数据由文件名为input, txl的文本文件杲供.文件的第1行有】卜止整数呱 接下 来的t打中有防个实Ug.结果戟出；因洋运行结束时将找到的最大问晾枪岀到文4+ourpui. ixt中.綸人文件示洌辑岀文件示例input, txtoutput, txt53.22. 3 X 1 7. 5 1. 5 6. 3分析与解答：用苗舍原埋说计慣大間隙何题的线性时间算法如下.double mA>$ap(.inv n» double

22、 *x)double mini = XL»im( m). c：iKi = x(aaAi<nf *): 用n 2个等刎距.盘分double nuixxa(/(ini n> doublednub I* mini = t«iini (nr x).cmx = xcwui (n. k); 用n 2卜确同逻色分割IX间;i"nxx)/产生n 1个稍.母个桶i中用high订和】owi “分别存矯分配细瀚I的数中的最大数和堆小数 int *CQunt = new1 J;double *low=n«w <loubef<fri":； double *hinh=nf» rluubleLn-+ t;/禰初始化fur(int i = i；|<=n-，l;i-r 4-)lowti J = iwiax;highlil=Tiini;.； 一 ,/縛ri个n 1个桶中for(i»l ;i<o;l±±) |ini bucket ini(n 1)* (xfij minx)/(mxx minx)十 I ； countbuckz+4:if(d-i< lnwbuckctj)lowCbucketifil:i f Gc订 >h i ghLbvckeO h i KhCbiicketJ=