【正文】 / 一圈的下行從左至右遞增 { a[h][v]=d。v++。d++。}for(j=1。j=m+12*b。j++) // 一圈的右列從下至上遞增 { a[h][v]=d。h。d++。if(dm*n) return。}for(j=1。j=n+12*b。j++) // 一圈的上行從右至左遞增 { a[h][v]=d。v。d++。if(dm*n) return。 // 另一遞歸出口 }t(b+1,s2,d)。 // 調(diào)用內(nèi)一圈遞歸函數(shù) }48 應(yīng)用遞歸設(shè)計(jì)實(shí)現(xiàn)n個(gè)相同元素與另m個(gè)相同元素的所有排列。解： 設(shè)置遞歸函數(shù)p(k)，1≤k≤m+n，元素a[k]取值為0或1。當(dāng)k=m+n時(shí)，作變量h統(tǒng)計(jì)“0”的個(gè)數(shù)。若h=m則打印輸出一排列，并用s統(tǒng)計(jì)排列個(gè)數(shù)。然后回溯返回，繼續(xù)。當(dāng)km+n時(shí)，還不足n+m個(gè)數(shù),則調(diào)用p(k+1)探索下一個(gè)數(shù)。主程序中調(diào)用p(1)。// n個(gè)1與另m個(gè)0的排列 include int m,n,r,a[30]。 long s=0。void main(){ int p(int k)。 printf( input n,m: )。 scanf(%d,%d,amp。n,amp。m)。 printf( %d個(gè)1與%d個(gè)0的排列:\n,n,m)。 p(1)。 // 從第1個(gè)數(shù)開始 printf(\n s=%ld \n,s)。 // 輸出排列的個(gè)數(shù) }// 排列遞歸函數(shù) include int p(int k){ int h,i,j。 if(k=m+n) { for(i=0。i=1。i++) { a[k]=i。 // 探索第k個(gè)數(shù)賦值i if(k==m+n) // 若已到m+n個(gè)數(shù)則檢測(cè)0的個(gè)數(shù)h { for(h=0,j=1。j=n+m。j++) if(a[j]==0) h++。 if(h==m) // 若0的個(gè)數(shù)為m個(gè),輸出一排列 { s++。 printf( )。 for(j=1。j=n+m。j++) printf(%d,a[j])。 if(s%10==0) printf(\n)。 } } else p(k+1)。 // 若沒到n+m個(gè)數(shù),則調(diào)用p(k+1)探索下一個(gè)數(shù) } }return s。}習(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]。 long m1,m2,m3。i=1。a[1]=1。while (1) {g=1。 for(k=i1。k=1。k) if(a[i]==a[k]) {g=0。break。} // 兩數(shù)相同,標(biāo)記g=0 if(i==9 amp。amp。 g==1 amp。amp。 a[1]a[4] amp。amp。 a[1]1 amp。amp。 a[7]1) {m1=a[2]*10+a[3]。m2=a[5]*10+a[6]。m3=a[8]*10+a[9]。for(t=0,u=2。u=9。u++) {if(a[1]%u==0 amp。amp。 m1%u==0) t=1。 if(a[4]%u==0 amp。amp。 m2%u==0) t=1。 if(a[7]%u==0 amp。amp。 m3%u==0) t=1。 } if(t==0 amp。amp。 m1*a[4]*a[7]+m2*a[1]*a[7]==m3*a[1]*a[4]) // 判斷等式 {printf( %d/%ld+%d/%ld,m1,a[1],m2,a[4])。printf(=%d/%ld \n,m3,a[7])。}} if(i9 amp。amp。 g==1) {i++。a[i]=1。continue。} // 不到9個(gè)數(shù),往后繼續(xù) while(a[i]==9 amp。amp。 i1) i。 // 往前回溯 if(a[i]==9 amp。amp。 i==1) break。else a[i]++。 // 至第1個(gè)數(shù)為9結(jié)束 }}52 兩組均分參加拔禾比賽的12個(gè)同學(xué)的體重如下：48，43，57，64，50，52，18，34，39，56，16，61為使比賽公平，要求參賽的兩組每組6個(gè)人，且每組同學(xué)的體重之和相等。請(qǐng)?jiān)O(shè)計(jì)算法解決這 “兩組均分”問題。（1） 求解要點(diǎn)一般地，對(duì)已知的2n(n從鍵盤輸入)個(gè)整數(shù)，確定這些數(shù)能否分成2個(gè)組，每組n個(gè)數(shù)，且每組數(shù)據(jù)的和相等。我們可采用回溯法逐步實(shí)施調(diào)整。 對(duì)于已有的存儲(chǔ)在b數(shù)組的2n個(gè)數(shù),求出總和s與其和的一半s1(若這2n個(gè)數(shù)的和s為奇數(shù),顯然無法分組)。把這2n個(gè)數(shù)分成二個(gè)組,每組n個(gè)數(shù)。為方便調(diào)整,設(shè)置數(shù)組a存儲(chǔ)b數(shù)組的下標(biāo)值，即a(i):1─2n。 考察b(1)所在的組,只要另從b(2)─b(2n)中選取n1個(gè)數(shù)。即定下a(1)=1,其余的a(i)(i=2,…,n)在2─2n中取不重復(fù)的數(shù)。因組合與順序無關(guān),不妨設(shè) 2 ≤ a(2)a(3)...a(n) ≤2n 從a(2)取2開始,以后a(i)從a(i1)+1開始遞增1取值,直至n+i為止。這樣可避免重復(fù)。 當(dāng)a(n)已取值,計(jì)算s=b(1)+b(a(2))+…+b(a(n)),對(duì)和s進(jìn)行判別: 若s=s1,滿足要求,實(shí)現(xiàn)平分。 若s≠s1,則a(n)繼續(xù)增1再試。如果a(n)已增至2n,則回溯前一個(gè)a(n1)增1再試。如果a(n1)已增至2n1,繼續(xù)回溯。直至a(2)增至n+2時(shí),結(jié)束。 二堆均分問題并不總有解。有解時(shí),找到并輸出所有解。沒有解時(shí),顯示相關(guān)提示信息“無法實(shí)現(xiàn)平分”。 （2） 兩組均分程序設(shè)計(jì)// 兩組均分程序設(shè)計(jì) define N 50include include include void main(){int n,m,a[N],b[2*N],i,j,t。 long s1,s=0。printf(把2n個(gè)整數(shù)分為和相等的兩個(gè)組,每組n個(gè)數(shù).\n)。 t=time(0)%1000。srand(t)。 // 隨機(jī)數(shù)發(fā)生器初始化 printf( input n :)。 scanf(%d,amp。n)。 for(s=0,i=1。i=2*n。i++) // 產(chǎn)生2n個(gè)不同的隨機(jī)整數(shù) {t=0。b[i]=rand()%(5*n)+10。 for(j=1。j=i1。j++) if(b[i]==b[j]) {t=1。break。} if(t==1) {i。continue。} // 出現(xiàn)相同數(shù)時(shí)，返回重新產(chǎn)生 s+=b[i]。 printf(%d ,b[i])。 } if(s%2==0) {printf(\n以上%d個(gè)整數(shù)總和為%d.\n,2*n,s)。s1=s/2。} else printf(\n 和%ld為奇數(shù),無法平分!\n,s)。 a[1]=1。i=2。a[i]=2。m=0。 while(1) {if(i==n) {for(s=0,j=1。j=n。j++)s+=b[a[j]]。 if(s==s1) // 滿足均分條件時(shí)輸出 {m++。 printf(NO%d: ,m)。 for(j=1。j=n。j++) printf(%d ,b[a[j]])。 } }else {i++。 a[i]=a[i1]+1。 continue。} while(a[i]==n+i) i。 // 調(diào)整或回溯 if(i1) a[i]++。 else break。 } if(m0) printf(共有以上%d種分法。,m)。else printf( 無法實(shí)現(xiàn)二堆均分. )。} 53 指定低逐位整除數(shù)探求試求出所有最高位為3的24位低逐位整除數(shù)（除個(gè)位數(shù)字為“0”外,其余各位數(shù)字均不得為“0”）。 // 最高位為3的n位右逐位整除 includevoid main(){ int i,j,n,r,t,a[100]。 long s=0。 printf( 逐位整除n位，請(qǐng)確定n：)。 scanf(%d,amp。n)。 printf( 所求%d位最高位為3的右逐位整除數(shù)：\n,n)。 for(j=1。j=100。j++) a[j]=1。 t=0。a[1]=0。i=1。 while(a[1]1) { if(t==0 amp。amp。 in) i++。 for(r=0,j=i。j=1。j) // 檢測(cè)i時(shí)是否整除i { r=r*10+a[j]。 r=r%i。 } if(r!=0) { a[i]=a[i]+1。t=1。 // 余數(shù)r!=0時(shí)a[i]增1,t=1 while(a[i]9 amp。amp。 i1) { a[i]=1。i。 // 回溯 a[i]=a[i]+1。} } else t=0。 // 余數(shù)r=0時(shí),t=0 if(t==0 amp。amp。 i==n) { if(a[n]==3){s++。printf( %ld: ,s)。 for(j=n。j=1。j) printf(%d,a[j])。 printf(\n)。} a[i]=a[i]+1。 }} if(s0) printf( 最高位為3的%d位右逐位整除數(shù)共%ld個(gè).,n,s)。 else printf( 未找到n位右逐位整除數(shù).,n)。 }54 枚舉求解8項(xiàng)素?cái)?shù)和環(huán)，與回溯結(jié)果進(jìn)行比較。(1) 設(shè)計(jì)要點(diǎn)為簡化輸出，環(huán)序列簡化為一般序列輸出，為避免重復(fù)，約定首項(xiàng)為“1”。環(huán)中的每一項(xiàng)為一個(gè)數(shù)字，相連的8項(xiàng)構(gòu)成一個(gè)8位數(shù)。因而設(shè)置a循環(huán)在沒有重復(fù)數(shù)字?jǐn)?shù)字且以“1”開頭的8位數(shù)812345678——18765432中枚舉。注意到所有1——8沒有重復(fù)數(shù)字的8位數(shù)的數(shù)字和為9的倍數(shù)，該數(shù)也為9的倍數(shù)，為此，枚舉循環(huán)步長可取9，以精簡枚舉次數(shù)。為操作與判斷方便，設(shè)置3個(gè)數(shù)組：f數(shù)組統(tǒng)計(jì)8位數(shù)a中各個(gè)數(shù)字的頻數(shù)。如f[3]=2，即a中有2個(gè)數(shù)字“3”。g數(shù)組表示8位數(shù)a中每位數(shù)的數(shù)字。如g[4]=6，即a的從高位開始第4位數(shù)為數(shù)字“6”。b數(shù)組標(biāo)記整數(shù)x是否為素?cái)?shù)。如b[13]=1，標(biāo)識(shí)“1”表示13為素?cái)?shù)，標(biāo)識(shí)“0”為非素?cái)?shù)。枚舉實(shí)施：1） 注意到8項(xiàng)中每相鄰兩項(xiàng)之和不超過15,對(duì)15以內(nèi)的5個(gè)素?cái)?shù)用b數(shù)組標(biāo)注“1”,其余均為“0”。2） 在8位數(shù)的a 循環(huán)中，對(duì)a實(shí)施8次求余分離出各個(gè)數(shù)字x，應(yīng)用f[x]++統(tǒng)計(jì)數(shù)字x的頻數(shù)，應(yīng)用g[9k]=x記錄a的各位數(shù)字。3） 設(shè)置k(1——8)判斷循環(huán)：若f[k]!=1 ，表明數(shù)字k出現(xiàn)重復(fù)或遺漏，返回。若 b[g[k]+g[k+1]]!=1，表明相鄰的第k項(xiàng)與第k+1項(xiàng)之和不是素?cái)?shù)，返回。順便說明，為判斷方便，首項(xiàng)“1”先行賦值給g[9]，以與g[8]相鄰，在k循環(huán)中一道進(jìn)行判別。4） 通過以上判斷篩選的a，其各個(gè)數(shù)字即為所求的8項(xiàng)素?cái)?shù)環(huán)的各項(xiàng)，打印輸出。(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]。long a,y。 for(k=1。k=15。k++) b[k]=0。 g[9]=1。s=0。 b[3]=b[5]=b[7]=b[11]=b[13]=