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