计算机算法设计与分析课后题答案第三版王晓东

1、第1龟算法概述习1-1面数的序近表迭式求下列感数的灣近表达式：3n-4-IO/rt m2/104 2'i 214-l/n; logn*» lCog3'd分析与屛答：3h* + lOwtXw);/104 2-=()(2');logw OUogw);IdlogfXd).习题1-2 OU)和0(2)的区别试论0(1)111(X2)的区别”分桥与解答：根询符号。的定义易知O一52。用O或52)茨示冋一个函数时差别仅在于 其屮的弾数囚子-习题整渐jg阶排列表达找按照逝近阶从低到离的腹序排列以下表达式：4,化I。助，M, 2g 2,/'。又/应该 排在嘟一泣刁分析

2、与解答：按细近阶从低到尙,函数排列駐洋如下：2. logw,能S 20n, W,:几 泌。习医1-5算法效率«1)俶设某筛法往编人规模为升时的计算时间为T(t» = 3X2-.在某台H於机上实现并 完成该算沈的吋间为(秒，班有另一台计算饥啟运行速懂为第一台的64侣.那么布这台新 机務卜冃冋一算法在f秒'内能:解环人戍校为多丈的问痢？若上述算法的计算时间改进为T(n)-/r其处条件不变.则在新机祚上用r秒时间 危統锚入煽模为去大的航匿？(：”若匕述算疋的计箕吋间进一步改进为丁S)U H余条件不变那么在新机務上用 /杪时间彪耕辅人史安为多大的问题丿分析与解削设新机曙用同

3、-?法在f秒内能解输人规楔为八的问題"因此侏X3X2J3X 2-1 /64.解得 jjl-JiH-6,(2) «F =64ir->»j = 3ws.<3>曲丁 丁(八一常数，因此算法可解任意规膜的冋題。习题卜6ifllH败罕硬件厂帝XYZ公司宜称他们最新硏制的微处理器运行速度为其竟争对手 产氐的胸倍°对于计算复爱性分别为mH沪和沢的各算法，若用ABC J小时内能的输入规聊"的问腮那么用XYZ公司的讣算机柱1小时内$ 模为多大的问题？分析与解答；=11换?|，-i = 1 OC)rl'=>t/ = 1 Or?7?

4、:| 7 lOi'M1>wz = /Io6pi = 4 61 w*! e lDl)zi!>r/<>i+loglOC,«+6. 64习题1-7 函数渐近阶对于下列各组函yCn)fH嶋定/<«)O(g(n)或fin)/(时并简述理由°(1> /lagrr ；g (心=leg” 牛 5(2) /G = k>g讥g(.n) f(n)=m只(处)=-1°分农(4) /(廿)=nlogw十rifg(w) = logw(5) JUSloLO /'(n) = lognjKn)二 k的7) fj) 2”；ff(&#

5、187;) = 100»2r5)=3分析与解答！(1) iag/r=0(五(3) MncWw)(4) nlogn-FrtOCiogn) io=.(loglO)(5) log/i- IJdog/t)；<7)?u-n(ioo?i2> 2“=CK3T习题18”！的阶分析与解答；Sliding*r approximation：”!=厉(*)1+0(切2 二 K屮(万二0习超1-9 加十1冋題下面的豆桧段用于确定的协姑值.试分析该算法段所需计算时间的上界和下界.hi 1巴(匸>1)if Gxid(n) n 3” I 1：cl"R=n/2;分析与解答：汝且法表述的足*

6、名的3” I 1的蹩.存長坏倩况下该悴法的计轩时间下界显然为 Q(bgm)。算法的讣算时问上屛至今水知，算法是否在右眼时间内结来.全今还余一个悬而未决的 问題.H本学者*出信夫旳对1屮内的所灯白然数验证匕述片快均在冇限步结束，人们猎 测对听冇自然数.上述韩法均右冇隈步结東但无法给出理论证明.因此也尢決分析上述 算沬的计算別间匕界.这个箱測就成为者乞的如+；猜恿.也称为CollMZ猥臥习題1-10 平均情况下的汁算时河复杂性址明：如果一个算法在平均情况卜的卄算时何复臬性为m 则诙算法在員坏情况 下所需的计算吋何为以An) 分析与解答：P<f) cnaxTI.VJ"(W ) YHD

7、传叭= T(.V,J->二 T"N)因此.TjN)rCC丁忸(2二4水/(力)=心/5儿算沬实现® 1-1第计数宅问题问軀描迷：一本书的卿从口然数I开始顺序编码直到自然数机书的贾码按列通常的习惯编出. 铮卜页码都不含$余的前导数字(例如 第6贞用数字6裘示.而不是06或COG搴 数字 il数何越翌求对给定书的总页码心计算出书的令部貝码中分别用到多少次数字0.i.2.9.負编程任务：治定表示书的总页码的十进制帑数ndClO,编程计算书的全部页码中分别用到 3 多少次数字0.2.9,数拯输入；输人数摇由文件名为inpui. txt的文4文件臭供。毎个文件只右1行，给岀表示

8、书的总 页码的整数礼结果输出：程疗;运行结耒时.将计算结果输岀到文件output, txt札 输出文件共有10行,在第上 行输岀页码中用到数字bl的次数.&=1.2,()输入文件示例雅岀文件示例input, txtoutput :Kt11I41111 11仍与解答：考察由0.1,2组成的所有"位数.从”个0到z>个9共有2个ri位数.在这10-个刃位数中，0J2-.9傅个数字使用次数相同设为f(n)a满也如卜递归式，,z 、f10/<n- 1)卜iV n>l小(1kl亠由此可知/5)川0。；锯此可从髙位向低位进行统计再减去多余的0的个数阳可.算法实现题1-2

9、字典序问题问席描述：2262728 »L十abac.在数据加密和数据压缩中*需耍对特殊的字符电进行编码°给止的亍母表A由2G个小 写芙文宁母组成A = 3b.z该？母表产生的升序了符申是拒字符串中字母从左到右出 现的次序与字母在字母表中出现的次序相同貝每个7符最多岀现片次例如，a.bab-bo 其”铮字符用都扯升方字符4J现在对字母表A产生的所有长盘不超过6的升序字符串按照 字與中推列并编码如氏.：.! .：vr.对丁任意长用味趨过G的升序宇符串迅琏汁算出它在上述年典中的编码。績程任务：.对干给定的长度不超过6的升序了符串.绍程计算出它在上述字典中的编码 台数据输入, 4

10、檢人数据山文件名为:npm.ixt的文文件提供“文件的第1冇雄-个iE整数趴 衣小 按孑夹共有*彳讥 在接下来的冷行中.毎行给出一个字符申，结果输出：秤序运行结束时,将计算貉果镣出列文件output txt中i文件共有*行.侮行对应尸- 个字符出的编码.龜入文件示洌称少文竹赤例input, txtoutpuU txtf? 21a2b分析与ft?答： 考察一股淸况下K庞不俎过A的尹序了符申°设以第!个7：符扌J头的长浚不超过後的升仔宇符申个数为fw 长皮不妊过定的尸序 字符串总个数为川I 则皿)=乞f(E 易知»r26/Cnl) = 1g(l)=工/G.I) = 26宛212

11、6fU.2)= V/CjJ)= 26-t 虹 2)=工/(if)=工(Z6-,) = 325/i' I-般祜况下有?«g、k)=工 “j、h 1)据此盯计珠出毎个昇序字符由的编码.3626 X讹）亠= EE/q-dJi法实现题i-3 尿多约数阿題険问期描述：止礬数丄的约数是能整除比的止整数。正整数工的约数个数记为div(xk创如，1,2, 5J0都是止製数10的约数.且山讥：仍=4设4和&是2个正輕数 Q0.找出“和&之 问约数个戮最多的数文.编科任务：对于给足的2个止整数4创，编程II算4貝"之间约数个数屍多的數.数第输入：输人数握山文件名为inp

12、ut, txi的文本文件提供。文件的第1 ?有2个i£襲数"和詆 结卑輸出,程斤运彳J笫束时若找到的之他约数个数杲多的数M-t.则埒diWT辎出到文件output. 1X4 中 <辂入文件示例縮出文件示例input, txtI 36OUtpJt. txt9分析与解答:设IT整数上的质因子分解为工*" p$納divCr= (N + l(M + 1)(M-H)招索 那 S 4中数的质因子分斛.primes产生质数void priocsOiiool gvt2MAXP4-C：for (int i2;i<.=i4AXK:i-F-h> gCtJJ=true;

13、for (i2;iVMAXF;i+ I )iruetcunint j-i十f：<hile(j<=UAXP)(BetLj=folse:*Ifor(int i = 2. J=O：ii<=ICAXP：i£ I -f > lf(firet7iil) rnrim：+ + j = ii:search搜兔最多約数.void aettrchCinl frota, ini tot, ir；l num. ini low, int up) if(nua>Dif(tot>toax) I (tot = = ndx)AA(hum<numb) t»x = tot

14、 ;nufrb=m:rB；if (lo«up)4A(l(jw>nuin)HHiLrch(fro« l.ot*2, nu»*lov9 L 1):for(int ifroa;i<PC0LXT:i4-+)if(pri«£i>up> return; Ielse int jprimCil.x low - 1, y up. n num, t tot, ra = l; while (true) <j; jf7=J;if(x -*y) break;search(i- 1, t. ru x l> y): )»=l&#

15、171;w;if (tot-<TOx/iD)return;实现算法的主函数如卜.int main()Jpr:cin»1»u;if «1 l)4A(u D) ni»x-l .nurb I;el.wiBax=2;nunb*=) search(lt L 1.1.u):) cniK«mar«Gr(ll:return 0;算法实现题1-4金币阵列制题问题描迷:有穴X讥必忘100"吃100；枚金活在束曲上拌成一个m讦刃列的金币阵列.每一枚金币 或正面朝上或背面朝上、用數字表示金币坎态.C表示金币正面対上.】衣鬲金币背面牺上.金币阵

16、列游戏的规则是：（1）加次可将任行金币翻过来放在原来的罚黑"（2）每次可任选2列.交换这2列金币的位賈编程任务：给定金币阵列的初始状态和目标状态.编程计算按金蹄戏規则.埒金币阵列从初始状 态龙换封冃标状态所需的晟少交换次数.版据愉入,山文件inpu.txt给出输入数据.文件中有多组数攥*文件的第行有个正整数乩 表朮有虑组数据、毎组数据的第1行有？个正幣数加和n以下的”行杲金币阵列的初妬状态每行冇"个数字典示该行金币的状态.0表示正曲朝上 1表示背面朝上。按着的F行是金币阵列的冃标状态。结果输出：将计算出的最少变换次数按照输入数強的次序输出到文件ourput txtv tfi

17、应数据无解时«i±-L输入文件水例筍出文件示例input, txt24 3outpui. ixt2-11 0 10001 1 01。11 0 I】11C 1 I1 0 14 31 0 10 0 01 001111 I 0111 0 1 11 0 1分析与"答！枚举初始状金毎一列变换为片惊状念第1列的悄况6算法怖述如bi rtt k. n, mt count, he« t;ini bOCSiz+lZCSjxe-t-l, blCSiz94-lSize+l. h：Siza+ ixe-f-1 j;Ibocl found;int main ()cin»k

18、;for(int i = l;K=k;i+ 4-*>(' -'fcr(int x=J：x<=n:i + 4-)foT(int T=?;y<=« jr-r-t-) T fgp*i«Akn 二十 4)- f o r ( 3 n ; Mry 八“弓 y1cs-vvzs?HyL!acpy (b2.) gJSctN 耳- nH-r fox-nt jHrCHmj+M /VI >cpyz- h) zounlnuJnR2(厂 j)- for(i!u DHrJ-<M£p+卜)!:、 if (bop】一 lb=pl)t,§ul

19、(pr for<PNrPAH-u-二ot;ndnf?»Teifokel GUFq 八 Hmq-3; “i f (»£© (prJjh)亠*rAnw!2(p t-r 二吻break 二 if= fcMJrebredr- + 2F(futmd && counrtAbdbes.ococnt. i一 - iHhestcIl+n-H) COUKAbQsrAAosdl: " ulxe CCIH-CA -aapike "1.0-ruTn cmiiililiii I 1111111111111111111111111111 s

20、:n21 Gru X)亠fdm 11 二、01 二 l+)b.lLli一LGL 二counr - “一5i 二gLS2 =二車 jiH y-:H【！n 1 i八H?.41f Fpcr-c.hx* bl. il y 7"if 2 H ynnunt I +"一bocl x im y(fu二 in 二 H-iANh二 -)f(sixNblirefun false rcL 匚n Lmt-void 8c3(im 匕 su-ei】siw-l 一nL hs;*c.4.二sdo二)tor (in t i = J :K-=n；i - I ) for(jnt j=l;j<mj-bi-)

21、a7nCjO=bLiTi：b法实玻题15绘大间隙问融问題描述：晟大间隙问帧:给定心个实数小兀求这刃个效在实轴上相邻2*数之间的臥 大左值。假设对任何实数的下取整函数耗时0( U 设汁解堆人间隙问題代线件册间算法。绸程任务：对于给定的n个实数“ 2山_编程讣算它们的杲人间取.*擞据输入：输入敌捉白丈件名为input. :xt的文本丈件捉供.文件的第1行有1个止堂數仇偿下 来佑】川|响”个实数小心严5.结果输出：程弄运行结束时杵找到的坡大何晾输出剁文件output, ixt中， 9 输人文件示例输岀文件示例inpuL txtoutput, txt53.?2. 3 X 1 y 5 6. 9分析与解答：用鸽舍原理设计荒大间隙问題的线性时间算法绷下.double iaAeapimt n, double