【正文】 ak。 for(i=1。i++) { for(j=1。j++) // 按m行n列輸出矩陣 printf(%4d,a[i][j])。 } }37 猴子吃桃有一猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了1個(gè)。以后每天早上都吃了前一天剩下的一半后又多吃1個(gè)。求第1天共摘了多少個(gè)桃子。設(shè)第k天的桃子數(shù)是t(k)，則有遞推關(guān)系 t(k)=2*(t(k+1)+1) (k=1,2,…,9)初始條件：t(10)=1逆推求出t(1)，即為所求的第一天所摘桃子數(shù)。 long t[1000]。 // 確定初始條件 for(k=9。k) // 逆推計(jì)算t(1) t[k]=2*(t[k+1]+1)。\n,t[1])。k=9。 printf( 吃了%4ld+1=%4ld個(gè)，,t[k]/2,t[k]/2+1)。\n,t[k]/21)。)。第2天早上又將剩下的桃子吃掉一半，又多吃了m個(gè)。到第n天早上想再吃時(shí)，見只剩下d個(gè)桃子了。// 拓廣猴子吃桃程序 include void main(){ int d,k,m,n。 printf( 請(qǐng)確定正整數(shù)m,n,d: )。m,amp。d)。 // 確定初始條件 for(k=n1。k) // 逆推計(jì)算t(1) t[k]=2*(t[k+1]+m)。\n,t[1])。k=n1。 printf( 吃了%4ld+%d=%4ld個(gè)，,t[k]/2,m,t[k]/2+1)。\n,t[k]/2m)。,n,d)。(1) 應(yīng)用遞推求解// 裴波那契數(shù)列遞推程序 include void main(){ int k。 f[1]=1。 s=f[1]+f[2]。k=40。 // 實(shí)施遞推 s+=f[k]。 printf( 前40項(xiàng)之和為: %ld \n,s)。 long a,b,s。b=1。 // 迭代變量a,b,s賦初值 k=2。 // 推出a是f數(shù)列的第2k1項(xiàng) b=a+b。 // 推出s是f數(shù)列的前2k項(xiàng)之和 k=k+1。printf( 前40項(xiàng)之和為：%ld \n,s)。程序設(shè)計(jì)：include long f(int n){ long g。 else g=n*f(n1)。 }void main(){ int k,n。 printf( 請(qǐng)輸入n: )。n)。k=n。 printf( s=%f \n,s)。解：定義f數(shù)列的遞歸函數(shù)f(n),在求和的k(1——n)循環(huán)中實(shí)施求和 s+=f(k)。 if(n==1 || n==2) g=1。 return(g)。 long s=0。scanf(%d,amp。 for(k=1。k++) s+=f(k)。 printf( s=%ld \n,s)。解：include long b(int n){ long g。 else if(n==2) g=2。 return(g)。 long s=0。scanf(%d,amp。 for(k=1。k++) s+=b(k)。 printf( s=%ld \n,s)。// 擺動(dòng)數(shù)列 include int a(int n){ int g。 else if(n%2==0) g=a(n/2)+1。 return(g)。 long s=0。scanf(%d,amp。 for(k=1。k++) s+=a(k)。 printf( s=%ld \n,s)。// 楊輝三角遞歸設(shè)計(jì) void c(int a[],int n){int i。 else if(n==1){a[1]=1。}else{c(a,n1)。for(i=n。i)a[i]=a[i]+a[i1]。}}includevoid main(){ int i,j,k,n,a[100]。 scanf(%d,amp。for(j=0。j++){c(a,j)。k=302*j。 for(i=1。i++) printf(%4d,a[i])。}}46 試把mn順轉(zhuǎn)矩陣的遞歸設(shè)計(jì)轉(zhuǎn)變?yōu)檫f推設(shè)計(jì)。設(shè)置i(1——d)循環(huán)，從外圈至內(nèi)圈，分4邊進(jìn)行遞推賦值。 printf( m行n列矩陣,請(qǐng)確定m,n: )。m,amp。 c=n。 d=(c+1)/2。h=0。i=d。 for(v=i。v++) {s++。} // d圈的首行從左至右賦值 for(h=i。h++) {s++。} // d圈的尾列從上至下賦值 for(v=n+1i。v) { s++。 // d圈的尾行從右至左賦值 if(s==m*n) {i=d。} } // 賦值完成即行退出 for(h=m+1i。h) { s++。 // d圈的首列從下至上賦值 if(s==m*n) {i=d。}} } printf( %d行%d列旋轉(zhuǎn)矩陣為:\n,m,n)。i=m。j=n。 printf(\n)。解：在遞歸函數(shù)中，每圈4邊按左列左列從上至下遞增、下行從左至右遞增、右列從下至上遞增、上行從右至左遞增給元素賦值。void main(){ int h,v,b,s,d。scanf(%d,%d,amp。n)。if(mn) s=n。d=1。 // 遞歸函數(shù)說(shuō)明 t(b,s,d)。 for(h=1。h++) {for(v=1。v++) printf( %3d,a[h][v])。 } return。if(s=0) return。j=m+12*b。h++。}for(j=1。j++) // 一圈的下行從左至右遞增 { a[h][v]=d。d++。j=m+12*b。h。if(dm*n) return。j=n+12*b。v。if(dm*n) return。 // 調(diào)用內(nèi)一圈遞歸函數(shù) }48 應(yīng)用遞歸設(shè)計(jì)實(shí)現(xiàn)n個(gè)相同元素與另m個(gè)相同元素的所有排列。當(dāng)k=m+n時(shí)，作變量h統(tǒng)計(jì)“0”的個(gè)數(shù)。然后回溯返回，繼續(xù)。主程序中調(diào)用p(1)。 long s=0。 printf( input n,m: )。n,amp。 printf( %d個(gè)1與%d個(gè)0的排列:\n,n,m)。 // 從第1個(gè)數(shù)開始 printf(\n s=%ld \n,s)。 if(k=m+n) { for(i=0。i++) { a[k]=i。j=n+m。 if(h==m) // 若0的個(gè)數(shù)為m個(gè),輸出一排列 { s++。 for(j=1。j++) printf(%d,a[j])。 } } else p(k+1)。}習(xí)題551 倒橋本分?jǐn)?shù)式把1,2,...,9這9個(gè)數(shù)字填入下式的9個(gè)方格中，數(shù)字不得重復(fù),且要求1不得填在各分?jǐn)?shù)的分母，且式中各分?jǐn)?shù)的分子分母沒有大于1的公因數(shù)，使下面的分?jǐn)?shù)等式成立□□ □□ □□── + ─── = ──□ □ □這一填數(shù)分?jǐn)?shù)等式共有多少個(gè)解?解: 在橋本分?jǐn)?shù)式回溯程序中修改 // 倒橋本分?jǐn)?shù)式回溯實(shí)現(xiàn) // 把1,2,...,9填入□□/□+□□/□=□□/□ include void main(){int g,i,k,u,t,a[10]。i=1。while (1) {g=1。k=1。break。amp。amp。amp。amp。m2=a[5]*10+a[6]。for(t=0,u=2。u++) {if(a[1]%u==0 amp。 m1%u==0) t=1。amp。 if(a[7]%u==0 amp。 m3%u==0) t=1。amp。printf(=%d/%ld \n,m3,a[7])。amp。a[i]=1。} // 不到9個(gè)數(shù),往后繼續(xù) while(a[i]==9 amp。 i1) i。amp。else a[i]++。請(qǐng)?jiān)O(shè)計(jì)算法解決這 “兩組均分”問(wèn)題。我們可采用回溯法逐步實(shí)施調(diào)整。把這2n個(gè)數(shù)分成二個(gè)組,每組n個(gè)數(shù)。 考察b(1)所在的組,只要另從b(2)─b(2n)中選取n1個(gè)數(shù)。因組合與順序無(wú)關(guān),不妨設(shè) 2 ≤ a(2)a(3)...a(n) ≤2n 從a(2)取2開始,以后a(i)從a(i1)+1開始遞增1取值,直至n+i為止。 當(dāng)a(n)已取值,計(jì)算s=b(1)+b(a(2))+…+b(a(n)),對(duì)和s進(jìn)行判別: 若s=s1,滿足要求,實(shí)現(xiàn)平分。如果a(n)已增至2n,則回溯前一個(gè)a(n1)增1再試。直至a(2)增至n+2時(shí),結(jié)束。有解時(shí),找到并輸出所有解。 （2） 兩組均分程序設(shè)計(jì)// 兩組均分程序設(shè)計(jì) define N 50include include include void main(){int n,m,a[N],b[2*N],i,j,t。printf(把2n個(gè)整數(shù)分為和相等的兩個(gè)組,每組n個(gè)數(shù).\n)。srand(t)。 scanf(%d,amp。 for(s=0,i=1。i++) // 產(chǎn)生2n個(gè)不同的隨機(jī)整數(shù) {t=0。 for(j=1。j++) if(b[i]==b[j]) {t=1。} if(t==1) {i。} // 出現(xiàn)相同數(shù)時(shí)，返回重新產(chǎn)生 s+=b[i]。 } if(s%2==0) {printf(\n以上%d個(gè)整數(shù)總和為%d.\n,2*n,s)。} else printf(\n 和%ld為奇數(shù),無(wú)法平分!\n,s)。i=2。m=0。j=n。 if(s==s1) // 滿足均分條件時(shí)輸出 {m++。 for(j=1。j++) printf(%d ,b[a[j]])。 a[i]=a[i1]+1。} while(a[i]==n+i) i。 else break。,m)。} 53 指定低逐位整除數(shù)探求試求出所有最高位為3的24位低逐位整除數(shù)（除個(gè)位數(shù)字為“0”外,其余各位數(shù)字均不得為“0”）。 long s=0。 scanf(%d,amp。 printf( 所求%d位最高位為3的右逐位整除數(shù)：\n,n)。j=100。 t=0。i=1。amp。 for(r=0,j=i。j) // 檢測(cè)i時(shí)是否整除i { r=r*10+a[j]。 } if(r!=0) { a[i]=a[i]+1。 // 余數(shù)r!=0時(shí)a[i]增1,t=1 while(a[i]9 amp。 i1) { a[i]=1。 // 回溯 a[i]=a[i]+1。 // 余數(shù)r=0時(shí),t=0 if(t==0 amp。 i==n) { if(a[n]==3){s++。 for(j=n。j) printf(%d,a[j])。} a[i]=a[i]+1。 else printf( 未找到n位右逐位整除數(shù).,n)。(1) 設(shè)計(jì)要點(diǎn)為簡(jiǎn)化輸出，環(huán)序列簡(jiǎn)化為一般序列輸出，為避免重復(fù)，約定首項(xiàng)為“1”。因而設(shè)置a循環(huán)在沒有重復(fù)數(shù)字?jǐn)?shù)字且以“1”開頭的8位數(shù)812345678——18765432中枚舉。為操作與判斷方便，設(shè)置3個(gè)數(shù)組：f數(shù)組統(tǒng)計(jì)8位數(shù)a中各個(gè)數(shù)字的頻數(shù)。g數(shù)組表示8位數(shù)a中每位數(shù)的數(shù)字。b數(shù)組標(biāo)記整數(shù)x是否為素?cái)?shù)。枚舉實(shí)施：1） 注意到8項(xiàng)中每相鄰兩項(xiàng)之和不超過(guò)15,對(duì)15以內(nèi)的5個(gè)素?cái)?shù)用b數(shù)組標(biāo)注“1”,其余均為“0”。3） 設(shè)置k(1——8)判斷循環(huán)：若f[k]!=1 ，表明數(shù)字k出現(xiàn)重復(fù)或遺漏，返回。順便說(shuō)明，為判斷方便，首項(xiàng)“1”先行賦值給g[9]，以與g[8]相鄰，在k循環(huán)中一道進(jìn)行判別。(2) 枚舉實(shí)現(xiàn)8項(xiàng)素?cái)?shù)和環(huán)// 8項(xiàng)素?cái)?shù)和環(huán)枚舉求解 includeincludevoid main(){ int t,k,s,x,g[10],f[10],b[18]。 for(k=1。k++) b[k]=0。s=