1、題目：已知有 3 個(gè)容量分別為 3kg ，5kg 和 8kg 且沒有刻度的酒瓶 3kg 和 5kg 的瓶 子均裝滿了酒。而 8kg 的瓶子為空?，F(xiàn)要求僅用這 3 個(gè)酒瓶將這些酒均分為兩個(gè) 4kg ，并 分別裝入 5kg 和 8kg 的瓶子中。一、問題分析和任務(wù)定義此程序需要完成如下要求： 3 個(gè)沒有刻度的酒瓶，容量分別為 3kg,5kg, 和 8kg,3kg 和 5kg 的瓶子裝滿了酒， 8 kg 的瓶子為空。不借用其他工具，將這些酒分為兩個(gè) 4kg ，并 分別裝入 5kg 和 8kg 的瓶子中。實(shí)現(xiàn)本程序需要解決一下幾個(gè)問題：該問題對應(yīng)的模型是什么 模型建立好以后，采用什么樣的存儲結(jié)構(gòu)怎樣建

2、立模型如何求解，即中心算法思想 如何將結(jié)果輸出本問題的關(guān)鍵在于建立模型，和中心算法思想。模型的描述可以把 3 個(gè)酒杯現(xiàn)在的容量當(dāng)做一組狀態(tài)，在求解過程中涉及狀態(tài)的轉(zhuǎn)化，可以用圖 模型求解。把每次可分的狀態(tài)抽象為一個(gè)圖節(jié)點(diǎn)，利用圖的相關(guān)知識去求解。中心算法思想圖的初始狀態(tài)為（ 053 ），最終狀態(tài)為（ 440 ），本題的求解過程就是把（ 053 ）變成 （ 440 ），也就是找到一條路徑，路徑的起始點(diǎn)為（ 053 ），終點(diǎn)為（ 440 ）。因此可以采 用圖的深度優(yōu)先搜索遍歷。但本題搜索的起點(diǎn)已經(jīng)給定。二、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的選擇設(shè)計(jì)本題算法的構(gòu)思如下：（1）為搜索除符合條件的簡單路徑，需要按深度

3、優(yōu)先搜索方式進(jìn)行遍歷。因此， 求解算法應(yīng)是深度遍歷算法的變形形式，因而也是遞歸是形式的算法。由于要求遍歷序列中的各結(jié)點(diǎn)按次序構(gòu)成一條簡單路徑，因此， 本算法與深度遍歷算法有明顯的不同 : 并非任意選擇的起點(diǎn)和訪問次序都能得到解。而本題的起點(diǎn)和終點(diǎn)是確定 的。既然要在求解過程中進(jìn)行試探，則需要記錄試探的中間狀態(tài) ; 某頂點(diǎn)是否在當(dāng)前試探 路徑中，已經(jīng)試探的各頂點(diǎn)和當(dāng)前試探頂點(diǎn)的信息。將所用的變量及有關(guān)參數(shù)設(shè)置如下： 用鄰接鏈表存儲所得圖的結(jié)構(gòu)，鏈表用兩個(gè)結(jié)構(gòu)體表示， （struct arc_node ， struct vex_node）, 其中每個(gè)鏈表的頭保存在一個(gè)數(shù)組中。用布爾數(shù)組 visit

4、edMAX_SIZE 表示各狀態(tài)頂點(diǎn)是否在當(dāng)前路徑中 （初始狀態(tài)全 為 false）.用數(shù)組 A 存儲當(dāng)前路徑中的個(gè)頂點(diǎn)。（4） 既然是試探型求解，則需要對當(dāng)前頂點(diǎn) v0 的每個(gè)鄰接點(diǎn)進(jìn)行試探（程序中用 sv0.next 表示 ）,試探由 v0 經(jīng) sv0.next 往下是否可以得到解， 每個(gè) sv0.next 都有可能成 功 （ 指現(xiàn)在可以放在路徑上，這包括暫時(shí)的和最終的）與失敗的（指狀態(tài)轉(zhuǎn)化不能完成 ）,，對此應(yīng)分別做不同的處理：若試探成功，則應(yīng)將 sv0.next 放在路徑中，。然后再由其往下求解。若不成功， 則應(yīng)恢復(fù) sv0.next 的用關(guān)信息， 以使 sv0.next 在試探其他路

5、徑 中成為可選的試探點(diǎn)。（5）為了能求出解以及所有可能的解，需要做如下的工作： 選擇路徑：本題中的起點(diǎn)已經(jīng)限定，即 start_vex=0 5 3 搜索路徑： 從 v 往下搜索時(shí)， 應(yīng)依次選擇 v 的所有不在當(dāng)前路徑中的鄰接點(diǎn)往 下搜索。為此，需要有這方面的保證：應(yīng)在試探某頂點(diǎn)之后并在換下一個(gè)試探頂點(diǎn)的前 恢復(fù)該頂點(diǎn)的有關(guān)狀態(tài)，以使其重新成為可選擇的頂點(diǎn)。本題的模型已經(jīng)抽象成了圖，所以可以用鄰接表來存儲圖。 鄰接表數(shù)據(jù)類型描述如下： typedef struct node / 邊節(jié)點(diǎn)int adjvex;/ 鄰接點(diǎn)的位置node *next;/ 指向下一個(gè)節(jié)點(diǎn)ARCNODE;/ 鄰接表中的結(jié)點(diǎn)

6、類型typedef struct / 頂點(diǎn)節(jié)點(diǎn)int vexdataN; / 各酒杯的存儲狀態(tài)ARCNODE *next;/ 指向下一個(gè)鄰接點(diǎn)VEXNODE;/ 表頭結(jié)點(diǎn)類型VEXNODE sMAX_SIZES; / 狀態(tài)表除了鄰接表外，本題還需要其他的輔助存儲結(jié)構(gòu) 深度優(yōu)先搜索是一個(gè)遞歸過程。需要一個(gè) visitedn 數(shù)組來記錄當(dāng)前定點(diǎn)是否已訪問 過，若訪問過，數(shù)組元素的值為“ 1 ”，若未訪問過，數(shù)組元素的值“ 0”。因此可以定義： bool visitedn;每求出一個(gè)解要把當(dāng)前路徑輸出，用數(shù)組 Atop 來記錄遍歷過程中頂點(diǎn) 其他變量的設(shè)置：#define N 3#define MA

7、X-SIZE 100int A;/ 存放路徑int top=0;/ 數(shù)組 A 中的個(gè)數(shù)int fullN;/ 各酒杯的最大容量int partN;/ 各酒杯的當(dāng)前容量int endN;/ 最終狀態(tài)int sta;/ 狀態(tài)表當(dāng)前狀態(tài)數(shù)int sum=0;/ 所有解的個(gè)數(shù)int end_vex;/ 結(jié)束的狀態(tài)點(diǎn)三、詳細(xì)設(shè)計(jì)和編碼 首先初始化各酒杯的最大容量 for(i=0;i<N;i+)scanf("%d",&fulli);初始化起點(diǎn)狀態(tài)for(i=0;i<N;i+)scanf("%d",&s0.vexdatai);給出要求的終點(diǎn)

8、for(i=0;i<N;i+)scanf("%d",&endi);下面對鄰接表和狀態(tài)表的建立進(jìn)行分析和說明將頂點(diǎn)為 number 的值即 snumber.vexdata 的值賦給 part ，調(diào)用 jisuan(number) 函數(shù)，依次求出頂點(diǎn) 0 的鄰接點(diǎn)，將求出的鄰接點(diǎn)保存到狀態(tài)表中，并加入到鄰接表中。 令 number=number+1, 重復(fù)上面的步驟， 求出所有頂點(diǎn)的鄰接點(diǎn)， 得到一個(gè)完整的狀態(tài)表 和鄰接表。求頂點(diǎn)鄰接點(diǎn)的過程如下：通過兩個(gè) for 循環(huán)來改變酒杯的下標(biāo)和比較。for(i=0;i<N;i+) for(j=0;j<N;j+

9、)If(i=j) continue先是 i 號酒杯與 j 號酒杯比較If(i=j) continue若 i=j, 則 i 和 j 是同一酒杯，無需比較和改變。若i冇則進(jìn)行下面的操作：I=parti ；J=fullj-partj ；I是i號酒杯里當(dāng)前的酒，J是j號酒杯里剩余的容量判斷i號酒杯的當(dāng)前容量是否小于等于 j號酒杯的空余量。若是，則將 i號酒杯里德酒 全部倒入 j 號酒杯，得到一種新的狀態(tài)，調(diào)用 save ()函數(shù)，保存到狀態(tài)表?；謴?fù) i 酒杯和 j 酒杯改變前的容量。 加入到鄰接表中； 若 i 號酒杯的當(dāng)前容量大于 j 號酒杯的空余量， 則將i號酒杯的酒倒入j號酒杯，直至j號酒杯滿為止

10、，得到一種新的狀態(tài)，調(diào)用save ()函數(shù)，保存到狀態(tài)表，加入到鄰接表中?；謴?fù)i酒杯和j酒杯改變前的容量。(注意，一定要恢復(fù)i酒杯和j酒杯改變前的容量，恢復(fù)到調(diào)用jisuan()之前的狀態(tài)，這樣才能求出該狀態(tài)所有的 鄰接點(diǎn)。)一次變換結(jié)束。然后j=j+1 ，重復(fù)上面的步驟，直至j>=N為止。然后是i=i+1,重復(fù)上面步驟，直至i>=N為止。這樣就把頂點(diǎn)number所有的鄰接點(diǎn) 都求出來了，并且加入到了狀態(tài)表和鄰接表中。保存狀態(tài)的過程如下：for(i=0;i<=sta;i+) 作為循環(huán)控制的條件，在循環(huán)中調(diào)用 compare(part,si.vexdata) 函數(shù)，使該狀態(tài)與狀

11、態(tài)表中的狀態(tài)一一比較，判斷該狀態(tài)是 否在。(compare。函數(shù)是比較兩個(gè)數(shù)組是否相等的函數(shù)，若相等返回false，若不等返回TRUE，為本程序子函數(shù)，在此不做詳細(xì)說明)若該狀態(tài)不存在，令sta+，將該狀態(tài)則加入到狀態(tài)表中，該狀態(tài)在狀態(tài)表中的下標(biāo)是sta ;判斷該狀態(tài)是否是最終狀態(tài)，若是令end-vex=sta.。同時(shí)將該狀態(tài)加入到鄰接表中。若該狀態(tài)存在，則僅將該狀態(tài)加入到鄰接表中。creat ()函數(shù)完成后，就將狀態(tài)表和鄰接表都建立好了。得到狀態(tài)表ssta,狀態(tài)表中的內(nèi)容為：表1 狀態(tài)表SO053S1503S2350S3800S4530S5323S6233S7620S8251S9602S10

12、701S11152S12710S13143S14413S15440S0為起點(diǎn)，S15為要求的狀態(tài)，也就是遍歷的終點(diǎn)。得到鄰接表：表2 鄰接表0n1n2A1n0n3>>4A2n0n3>>5A3n1n2A4n1n3>>6A5n0n1>>2>>7A6n0n11>>2>>8A7n2n3>>5>>9A8n0n2>>10A9n1n3>>7>>11A10n1n3>>8>>12A11n0n2>>9>>13A12n2n3&

13、gt;>10>>14A13n0n1>>11>>15A14n0n1>>12>>15A15n2n3>>13>>14A以上我們解決了狀態(tài)表和鄰接表的建立，下面就要進(jìn)行求解了，對鄰接表進(jìn)行深度優(yōu)先搜索，從起點(diǎn)053開始，求出所有到440的路徑，每求出一條路徑，輸出。每一條路徑對應(yīng) 一種解法深度優(yōu)先搜蘇遍歷：本程序和普通的深度優(yōu)先搜素遍歷有點(diǎn)不同，那就是起點(diǎn)已將給定,即0 5 3 o首先判斷起點(diǎn)是否已訪問過，若沒有，分兩種情況：當(dāng)訪問的到頂點(diǎn)狀態(tài)v=e nd_vex(最終狀態(tài))時(shí)，則說明已經(jīng)求得一解，因此可輸出結(jié)果

14、，并結(jié)束本次算法，繼續(xù)求解其他可能的解的情況。若v! =end_vex，則依次選擇v的所有不在當(dāng)前試探路徑中鄰接點(diǎn)sv0.next往下搜索,這包括以下的操作：試探：通過 Atop+=p->adjvex 將 sv0.next 放在數(shù)組 A 中，并置 visitedsv0.next 為true，然后以sv0.nex為起點(diǎn)往下搜索，直到搜索到終點(diǎn) 4 4 0或者不滿足循環(huán) 條件為止恢復(fù)：通過 A-top將sv0.next 恢復(fù)為不在當(dāng)前的路徑中，并置visitedv0=false以使其在試探其他路徑時(shí)可用。每求出一種解就調(diào)用prtf()函數(shù)，進(jìn)行輸出。輸出過程如下：路徑存儲在數(shù)組 A中，A中存

15、儲的是路徑中的各頂點(diǎn)，通過循環(huán)for(i=0;i<top;i+)來控制輸出，沒執(zhí)行一次for循環(huán)就輸出路徑中的一個(gè)頂點(diǎn)；令 j=Ai,即用j記錄頂點(diǎn)在路徑中的位置，用來輸出頂點(diǎn)Ai對應(yīng)的狀態(tài)。通過 for(k=0;k<N;k+)prin tf("%d",s j.vexdatak);來輸出該狀態(tài)，當(dāng)把數(shù)組 A中的路徑輸出完以后就得到了一種解。在dfs()函數(shù)中每求出一 種解就調(diào)用一次 prtf() 函數(shù)，當(dāng)遍歷結(jié)束后，所有解也已全部求出并輸出。程序完成。四、上機(jī)調(diào)試1 、語法錯(cuò)誤機(jī)修改：算法中定義了很多全局變量，在完成本程序的過程中，有些全局 變量忘了賦值，這樣系

16、統(tǒng)就賦給它一個(gè)隨機(jī)值，影響程序的正確性，發(fā)現(xiàn)錯(cuò)誤后及 時(shí)給它賦值，例如，作為數(shù)組下標(biāo)的 top ，剛一個(gè)開始沒有賦值，在輸出路徑是， 全部都是隨機(jī)數(shù)，在定義是令 top=0 即可。語法的主要問題在于子函數(shù)定義，括號 的配對，尤其是括號的配對，在有些地方使用的循環(huán)比較多，這樣就會產(chǎn)生括號配 對的錯(cuò)誤，細(xì)心的檢查，改錯(cuò)就行了。還有一些輸入錯(cuò)誤，相應(yīng)的將其解決。2 、邏輯問題修改及調(diào)整：在 jisuan 函數(shù)中，通過兩條 for 語句來控制酒杯的下標(biāo)和比較， for(i=0;i<N;i+)/ 編 號為 i 的酒杯與其他酒杯交換for( j=0;j<N;j+)if(j=i) continu

17、e;/ 同一酒杯，無法變換沒有 if(j=i) continue 這條語句，造成了時(shí)間上的浪費(fèi)。因?yàn)槿绻?i=j 的話，兩 者是同一個(gè)酒杯無需比較， 在人工運(yùn)行算法的過程中， 發(fā)現(xiàn)了該問題， 加上 if 語句即可。 在 jisuan() 函數(shù)中每求出一種新的狀態(tài)就調(diào)用 save ()函數(shù)，若該狀態(tài)存在就僅加入到 鄰接表；若該狀態(tài)不存在，則不僅要加入到鄰接表還要加入到狀態(tài)表。在一開始的時(shí)候 沒有判斷該狀態(tài)是否已經(jīng)存在的語句 for(i=0;i<=sta;i+)if(!compare(part,si.vexdata)break;這樣調(diào)用一次 save ()函數(shù)就會執(zhí)行下面的語句if(i>

18、;sta)/ 將該狀態(tài)加入狀態(tài)表sta+;for(int j=0;j<N;j+)ssta.vexdata j=partj;ssta.next=NULL;if(!compare(part,end)end_vex=sta;/ 該狀態(tài)是最終狀態(tài)，記住在狀態(tài)表中的位置不管該狀態(tài)是否存在都會重新保存， 這樣就會造成時(shí)間上的浪費(fèi)。 加上上面的判斷語句就行 了。在深度優(yōu)先搜索遍歷函數(shù)中，首先是判斷該節(jié)點(diǎn)是否已訪問過，一開始是用 while ( !visitedv0 )，這樣就會造成死循環(huán)， 程序一直在執(zhí)行 dfs() 函數(shù)，在屏幕上會看到不停的 輸出那 15 種解。這是由于對深度優(yōu)先搜索遍歷算法理解有

19、問題，深度優(yōu)先搜索遍歷采用了 遞歸的思想，雖然讓程序簡單了，但增加了理解的難度。將while ( !visitedv0 )改成if(!visitedv0) 即可。3 、時(shí)間、空間性能分析： 本算法定義了很多全局變量，而且是三個(gè)杯子，不管是全局變量中還是局部變量中 都定義了許多數(shù)組，增加了空間復(fù)雜度， 。由于本算法所有問題的求解都是圍繞三個(gè)杯 子之間的轉(zhuǎn)換進(jìn)行的，而且函數(shù)之間都是嵌套調(diào)用，全局變量的使用在一定程度上降低 了空間復(fù)雜度。由于采用圖的模型，圖中頂點(diǎn)和頂點(diǎn)之間的關(guān)系比較復(fù)雜，要建立狀態(tài) 表建立存儲所有的狀態(tài)，還要建立鄰接表，在遍歷過程中要有記錄路徑的數(shù)組，這些都 增加了空間復(fù)雜度。三個(gè)

20、杯子之間的轉(zhuǎn)化，不能借用其他工具，只能在它們之間進(jìn)行變環(huán)，這樣就增加 了時(shí)間復(fù)雜度，要計(jì)算出三個(gè)杯子所有可能的狀態(tài)，在計(jì)算過程中，要用到雙重循環(huán)， 每建立一種新的狀態(tài)就要調(diào)用一次save ()函數(shù)，save ()函數(shù)中又調(diào)用了 compare。函數(shù)，這樣的嵌套調(diào)用再加上循環(huán)語句的大量使用，使算法的時(shí)間復(fù)雜度進(jìn)一步增加。 在深度優(yōu)先搜索遍歷算法，用了遞歸的思想，大大增加了時(shí)間復(fù)雜度4、 經(jīng)驗(yàn)和體會：剛一開始拿到題目確實(shí)有種無從下手的感覺， 雖然在任務(wù)書中提示了用回溯和遞歸算法 求解本問題， 但不知道該采用什么樣的模型。 經(jīng)過分析可知就是把 053 變成440 就是找到 從053 到440 的路徑

21、， 這和圖的深度優(yōu)先搜索遍歷很相像， 而且回溯算法就是在圖的遍歷 中講到的，所以我就采用了圖的模型，用鄰接表存儲，建立狀態(tài)表，用圖的深度優(yōu)先搜索遍 歷求出所有解。 在課程設(shè)計(jì)過程中， 我發(fā)現(xiàn)我沒看一次深度優(yōu)先搜索遍歷， 我對這個(gè)算法的 理解就加深一步， 所以我覺得我現(xiàn)在只是把書上的表面知識學(xué)會了， 這本書中蘊(yùn)含的更深的 東西還值得我花更多的時(shí)間去學(xué)習(xí)。 獨(dú)立思考很重要， 跟別人交流也很重要。 在我和別人交 流的時(shí)候， 開闊了我的思維空間， 很多原先我沒想到的東西一下子就蹦出來了， 而且能填補(bǔ) 我知識的空白。 跟老師交流就更重要了， 以老師的知識層面和對問題的見解， 他的想法具有 很強(qiáng)的針對性和

22、可行性。五、用戶使用說明 本程序運(yùn)行過程中帶有提示性語句，而且本程序的輸入比較簡單，就是固定的幾 個(gè)數(shù)：首先輸入個(gè)酒杯的最大容量：8 5 3 ，然后輸入個(gè)酒杯當(dāng)前的狀態(tài)： 0 5 3 ，最后輸入要求解的最終狀態(tài)： 4 4 0 。按回車鍵，會輸出狀態(tài)表中的狀態(tài)和所有解。六、測試結(jié)果數(shù)據(jù)說明：本題的數(shù)據(jù)都是固定的，首先輸入各酒杯的最大容積： 8 5 3 ，然后輸入當(dāng)前的 容積： 0 5 3 ，再輸入要求解的最終狀態(tài)： 4 4 0 。按回車鍵程序輸出狀態(tài)表中的所有狀態(tài)和 所有解。七、附錄#include "stdio.h"#include "string.h"

23、#define N 3/ 酒杯數(shù)#define MAX_SIZES 100/ 狀態(tài)表中的最大狀態(tài)數(shù)typedef struct node/ 邊節(jié)點(diǎn)int adjvex;/ 鄰接點(diǎn)的位置node *next;/ 指向下一個(gè)節(jié)點(diǎn)ARCNODE;/ 鄰接表中的結(jié)點(diǎn)類型typedef struct/ 頂點(diǎn)節(jié)點(diǎn)int vexdataN; / 各酒杯的存儲狀態(tài)ARCNODE *next;/ 指向下一個(gè)鄰接點(diǎn)VEXNODE;/ 表頭結(jié)點(diǎn)類型int AMAX_SIZES;/ 用于存儲路徑的數(shù)組int top=0;/ 數(shù)組中的個(gè)數(shù)int fullN;/ 各酒杯的最大容量int partN;/ 各酒杯的當(dāng)前容量i

24、nt endN;/ 最終狀態(tài)VEXNODE sMAX_SIZES; / 狀態(tài)表int sta;/ 狀態(tài)表當(dāng)前狀態(tài)數(shù)int sum=0;/ 所有解的個(gè)數(shù)int end_vex;/ 結(jié)束的狀態(tài)點(diǎn)bool visitedMAX_SIZES;/ 標(biāo)記狀態(tài)是否被訪問bool compare(int a,int b) / 比較狀態(tài)int i;for(i=0;i<N;i+)if(ai!=bi)return true;/ 兩數(shù)組不相等，返回 truereturn false;/ 相等，返回 falsevoid save(int number) / 保存狀態(tài) ,如果狀態(tài)存在則僅僅加入領(lǐng)接表 ,如果不存在則

25、加入狀態(tài)表，并加入鄰 接表ARCNODE *p;int i;for(i=0;i<=sta;i+)if(!compare(part,si.vexdata)break;/ 該狀態(tài)存在，跳出 for 循環(huán)if(i>sta)/ 將該狀態(tài)加入狀態(tài)表sta+;for(int j=0;j<N;j+)ssta.vexdata j=partj;ssta.next=NULL;if(!compare(part,end)記住在狀態(tài)表中的位end_vex=sta;/ 該狀態(tài)是最終狀態(tài)，置p=new ARCNODE;p->adjvex=i;p->next=snumber.next;snumb

26、er.next=p;/ 加入鄰接表void jisuan(int number)/ 求出某狀態(tài)的所有鄰接點(diǎn)int i,j,I,J;for(i=0;i<N;i+)/ 編號為 i 的酒杯與其他酒杯交換for( j=0;j<N;j+)if(j=i) continue;/ 同一酒杯，無法變換I=parti;/ 保存 i 酒杯的當(dāng)前的容量J=fullj-partj;/j 酒杯的空閑量if(I<=J)/ 若 i 酒杯的當(dāng)前容量小于等于 j 酒杯的空閑量parti=0;partj+=I;/ 將 i 酒杯的酒倒向 j 酒杯save(number);/ 調(diào)用 save() 函數(shù)，保存當(dāng)前的狀態(tài)

27、parti=I;partj-=I;/ 恢復(fù)各酒杯的原始狀態(tài)else/ 若 i 酒杯的當(dāng)前容量大于 j 酒杯的空閑量parti-=J;partj=full j;/ 把 j 酒杯加滿save(number);/ 調(diào)用 save() 函數(shù)，保存當(dāng)前的狀態(tài)parti+=J;partj-=J;/ 恢復(fù)各酒杯的原始狀態(tài)void create()/ 建立狀態(tài)的函數(shù)int number,i;printf(" 輸入各個(gè)酒杯的容積 :");for(i=0;i<N;i+)scanf("%d",&fulli);printf(" 輸入對應(yīng)酒杯的起始狀態(tài) :");for(i=0;i<N;i+)s0scanf("%d",&s0.vexdatai);/ 初始狀態(tài)即狀態(tài)表中的printf(" 輸入對應(yīng)酒杯的最終狀態(tài) :");for(i=0;i<N;i+)scanf("%d",&endi);/ 所求的狀態(tài)number=0; sta=0;s0.next=NULL;while(number<=sta)for(i=0;i<N;i+)parti=snumber.vexdatai;/ 將 snumber 的狀態(tài)賦給各酒杯當(dāng)前的容量jisuan(n