計算機(jī)算法設(shè)計與分析課后題答案(第三版)王曉東

1、第1章算法概述習(xí)題1-1 函數(shù)的存近表達(dá)式求下列函數(shù)的源近表達(dá)式，3zr 4-lO?n ?r/10 I21 + ； log, lC)og3%分析與斛答：3”，十(況 T)(/)iV104 2M=(K2)；21+ 一 3 ；log?r (Xlogw)；IOIorM (X11：及+ 10匕1。=藺+6. 6，習(xí)題17 函數(shù)漸近階對于下列各組函數(shù)/）和5）*確定/ 15）=儀口54,并簡述理由。11/11(2) (5.) F/5) = k白 3/(?j)=力,./Cw) = Mcg 履十/(ni=log2“3-2”；f5)二2一 g5) = logw+5 gS)=i)=k)必，】 g(n) = lo

2、gji g(n) -loglO g(?)-=kigw ff(n) = 100nz g(N=3分析與解答！(1 )=8(2)右)ymi6的)(4) rtlogn-|-rtDC)0Rrt)(5) 10 = f?(logl0)(5)icg%ndogn)滬=】8科 2” = CK3D.習(xí)題1-8 n!的階證明通!=。(力).分析與解答；Slidings approximation：閔口+陪)習(xí)題1-9 3九+1問題F面的其法段用于確定，的初始值試分析核算法段所需計算時間的上界和下界。while(nli f (odd(n)n -3n 1-1;elsen=n/2;分析與解答：該箕法表述的是著名的和11問題

3、。在最壞情況下，該算法的計算時間下界顯然為 C(!cg“算法的心算時間上界至今未知，算法是否在在限時間內(nèi)結(jié)束，至今還是一個懸而未決的 問題。a本學(xué)齊米田信夫曾對1記內(nèi)的所有自然數(shù)驗證匕述第法均在有限步結(jié)束，人們猜 測，對所自然數(shù).上述算法均石為限步結(jié)束但無法給出理論證明.因此也無法分析上述 算法的計算時間匕界。這個猜測就成為著名的加+：猜想，也稱為GjILmz猜想.習(xí)題 M0 平均情況下的汁算時間復(fù)雜性證明：如果一個算法在平均情況卜.的計算時間復(fù)雜性為仇.“加)，則該算法在最壞情況 下所需的訐養(yǎng)時間為n1J?。?!11n-1 . .，由此可知./(#一1步一二;據(jù)此，可從高位向低位進(jìn)行統(tǒng)計，再

4、減去多余的G的個數(shù)即可。算法實現(xiàn)題1-2字典序問題問題描述：在數(shù)據(jù)加密和數(shù)據(jù)壓縮中常需要對特殊的字符串進(jìn)行編碼。給定的字母表A由26個小 寫英文字母組成八=(a,b,z。該字母式產(chǎn)生的升序字符串是指字符串中字母從左到右出 現(xiàn)的次序與字母在字母表中出現(xiàn)的次序相同，.月每個字符最多出現(xiàn)工-次。例如，a,hab,bc, xyZ等字符串都是升序字符串n現(xiàn)在對字母表A產(chǎn)生的所有氏度不超過6的升序字符串披照 字典中排列并編碼如F,；： ,：?,；% .12 26272b- a | b abac.對于任意長爵;超過6的升序字符串，迅速計算出它在上述字典中的編碼。微程任務(wù)： .-對于給定的長度不超過6的升序字

5、符審，編程計算出它在上述字典中的編6丸數(shù)據(jù)輸入：.輸入數(shù)據(jù)由文件名為mp-xi的文本文件提供,.文件的第1行是一個iE整數(shù)人 表示 按下夾共有A行.在接下來的右行中.每行給出一個字符串，結(jié)果輸出：程序運行結(jié)束時，格計算結(jié)果輸出到文件osrmt. txt中，文件共有上行.每行對應(yīng)于 個字符事的編瑪.輸入文件示例輸出文件示例input, txtoutput txt礦 21&2b 分析與解答： 考察一般情況下長度不相過A的升序字符申。設(shè)以第？個字符打頭的長;攵不超過4的升序字符中個數(shù)為/(八/，氏度不妞打的尸序字符申總個數(shù)為X” 則以我=.易知r-l 26 /3J)= 1xjCD -匯八；,1) =

6、 26j-i 西21126八?0= 2,5)= 26 7 8= ZQ6 力= 325 八，-IJ-lC-.I一般恬況下看 Jfi3626 26“)= E/Q-n 晨幻 4 =月 E!f5i) 尸什】-j-1據(jù)此可計算出每個升序字符序的編碼.算法實現(xiàn)題1-3最多約數(shù)問題問題描述：正嚓數(shù)上的約數(shù)是能接除l的正整數(shù)g正整數(shù)了的約數(shù)個數(shù)記為divCr）.例如，1,2, 5,。都是1E整數(shù)10的約數(shù)，且,12（1=4。沒&和8是2個正整數(shù).0兒找出和5之 問約數(shù)個數(shù)區(qū)委的數(shù)1“編程任務(wù)：對于給定的2個正整數(shù)位Q,編程計算司）之間約數(shù)個數(shù)辰多的教。數(shù)據(jù)輸入：輸人數(shù)據(jù)四文件名為input txt的文本文件提

7、供，文件的第1行有2個正轉(zhuǎn)數(shù)以和人結(jié)果輸出；程序運彳j結(jié)束時,若找到的2和4之同約數(shù)個數(shù)垠多的數(shù)是m，則% div（R輸出到.文件 ClKpLU. 1兌（中給人文件示例inipuh txt1 36輸出文件示例output, txt9設(shè)正整數(shù)1的質(zhì)因子分解為分析與解答:：x=戶 pFdivG)= (N + D(M + lA7M+l)楣索遺加以法中數(shù)的質(zhì)因子分解。 primes嚴(yán)生質(zhì)數(shù)void priacsObool getMAXP+l1:for (int i -Z; i get_i=true：for (i-2:i-UAXP;i-4-)if(getZi)1int j -L十i;wb ile (j=

8、UAXP) (getC j= fa Ise: j+= i: 11for(iat i = 2, J=O：iiaax)l | (td t = = a ax) ft& (iiuiinuin)search (Proa, l.ot*2, miB*low, 1, 1);forins i-fromii-C-PC0ENTJ+-.4-)if(primCijup) return; .I.else int j=priniZ,xlow - 1, y=up n=num. t = tot,ro = l; while(true)a+：i4- = tot;x=j; y7=j;*if(x = =y) break;n* 二 j;

9、search t. n? x+1, y)：實現(xiàn)算法的主函數(shù)如下ci(” main() )pr imes。： cin1uf (=。蛤(u= D) ininx knunb I; elscmax=2.numbq) search (I, 1. . Lu): courmaxendl:upturn 0;算法實現(xiàn)題1-4金吊陣列河題問題描述：有mXWm10010。）枚金閂在束面上排成一個中行普列的金而陣列：每一枚金幣 或正面朝上，或背面朝上，用數(shù)字表示金幣荻態(tài)，C表示金幣正面朝上】表示金幣背面朝上.金幣陣列游戲的規(guī)則是：（1）征次可將任一行金幣嬲過來放在原來的位置匕（2）每次可任選2列，交換這2列金幣的位置

10、.摭程任務(wù)：給定金幣陣列的初始狀態(tài)和目標(biāo)狀態(tài).編程計算按金幣游戲規(guī)則，將金幣陣列從初始狀 態(tài)變換釗目標(biāo)狀態(tài)所需的最少變換次數(shù).數(shù)據(jù)輸入：山文件inmu.ixt給出輸入數(shù)據(jù)e文件中有多組數(shù)據(jù).文件的笫i行有i個正鐐數(shù)機(jī) 表示有及組數(shù)據(jù)。每組數(shù)據(jù)的第1行有2個正整數(shù)帆和明 以下的由行是金幣陣列的初始狀態(tài)，每行布.桂個數(shù)宇表示該行金幣的狀態(tài)，。表示亞面朝上.1表示背面朝上。接著的由行 是金市陣列的目標(biāo)狀態(tài)。結(jié)果輸出；將計算出的最少變換次數(shù)按照輸入數(shù)據(jù)的次序輸”到文件output. ixt。相應(yīng)數(shù)據(jù)無解付輸出一 1。輸入文件示例輸用文件示例input, txtoutput,ixt224 3-11 0

11、10 001 1 01 0 11 0 i】110 1 I 7 1 0 14 31 0 10 0 01 f)G1111 I 01110 1 11 0 1分析與解答！枚舉初始狀態(tài)每一列變換為目標(biāo)狀態(tài)第1列的情況.算法哦述如下,0inbOx?y;for=i.；3c-=in;x-Hfordnt 廠Ly Abl-acpy (btabl) ： beL=如十 n 十 1;forGnt j=l；j=ni;j + +)f=arpy (bl r h) ;conr：t=0; trausz! (lr j);for(int p=l;p=;:a;p4-)：；,，tf (b0p113! LlEpZiriDlrursl (p

12、);、for G= l：p；p+)(fQ：nd=fzlJ5e;fortint q=p；q) |trftn?2(pf q) ：foimri = true:break4) if iL found) break;) Iif (fuund ill covntIbestJbest=count;I：1 tbsta+a |-1) cout b?s tond 1:： ；else coutK I; 8 ro-turn C.for(int i =n;i - I )for(int j = l; j； 用(1-2個警同距點分割區(qū)05丘|5工,|工(1/產(chǎn)生ii 1個桶.每個桶i中用high匚和lovLiZ 分別專儲分

13、配給桶的數(shù)中的京人致和最小數(shù) iiit cojnl-ijcw i口+1;doubl-edodbe-r C；cipuble *hiRh=ne* dvubLen4- il；/桶切妁化fwr(j力2 i=l：i-4-) Ieojut _IJ 0；1。匯口=皿工x；highiJ=iDinx!少將n個數(shù)R干力一 l個桶中fi2r(i = I =int bucket-int(n =：)拿(k門- minx)/(maxx - minx) + I;coun tbucke t十:i f (xiJ-ucke tJ) lovbtLcket- = xQi ;ifOcihigh b-jketl)highLbuckeJ=

14、xLij;此時,除了 nmx和蚯nI外的n 2個數(shù)被置Fel 1個桶中./由熊合原理即如,至少省一個福是空的./這套味者增大間隙不會出現(xiàn)在同一桶中的兩個數(shù)之間./對3 個橘嫩一次線性打貓即可找山最大間隙.dmibio tnp-=0loft=hlghl;for(i=2:itoip) lnp= thisgap:電 f:=highi) return top;i nt k, n, m, count, bes I;ini 1Q二Siu1+1 工S izg-M1b lSi /e+lEize4-l.h$ ize+iz9+ I;itocl found:int main ()! . .cink;for(int i-l;i ( * 1cinun;fcrCint x=J：xlaVi bl-：coun