【正文】 《計(jì)算機(jī)常用算法與程序設(shè)計(jì)案例教程》習(xí)題解答提要習(xí)題111 分?jǐn)?shù)分解算法描述把真分?jǐn)?shù)a/b分解為若干個(gè)分母為整數(shù)分子為“1”的埃及分?jǐn)?shù)之和： （1） 尋找并輸出小于a/b的最大埃及分?jǐn)?shù)1/c； （2） 若c900000000，則退出； （3） 若c≤900000000，把差a/b1/c整理為分?jǐn)?shù)a/b，若a/b為埃及分?jǐn)?shù)，則輸出后結(jié)束。 （4） 若a/b不為埃及分?jǐn)?shù)，則繼續(xù)（1）、（2）、（3）。試描述以上算法。解：設(shè) (這里int(x)表示取正數(shù)x的整數(shù))，注意到，有 算法描述：令c=d+1，則 input (a,b) while(1) {c=int(b/a)+1。 if(c900000000) return。 else { print(1/c+)。 a=a*cb。 b=b*c。 // a,b迭代，為選擇下一個(gè)分母作準(zhǔn)備 if(a==1) { print(1/b)。return。} } } 12 求出以下程序段所代表算法的時(shí)間復(fù)雜度（1）m=0。 for(k=1。k=n。k++) for(j=k。j=1。j) m=m+j。 解：因s=1+2+…+n=n(n+1)/2 時(shí)間復(fù)雜度為O(n2)。（2）m=0。 ?for(k=1。k=n。k++) ?for(j=1。j=k/2。j++) m=m+j。解：設(shè)n=2u+1，語(yǔ)句m=m+1的執(zhí)行頻數(shù)為s=1+1+2+2+3+3+…+u+u=u(u+1)=(n?1)(n+1)/4設(shè)n=2u，語(yǔ)句m=m+1的執(zhí)行頻數(shù)為s=1+1+2+2+3+3+…+u=u2=n2/4時(shí)間復(fù)雜度為O(n2)。（3）t=1。m=0。 for(k=1。k=n。k++) {t=t*k。 for(j=1。j=k*t。j++) m=m+j。 }解：因s=1+22!+ 33!+…+ nn!=(n+1)!?1時(shí)間復(fù)雜度為O((n+1)!).（4）for(a=1。a=n。a++) {s=0。 for(b=a*100?1。b=a*100?99。b?=2) {for(x=0,k=1。k=sqrt(b)。k+=2) if(b%k==0) {x=1。break。} s=s+x。 } if(s==50) printf(%ld \n,a)。break。}}解：因a循環(huán)n次；對(duì)每一個(gè)a,b循環(huán)50次；對(duì)每一個(gè)b,k循環(huán)次。因而k循環(huán)體的執(zhí)行次數(shù)s滿足時(shí)間復(fù)雜度為O()。13 若p(n)是n的多項(xiàng)式，證明：O(log(p(n)))=O(logn)。證：設(shè)m為正整數(shù)，p(n)=a1nm+a2nm1+…+amn，取常數(shù)cma1+(m1)a2+…+am, 則log(p(n))=ma1logn+(m1)a2logn+…=(ma1+(m1)a2+…)logn clogn因而有O(log(p(n)))=O(logn)。14 構(gòu)建對(duì)稱方陣觀察圖15所示的7階對(duì)稱方陣： 圖15 7階對(duì)稱方陣試構(gòu)造并輸出以上n階對(duì)稱方陣。解：這是一道培養(yǎng)與鍛煉我們的觀察能力與歸納能力的案例，一個(gè)一個(gè)元素枚舉賦值顯然行不通，必須全局著眼，分區(qū)域歸納其構(gòu)造特點(diǎn)，分區(qū)域枚舉賦值。（1） 設(shè)計(jì)要點(diǎn)設(shè)方陣中元素的行號(hào)為i，列號(hào)為j?？芍鲗?duì)角線：i=j；次對(duì)角線：i+j=n+1。兩對(duì)角線賦值“0”。按兩條對(duì)角線把方陣分成上部、左部、右部與下部4個(gè)區(qū),如圖16所示。圖16 對(duì)角線分成的4個(gè)區(qū)上部按行號(hào)i賦值；下部按行號(hào)函數(shù)n+1i賦值。左部按列號(hào)j賦值；右部按列號(hào)函數(shù)n+1j賦值。（2） 程序?qū)崿F(xiàn)include void main(){int i,j,n,a[30][30]。 printf( 請(qǐng)確定方陣階數(shù)n: )。 scanf(%d,amp。n)。 for(i=1。i=n。i++) for(j=1。j=n。j++) {if(i==j || i+j==n+1) a[i][j]=0。 // 方陣對(duì)角線元素賦值 if(i+jn+1 amp。amp。 ij) a[i][j]=i。 // 方陣上部元素賦值 if(i+jn+1 amp。amp。 ij) a[i][j]=j。 // 方陣左部元素賦值 if(i+jn+1 amp。amp。 ij) a[i][j]=n+1i。 // 方陣下部元素賦值 if(i+jn+1 amp。amp。 ij) a[i][j]=n+1j。 // 方陣右部元素賦值 } printf( %d階對(duì)稱方陣為:\n,n)。 for(i=1。i=n。i++) { for(j=1。j=n。j++) // 輸出對(duì)稱方陣 printf(%3d,a[i][j])。 printf(\n)。 } }15 據(jù)例12的算法，寫(xiě)出求解n個(gè)“1”組成的整數(shù)能被2011整除的程序。修改程序，求出 n至少為多大時(shí)，n個(gè)“1”組成的整數(shù)能被2013整除？解：程序?yàn)閕nclude void main(){ int a,c,p,n。 p=2011。c=1111。n=4。 // 變量c與n賦初值 while(c!=0) // 循環(huán)模擬整數(shù)豎式除法 { a=c*10+1。c=a%p。n=n+1。 // 每試商一位n增1 }printf( 由 %d 個(gè)1組成的整數(shù)能被 %d 整除。\n,n,p)。}習(xí)題221 解不等式設(shè)n為正整數(shù)，解不等式解：上下限一般為鍵盤(pán)輸入的a,b。// 解不等式: a1+1/(1+1/2)+...+1/(1+1/2+...+1/n)binclude includevoid main(){ long a,b,c,d,i。 double ts,s。 printf( 請(qǐng)輸入a,b: )。 scanf(%d,%d,amp。a,amp。b)。 i=0。ts=0。s=0。 while(sa) { i=i+1。 ts=ts+(double)1/i。 s=s+1/ts。} c=i。 while(sb) {i=i+1。 ts=ts+(double)1/i。 s=s+1/ts。} d=i1。 printf(\n 滿足不等式的正整數(shù)n為: %ld≤n≤%ld \n,c,d)。}22 韓信點(diǎn)兵韓信在點(diǎn)兵的時(shí)候，為了知道有多少個(gè)兵，同時(shí)又能保住軍事機(jī)密，便讓士兵排隊(duì)報(bào)數(shù)。按從1至5報(bào)數(shù),記下最末一個(gè)士兵報(bào)的數(shù)為1；再按從1至6報(bào)數(shù),記下最末一個(gè)士兵報(bào)的數(shù)為5；再按1至7報(bào)數(shù),記下最末一個(gè)報(bào)的數(shù)為4；最后按1至11報(bào)數(shù),最末一個(gè)士兵報(bào)的數(shù)為10。你知道韓信至少有多少兵?1. 求解要點(diǎn)設(shè)兵數(shù)為x，則x滿足下述的同余方程組: x=5y+1 即 x=1 (mod 5) x=6z+5 x=5 (mod 6) x=7u+4 x=4 (mod 7) x=11v+10 x=10 (mod 11)其中y,z,u,v都為正整數(shù)。試求滿足以上方程組的最小正整數(shù)x。應(yīng)用枚舉可得到至少的兵數(shù)。x從1開(kāi)始遞增1取值枚舉當(dāng)然可以，但不必要。事實(shí)上枚舉次數(shù)可聯(lián)系問(wèn)題的具體實(shí)際大大縮減。（1) 注意到x除11余10，于是可設(shè)置x從21開(kāi)始，以步長(zhǎng)11遞增。此時(shí)，只要判別前三個(gè)條件即可。（2) 由以上第2，4兩方程知x+1為11的倍數(shù)，也為6的倍數(shù)。而11與6互素，因而x+1必為66的倍數(shù)。于是取x=65開(kāi)始，以步長(zhǎng)66遞增。此時(shí),只要判別x%5=1與x%7=4 兩個(gè)條件即可。這樣可算得滿足條件的最小整數(shù)x即點(diǎn)兵的數(shù)量。 2. 程序?qū)崿F(xiàn)// 韓信點(diǎn)兵 include void main(){ long int x。 x=65。 while(1) { x=x+66。 if(x%5==1 amp。amp。 x%7==4) { printf(至少有兵: %ld 個(gè)。,x)。 break。 } }}23 分解質(zhì)因數(shù)對(duì)給定區(qū)間[m,n]的正整數(shù)分解質(zhì)因數(shù),每一整數(shù)表示為質(zhì)因數(shù)從小到大順序的乘積形式。如果被分解的數(shù)本身是素?cái)?shù)，則注明為素?cái)?shù)。例如, 2012=2*2*503, 2011=(素?cái)?shù)!)。解：對(duì)區(qū)間中的每一個(gè)整數(shù)i(b=i)，用k(2——sqrt(i))試商：若不能整除，說(shuō)明該數(shù)k不是b的因數(shù)，k增1后繼續(xù)試商。若能整除，說(shuō)明該數(shù)k是b的因數(shù)，打印輸出k*；b除以k的商賦給b(b=b/k)后繼續(xù)用k試商(注意，可能有多個(gè)k因數(shù))，直至不能整除，k增1后繼續(xù)試商。按上述從小至大試商確定的因數(shù)顯然為質(zhì)因數(shù)。如果有大于sqrt(n)的因數(shù)(至多一個(gè)!),在試商循環(huán)結(jié)束后要注意補(bǔ)上，不要遺失。如果整個(gè)試商后b的值沒(méi)有任何縮減，仍為原待分解數(shù)n，說(shuō)明n是素?cái)?shù)，作素?cái)?shù)說(shuō)明標(biāo)記。若k是b的因數(shù)，按格式輸出，然后b=b/k后繼續(xù)試商k。若k不是b的因數(shù)，則k增1后繼續(xù)。若上述試商完成后1bi，說(shuō)明i有一個(gè)大于sqrt(i)的因數(shù)，要補(bǔ)上該因數(shù)。若試商后b還是原來(lái)的i,則i是素?cái)?shù)。// 質(zhì)因數(shù)分解乘積形式 includeinclude void main(){long int b,i,k,m,n,w=0。printf([m,n]中整數(shù)分解質(zhì)因數(shù)（乘積形式）.\n)。printf(請(qǐng)輸入m,n:)。scanf(%ld,%ld,amp。m,amp。n)。for(i=m。i=n。i++) // i為待分解的整數(shù) { printf(%ld=,i)。 b=i。k=2。 while(k=sqrt(i)) // k為試商因數(shù) {if(b%k==0) {b=b/k。if(b1) {printf(%ld*,k)。continue。 // k為質(zhì)因數(shù),返回再試 }if(b==1) printf(%ld\n,k)。} k++。} if(b1 amp。amp。 bi) printf(%ld\n,b)。 // 輸出大于i平方根的因數(shù) if(b==i) {printf((素?cái)?shù)!)\n)。w++。} // b=i,表示i無(wú)質(zhì)因數(shù) }}24 基于素?cái)?shù)代數(shù)和的最大最小定義和： (和式中第k項(xiàng)177。(2k1)*(2k+1)的符號(hào)識(shí)別：當(dāng)(2k1)與(2k+1)中至少有一個(gè)素?cái)?shù)，取“+”；其余取“”。例如和式中第13項(xiàng)取“”，即為25*27。)1) 求s(2011)。2) 設(shè)1=n=2011，當(dāng)n為多大時(shí)，s(n)最大。3) 設(shè)1=n=2011，當(dāng)n為多大時(shí)，s(n)最小。解：代數(shù)和式中各項(xiàng)的符號(hào)并不是簡(jiǎn)單的正負(fù)相間，而是隨著構(gòu)成素?cái)?shù)而改變。因而在求和之前應(yīng)用“試商判別法”對(duì)第k個(gè)奇數(shù)2k1是否為素?cái)?shù)進(jìn)行標(biāo)注：若2k1為素?cái)?shù)，標(biāo)注a[k]=1；否則，若2k1不是素?cái)?shù)，a[k]=0。設(shè)置k循環(huán)（1——n），循環(huán)中分別情況求和：若a[k]+a[k+1]=1，即(2k1)與(2k+1)中至少有一個(gè)素?cái)?shù)，實(shí)施“+”；否則，若a[k]+a[k+1]==0，即(2k1)與(2k+1)中沒(méi)有素?cái)?shù)，實(shí)施“”。同時(shí)，設(shè)置最大值變量smax，最小值變量smin。在循環(huán)中，每計(jì)算一個(gè)和值s，與smax比較確定最大值，同時(shí)記錄此時(shí)的項(xiàng)數(shù)k1；與smin比較確定最小值，同時(shí)記錄此時(shí)的項(xiàng)數(shù)k2。// 基于素?cái)?shù)的整數(shù)和 includeincludevoid main(){ int t,j,n,k,k1,k2,a[3000]。 long s,smax,smin。 printf( 請(qǐng)輸入整數(shù)n: )。 scanf(%d,amp。n)。 for(k=1。k=n+1。k++) a[k]=0。 for(k=2。k=n+1。k++) {for(t=0,j=3。j=sqrt(2*k1)。j+=2) if((2*k1)%j==0)