C語言課件 第25 26章.ppt

第25章 八皇后問題的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第25章 八皇后問題的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第25章 八皇后問題的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第25章 八皇后問題的實現(xiàn),問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,八皇后問題的實現(xiàn),國際象棋中，“皇后”在橫、豎、兩個方向的對角線上都可以吃對方的棋子。如果一個棋盤上有八個皇后，那么如何放置才可以相互不能攻擊呢？又有多少種放置方案呢？本章就通過c語言來實現(xiàn)此算法。,25.1 問題描述,八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是19世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在88格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。,25.2 問題分析及實現(xiàn),25.2.1 問題分析 25.2.2 問題實現(xiàn) 25.2.3 程序運行,25.2 問題分析及實現(xiàn),對于此問題，首先想到的前面提到的要領(lǐng)：看清、想明、把握每一個細(xì)節(jié)。由問題描述可知，我們要實現(xiàn)的是找到皇后的行列坐標(biāo)以及對應(yīng)方案號即可。,25.2.1 問題分析,我們將要開發(fā)的程序，就是設(shè)置一個棋盤（nn，n=8），并設(shè)置此棋盤上所有點均是空的。然后一種情況一種情況地試驗，遇到與問題的要求相匹配的情況時，方案數(shù)累加1，并輸出這種情況。,25.2.2 問題實現(xiàn),通過分析，我們得出此問題實現(xiàn)的2個要點：第一個是在哪種情況下，我們可以認(rèn)為是與問題的要求一致；第二個是怎么劃分模塊。問題實現(xiàn)的代碼如下。 1. 輸出結(jié)果 將結(jié)果輸出至屏幕，以循環(huán)打印的方式，調(diào)用標(biāo)準(zhǔn)輸入輸出函數(shù)printf，將結(jié)果回顯，代碼如下（代碼25-1.txt）。,25.2.2 問題實現(xiàn),01 #include 02 #define n 8 03 void output(int bcn,int *count) 04 05 int i; 06 int j; 07 *count=*count+1; 08 printf(“第%d種:n“,*count); 09 for(i=0;in;i+) 10 11 for(j=0;jn;j+) 12 13 if(bcij) 14 printf(“q“); /*在皇后位置打印q*/ 15 else 16 printf(“0“); /*在非皇后位置打印0*/ 17 18 printf(“nr“); 19 20 system(“pause“); /*暫停*/ 21 ,25.2.2 問題實現(xiàn),2. 求解每種方案是否符合題目要求 我們采用遞歸的方法，可以很容易地將這個問題簡化。就是要想讓第八個皇后的情況合法，我們需要去找第七個合法的皇后位置。那么，要想讓第七個皇后的位置合法，怎么辦？當(dāng)然是去找第六個皇后的位置，依此類推，可以推到第一個合法皇后的位置后，我們就返回調(diào)用處。代碼如下（代碼25-2.txt）。,25.2.2 問題實現(xiàn),3. 主程序函數(shù) 可實現(xiàn)對數(shù)據(jù)初始化，調(diào)用問題求解功能函數(shù)，并輸出最終方案個數(shù)。代碼如下（代碼25-3.txt）。,25.2.2 問題實現(xiàn),01 void main() 02 03 int padnn; 04 int count=0; 05 int i ,j; 06 for(i=0;in;i+) 07 08 for(j=0;jn;j+) 09 10 padij=0; /*將棋牌中所有位置置為0進(jìn)行初始化*/ 11 12 13 queen(pad,0, 15 ,25.2.3 程序運行,單擊【調(diào)試】工具欄中的按鈕，根據(jù)提示輸入數(shù)據(jù)，按【enter】鍵，即可輸出如下結(jié)果。,25.3 開發(fā)過程常見問題及解決,開發(fā)過程常見問題及解決辦法如下，僅供參考。 如何編寫這個遞歸函數(shù)呢？這里所要寫的遞歸函數(shù)的主要目的確認(rèn)后，就可以編寫正確的函數(shù)了，主要目的是試探方案是不是合法。無論如何，在函數(shù)中，一定要邊寫邊思考一旦條件成立后，遞歸它時，程序運行的流程，控制的對嗎？還要考慮函數(shù)遞歸結(jié)束后，返回到上次調(diào)用的那個位置之后。而且，我們采用的變量沒有傳遞進(jìn)遞歸函數(shù)，因此，函數(shù)返回后，需要歸位。即將還原某些變量的值，在本例中，需要還原棋牌的最后試探的點，標(biāo)為未試探，這樣，程序可以一直試驗其他情況。 此程序的難點之一理解本例的遞歸函數(shù)。遞歸的函數(shù)，本例中，只在一個地方調(diào)用自己。那就是找到一個合法皇后，再找下一個皇后，這樣，只要找夠8個皇后，則函數(shù)打印此方案并返回上次調(diào)用的位置。而在這個位置，向后執(zhí)行，則是繼續(xù)循環(huán)查找棋牌中其他位置上放置皇后是否合法，一旦合法，又將繼續(xù)找本方案中下一個合法皇后。,第26章 商人過河游戲,問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第26章 商人過河游戲,問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第26章 商人過河游戲,問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,第26章 商人過河游戲,問題描述 問題分析及實現(xiàn) 開發(fā)過程常見問題及解決,商人過河游戲,c語言的功能是強大而又靈活的。特別是在算法與數(shù)據(jù)結(jié)構(gòu)上，其靈活性、高效性更加明顯。本章研究對商人過河問題的求解。,26.1 問題描述,三名商人各帶一個隨從乘船渡河，一只小船只能容納二人，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商人們手中。商人們怎樣才能安全渡河呢?,26.2 問題分析及實現(xiàn),26.2.1 問題分析 26.2.2 問題實現(xiàn) 26.2.3 程序運行,26.2 問題分析及實現(xiàn),對于此問題，首先想到的前面提到的要領(lǐng)：看清、想明、把握每一個細(xì)節(jié)。由問題描述可知，我們要實現(xiàn)的是打印安全過河的方案，即不觸發(fā)殺人越貨并能安全過河的方案。,26.2.1 問題分析,我們的將要開發(fā)的程序，就是從所有過河方案中，排除錯誤的方案，留下正確可行的方案。,26.2.2 問題實現(xiàn),本小節(jié)就來通過編程來實現(xiàn)商人過河的游戲。 1. 采用結(jié)構(gòu)體保存過程數(shù)據(jù) 通過定義一個結(jié)構(gòu)體類型，模擬商人過河時，所有可能的方案及此方案的狀態(tài)，即需要記錄當(dāng)前河?xùn)|（原點）有幾位商人、幾位仆人，當(dāng)前河西（目的地）有幾位商人、幾位仆人。實現(xiàn)代碼見隨書光盤中的代碼26-1.txt。,26.2.2 問題實現(xiàn),2. 求解問題的主要實現(xiàn)函數(shù) 由于渡河過程有兩種情況：向東渡河，向西返回，因此，在設(shè)置的兩個狀態(tài)0,1時，均需要分別判斷商人與仆人個數(shù)是否合法。代碼如下（代碼26-1.txt）。,26.2.2 問題實現(xiàn),3. 求解問題的判斷函數(shù) 如果合法則繼續(xù)遞歸查找剩下的商人和仆人過河的方案，否則為不合法的方案，則應(yīng)該將此方案放棄。放棄后，程序返回上一級，繼續(xù)遞歸判斷其他情況是否合法，直到全部情況遞歸完畢。代碼如下（代碼26-2.txt）,26.2.3 程序運行,單擊【調(diào)試】工具欄中的按鈕，根據(jù)提示輸入數(shù)據(jù)，按【enter】鍵，即可輸出如下結(jié)果。,26.3