算法競(jìng)賽入門經(jīng)典授課教案第7章暴力求解法

1、文檔編碼 : CS1N6A9A5W3 HX3B4F6F6R8 ZP6H8A3E5E4【教學(xué)內(nèi)容相關(guān)章節(jié)】第 7 章暴力求解法子集生成7.1 簡(jiǎn)潔枚舉 7.2枚舉排列 7.37.4 回溯法 7.5隱式圖搜尋【教學(xué)目標(biāo) 】（1）把握整數(shù)、子串等簡(jiǎn)潔對(duì)象的枚舉方法；（2）嫻熟把握排列生成的遞歸方法；（3）嫻熟把握用“ 下一個(gè)排列” 枚舉全排列的方法；（4）懂得解答樹,并能估算典型解答樹的結(jié)點(diǎn)數(shù)；（5）嫻熟把握子集生成的增量法、位向量法和二進(jìn)制法；（6）嫻熟把握回溯法框架,并能懂得為什么它往往比生成- 測(cè)試法高效；（7）嫻熟把握解答樹的寬度優(yōu)先搜尋和迭代加深搜尋；（8）懂得倒水問題的狀態(tài)圖與八皇后問題

2、的解答樹的本質(zhì)區(qū)分；（9）嫻熟把握八數(shù)碼問題的 BFS實(shí)現(xiàn)；（10）嫻熟把握集合的兩種典型實(shí)現(xiàn)【教學(xué)要求 】hash 表和 STL集合；把握整數(shù)、 子串等簡(jiǎn)潔對(duì)象的枚舉方法；嫻熟把握排列生成的遞歸方法；嫻熟把握用 “ 下一個(gè)排列”枚舉全排列的方法；懂得子集樹和排列樹；嫻熟把握回溯法框架；嫻熟把握解答樹的寬度優(yōu)先搜尋和迭代搜尋；嫻熟把握集合的兩種典型實(shí)現(xiàn)【教學(xué)內(nèi)容提要 】hash 表和 STL 集合；本章主要爭(zhēng)辯暴力法（也叫窮舉法、蠻力法）,它要求調(diào)設(shè)計(jì)者找出全部可能的方法,然后選擇其中的一種方法,如該方法不行行就摸索下一種可能的方法；介紹了排列生成的遞歸方法；在求解的過程中,提出明白答樹的概念

3、（如子集樹和排列樹）；介紹了回溯法的基本框架；介紹了集合的兩種典型實(shí)現(xiàn)【教學(xué)重點(diǎn)、難點(diǎn)】教學(xué)重點(diǎn)：hash 表和 STL 集合；（1）嫻熟把握排列生成的遞歸方法；（2）懂得解答樹,并能估算典型解答樹的結(jié)點(diǎn)數(shù)；（3）嫻熟把握子集生成的增量法、位向量法和二進(jìn)制法；（4）嫻熟把握回溯法框架,并能懂得為什么它往往比生成- 測(cè)試法高效；（5）嫻熟把握解答樹的寬度優(yōu)先搜尋和迭代搜尋；（6）嫻熟把握集合的兩種典型實(shí)現(xiàn)教學(xué)難點(diǎn)：hash 表和 STL集合；（1）嫻熟把握子集生成的增量法、位向量法和二進(jìn)制法；（2）嫻熟把握回溯法框架,并能懂得為什么它往往比生成- 測(cè)試法高效；（3）嫻熟把握解答樹的寬度優(yōu)先搜尋和

4、迭代搜尋；（4）嫻熟把握集合的兩種典型實(shí)現(xiàn)【課時(shí)支配 】hash 表和 STL集合；7.1 簡(jiǎn)潔枚舉 7.2枚舉排列 7.3子集生成7.4 回溯法 7.5隱式圖搜尋暴力法也稱為窮舉法、引言然后選擇其中的蠻力法, 它要求調(diào)設(shè)計(jì)者找出全部可能的方法,一種方法,如該方法不行行就摸索下一種可能的方法；暴力法也是一種直接解決問題的方法,常常直接基于問題的描述和所涉及的概念定義；暴力法不是一個(gè)最好的算法,但當(dāng)我們想不出更好的方法時(shí),它也是一種有效的解決問題的方法；暴力法的優(yōu)點(diǎn)是規(guī)律清晰,編寫程序簡(jiǎn)潔；在程序設(shè)計(jì)競(jìng)賽時(shí),時(shí)間緊急,相對(duì)于高效 的、神奇的算法,暴力法編寫的程序簡(jiǎn)潔,能更快地解決問題；同時(shí)蠻力法

5、也是很多算法的 基礎(chǔ),可以在蠻力法的基礎(chǔ)上加以優(yōu)化,得到更高效的算法；而且, 某些情形下, 算法規(guī)模不大, 使用優(yōu)化的算法沒有必要,而且某些優(yōu)化算法本身 較復(fù)雜,在規(guī)模不在時(shí)可能由于復(fù)雜的算法鋪張時(shí)間,反而不如簡(jiǎn)潔的暴力搜尋；使用暴力法常用如下幾種情形：（1）搜尋全部的解空間；（2）搜尋全部的路徑；（3）直接運(yùn)算；（4）模擬和仿真；7.1 簡(jiǎn)單枚舉在枚舉復(fù)雜對(duì)象之前,先嘗試著枚舉一些相對(duì)簡(jiǎn)潔的東西,如整數(shù)、子串等；暴力枚舉 對(duì)問題進(jìn)行確定的分析往往會(huì)讓算法更加簡(jiǎn)潔、高效；7.1.1 除法abcde/fghij=n的表達(dá)式,其中aj輸入正整數(shù)n,按從小到大的次序輸出全部形如恰好為數(shù)字09 的一個(gè)

6、排列, 2 n79；樣例輸入：62 樣例輸出：79546/01283=62 94736/01528=62 【分析】就可以運(yùn)算出 abcde,然后判定是否全部數(shù)字都不相同即可；不僅程 只需要枚舉 fghij 序簡(jiǎn)潔,而枚舉量也從 10.=3628800 降低至不到 1 萬；由此可見,即使接受暴力枚舉,也是 需要認(rèn)真分析問題；完整的程序如下：#include using namespace std; bool testint i,int j /用數(shù)組 t 存放 i ,j 的各位數(shù)字 int t10=0; /初始化數(shù)組t ,使得各位數(shù)字為0,好處是使得fghij10000時(shí) f 位置為 0 int

7、ia = 0; whilei /取 i 中各位數(shù)字存放在數(shù)組t 中 tia+ = i % 10; i = i / 10; whilej /取 j 中各位數(shù)字存放在數(shù)組t 中 tia+ = j % 10; j = j / 10; / 判定 aj 是否恰好為數(shù)字的 09 的一個(gè)排列 forint m = 0; m 10; +m forint n = m+1; n n & n =2 & n = 79 k = 1234; whilek = 98765 int j = k * n; ifj 100000 /如 fghij10000,中意題目的條件,f 位置輸出 0 iftestj,k cout j /

8、; ifk 10000 cout 0; cout k = n endl; +k; return 0; 7.1.2 最大乘積輸入 n 個(gè)元素組成的序列S,你需要找出一個(gè)乘積最大的連續(xù)子序列；假如這個(gè)最大的乘積不是正整,應(yīng)輸出-1 （表示無解） ；1n18,-10 Si 10；樣例輸入：3 2 4 -3 5 2 5 -1 2 -1 樣例輸出：8 20 【分析】連續(xù)子序列有兩個(gè)要素：起點(diǎn)和終點(diǎn), 因此只需要枚舉起點(diǎn)和終點(diǎn)即可；由于每個(gè)元素 18,可以用 long 的確定值不超過10,一共又不超過18 個(gè)元素,最大可能的乘積示會(huì)超過10long 存下；完整的程序如下：#include int main

9、 int a20; / 存放輸入序列的每一個(gè)元素 _int64 ans = 0; / 存放最大的乘積 int n; / 輸入元素的個(gè)數(shù)_int64 tmp； / 存放乘積的中間結(jié)果 whilescanf%d,&n.=EOF / 輸入序列中元素的個(gè)數(shù) n forint i = 0;i n; i+ / 輸入序列中的元素 scanf%d,&ai; fori = 0; i n; i+ / 從序列中的第0 個(gè)元素開頭,枚舉最大連續(xù)乘積,并用ans 儲(chǔ)備 tmp = 1; forint j = i; j ans ans = tmp; ifans0 printf%I64dn,ans; else printf

10、%dn,-1; return 0; 7.1.3 分?jǐn)?shù)拆分x y,使得1 k11；輸入正整數(shù)k,找到全部的正整數(shù)xy樣例輸入：2 12 樣例輸出：2 1/2=1/6+1/3 1/2=1/4+1/4 8 1/12=1/156+1/13 1/12=1/84+1/14 1/12=1/60+1/15 1/12=1/48+1/16 1/12=1/36+1/18 1/12=1/30+1/20 1/12=1/28+1/21 1/12=1/24+1/24 【分析】找出全部有x,y,枚舉完成了就行了；但是從1/12=1/156+1/13可以看出, x 可以比 y大很多；由于xy,有1 x1,因此1 k11,即 y

11、2k；這樣,只需要在2k 范疇內(nèi)枚yyy舉 y,然后依據(jù)y 嘗試運(yùn)算出x 即可；完整的程序如下：#include int main int k; int x, y, count = 0;/ 變量 count 統(tǒng)計(jì)等式的個(gè)數(shù) whilescanf%d, &k .= EOF fory = k+1;y = 2 * k; y+ /判定 1/k=1/x+1/y等式的個(gè)數(shù), x=k * y / y - k; ifx * y-k = k * y count+; printf%dn,count; /輸出中意條件的等式的個(gè)數(shù) fory = k+1; y = 2 * k; y+ / 輸出中意條件的等式 x=k *

12、 y / y - k; ifx * y - k = k * y printf1/%d=1/%d+1/%dn,k,x,y; return 0; 7.1.4 雙基回文數(shù) 假如一個(gè)正整數(shù) n 至少有兩個(gè)不同的進(jìn)位制 b1 和 b2 下都是回文數(shù) （2b1,b 210）,就；輸入正整數(shù) S106,輸出比 S 大的最 稱 n 是雙基回文數(shù)（留意,回文數(shù)不以包含前導(dǎo)零）小雙基回文數(shù)；樣例輸入： 1600000 樣例輸出： 1632995 【分析】最自然的想法是： 從 n+1 開頭依次判定每個(gè)數(shù)是否為雙基回文數(shù),而在判定時(shí)要枚舉所 有可能的基數(shù)（210）；意外的是：對(duì)于 S10 6 的“ 小規(guī)模數(shù)據(jù)” 來說

13、是足夠快的雙基 回文數(shù)太多太密；完整的程序如下：#include using namespace std; bool huiwenint n int i,j,a30,s; int total = 0; / 存放數(shù) s 是回文數(shù)的基數(shù)個(gè)數(shù) forint base = 2; base = 10; base+ i = 1; s = n; whiles ai = s % base; s = s / base; i+; i-; forj = 1; j i/2 total+; /數(shù) s 在基 base 下是回文數(shù),就total+ iftotal = 2 return true; return false;

14、 int main int s; whilescanf%d,&s = 1 fors = s+1; ; s+ ifhuiwens cout s endl; break; return 0; 7.2 枚舉排列輸入整數(shù) n,按字典序從大到小的次序輸出前n 個(gè)數(shù)的全部排列；兩個(gè)序列的字典序大小關(guān)系等價(jià)于從頭開頭第一個(gè)不相同位置處的大小關(guān)系；例如,1,3,22,1,3,字典序最小的排列是 1,2,3,4, ,n ,最大的排列是 n,n-1,n-2, ,1 ；n=3 時(shí),全部排列的排序結(jié)果是： 1,2,3、1,3,2、2,1,3、2,3,1、 3,1,2、3,2,1 7.2.1 生成 1n 的排列對(duì)此問題

15、用遞歸的思想解決：先輸出全部以 1 開頭的排列（遞歸調(diào)用）,然后輸出以 2開頭的排列（遞歸調(diào)用） ,接著以 3 開頭的排列, ,最終才是以 n 開頭的排列；以 1 開頭的排列的特點(diǎn)是：第一位是 1,后面是按字典序的 29 的排列；所以在設(shè)計(jì)遞歸函數(shù)需要以下參數(shù)：（1）已經(jīng)確定的“ 前綴” 序列,以便輸出；（2）需要進(jìn)行全排列的元素集合,以便依次選做第一個(gè)元素；這樣,寫出以下的偽代碼：void print_permutation 序列 A,集合 S ifS為空 輸出序列 A; v else 依據(jù) 從小到大次序 依次考慮 S 的每個(gè)元素 print_permutation在 A的末尾填加v 后得到

16、的新序列,S-v; 上面的遞歸函數(shù)中遞歸邊界是 S 為空的情形,可以直接輸出序列 A；如 S 不為空,就按從小到大的次序考慮 S 中的每個(gè)元素,每次遞歸調(diào)用以 A 開頭；下面考慮程序的實(shí)現(xiàn)；用數(shù)組表示序列 A,集合 S 可以由序列 A完全確定 A 中沒有顯現(xiàn)的元素都可以選；C語(yǔ)言中的函數(shù)在接受數(shù)組參數(shù)時(shí)無法得到數(shù)組的元素個(gè)數(shù),所以需要傳一個(gè)已經(jīng)填好的位置個(gè)數(shù),或者當(dāng)前需要確定的元素位置cur ；聲明一個(gè)足夠大的數(shù)組A,然后調(diào)用print_permutationn,A,0,即可按字典序輸出1n 的全部排列；完整的程序如下：#include int A100; / 輸出 1 n 的全排列的遞歸函數(shù)

17、 void print_permutationint n, int* A, int cur int i, j; ifcur = n / 遞歸邊界 fori = 0; i n; i+ printf%d , Ai; printfn; else fori = 1; i = n; i+ / 嘗試在 Acur 中填各種整數(shù)i int ok = 1; forj = 0; j cur; j+ ifAj = i ok = 0; / 假如 i 已經(jīng)在 A0 Acur-1顯現(xiàn)過,就不能再選 ifok Acur = i; print_permutationn, A, cur+1; / 遞歸調(diào)用 int main p

18、rint_permutation4, A, 0; return 0; 在遞歸函數(shù) print_permutation 中循環(huán)變量 i 是當(dāng)前考慮的 Acur ；為了檢查元素 i是否已經(jīng)用過, 仍用到了一個(gè)標(biāo)志變量 ok,初始值為 1（真）,假如發(fā)覺有某個(gè) Aj=i 時(shí),就改為 0（假）；假如最終 ok 仍為 1,就說明 i 沒有在序列中顯現(xiàn)過,把它添加到序列末尾（Acur=i）后遞歸調(diào)用；7.2.2 生成可重集的排列假如把問題改成：輸入數(shù)組 A,并按字典序輸出數(shù)組 A 各元素的全部全排列,就需要對(duì)上述遞歸函數(shù) print_permutation 修改把 P加到 print_permutatio

19、n 的參數(shù)列表中, 然后把代碼中的 ifAj=i 和 Acur=i 分別改成 ifAj=Pi 和 Acur=Pi；只有把 P的全部元素按從小到大的次序排序,然后調(diào)用 print_permutationn,P,A,0 即可；但是上述遞歸函數(shù) print_permutation 中,禁止 A 數(shù)組中顯現(xiàn)重復(fù), 而在 P 中可能就有重復(fù)元素時(shí),所以輸出數(shù)組 A 時(shí)就會(huì)顯現(xiàn)問題；解決方法是統(tǒng)計(jì) A0 Acur-1 中 Pi 的顯現(xiàn)次數(shù) c1,以及 P 數(shù)組中 Pi 的顯現(xiàn)次數(shù)c2；只要 c1c2,就能遞歸調(diào)用；枚舉的下標(biāo) i 應(yīng)不重復(fù)、不遺漏地取遍全部 Pi 值；由于 P 數(shù)組已經(jīng)排過序,所以只需檢查

20、 P 的第一個(gè)元素和全部“ 與前一個(gè)元素不相同”的元素, 即只需在 fori=0;in;i+和其后的花括號(hào)之前加上 if.i|Pi.=Pi-1 即可；完整的程序如下：#include int P100, A100; / 輸出數(shù)組 P中元素的全排列；數(shù)組P 中可能有重復(fù)元素void print_permutationint n, int* P, int* A, int cur int i, j; ifcur = n fori = 0; i n; i+ printf%d , Ai; printfn; else fori = 0; i n; i+ if.i | Pi .= Pi-1 int c1 =

21、 0, c2 = 0; forj = 0; j cur; j+ ifAj = Pi c1+; forj = 0; j n; j+ ifPi = Pj c2+; ifc1 c2 Acur = Pi; print_permutationn, P, A, cur+1; int main int i, n; scanf%d, &n; fori = 0; i n; i+ scanf%d, print_permutationn, P, A, 0; return 0; 7.2.3 解答樹假設(shè) n=4,序列為 1,2,3,4,如圖 7-1 所示的樹顯示出了遞歸函數(shù)的調(diào)用過程；其中,結(jié)點(diǎn)內(nèi)部的序列表示為 A,位

22、置 cur 用高亮表示, 另外,由于從該處開頭的元素和算法無關(guān),因此用星號(hào)表示；圖 7-1 排列生成算法的解答樹從圖 7-1 可以看出,它是一棵二叉樹；第 0 層（根）結(jié)點(diǎn)有 n 個(gè)兒子,第 1 層結(jié)點(diǎn)各有n-1 個(gè)兒子,第 2 層結(jié)點(diǎn)各有 n-2 個(gè)兒子,第 3 層結(jié)點(diǎn)各 n-3 個(gè)兒子, ,第 n 層結(jié)點(diǎn)都沒有兒子（即都是葉子） ,而每個(gè)葉子對(duì)應(yīng)于一個(gè)排列,共有 逐步生成完整解的過程,因此將其稱為解答樹；n. 個(gè)葉子；由于這棵樹呈現(xiàn)的是提示 7-1 ：假如某問題的解可以由多個(gè)步驟得到,而每個(gè)步驟都有如干種選擇（這些候選方案集可能會(huì)依靠于從前作出的選擇）用解答樹描述；,且可以用遞歸枚舉法實(shí)現(xiàn)

23、,就它的工作方式可以通過逐層查看,第 0 層有 1 個(gè)結(jié)點(diǎn),第 1 層有 n 個(gè)結(jié)點(diǎn),第 2 層有 n*n-1 個(gè)結(jié)點(diǎn),第3 層有 n*n-1*n-2 個(gè)結(jié)點(diǎn), ,第 n 層有 n*n-1*n-2* *2*1=n. 個(gè)；為了推導(dǎo)便利,把 n*n-1*n-2* *n-k 寫成 n./n-k-1.,就全部結(jié)點(diǎn)之和為：T n n 1 n . n . n 1 1 n . n 1 1k 0 n k 1. k 0 n k 1. k 0 k .依據(jù)高等數(shù)學(xué)中的泰勒開放公式,lim xk n 10 k 1.e,因此 Tnn. e=On. ；由于葉子有 n. 個(gè),倒數(shù)其次層也有 n. 個(gè)結(jié)點(diǎn),因此上面的各層全部

24、來源于最終一兩層,所以上面的結(jié)點(diǎn)數(shù)可以忽視不計(jì)；7.2.4 下一個(gè)排列不停調(diào)用 “ 求下一個(gè)排列”的過枚舉全部排列的另一個(gè)方法是從字典序最小排列開頭,程,在 C+的 STL 中供應(yīng)了一個(gè)庫(kù)函數(shù)next_permutation；完整的程序如下：#include #include using namespace std; int main int n, p10; scanf%d, &n; forint i = 0; i n; i+ scanf%d, sortp, p+n; / 排序,得到 p 的最小排列 do forint i = 0; i n; i+ printf%d , pi; / 輸出排列

25、p printfn; whilenext_permutationp, p+n; / 求下一個(gè)排列 return 0; 說明：（ 1）STL 里面有個(gè) sort函數(shù),可以直接對(duì)數(shù)組進(jìn)行隨機(jī)化快速排序,復(fù)雜度為n*log 2n,效率高；使用這個(gè)函數(shù),需要包含頭文件：#include using namespace std; 它的函數(shù)原型如下：template void sortRandomAccessIterator first, RandomAccessIterator last; 這個(gè) sort 函數(shù)可以傳兩個(gè)參數(shù)；第一個(gè)參數(shù)是要排序的區(qū)間首地址,其次個(gè)參數(shù)是區(qū)間尾地址的下一地址；也就是說,排

26、序的區(qū)間是 a,b ；簡(jiǎn)潔來說, 有一個(gè)數(shù)組 int a100 ,要對(duì)從 a0 到 a99 的元素進(jìn)行排序,只要寫 sorta,a+100 就行了,默認(rèn)的排序方式是升序；假如需要對(duì)數(shù)組 t 的第 0 到 len-1 的元素排序,就寫 sortt,t+len;,對(duì)向量 v 定義vector v; 進(jìn)行排序,寫成 sortv.begin,v.end; ,排序的數(shù)據(jù)類型不局限于整數(shù),只要是定義了小于運(yùn)算的類型都可以,比如字符串類 string；template void sortRandomAccessIterator first, RandomAccessIterator last, Strict

27、WeakOrdering comp; 這個(gè) sort 函數(shù)可以傳三個(gè)參數(shù)；第一個(gè)參數(shù)是要排序的區(qū)間首地址,其次個(gè)參數(shù)是區(qū)間尾地址的下一地址；也就是說,排序的區(qū)間是 a,b ；簡(jiǎn)潔來說, 有一個(gè)數(shù)組 int a100 ,要對(duì)從 a0 到 a99 的元素進(jìn)行排序,只要寫 sorta,a+100 就行了,默認(rèn)的排序方式是升序；假如是沒有定義小于運(yùn)算的數(shù)據(jù)類型,或者想轉(zhuǎn)變排序的次序,就要用到第三參數(shù)比較函數(shù)；比較函數(shù)是一個(gè)自己定義的函數(shù),返回值是bool 型,它規(guī)定了什么樣的關(guān)系才是“ 小于” ；想把剛才的整數(shù)數(shù)組按降序排列,可以先定義一個(gè)比較函數(shù) cmp bool cmpint a,int b re

28、turn ab; 排序的時(shí)候就寫 sorta,a+100,cmp;；（2）在 C+的 STL中定義的 next_permutation 和 prev_permutation 函數(shù)就是特殊靈活且高效的方法,它被廣泛的應(yīng)用于為指定序列生成不同的排列；next_permutation 和prev_permutation 函數(shù)需要包含 algorithm.h 頭文件；需要留意的是“ 假如要走遍全部的排列,必需先將元素排序”；（3）依據(jù) STL 文檔的描述, next_permutation函數(shù)將按字母表次序生成給定序列的下一個(gè)較大的排列,直到整個(gè)序列為降序?yàn)橹梗?prev_permutation函數(shù)與

29、之相反,是生成給定序列的上一個(gè)較小的排列（前一個(gè)排列）據(jù)可以對(duì)整型數(shù)組或字符數(shù)組操作；（4）next_permutation 函數(shù)原型；二者原理相同,僅遍歷次序相反；這兩個(gè)函數(shù)template bool next_permutationBidIt first, BidIt last; template bool next_permutationBidIt first, BidIt last, Compare comp; next_permutation 函數(shù)取由 first,last 標(biāo)記的排列, 并將其重新排序?yàn)橄乱粋€(gè)排列；假如不存在下一個(gè)排列,就返回 false ；否就,返回 true ；

30、第一個(gè)版本（）使用底層類型的小于操作符來確定下一個(gè)排列,其次個(gè)版本（）依據(jù)comp 對(duì)元素進(jìn)行排序；假如原始字 符 串 是 排 過 序 的 , 就 連 續(xù) 調(diào) 用 next_permutation 函 數(shù) 會(huì) 生 成 整 個(gè) 排 列 集 合 ；prev_permutation 函數(shù)原型與 next_permutation 函數(shù)型類似；7.3 子 集 生 成本節(jié)介紹子集生成算法：給定一個(gè)集合, 枚舉它全部可能的子集；為了簡(jiǎn)潔起見, 本節(jié)爭(zhēng)辯的集合中沒有重復(fù)元素；7.3.1 增量構(gòu)造法第一種思路是一次選出一個(gè)元素放到集合中,完整程序如下：#include void print_subsetint

31、n, int* A, int cur int i; fori = 0; i cur; i+ printf%d , Ai; / 打印當(dāng)前集合 printfn; int s = cur . Acur-1+1 : 0; / fori = s; i n; i+ Acur = i; 確定當(dāng)前元素的最小可能值 print_subsetn, A, cur+1; / 遞歸構(gòu)造子集 int A10; int main print_subset5, A, 0; return 0; 留意： 由于 A 中的元素個(gè)數(shù)不確定,每次遞歸調(diào)用都要輸出當(dāng)前集合；另外,遞歸邊界也不需要顯式確定假如無法連續(xù)添加元素,自然不會(huì)再遞歸

32、了；上面的代碼用到了定序的技巧：規(guī)定集合 A 中全部元素的編號(hào)從小到大排列,就不會(huì)把集合 1,2 依據(jù) 1,2 和2,1 輸出兩次了；這棵解答樹上有 1024 個(gè)結(jié)點(diǎn),由于每個(gè)可能的 A 都對(duì)應(yīng)一個(gè)結(jié)點(diǎn),而 n 元素集合恰好 有 2 n 個(gè)子集, 2 10=1024；7.3.2 位向量法 其次種思路是構(gòu)造一個(gè)位向量 Bi,而不是直接構(gòu)造子集 A 本身,其中 Bi=1 當(dāng)且僅當(dāng) i 在子集 A 中；完整程序如下：#include void print_subsetint n, int* B, int cur ifcur = n forint i = 0; i cur; i+ ifBi print

33、f%d , i; / 打印當(dāng)前集合 printfn; return; Bcur = 1; / 選第 cur 個(gè)元素 print_subsetn, B, cur+1; Bcur = 0; / 不選第 cur 個(gè)元素 print_subsetn, B, cur+1; int B10; int main print_subset5, B, 0; return 0; 必需當(dāng)“ 全部元素是否選擇”全部確定完畢后才是一個(gè)完整的子集,因此當(dāng) ifcur=n成立時(shí)才輸出；全部部分解（不完整的解）也對(duì)應(yīng)著解答樹上的結(jié)點(diǎn)；這是一棵 n+1 層的二叉樹（ cur 從 0 n）,第 0 層有 1 個(gè)結(jié)點(diǎn),第2 層有

34、4 個(gè)結(jié)點(diǎn),第 3 層有 8 個(gè)結(jié)點(diǎn), ,第 i 層有 2 i 個(gè)結(jié)點(diǎn),總數(shù)為1 層有 2 個(gè)結(jié)點(diǎn),第1+2+4+ +2n=2 n+1-1 ；圖 7-2 就是這棵解答樹；最終幾層結(jié)點(diǎn)數(shù)占整棵樹的絕大多數(shù)；圖 7-2 位向量法的解答樹7.3.3 二進(jìn)制法用二進(jìn)制來表示 0,1,2, ,n-1 的子集 S：從右往左第 i 位（各位從 0 開頭編號(hào)）表示元素 i 是否在集合 S中；用圖 7-3 呈現(xiàn)了二進(jìn)制 010001100011011 是如何表示集合 0,1,2,4, 5,9,10,14 的；圖 7-3 用二進(jìn)制表示子集留意： 為了處理便利,最右邊那個(gè)位總是對(duì)應(yīng)元素 0,而不是元素 1；提示 7

35、-2 ：可以用二進(jìn)制表示子集,其中從右往左第 i 位（從 0 開頭編號(hào)）表示元素 i是否在集合中（1 表示“ 在” ,0 表示“ 不在”）；不僅要表示集合,仍在對(duì)集合進(jìn)行操作；對(duì)集合的運(yùn)算都可以用位運(yùn)算符簡(jiǎn)潔實(shí)現(xiàn)；最常見的二元運(yùn)算是與（&）、或（ | ）、非 . 、異或（） ；“ 異或（ XOR）” 運(yùn)算符,它的規(guī)章是“ 假如A和 B 不相同,就 AB 為 1,否就為 0” ；異或運(yùn)算最重要的性質(zhì)就是“ 開關(guān)性” 異或兩次以后相當(dāng)于沒有異或,即 ABB=A；由于 A&B、A|B、A B分別對(duì)應(yīng)著集合的交、 并和對(duì)稱差； 另外,空集為 0,全集 0,1,2, , n-1 的二進(jìn)制為 n 個(gè) 1,

36、即十進(jìn)制的 2 n-1 ；在程序中把全集定義為 ALL_BITS=1n-1 ,就A的補(bǔ)集為 ALL_BITSA；也可以直接用整數(shù)減法ALL_BITS-A 表示,但速度比位運(yùn)算慢；提示 7-3 ：當(dāng)用二進(jìn)制表示子集時(shí),位運(yùn)算中的按位與、或、異或?qū)?yīng)集合的交、并和對(duì)稱差；輸出子集 S 對(duì)應(yīng)的各個(gè)元素的完整程序如下：#include void print_subsetint n, int s / 打印 0, 1, 2, ., n-1的子集 S forint i = 0; i n; i+ ifs&1i printf%d , i; / 這里利用了C語(yǔ)言“ 非 0 值都為真” 的規(guī)定 printfn; i

37、nt main int n = 5; i = 0; i 1n; i+ / 枚舉各子集所對(duì)應(yīng)的編碼 0, 1, 2, ., 2 n-1 forint print_subsetn, i; return 0; 7.4 回 溯 法無論是排列生成仍是子集枚舉,兩種思路： 遞歸構(gòu)造和直接遍歷；直接遍歷的優(yōu)點(diǎn)是思路和程序都很簡(jiǎn)潔,缺點(diǎn)在于無法簡(jiǎn)便地削減枚舉量必需生成（generate ）全部可能的解,然后一一檢查（test ）；另一方面, 在遞歸構(gòu)造中, 生成和檢查過程可以有機(jī)結(jié)合起來,從而削減不必要的枚舉,這就是本節(jié)的主題回溯法（backtracking）；回溯法是一種系統(tǒng)的搜尋問題的解的方法；它的基本思

38、想是： 從一條路前行, 能進(jìn)就進(jìn),不能進(jìn)就退回來,換一條路再試；回溯法是一種通用的解題方法；應(yīng)用回溯法的時(shí)候,第一明確定義問題的解空間；解空間至少應(yīng)當(dāng)包含問題的一個(gè)解；確定明白空間后,回溯法從開頭結(jié)點(diǎn)動(dòng)身,以深度優(yōu)先的方法搜尋整個(gè)解空間；對(duì)于回溯法一般可以接受遞歸方式來實(shí)現(xiàn)；7.4.1 八皇后問題在棋盤上放置 8 個(gè)皇后, 使得它們互不攻擊,此時(shí)每個(gè)皇后的攻擊范疇為同行同列和對(duì)角線,要求找出全部解,如圖 7-4 所示；Q Q Q Q Q Q Q Q Q a 皇后的攻擊范疇 b 一個(gè)可行解 圖 7-4 八皇后問題【分析】思路一：把問題轉(zhuǎn)化為“ 從64 個(gè)格子中選一個(gè)子集”,使得“ 子集中恰好有8

39、 個(gè)格子,且任意兩個(gè)選出的格子都不在同一行、同一列或同一個(gè)對(duì)角線上”是一個(gè)好的模型；這是子集枚舉問題,不思路二： 把問題轉(zhuǎn)化為 “ 從 64 個(gè)格子中選8 個(gè)格子” ,這是組合生成問題；比思路一好,但是仍然不是很好；思路三：由分析可得,恰好每行每列各放置一個(gè)皇后；假如用 列編號(hào),就問題變成了全排列生成問題；Cx 表示第 x 行皇后的提示 7-4 ：在編寫遞歸枚舉程序之前,需要深化分析問題,對(duì)模型精雕細(xì)琢；一般仍應(yīng)對(duì)解答樹的結(jié)點(diǎn)數(shù)有一個(gè)粗略的估量,作為評(píng)判模型的重要依據(jù),如圖 7-5 的所示；圖 7-5 在四皇后問題的解答樹圖 7-5 中給出了四皇后問題的完整解答樹；它只有18 個(gè)結(jié)點(diǎn),比4.=

40、24 小；緣由是有些結(jié)點(diǎn)無法連續(xù)擴(kuò)展；在各種情形下, 遞歸函數(shù)將不再遞歸調(diào)用本身,而是返回上一層調(diào)用,稱這種現(xiàn)象為回溯（ backtracking）；提示 7-5 ：當(dāng)把問題分成如干步驟并遞歸求解時(shí),假如當(dāng)前步驟沒有合法選擇,就函數(shù)將返回上一級(jí)遞歸調(diào)用,這種現(xiàn)象稱為回溯；正是由于這個(gè)緣由,遞歸枚舉算法常稱為回溯法,它的應(yīng)用特殊普遍；在主程序中讀入n,并為 tot清 0,然后調(diào)用search0,即可得到解的個(gè)數(shù)tot ；當(dāng)n=8,就 tot=92,狀態(tài)空間結(jié)點(diǎn)數(shù)nc=2057；完整的程序如下：#include int C50, tot = 0, n, nc = 0; void searchint

41、 cur int i, j; nc+; /nc 狀態(tài)空間結(jié)點(diǎn)數(shù) ifcur = n tot+; /遞歸邊界；只要走到了這里,全部皇后必定不沖突 else fori = 0; i n; i+ int ok = 1; Ccur = i; /嘗試把 cur 行的皇后放在第i 列 forj = 0; j cur; j+ /檢查是否和前面的皇后沖突 ifCcur = Cj | cur-Ccur = j-Cj | cur+Ccur = j+Cj ok = 0; break; ifok searchcur+1; / 假如合法,就連續(xù)遞歸 int main scanf%d,&n; search0; print

42、f%dn, tot; printf%dn, nc; return 0; 留意： 既然是逐行放置的,就皇后確定不會(huì)橫向攻擊,因此只需檢查是否縱向和斜向攻擊即可；條件 cur-Ccur = j-Cj | cur+Ccur = j+Cj 用來判定皇后 cur,Ccur和j,Cj 是否在同一條對(duì)角線上；其原理可以用圖 7-26 說明；0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 -1 0 1 2 3 4 5 6 1 2 3 4 5 6 7 8 -2 -1 0 1 2 3 4 5 2 3 4 5 6 7 8 9 -3 -2 -1 0 1 2 3 4 3 4 5 6 7 8 9 10 -

43、4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 -5 -4 -3 -2 -1 0 1 2 5 6 7 8 9 10 11 12 -6 -5 -4 -3 -2 -1 0 1 6 7 8 9 10 11 12 13 -7 -6 -5 -4 -3 -2 -1 0 7 8 9 10 11 12 13 14 a 格子 x,y 的 y-x 值標(biāo)識(shí)了主對(duì)角線 b 格子 x,y 的 x+y 值標(biāo)識(shí)了副對(duì)角線圖 7-6 棋盤中的對(duì)角線標(biāo)識(shí)上面的程序仍可改進(jìn)：利用二維數(shù)組 vist2 直接判定當(dāng)前嘗試的皇后所在的列和兩個(gè)對(duì)角線是否已有其他皇后；留意到主對(duì)角線標(biāo)識(shí) y-x 可能為負(fù),存取時(shí)

44、要加上 n；完整的程序如下：Include int C50, vis350, tot = 0, n, nc = 0; void searchint cur int i, j; nc+; ifcur = n tot+; else fori = 0; i n; i+ if.vis0i & .vis1cur+i & .vis2cur-i+n / 利用二維數(shù)組直接判定 Ccur = i; /假如不打印解,整個(gè)C數(shù)組都可以省略修改全局變量 vis0i = vis1cur+i = vis2cur-i+n = 1; / searchcur+1; vis0i = vis1cur+i = vis2cur-i+n

45、 = 0; / int main scanf%d,&n; memsetvis, 0, sizeofvis; search0; printf%dn, tot; printf%dn, nc; return 0; 切記！確定要改回來上面的程序關(guān)鍵的地方是 vis 數(shù)組的使用； vis 數(shù)組表示已經(jīng)放置的皇后占據(jù)了哪些列、主對(duì)角線和副對(duì)角線；將來放置的皇后不應(yīng)當(dāng)修改這些值；一般地, 假如要回溯法中修改了幫忙的全局變量,就確定要及進(jìn)把它們復(fù)原原狀（除非有意保留修改）；另外,千萬不要忘記在調(diào)試之前把 vis 數(shù)組清空；提示 7-6 ：假如在回溯法中使用了幫忙的全局變量,就確定要準(zhǔn)時(shí)把它們復(fù)原原狀；例如,如

46、函數(shù)有多個(gè)出口,就需在每個(gè)出口處復(fù)原被修改的值；7.4.2 素?cái)?shù)環(huán)輸入正整數(shù) n,把整數(shù) 1,2,3, ,n 組成一個(gè)環(huán),使得相鄰兩個(gè)整數(shù)之和均為素?cái)?shù)；輸 出時(shí)從整數(shù) 1 開頭逆時(shí)針排列；同一個(gè)環(huán)應(yīng)恰好輸出一次；n16；樣例輸入：6 樣例輸出：1 4 3 2 5 6 1 6 5 2 3 4 【分析】素?cái)?shù)環(huán)問題的程序?qū)嶋H上主要由求素?cái)?shù)和整數(shù)1,2,3, ,n 的排列構(gòu)成； 生成 - 測(cè)試法的完整程序如下：#include #include using namespace std; int is_primeint x /判數(shù)一個(gè)整數(shù)x 是否是一個(gè)素?cái)?shù) forint i = 2; i*i = x;

47、i+ ifx % i = 0 return 0; return 1; int main int n, A50, isp50; scanf%d, &n; forint i = 2; i = n*2; i+ / ispi = is_primei; 生成素?cái)?shù)表,加快后繼判定 forint i = 0; i n; i+ Ai = i+1; / 第一個(gè)排列 do int ok = 1; forint i = 0; i n; i+ if.ispAi+Ai+1%n / 判定合法性 ok = 0; break; ifok forint i = 0; i n; i+ printf%d , Ai; / 輸出序列

48、printfn; whilenext_permutationA+1, A+n; return 0; 運(yùn)行后, 發(fā)覺當(dāng) n=12 時(shí)就已經(jīng)很慢了,此問題,完整的回溯法的程序如下：#include #include using namespace std; 而當(dāng) n=16 根本出不來； 下面實(shí)行回溯法來解決int is_primeint x /判數(shù)一個(gè)整數(shù)x 是否是一個(gè)素?cái)?shù) forint i = 2; i*i = x; i+ ifx % i = 0 return 0; return 1; int n, A50, isp50, vis50; void dfsint cur ifcur = n & i

49、spA0+An-1 /遞歸邊界,別忘測(cè)試第一個(gè)數(shù)和最終一個(gè)數(shù) forint i = 0; i n; i+ printf%d , Ai; printfn; else forint i = 2; i = n; i+ /嘗試放置每個(gè)數(shù)i if.visi & ispi+Acur-1 / 假如 i 沒有用過,并且與前一個(gè)數(shù)之和為素?cái)?shù) Acur = i; visi = 1; / 設(shè)置標(biāo)志 dfscur+1; visi = 0; / 清除標(biāo)志 int main scanf%d, &n; forint i = 2; i = n*2; i+ ispi = is_primei; memsetvis, 0, siz

50、eofvis; A0 = 1; dfs1; return 0; 測(cè)試后, 回溯法比生成 - 測(cè)試法要快很多； 回溯法是依據(jù)深度優(yōu)先的次序在遍歷解答樹；7.4.3 困難串假如一個(gè)字符串包含兩個(gè)相鄰的重復(fù)子串,就稱它是“ 簡(jiǎn)潔的串”,其它的串稱為“ 困難的串” ；輸入正整數(shù)n 和 L,輸出由前 L 個(gè)字符組成的、 字典序第k 小的困難的串； 例如,當(dāng) L=3時(shí),前 7 個(gè)困難的串分別為：答案不超過 80 個(gè)字符；樣例輸入：7 3 30 3 樣例輸出：ABACABA A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA；輸入保證字符ABACABCACBABCABACABCACBACA

51、BA 【分析】從左到右依次考慮每個(gè)位置上的字符；因此,主要問題是如何判定當(dāng)前字符串是否已存在連續(xù)的重復(fù)子串；所在只需判定當(dāng)前串的后綴,而非全部子串；完整的程序如下：#include int n, L, cnt = 0; int S100; int dfsint cur / ifcnt+ = n 返回 0 表示已經(jīng)得到解,無須連續(xù)搜尋 forint i = 0; i cur; i+ printf%c, A+Si; / 輸出方案 printfn; return 0; forint i = 0; i L; i+ Scur = i; int ok = 1; forint j = 1; j*2 = cu

52、r+1; j+ / 嘗試長(zhǎng)度為j*2 的后綴 int equal = 1; forint k = 0; k j; k+ / 檢查后一半是否等于前一半 ifScur-k .= Scur-k-j equal = 0; break; ifequal ok = 0; break; / 后一半等于前一半,方案不合法 ifok if.dfscur+1 return 0; / 遞歸搜尋；假如已經(jīng)找到解,就直接退出 return 1; int main scanf%d%d, &n, &L; dfs0; return 0; 7.4.4 帶寬 給出一個(gè) n 個(gè)結(jié)點(diǎn)的圖 G和一個(gè)結(jié)點(diǎn)的排列,定義結(jié)點(diǎn) i 的帶寬 b

53、i 為 i 和相鄰結(jié)點(diǎn)在排列中的最遠(yuǎn)距離,而全部 bi 的最大值就是整個(gè)圖的帶寬；給定圖 G,求出讓帶寬最小 的結(jié)點(diǎn)排列；【分析】可以記錄下目前已經(jīng)找到的最小帶寬 k,再怎么擴(kuò)展也不行能比當(dāng)前解更優(yōu),k；假如發(fā)覺已經(jīng)有某兩個(gè)結(jié)點(diǎn)的距離大于或等于 應(yīng)當(dāng)強(qiáng)制把它 “ 剪掉” ,即為解答樹 “ 剪枝（prune ）” ；除此之外,仍可以剪掉更多的枝葉；假如在搜尋到結(jié)點(diǎn) u 時(shí),u 結(jié)點(diǎn)仍有 m個(gè)相鄰接點(diǎn)沒有確定位置, 那么對(duì)于結(jié)點(diǎn) u 來說, 最理想的情形就是這 m個(gè)結(jié)點(diǎn)緊跟在 u 后面, 這樣的結(jié)點(diǎn)帶寬為 m,而其他任何“ 非理想情形” 的帶寬至少為 m+1；這樣,假如 mk,即“ 最理想的情形下

54、都不能得到比當(dāng)前最優(yōu)解更好的方案”,就明顯應(yīng)當(dāng)剪枝；7.5 隱式圖搜尋對(duì)很多問題可以用圖的遍歷算法解決,但這些問題的圖卻不是事先給定、從程序讀入的,而是由程序動(dòng)態(tài)生成的；7.5.1 隱式樹的遍歷到目前為止,本章中的解答樹都有是樹,有著嚴(yán)格的“ 層次” 概念從根往下走,你永久都無法回到根結(jié)點(diǎn)；回溯法是依據(jù)深度優(yōu)先次序遍歷的,它的優(yōu)點(diǎn)是空間很節(jié)?。褐挥羞f歸棧中結(jié)點(diǎn)需要保存；換句話說,回溯法的空間開銷和拜望的最深結(jié)點(diǎn)的深度成正比；樹不僅可以深度優(yōu)先遍歷,仍可以寬度優(yōu)先遍歷；好處是找到的第一個(gè)解確定是離根最近的解,但空間開銷卻大增加（隊(duì)列中結(jié)點(diǎn)很多）；例 7-1 最優(yōu)程序；有一臺(tái)只有一個(gè)數(shù)據(jù)棧的運(yùn)算機(jī)

55、,支持整數(shù)的5 種運(yùn)算： ADD、SUB、MUL、DIV、DUP；假設(shè)棧頂?shù)?3 個(gè)元素分別為 a、b、c,就 5 種運(yùn)算的成效依次如下：ADD：a 和 b 依次出棧,運(yùn)算 a+b,把結(jié)果壓棧；SUB：a 和 b 依次出棧,運(yùn)算 b-a ,把結(jié)果壓棧；MUL：a 和 b 依次出棧,運(yùn)算 a b,把結(jié)果壓棧；DIV：a 和 b 依次出棧,運(yùn)算b/a 并向下取整,把結(jié)果壓棧；DUP：a 出棧,再連續(xù)把兩個(gè) a 壓棧；遇到以下情形之一,機(jī)器會(huì)產(chǎn)生錯(cuò)誤： 執(zhí)行 DIV 操作時(shí), 棧頂元素為 0；執(zhí)行 ADD、SUB、MUL、DIV 操作時(shí),棧中只有一個(gè)元素；運(yùn)算結(jié)果的確定值大于 30000；給出 n

56、個(gè)整數(shù)對(duì) a i,b i （ai 互不相同）,你的任務(wù)是設(shè)計(jì)一個(gè)最短的程序,使得對(duì)于 1和 n 之間的全部 i ,假如程序執(zhí)行前棧中只有一個(gè)元素 ai ,就執(zhí)行后棧頂元素是 bi；n5；【分析】此題沒有方法用回溯法來解決；此題的解答樹是無窮大的多長(zhǎng)的程序都是合法的；題目要求最短的程序,最簡(jiǎn)潔可行的方法是利用寬度優(yōu)先遍歷解答樹；例 7-2 埃及分?jǐn)?shù)；在古埃及,人們使用單位分?jǐn)?shù)的和（如1/a ,a 是自然數(shù)）表示一切有理數(shù)；例如,2/3=1/2+1/6,但不答應(yīng) 2/3=1/3+1/3, 由于在加數(shù)中不答應(yīng)有相同的；對(duì)于一個(gè)分?jǐn)?shù) a/b ,表示方法有很多種,其中加數(shù)少的比加數(shù)多的好,假如加數(shù)個(gè)數(shù)相

57、同,就最小的分?jǐn)?shù)越大越好；例如,19/45=1/5+1/6+1/18 是最優(yōu)方案；輸入整數(shù) a,b （0ab1000）,試編程運(yùn)算正確表達(dá)式；【分析】此題的解決方案是接受迭代加深搜尋（iterative deepening ）：從小到大枚舉深度上限d,每次只考慮不超過 d 的結(jié)點(diǎn)；這樣,只要解的深度有限,就確定可以在有限時(shí)間內(nèi)枚舉得到；深度上限仍可以用來剪枝；依據(jù)分母遞增的次序來進(jìn)行擴(kuò)展,假如擴(kuò)展到 i 層時(shí),前 i個(gè)分?jǐn)?shù)之和為 c/d ,而第 i 個(gè)分?jǐn)?shù)為 1/e ,就接下來至少仍需要 a/b-c/d/1/e 個(gè)分?jǐn)?shù), 總和才能達(dá)到 a/b ；使用上述算法,題目規(guī)模中的任意數(shù)據(jù)都能很快解出；

58、7.5.2 一般隱式圖的遍歷有很多問題難以建立嚴(yán)格層次的解答樹,下的圖；例 7-3 倒水問題；于是就只能把狀態(tài)之間的關(guān)系懂得成一般意義有裝滿水的 6 升的杯子、空的 3 升杯子和 1 升杯子, 3 個(gè)杯子中都沒有刻度；在不使用其他道具的情形下,是否可以量出 4 升的水呢？方法如圖 7-7 所示；圖 7-7 倒水問題：一種方法是 6,0,0 3,3,03,2,14,2,0留意：由于沒有刻度, 用杯子 x 給杯子 y 倒水時(shí)必需始終連續(xù)到把杯子 y 倒?jié)M或者把杯子 x 倒空,而不能中途停止；你的任務(wù)是解決一般性的問題：設(shè)大、中、小 3 個(gè)杯子的容量分別為 a,b,c ,最初只有大杯子裝滿水, 其他

59、兩個(gè)杯子為空；最少需要多少步才能讓某一個(gè)杯子中的水有 x 升呢？你需要打印出每步操作后各個(gè)杯子中的水量（0cba1000）；【分析】假設(shè)在某一時(shí)刻,大杯子中有v0 升水,中杯子有v1升水,小杯子有v2 升水,稱當(dāng)時(shí)的系統(tǒng)狀態(tài)為 v 0,v 1,v 2 ；把“ 狀態(tài)” 想象成圖中的結(jié)點(diǎn), 可以得到 如圖 7-8 所示的 狀態(tài)圖（stata graph ）；圖 7-8 倒水問題狀態(tài)圖留意圖 7-8 所示的狀態(tài)圖和迷宮是不同的；在迷宮中, 只在可以成功往上走,走完后往下確定會(huì)回到剛才的地方,但此圖并不相同：從狀態(tài)（4,2,0 ）可以通過把水從中杯子倒入大杯子而一步到達(dá)（6,0,0 ）,但是從（ 6,0,0 ）卻無法一步到達(dá)（4,2,0 ）；換句話說,迷宮圖是無向圖（ undirected graph）,而此題“ 倒水狀態(tài)圖” 是有向圖（directed graph）由于無論如何倒,杯子中的水量都是整數(shù)（依據(jù)倒水次數(shù)歸納即可）,因此水杯的小量最多只有 0,1,2, ,c 共 c+1 種可能；同理,中杯子的水量一共只有 b+1 種可能,大杯子一共只有 a+1 種可能,因此理論上狀態(tài)最多有 a+1b+1c+1 種可能性；但是由于水量 x 永遠(yuǎn)不變,假如有兩個(gè)狀態(tài)的小杯子和中杯小量都相同,就大杯子小量相同；換句話說, 最多可能的狀態(tài)數(shù)不會(huì)超過b+1c+1,因此結(jié)點(diǎn)數(shù)不超過10