折半算法的解決完整文檔

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

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

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

3、，m）是否等于0（未被占領）。如果是，擺放第n個皇后，并宣布占領（記得姚橫列豎列斜列一起設置），接著進行遞歸；如果不是，測試下一個位置（n，m+1），但是如果當n<=8，m=8時，發(fā)現(xiàn)此時已無法擺放時，便要進行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”。C、使用數(shù)組實現(xiàn)回溯法的思想。D、當n>8時，便打印出結(jié)果。E、輸出函數(shù)我使用printf輸出，運行形式為：第m種方法為：********算法流程圖：一、結(jié)構(gòu)體變量說明：intiCount=0;//!記錄解的序號的全局

4、變量。intSite[QUEENS];//!記錄皇后在各行上的放置位置的全局數(shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個解。intIsValid(intn);//!判斷第n個皇后放上去之后，是否有〉沖突。四、函數(shù)說明：解決沖突問題：在這個問題中包括了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的沖突；行：當?shù)贗行被某個皇后占領后，則同一行上的所有空格都不能再放皇后，要把以I為下標的標記置為被占領狀態(tài)；對角線：對角線有兩個方向。在這我把這兩條對角線稱為：主對角線和從

5、對角線。在同一對角線上的所有點（設下標為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當?shù)贗個皇后占領了第J列后，要同時把以(i+j)、(i-j)為下標的標記置為被占領狀態(tài)。對于數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，著重于:數(shù)組a[I]：a[I]表示第I個皇后放置的列；I的范圍：1..8;對角線數(shù)組：b[j](主對角線),c[j]（從對角線），根據(jù)程序的運行，去決定主從對角線是否放入皇后；五、程序執(zhí)行結(jié)果：五、遇到的問題：當用printf輸出時,出現(xiàn)了一些錯誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來是缺少了stdio.h這樣一個頭文件,添加了頭文件后,還

6、出現(xiàn)了一些問題,邏輯錯誤導致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時卻沒有錯誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學的交流,發(fā)現(xiàn)是邏輯錯誤,經(jīng)過改正后,程序終于可以運行了.六、附錄：程序源代碼#include#include#include#include#include#defineQUEENS8intiCount=0;//!記錄解的序號的全局變量。intSite[QUEENS];//!記錄皇后在各行上的放

7、置位置的全局數(shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個解。intIsValid(intn);//!判斷第n個皇后放上去之后，是否有沖突。voidmain(){system("title遞歸算法八皇后問題");cout<<""<<"八皇后的解法："<

8、tn)/*--Queen：遞歸放置第n個皇后，程序的核心!--*/{inti;if(n==QUEENS)//!參數(shù)n從0到8試出一個解，將它輸出并回溯。{Output();return;}for(i=1;i<=QUEENS;{Site