折半算法的解決完整文檔

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

1、數(shù)據(jù)結(jié)構(gòu)第二次上機(jī)作業(yè)班級(jí)：070921姓名：張玲玲學(xué)號(hào)：07092017報(bào)告名稱(chēng)：利用遞歸進(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í)行過(guò)程；學(xué)會(huì)利用函數(shù)的執(zhí)行過(guò)程。實(shí)驗(yàn)方法：利用把迭代公式翻譯成代碼和確定終止代碼的方法，寫(xiě)出遞歸函數(shù)，從而執(zhí)行程序。實(shí)驗(yàn)結(jié)果：程序運(yùn)行成功，順利得出結(jié)果。題1：八皇后問(wèn)題【在8*8的棋盤(pán)上放置八個(gè)皇后，要求這八個(gè)皇后相互不能攻擊（同行，同列，斜線(xiàn)）】一、問(wèn)題重述：八皇后問(wèn)題要求在一個(gè)８＊８的棋盤(pán)上放上８?jìng)€(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊．按照國(guó)際象棋

2、的規(guī)則，一個(gè)皇后可以攻擊與之處在同一行或同一列或同一斜線(xiàn)上的其他任何棋子．因此，八皇后問(wèn)題等于要求八個(gè)皇后中的任意兩個(gè)不能被放在同一行或同一列或同一斜線(xiàn)上。而我的目的也是通過(guò)用C語(yǔ)言平臺(tái)將一個(gè)８＊８的棋盤(pán)上放上８?jìng)€(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．?使用遞歸方法最終將其問(wèn)題變得一目了然，更加易懂。二、算法描述：A、數(shù)據(jù)初始化。B、從n列開(kāi)始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測(cè)試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測(cè)試

3、下一個(gè)位置（n，m+1），但是如果當(dāng)n<=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無(wú)法擺放時(shí)，便要進(jìn)行回溯。從問(wèn)題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱(chēng)為“回溯法”。C、使用數(shù)組實(shí)現(xiàn)回溯法的思想。D、當(dāng)n>8時(shí)，便打印出結(jié)果。E、輸出函數(shù)我使用printf輸出，運(yùn)行形式為：第m種方法為：********算法流程圖：一、結(jié)構(gòu)體變量說(shuō)明：intiCount=0;//!記錄解的序號(hào)的全局變量。intSite[QUEENS];//!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個(gè)解。int

4、IsValid(intn);//!判斷第n個(gè)皇后放上去之后，是否有〉沖突。四、函數(shù)說(shuō)明：解決沖突問(wèn)題：在這個(gè)問(wèn)題中包括了行，列，兩條對(duì)角線(xiàn)；列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；對(duì)角線(xiàn)：對(duì)角線(xiàn)有兩個(gè)方向。在這我把這兩條對(duì)角線(xiàn)稱(chēng)為：主對(duì)角線(xiàn)和從對(duì)角線(xiàn)。在同一對(duì)角線(xiàn)上的所有點(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]表示第

5、I個(gè)皇后放置的列；I的范圍：1..8;對(duì)角線(xiàn)數(shù)組：b[j](主對(duì)角線(xiàn)),c[j]（從對(duì)角線(xiàn)），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線(xiàn)是否放入皇后；五、程序執(zhí)行結(jié)果：五、遇到的問(wèn)題：當(dāng)用printf輸出時(shí),出現(xiàn)了一些錯(cuò)誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來(lái)是缺少了stdio.h這樣一個(gè)頭文件,添加了頭文件后,還出現(xiàn)了一些問(wèn)題,邏輯錯(cuò)誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時(shí)卻沒(méi)有錯(cuò)誤,就是沒(méi)有正確的輸出答案,一開(kāi)始我也不知道是怎么回事,通過(guò)和同學(xué)的交流,發(fā)現(xiàn)是邏輯錯(cuò)誤,經(jīng)過(guò)改正后,程序終于可以運(yùn)行了.六、附錄：程序源代碼#include#include#include

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

7、---------------------"<