【正文】 %j==0) {t=1。 for(k=2。n)。// 基于素?cái)?shù)的整數(shù)和 includeincludevoid main(){ int t,j,n,k,k1,k2,a[3000]。因而在求和之前應(yīng)用“試商判別法”對第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。)1) 求s(2011)。w++。} if(b1 amp。if(b1) {printf(%ld*,k)。i++) // i為待分解的整數(shù) { printf(%ld=,i)。m,amp。// 質(zhì)因數(shù)分解乘積形式 includeinclude void main(){long int b,i,k,m,n,w=0。若k是b的因數(shù)，按格式輸出，然后b=b/k后繼續(xù)試商k。若能整除，說明該數(shù)k是b的因數(shù)，打印輸出k*；b除以k的商賦給b(b=b/k)后繼續(xù)用k試商(注意，可能有多個(gè)k因數(shù))，直至不能整除，k增1后繼續(xù)試商。 } }}23 分解質(zhì)因數(shù)對給定區(qū)間[m,n]的正整數(shù)分解質(zhì)因數(shù),每一整數(shù)表示為質(zhì)因數(shù)從小到大順序的乘積形式。amp。 2. 程序?qū)崿F(xiàn)// 韓信點(diǎn)兵 include void main(){ long int x。而11與6互素，因而x+1必為66的倍數(shù)。事實(shí)上枚舉次數(shù)可聯(lián)系問題的具體實(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ù)。} d=i1。} c=i。s=0。a,amp。// 解不等式: a1+1/(1+1/2)+...+1/(1+1/2+...+1/n)binclude includevoid main(){ long a,b,c,d,i。n=n+1。c=1111。 printf(\n)。i=n。amp。 // 方陣左部元素賦值 if(i+jn+1 amp。 ij) a[i][j]=i。j=n。n)。左部按列號j賦值；右部按列號函數(shù)n+1j賦值?？芍鲗蔷€：i=j；次對角線：i+j=n+1。證：設(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)。break。k+=2) if(b%k==0) {x=1。 for(b=a*100?1。j++) m=m+j。k=n。解：設(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)。k=n。j) m=m+j。 for(k=1。 b=b*c。解：設(shè) (這里int(x)表示取正數(shù)x的整數(shù))，注意到，有 算法描述：令c=d+1，則 input (a,b) while(1) {c=int(b/a)+1?！队?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é)束。 if(c900000000) return。 // a,b迭代，為選擇下一個(gè)分母作準(zhǔn)備 if(a==1) { print(1/b)。k=n。 解：因s=1+2+…+n=n(n+1)/2 時(shí)間復(fù)雜度為O(n2)。k++) ?for(j=1。（3）t=1。k++) {t=t*k。 }解：因s=1+22!+ 33!+…+ nn!=(n+1)!?1時(shí)間復(fù)雜度為O((n+1)!).（4）for(a=1。b=a*100?99。break。}}解：因a循環(huán)n次；對每一個(gè)a,b循環(huán)50次；對每一個(gè)b,k循環(huán)次。14 構(gòu)建對稱方陣觀察圖15所示的7階對稱方陣： 圖15 7階對稱方陣試構(gòu)造并輸出以上n階對稱方陣。兩對角線賦值“0”。（2） 程序?qū)崿F(xiàn)include void main(){int i,j,n,a[30][30]。 for(i=1。j++) {if(i==j || i+j==n+1) a[i][j]=0。 // 方陣上部元素賦值 if(i+jn+1 amp。amp。 ij) a[i][j]=n+1j。i++) { for(j=1。 } }15 據(jù)例12的算法，寫出求解n個(gè)“1”組成的整數(shù)能被2011整除的程序。n=4。 // 每試商一位n增1 }printf( 由 %d 個(gè)1組成的整數(shù)能被 %d 整除。 double ts,s。b)。 while(sa) { i=i+1。 while(sb) {i=i+1。 printf(\n 滿足不等式的正整數(shù)n為: %ld≤n≤%ld \n,c,d)。試求滿足以上方程組的最小正整數(shù)x。（1) 注意到x除11余10，于是可設(shè)置x從21開始，以步長11遞增。于是取x=65開始，以步長66遞增。 x=65。 x%7==4) { printf(至少有兵: %ld 個(gè)。如果被分解的數(shù)本身是素?cái)?shù)，則注明為素?cái)?shù)。按上述從小至大試商確定的因數(shù)顯然為質(zhì)因數(shù)。若k不是b的因數(shù)，則k增1后繼續(xù)。printf([m,n]中整數(shù)分解質(zhì)因數(shù)（乘積形式）.\n)。n)。 b=i。continue。amp。} // b=i,表示i無質(zhì)因數(shù) }}24 基于素?cái)?shù)代數(shù)和的最大最小定義和： (和式中第k項(xiàng)177。2) 設(shè)1=n=2011，當(dāng)n為多大時(shí)，s(n)最大。設(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í)施“”。 long s,smax,smin。 for(k=1。k=n+1。break。smin=s。 // 實(shí)施代數(shù)和 else s=(2*k1)*(2*k+1)。k2=k。}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中。在不存在重復(fù)數(shù)字的情形下，檢測若f[0]+f[1]+f[4]=0，說明7位平方數(shù)d中沒有數(shù)字“0”,“1”,“4”,d滿足題意要求，打印輸出。b=sqrt(2356789)。a++){d=a*a。k++) f[k]=0。} for(t=0,k=1。amp。 }} printf( 共可組成%d個(gè)沒有重復(fù)數(shù)字的7位平方數(shù).\n,n)。 scanf(%d,amp。i++) for(j=1。 i=j) a[i][j]=(n+1)/2i+1。 // 方陣左部元素賦值 if(i+j=n+1 amp。amp。i=n。 printf(\n)。設(shè)置a,b,c,d循環(huán)，對每一組a,b,c,d,計(jì)算e=a*b+c/d。設(shè)置n統(tǒng)計(jì)解的個(gè)數(shù)。a=98。c=987。e=a*b+x。m[3]=e。x=9。k++) {y=m[k]。 // 分離數(shù)字f數(shù)組統(tǒng)計(jì) } } for(t=0,x=1。} // 檢驗(yàn)數(shù)字09各只出現(xiàn)一次 if(t==0) // 輸出一個(gè)解，用n統(tǒng)計(jì)個(gè)數(shù) {n++。探索最早的合數(shù)世紀(jì)。 int s,x。 // 檢驗(yàn)a世紀(jì) for(b=a*10099。k=sqrt(b)。 // 當(dāng)前為非合數(shù)世紀(jì)時(shí)，跳出循環(huán)進(jìn)行下世紀(jì)的探求 s=s+x。（其中n是鍵盤輸入的任意正整數(shù)。求出該區(qū)間內(nèi)的一個(gè)素?cái)?shù)m，設(shè)前一個(gè)素?cái)?shù)為f,判別：若mfn，則輸出結(jié)果[f+1,f+n]后結(jié)束；否則，作賦值f=m，為求下一個(gè)素?cái)?shù)作準(zhǔn)備。 printf( 求最小的n個(gè)連續(xù)合數(shù).\n)。 c=3。m=d。break。 printf([%ld,%ld]。 } if(t==0) f=m。 圖27 9數(shù)字三角形（1）求解要點(diǎn)。b(7)的取值范圍為b(1)+1～(s28)/2。 b(5)的取值范圍為(s1b(4)b(7))/2+1～s1b(4)b(7)。（2）9數(shù)字三角形求解程序設(shè)計(jì)。s)。b[1]++) for(b[7]=b[1]+1。b[4]++) { if((s+b[1]+b[4]+b[7])%3!=0) continue。b[3]++) for(b[5]=(s1b[4]b[7])/2+1。b[8]++) { b[2]=s1b[1]b[4]b[3]。 for(k=1。j++) if(b[k]==b[j]) {t=1。 s2=b[1]*b[2]*b[3]*b[4]。 printf( %3d：%2d,n,b[1])。 printf( s1=%d, s2=%d \n,s1,s2)。解： include void main(){ int k,n。n)。 for(k=3。} printf( b(%d)=%ld \n,n,b[n])。所謂“排頭”就是隊(duì)列中尚未選入m的最小的數(shù)（下標(biāo)）。}if(2*m(p2)3*m(p3)){ m(i)=3*m(p3)+1。p2++。 m[1]=1。 // 排頭p2,p3賦初值 printf( 請輸入n: )。i=n。} else { m[i]=3*m[p3]+1。} printf( m(%d)=%ld\n,n,m[n])。顯然，第1項(xiàng)也是最小項(xiàng)為1（當(dāng)x=y=z=0時(shí)）。c=5。遞推過程描述：a=2。k=n。a=a*2。b=b*3。上述遞推算法的時(shí)間復(fù)雜度與空間復(fù)雜度均為O(n)。 scanf(%d,amp。p3=0。c=5。k++) { if(ab amp。 // 用2的冪給f[k]賦值 t=2。 bc) { f[k]=b。 // t=3表示3的冪，p3為指數(shù) } else { f[k]=c。 // t=5表示5的冪，p5為指數(shù) } s+=f[k]。 else printf((5^%d) \n,p5)。（2）程序?qū)崿F(xiàn)// 復(fù)合冪序列求和 include void main(){int k,n。n)。 for(k=1。 // 實(shí)施遞推 sum=sum+s[k]。1. 算法設(shè)計(jì)設(shè)在t秒時(shí)α粒子數(shù)為f(t)，β粒子數(shù)為g(t)，依題可知： g(t)=3f(t1)+2g(t1) （1）f(t)=g(t1) （2）g(0)=0,f(0)=1由（2）得f(t1)=g(t2)