折半算法的解決完整文檔

《折半算法的解決完整文檔》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)第二次上機(jī)作業(yè)班級(jí)：070921姓名：張玲玲學(xué)號(hào)：07092017報(bào)告名稱：利用遞歸進(jìn)行編程上機(jī)時(shí)間：2010年9月29日?qǐng)?bào)告時(shí)間：2010年10月5日實(shí)驗(yàn)?zāi)康模荷钊肓私夂瘮?shù)的調(diào)用與返回；理解遞歸函數(shù)的執(zhí)行過程；學(xué)會(huì)利用函數(shù)的執(zhí)行過程。實(shí)驗(yàn)方法：利用把迭代公式翻譯成代碼和確定終止代碼的方法，寫出遞歸函數(shù)，從而執(zhí)行程序。實(shí)驗(yàn)結(jié)果：程序運(yùn)行成功，順利得出結(jié)果。題1：八皇后問題【在8*8的棋盤上放置八個(gè)皇后，要求這八個(gè)皇后相互不能攻擊（同行，同列，斜線）】一、問題重述：八皇后問題要求在一個(gè)８＊８的棋盤

2、上放上８個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊．按照國際象棋的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子．因此，八皇后問題等于要求八個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線上。而我的目的也是通過用C語言平臺(tái)將一個(gè)８＊８的棋盤上放上８個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．?使用遞歸方法最終將其問題變得一目了然，更加易懂。二、算法描述：A、數(shù)據(jù)初始化。B、從n列開始擺放第n個(gè)皇后（因

3、為這樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測試下一個(gè)位置（n，m+1），但是如果當(dāng)n<=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無法擺放時(shí)，便要進(jìn)行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”。C、使用數(shù)組實(shí)現(xiàn)回溯法的思想。D、當(dāng)n>8時(shí)，便打印出結(jié)果。E、輸出函數(shù)我使用printf輸出，運(yùn)行形式為：第m種方法為：***

4、*****算法流程圖：一、結(jié)構(gòu)體變量說明：intiCount=0;//!記錄解的序號(hào)的全局變量。intSite[QUEENS];//!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個(gè)解。intIsValid(intn);//!判斷第n個(gè)皇后放上去之后，是否有〉沖突。四、函數(shù)說明：解決沖突問題：在這個(gè)問題中包括了行，列，兩條對(duì)角線；列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有

5、空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；對(duì)角線：對(duì)角線有兩個(gè)方向。在這我把這兩條對(duì)角線稱為：主對(duì)角線和從對(duì)角線。在同一對(duì)角線上的所有點(diǎn)（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當(dāng)?shù)贗個(gè)皇后占領(lǐng)了第J列后，要同時(shí)把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。對(duì)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，著重于:數(shù)組a[I]：a[I]表示第I個(gè)皇后放置的列；I的范圍：1..8;對(duì)角線數(shù)組：b[j](主對(duì)角線),c[j]（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；

6、五、程序執(zhí)行結(jié)果：五、遇到的問題：當(dāng)用printf輸出時(shí),出現(xiàn)了一些錯(cuò)誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來是缺少了stdio.h這樣一個(gè)頭文件,添加了頭文件后,還出現(xiàn)了一些問題,邏輯錯(cuò)誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時(shí)卻沒有錯(cuò)誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學(xué)的交流,發(fā)現(xiàn)是邏輯錯(cuò)誤,經(jīng)過改正后,程序終于可以運(yùn)行了.六、附錄：程序源代碼#include#include#include#include

7、#include#defineQUEENS8intiCount=0;//!記錄解的序號(hào)的全局變量。intSite[QUEENS];//!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個(gè)解。intIsValid(intn);//!判斷第n個(gè)皇后放上去之后，是否有沖突。voidmain(){system("title遞歸算法八皇后問題");cout<<""<<"八皇后的解法："<

8、<""<<"-------------------------------------"<