第一章-算法與程序設(shè)計(jì)概述

第2章窮舉與回溯1主要內(nèi)容2.1窮舉及其應(yīng)用2.2窮舉設(shè)計(jì)的優(yōu)化2.3回溯法及其描述2.4回溯設(shè)計(jì)應(yīng)用2.5回溯設(shè)計(jì)的優(yōu)化22.1窮舉及其應(yīng)用2.1.1窮舉概述窮舉法又稱列舉法，其基本思想是逐一列舉問題所涉及的所有情況。窮舉法常用于解決“是否存在”或“有多少種可能”等問題。應(yīng)用窮舉法時(shí)應(yīng)注意對(duì)問題所涉及的有限種情形須一一列舉，既不能重復(fù)，又不能遺漏。窮舉通常應(yīng)用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。在循環(huán)體中，應(yīng)用選擇結(jié)構(gòu)實(shí)施判斷篩選，求得所要求的解。3窮舉法的框架描述：

n=0;for(k=<區(qū)間下限>;k<=<區(qū)間上限>;k++)/*據(jù)指定范圍實(shí)施窮舉*/if(<約束條件>)/*據(jù)約束條件實(shí)施篩選*/{printf(<滿足要求的解>);/*輸出解*/n++;/*統(tǒng)計(jì)解的個(gè)數(shù)*/}4【例2.2】統(tǒng)計(jì)分母在區(qū)間[a,b]的最簡真分?jǐn)?shù)(分子小于分母，且分子分母無公因數(shù))共有多少個(gè),并求最簡真分?jǐn)?shù)升序序列中的第k項(xiàng)(正整數(shù)a,b,k從鍵盤輸入)。

算法設(shè)計(jì):為排序方便，設(shè)置數(shù)組c存儲(chǔ)分子，數(shù)組d存儲(chǔ)分母。真分?jǐn)?shù)升序排序后的第k項(xiàng)為c(k)/d(k)。在[a,b]內(nèi)窮舉分?jǐn)?shù)i/j的分母j:a,a+1,…,b；對(duì)每一個(gè)分母j窮舉分子i:1,2,…,j-1。若分子i與分母j存在大于1的公因數(shù),說明i/j非最簡,忽略不計(jì)；否則賦值得一個(gè)最簡真分?jǐn)?shù)c(n)/d(n)。數(shù)組下標(biāo)n統(tǒng)計(jì)最簡真分?jǐn)?shù)的個(gè)數(shù)。應(yīng)用冒泡法排序后即可打印出指定的第k項(xiàng)c(k)/d(k)。5【例2.3】已知集合A定義如下:1∈A，2∈A；x,y∈A=>2x+3y∈A試求集合A元素從小到大排列的序列的前n項(xiàng)。（1）按第n項(xiàng)的大小循環(huán)設(shè)計(jì)

x,y可以是已產(chǎn)生的所有已有項(xiàng)中的任意兩項(xiàng)，已產(chǎn)生項(xiàng)越多，遞推生成的新項(xiàng)也就越多。窮舉循環(huán)變量k從3開始遞增1取值,到第n項(xiàng)時(shí)k的終值尚無法確定，可約定一個(gè)較大的終值（例如10000）。若k可由已有的項(xiàng)a(j)，a(i)(j<i)推得，即若k滿足條件k=2*a[j]+3*a[i]或k=2*a[i]+3*a[j]，說明k是a數(shù)列中的一項(xiàng)，賦值給a(t)。當(dāng)項(xiàng)數(shù)t達(dá)到規(guī)定項(xiàng)數(shù)n時(shí),則退出窮舉。6（２）按項(xiàng)數(shù)循環(huán)設(shè)計(jì)已知前2項(xiàng)，t循環(huán)從3開始遞增1取值到指定的項(xiàng)數(shù)n。第一項(xiàng)的值k從2開始遞增取值，對(duì)每一個(gè)k取值，標(biāo)記h=0賦值；若k可由已有的項(xiàng)a(j)，a(i)(j<i)推得，即若k滿足條件k=2*a[j]+3*a[i]或k=2*a[i]+3*a[j]，說明k是a數(shù)列中的一項(xiàng)，賦值給a(t)，同時(shí)標(biāo)記h=1賦值。對(duì)某項(xiàng)數(shù)t若h=0時(shí)，則t減1后循環(huán)，即對(duì)于原t使k增值后繼續(xù)，直到達(dá)到規(guī)定項(xiàng)數(shù)n為止。72.2.1優(yōu)選窮舉對(duì)象選擇合適的窮舉對(duì)象是窮舉優(yōu)化的首要條件?！纠?.4】把一個(gè)6位整數(shù)分為前后兩個(gè)3位數(shù),若該數(shù)等于所分兩個(gè)3位數(shù)和的平方,則稱該數(shù)為6位分段和平方數(shù)。試求出所有6位分段和平方數(shù)。（1)對(duì)所有6位數(shù)窮舉（2)對(duì)3位數(shù)窮舉2.2窮舉設(shè)計(jì)的優(yōu)化82.2.2優(yōu)化窮舉循環(huán)參量優(yōu)化窮舉循環(huán)參量可減少無效循環(huán)，提高窮舉效率?！纠?.6】求解高斯八皇后問題。在國際象棋的8×8方格的棋盤上如何放置8個(gè)皇后,使得這8個(gè)皇后不能相互攻擊。算法設(shè)計(jì)：高斯八后問題的一個(gè)解用一個(gè)八位數(shù)表示,八位數(shù)解的第k個(gè)數(shù)字為j,表示棋盤上的第k行的第j格放置一個(gè)皇后。兩個(gè)皇后不允許處在同一橫排,同一縱列，要求八位數(shù)中數(shù)字1—8各出現(xiàn)一次，不能重復(fù)。因而解的范圍區(qū)間應(yīng)為[12345678，87654321]。注意到數(shù)字1—8的任意一個(gè)排列的數(shù)字和為9的倍數(shù)，即數(shù)字1—8的任意一個(gè)排列均為9的倍數(shù)，因而窮舉a循環(huán)的窮舉范圍定為[12345678，87654321]，其循環(huán)步長可定為9。9

2.2.3精簡窮舉循環(huán)精簡一些不必要的循環(huán)，可大大提高窮舉的效率?！纠?.7】整幣兌零求解。計(jì)算把一張1元整幣兌換成1分,2分,5分,1角,2角,5角共6種零幣的不同兌換種數(shù)。（1）窮舉設(shè)計(jì)求解設(shè)面值為1，2，5，10，20，50單位零幣的個(gè)數(shù)分別為p1,p2,p3,p4,p5,p6。設(shè)置窮舉的6重循環(huán)。（2）精簡窮舉循環(huán)設(shè)計(jì)在上述程序的6重循環(huán)中，我們可精簡p1循環(huán)。（3）窮舉設(shè)計(jì)的進(jìn)一步優(yōu)化在循環(huán)設(shè)置中，p3循環(huán)從0—n/5可改進(jìn)為0—(n-2*p2)/5。102.3回溯法及其描述2.3.1回溯的基本概念回溯法找出求解問題的線索往前試探，若試探成功，即得到解；若試探失敗，就逐步往回退，換其他路線再往前試探。回溯法可以形象地概括為“向前走，碰壁回頭”。與窮舉法相比，回溯法的“聰明”之處在于能適時(shí)“回頭”，若再往前走不可能得到解，就回溯，退一步另找線路，這樣可省去大量的無效操作。應(yīng)用回溯設(shè)計(jì)求解實(shí)際問題，由于解空間的結(jié)構(gòu)差異，而且很難計(jì)算與估計(jì)回溯產(chǎn)生的結(jié)點(diǎn)數(shù)，因此回溯計(jì)算復(fù)雜度是分析回溯法效率時(shí)遇到的主要困難?；厮莘óa(chǎn)生的結(jié)點(diǎn)數(shù)通常不足解空間結(jié)點(diǎn)數(shù)的3%，這也是回溯法的計(jì)算效率大大高于窮舉法的原因所在。

112.3.2回溯法描述

1.回溯的一般方法122.回溯算法框架描述

/*輸入正整數(shù)n,m,(n≥m)*/i=1;a[i]=<元素初值>;while(1){g=1;for(k=i-1;k>=1;k--)if(<約束條件1>)g=0;/*檢測(cè),不滿足則返回*/if(g&&<約束條件2>)printf(a[1-m]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=<取值點(diǎn)>;continue;}while(a[i]==<回溯點(diǎn)>&&i>1)i--;/*向前回溯*/if(a[i]==n&&i==1)break;/*退出循環(huán)，結(jié)束*/elsea[i]=a[i]+1;}132.3.3回溯法的效益分析回溯法的時(shí)間通常取決于狀態(tài)空間樹上實(shí)際生成的那部分問題狀態(tài)的數(shù)目。對(duì)于元組長度為n的問題，若其狀態(tài)空間樹中結(jié)點(diǎn)總數(shù)為n!，則回溯算法的最壞情形的時(shí)間復(fù)雜度可達(dá)O(p(n)n!)；對(duì)于某一具體實(shí)際問題的回溯求解，常通過計(jì)算實(shí)際生成結(jié)點(diǎn)數(shù)的方法即蒙特卡羅方法（Montecarlo）來評(píng)估其計(jì)算效率。把所求得的隨機(jī)路徑上的結(jié)點(diǎn)數(shù)（或若干條隨機(jī)路徑的結(jié)點(diǎn)數(shù)的平均值）與狀態(tài)空間樹上的總結(jié)點(diǎn)數(shù)進(jìn)行比較，由其比值可以初步看出回溯設(shè)計(jì)的效益。142.4回溯設(shè)計(jì)應(yīng)用

2.4.1橋本分?jǐn)?shù)式1.問題提出日本數(shù)學(xué)家橋本吉彥教授于1993年10月在我國山東舉行的中日美三國數(shù)學(xué)教育研討會(huì)上向與會(huì)者提出以下填數(shù)趣題:把1,2,...,9這9個(gè)數(shù)字填入下式的九個(gè)方格中(數(shù)字不得重復(fù)),使下面的分?jǐn)?shù)等式成立□□□──+──=──□□□□□□橋本教授當(dāng)即給出了一個(gè)解答。這一分?jǐn)?shù)式填數(shù)趣題究竟共有多少個(gè)解答?試求出所有解答。(等式左邊兩個(gè)分?jǐn)?shù)交換次序只算一個(gè)解答)。151.回溯算法設(shè)計(jì)設(shè)置a數(shù)組,式中每一□位置用一個(gè)數(shù)組元素來表示.為判斷數(shù)字是否重復(fù),設(shè)置中間變量g：若出現(xiàn)某兩數(shù)字相同(即a(i)=a(k))或a(1)>a(4),則賦值g=0(重復(fù)標(biāo)記)。首先從a(1)=1開始,逐步給a(i)(1≤i≤9)賦值,每一個(gè)a(i)賦值從1開始遞增至9。直至a(9)賦值,判斷：若i=9,g=1,等式同時(shí)滿足,則為一組解,用n統(tǒng)計(jì)解的個(gè)數(shù)后,格式打印輸出這組解。若i<9且g=1,表明還不到九個(gè)數(shù)字,則下一個(gè)a(i)從1開始賦值繼續(xù)。若a(9)=9,則返回前一個(gè)數(shù)組元素a(8)增1賦值(此時(shí),a(9)又從1開始)再試。若a(8)=9,則返回前一個(gè)數(shù)組元素a(7)增1賦值再試。依此類推，直到a(1)=9時(shí),已無法返回,意味著已全部試畢,求解結(jié)束。16２．算法描述輸入正整數(shù)n,m,(n≥m);i=1;a[i]=<元素初值>;while(1){g=1;for(k=i-1;k>=1;k--)if(<約束條件1>)g=0;/*檢測(cè),不滿足返回*/if(g&&<約束條件2>)printf(a[1-m]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=<取值點(diǎn)>;continue;}while(a[i]==<回溯點(diǎn)>&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循環(huán)，結(jié)束*/elsea[i]=a[i]+1;}17２．算法描述輸入n=m=9;i=1;a[i]=1;while(1){g=1;for(k=i-1;k>=1;k--)if(a[i]==a[k]||a[1]>a[4]

)g=0;/*檢測(cè),不滿足返回*/if(g&&i=9&&a[1]*m2*m3+a[4]*m1*m3=a[7]*m1*m2

)printf(a[1-m]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=1;continue;}while(a[i]==n&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循環(huán)，結(jié)束*/elsea[i]=a[i]+1;}182.4.2排列組合1.實(shí)現(xiàn)排列A(n,m)對(duì)指定的正整數(shù)m,n(約定1<m<=n),具體實(shí)現(xiàn)排列A(n,m)。（1）回溯算法設(shè)計(jì)設(shè)置一維數(shù)組a，a(i)（i=1,2,…,m）在1—n中取值。首先從a(1)=1開始,逐步給a(i)(1≤i≤m)賦值,每一個(gè)a(i)賦值從1開始遞增至n。為判斷數(shù)字是否重復(fù),設(shè)置中間變量g：先賦值g=1；若出現(xiàn)某兩數(shù)字相同(即a(i)=a(j)),則賦值g=0(重復(fù)標(biāo)記)。若i=m與g=1同時(shí)滿足,則為一組解,用s統(tǒng)計(jì)解的個(gè)數(shù)后,格式打印輸出這組解。若i<m且g=1,表明不到m個(gè)數(shù)字,下一個(gè)a(i)從1開始賦值，繼續(xù)。若a(i)=n,則返回前一個(gè)數(shù)組元素a(i-1)增1賦值。直到a(1)=9時(shí),已無法返回,意味著已全部試畢,求解結(jié)束。

19２．算法描述輸入正整數(shù)n,m,(n≥m);i=1;a[i]=1;while(1){g=1;for(j=1;j<i;j++)if(a[j]==a[i]

)g=0;/*檢測(cè),不滿足返回*/if(g&&i==m)printf(a[1-m]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=1;continue;}while(a[i]==n&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循環(huán)，結(jié)束*/elsea[i]=a[i]+1;}203.程序變通注意到組合與組成元素的順序無關(guān)，約定組合中的組成元素按遞增排序。因而，把以上程序中的約束條件1（a[j]==a[i]）修改為a[j]>=a[i]，即可實(shí)現(xiàn)從n個(gè)不同元素中取m個(gè)(約定1<m<n)的組合。把以上程序中的輸出語句printf("%d",a[j])改為printf("%c",a[j]+64);排列(或組合)輸出由前n個(gè)正整數(shù)改變?yōu)榍皀個(gè)大寫英文字母輸出。把以上程序中的輸出語句printf("%d",a[j])改為printf("%c",n+65-a[j]);排列(或組合)輸出由前n個(gè)正整數(shù)改變?yōu)榍皀個(gè)大寫英文字母逆序輸出。

21

1.問題提出由2n個(gè)0或1組成的數(shù)環(huán)，形成的由相連n個(gè)數(shù)字組成的2n個(gè)二進(jìn)制數(shù)恰好在環(huán)序列中都出現(xiàn)一次。這個(gè)序列被稱作n階德布魯金（Debrujin）環(huán)序列。為構(gòu)造與統(tǒng)計(jì)方便，約定n階德布魯金環(huán)序列由n個(gè)0開頭。二階德布魯金環(huán)序列非常簡單，顯然只有0011這一個(gè)解，2個(gè)數(shù)字組成的二進(jìn)制數(shù)依次為00,01,11,10（因?yàn)槭黔h(huán)，尾部0即開頭的0，下同），共4個(gè)，每個(gè)各出現(xiàn)一次。三階德布魯金環(huán)序列也不復(fù)雜，由000開頭,第4個(gè)數(shù)字與第8個(gè)數(shù)字顯然都為1(否則會(huì)出現(xiàn)0000出界)。余下三個(gè)數(shù)字組合只能為011,110,101三種情形。而00011011未出現(xiàn)111,且有110,011等重復(fù)，顯然不滿足三階德布魯金環(huán)序列條件。因而三階德布魯金環(huán)序列有00010111與00011101兩個(gè)解：隨著階數(shù)的增加，求解德布魯金序列難度也相應(yīng)增大。

2.4.3德布魯金環(huán)序列222.回溯求解n階德布魯金環(huán)序列在n階德布魯金環(huán)序列中，共有m=2^n個(gè)二進(jìn)制數(shù)字。設(shè)置一維a數(shù)組，約定a(n)=1，a(m-1)=1，其余數(shù)組元素為0。應(yīng)用回溯法探求a(n)——a(m-2)，這些元素取0或1。問題的解空間是由數(shù)字0或1組成的m-n-2位整數(shù)組，其約束條件是0的個(gè)數(shù)為m/2-n個(gè)，且沒有相同的由相連n個(gè)數(shù)字組成的二進(jìn)制數(shù)。當(dāng)i≤m-2時(shí)，a(i)從0取值；當(dāng)i>n+1且a(i)=1時(shí)回溯；當(dāng)i=n+1且a(i)=1時(shí)退出。當(dāng)a(n)——a(m-2)已取數(shù)字時(shí)，設(shè)置h統(tǒng)計(jì)其中0的個(gè)數(shù)，若h≠m/2-n，則返回；若h=m/2-n，判斷是否有相同的由n個(gè)數(shù)字組成的二進(jìn)制數(shù)。若存有相同的，標(biāo)注t=1；若不存在有相同的，保持t=0,作打印輸出。

233．算法描述輸入正整數(shù)n,計(jì)算m=2^n;a[n]=1;a[m-1]=1;

i=n+1;while(1){if(a[j]==a[i]

)g=0;/*檢測(cè),不滿足返回*/if(i=m-2&&h=m/2-n&&m1≠m2)printf(a[0—m-1]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=0;continue;}while(a[i]==1&&i>n+1)i--;/*回溯*/if(a[i]==1&&i==n+1)break;/*退出，結(jié)束*/elsea[i]=a[i]+1;}241.n皇后問題要求在n×n方格棋盤放置n個(gè)皇后使它們不相互攻擊(即任意兩個(gè)皇后不允許處在同一橫排,同一縱列,也不允許處在同一與棋盤邊框成45度角的斜線上。正整數(shù)n從鍵盤輸入,n>2)。2.回溯探求設(shè)計(jì)設(shè)置數(shù)組a(n),數(shù)組元素a(i)表示第i行的皇后位于第a(i)列.求n皇后問題的一個(gè)解,即尋求a數(shù)組的一組取值,該組取值中每一元素的值互不相同(即沒有任兩個(gè)皇后在同一列),且第i個(gè)元素與第k個(gè)元素相差不為abs(i-k),(即任兩個(gè)皇后不在同一45度角的斜線上)。2.4.4高斯皇后問題及其拓廣25首先a(1)從1開始取值。然后從小到大選擇一個(gè)不同于a(1)且與a(1)相差不為1的整數(shù)賦給a(2)。再從小到大選擇一個(gè)不同于a(1),a(2)且與a(1)相差不為2,與a(2)相差不為1的整數(shù)賦給a(3)。依此類推,至a(n)也作了滿足要求的賦值,打印該數(shù)組即為找到的一個(gè)n皇后的解。為了檢驗(yàn)a(i)是否滿足上述要求,設(shè)置標(biāo)志變量g,g賦初值1。若不滿足上述要求,則g=0。按以下步驟操作:

令x=abs(a(i)-a(k))(k=1,2,...,i-1)判別:若x=0或x=i-k,則g=0。若出現(xiàn)g=0,則表明a(i)不滿足要求,a(i)調(diào)整增1后再試,依此類推。若i=n且g=1,則滿足要求,用s統(tǒng)計(jì)解的個(gè)數(shù)后，格式打印輸出這組解。若i<n且g=1，表明還不到n個(gè)數(shù)，則下一個(gè)a(i)從1開始賦值繼續(xù)。

26

3．算法描述輸入正整數(shù)n;i=1;a[i]=1;while(1){g=1;for(k=i-1;k>=1;k++){x=absf(a[i]-a[k]);if(a[k]==a[i]&&x=i-k

)g=0;}/*檢測(cè),不滿足返回*/if(g&&i==n)printf(a[1-n]);/*輸出一個(gè)解*/if(i<n&&g){i++;a[i]=1;continue;}while(a[i]==n&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出，結(jié)束*/elsea[i]=a[i]+1;}274.時(shí)間測(cè)試282.5回溯設(shè)計(jì)的優(yōu)化回溯算法在搜索執(zhí)行的同時(shí)產(chǎn)生解空間，是一種系統(tǒng)地搜索問題解答的方法?；厮菟惴ū苊饬松赡切┎豢赡墚a(chǎn)生解的狀態(tài)，不斷去除那些實(shí)際上不可能產(chǎn)生所需