《计算机算法设计与分析(第三版)课后习题答案详解》由会员分享，可在线阅读，更多相关《计算机算法设计与分析(第三版)课后习题答案详解（17页珍藏版）》请在装配图网上搜索。
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 3. 20,i, 2严乂刃!应该排在哪一位？分析与解答：函数排列颐序如下r/r 100 = 4. 6lwn l(X)n!Vn+k)R103=72+6 64习题17 函数渐近阶对于下列各组函数/（Q和gM,确定/（n）=O（K（n）或/）（*（”）或g5) = lo* 卄 5f(n)&(gCn)9并简述理由o()=log?r jgn)/n心=1。刊(
2、4)f(n) noRnni（=1OR 力/M(3 n=fl(o(frO(4) nogn 卜并=Q()ogn)(5) 10=0怙 glO) *l)ii (ocd(n)n 3*n + l;n=n/2;分析与解答:该算法表述的是著名的：5卜1问題.在最坏悄况 厂 该算法的计算时间F界显然为/2(!ogF7)c算法的计算时问卜界至今未知“算法足否在冇限时间内结.来.至今还足一个思而未决的 问題.h本学者米田信夫曾对内的所有自然数验证f.述算法均在右限步结束。人们猎 测对所仃自然数上述算法均在有限步结束.但无法给出理论证明.因此也无法分析上述 算法的计算时间上界.这个猜测就成为著名的前+】猜想.也称为C
3、ollacz 想，习题1-10平均情况下的计算时间复杂性证明；如果一个算法在平均情况下的计算时间复杂忤为&(/(Q),则该算法衣最坏情况 下所需的计算时问为f2y(n)0ft 1 r*tees分析与解答：T/N)-另八1/M1 =1由此可知丿（托）=讥（）1。r据此，町从高位向低位进行统計再滅去多余的0的个数即可.算法实现题12 字典序问题问题描述:在数据加密和数据压缩中営需耍对特殊的字符圉进行編码。给定的宇母衷A由滋个小写英文字母组成人=Sh“儿 该字母衣产生的升序字符申是指宇符串中字僚从左到右出 现的次字与字母在字母表中出现的次序相同月每个字符最多出现：乃次.例如触bxb.bc xyz等字
4、符串都是升序字符串.现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。12 26 |272RI -Pb 一一乙1叫1 对于任意长度不趨过6的升序字符串.迅速计算出它在上述字典中的编码。细程任务肘于给定的K度不超过6的升序字符串编程计算出它在JL述字典中的編码。散据输入:输入数据由文件名为input, txt的文本文件提供.文件的第1行足个止鹤数乞表示 接下来共有&行，在接下来的&行中，每行给岀一个字符串。结果输出：称序运行结束&仁 将计算结果编出到丈件OUtiMH.txt中.文件共行.侮行对应于 个字符半的编码。输人文件示例揄出文件示例input txroutput t
5、xt21a*2b分析弓解答：序察一般情况下长度不超过k的升序字符串。设以第2个字符打头的长度不崔过怡的升序字符串个数为长盛不超过七的斧序 字符申总个数为以怡儿则肛切=刀/（八小，易知=1g（l） =- 26/（八2）=工 f （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
6、找出a和b之 间约数个数協多的数文.编袴任务： 对干给定的2个正鞘数ab.编稈计算a和b之间约数个数最多的数“数据输入：输入数据苗文件名为input, txt的文本文件提供。文件的第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 :fo
7、r(ini 12; 1=HAXP;t +) gcti = true;for (i a2:iMAXP:i + + )if(80ti)int j=i-Fi；while(jif(getriil) prio*+j=ii:search搜索最多约数。search捜索最多约数。void 6arch(inl from, ini lol. ini duil ini low, incp)(if (nun = l)if (totmax) I (tot = - max) & (numnumb) ( *max = tot .numb二num;1 i f (lowup)M(lovii ju)search(froanuoi
8、low. 1,1);fg(irrt i=from；iup) 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=1ZP；if(totDax/m) return:实现算法的主函数如下。 6 int awinOJorimesO : cin3u;1) fmnx :nunbI; els；o3ax=2rnunb=】:search(1, b hD ： cout?*inaxr*Ardl :return 0;算法实现题1-4金币
9、阵列问题问题描述：有mXwCwClOO,wCl00）枚金币在桌面上井成一个也行n列的金币阵列每一枚金币 或正面朝上,或背面朝上用数字表示金币状态，C表示金币正面朝上，1表示金币背面朝上C金币阵列游戏的规则是；1）每次町将任一行金币翻过来放在原来的位置上；（2）每次町仕选2列，交换这2列金帀的位置。编程任铸：给定金币阵列的初始状态和目标状态.編程汁算按金币游戏规则.将金币阵列从初始状 态变换到目标状态所需的最少变换次数C数据输入：由文件.nput. txt给出输人数据.文件中有多组数据。文件的第1行有1个正整数冷. 表示有上组数据 n mr count, best;int b0Size+1 |
10、Size十 1 L bl|_Size+ lSize+ l,bSize十lSize十 1;fbool found:int main ()Ik;for(int il;i=k;l + +) (1cinnfn;：mi k. n. couot. tsi:li t UfSite4-lXSiw4-门,bPSixe FlCSii+.b：Si“+lSizQ+ Ij; bool found;int nminO1 ” cink;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;
11、xn；x+ 十)efor(int y=l：ycinblxyl：acpy(b.bl) ibesxD-Hn+l;for(int J=1；J: for(p = l;p=m;p十+)( fnund=false：4for(int qbp：qy;q+ +),if(saoe (p, q) Hrns2(pr q ;foanl = i rue;brtak: if (1 found) brk;.jif (found & countbest)bestcount;if (bsta+ n-hl cuutVVbetVOndl;else cmtV_ Kendl;icturn fl.其中山皿1模槪行劃转变换uransZ繼拟列
12、交换变换void i ransl Cmt k)foi ieil l=1; i irtl bCrJLiJ 1:count t :1：vnlrt rran2itit 儿 int y)Ifor (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
13、“十门)4%for(int J = l j$ap(.inv n double *x)double mini = XLim( m). c：iKi = x(aaAi doublednub I* mini = tiini (nr x).cmx = xcwui (n. k); 用n 2卜确同逻色分割IX间;inxx)/产生n 1个稍.母个桶i中用high订和】owi “分别存矯分配细瀚I的数中的最大数和堆小数 int *CQunt = new1 J;double *low=nw loubeffri:； double *hinh=nf rluubleLn-+ t;/禰初始化fur(int i = i；|
14、=n-，l;i-r 4-)lowti J = iwiax;highlil=Tiini;.； 一 ,/縛ri个n 1个桶中for(il ;io;l) |ini bucket ini(n 1)* (xfij minx)/(mxx minx)十 I ； countbuckz+4:if(d-ih i ghLbvckeO h i KhCbiicketJ=賈i :1此时除了 maxjs和minx外的n 2个Ifc被氏于n 1个柄中由鸽舍原理即知至少右一个怖是空的./这意味着最大I可陳不会出现在同书中的衢个数之何./苛鲜一个慵做一次线性扫描即可找小毂次:间球 double tap()for(i=2.itwp
15、ftcpthi?ap: left=hiuhLi j/xeiunj irq;”中miru fn max,分别卄算数组中亲小元素和最丈元素的下标.(.nnplntPin： mw) (W 儿 T和)IT lwpH於l；fort I nt i T. k1; Hn . i 4 + )i/jiCxJ (trp-xrij.k i:lreturn k;MBWwVub Tint kl)a i (tnl n, T*a)t1 W-xLl;forhnt m；lV = n,【I丄 if ti) -tnp) (rn:p=x l：k i : I return k.由于卞散整甬数耗时CX1;.故循环体内的运算耗时0(1)。因此签个昇法耗时05几即算法maxgap足求最大间陳问翹的线性时间算法負注意到在代数判定树计算模型下.mg心是晟大问粽问题的-十廿算时间下瓶 这怠味着&代数判定树的H尊模型下.最大 间隠何题星不可能白线件时间笄法的。虫此聽中假设下取懵鬲数耗时Ol、实甌上这可以 看作足在代数判定树模魁中.将下取生运算作为基本运罪増織到原有的基本运算輿屮从而 便代数判定林计耳裡型的计算能力得到增强.因而可以/线性时间内舗殳大间畝阿曲.
计算机算法设计与分析(第三版)课后习题答案详解
