1、成績評定表學生吳旭東班級學號1309010236專業信息與計算科學課程設計題目分治法解決棋盤覆蓋問題；回溯法解決數字拆分問題評語組長簽字：成績日期20 年 月曰課程設計任務書學院理學院專業信息與計算科學學生吳旭東班級學號1309010236課程設計題目分治法解決棋盤覆蓋問題；回溯法解決數字拆分問題實踐教學要求與任務：要求：1 鞏固和加深對基本算法的理解和運用，提高綜合運用課程知識進行算法設計 與分析的能力。2 培養學生自學參考書籍，查閱手冊、和文獻資料的能力。3 通過實際課程設計，掌握利用分治法或動態規劃算法，回溯法或分支限界法 等萬法的算法的基本思想，并能運用這些方法設計算法并編與程序解決頭

2、際冋題。4 了解與課程有關的知識，能正確解釋和分析實驗結果。任務：按照算法設計方法和原理，設計算法，編寫程序并分析結果，完成如下容：1. 運用分治算法求解排序問題。2. 運用回溯算法求解N后問題。工作計劃與進度安排：第12周：查閱資料。掌握算法設計思想，進行算法設計。第13周：算法實現，調試程序并進行結果分析。撰寫課程設計報告，驗收與答辯。指導教師：201年月專業負責人：201年 月曰學院教學副院長：201年 月曰日摘要算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。算法(Algorithm )是解題的步驟，可以把算法定義成解一確定類問題的任意一種特 殊的方法。在 計算機科學中，算

3、法要用 計算機算法語言描述，算法代表用計算 機解一類問題的精確、有效的方法。分治法字面上的解釋是 分而治之”，就是把一個復雜的問題分成兩個或更多 的相同或相似的子問題，再把子問題分成更小的子問題 直到最后子問題可以 簡單的直接求解，原問題的解即子問題的解的合并。 在一個2Ak*2Ak的棋盤上, 恰有一個放歌與其他方格不同，且稱該棋盤為特殊棋盤。回溯法的基本做法是深度優先搜索，是一種組織得井井有條的、能避免不必要重復搜索的窮舉式搜索算法。數字拆分問題是指將一個整數劃分為多個整數之和的問題。利用回溯法可以很好地解決數字拆分問題。將數字拆分然后回溯，從未解決問題。關鍵詞：分治法，回溯法，棋盤覆蓋，數

4、字拆分目錄1 分治法解決期盼覆問題 11.1 問題描述 11.2 問題分析 11.3 算法設計 11.4 算法實現 21.5 結果分析 41.6 算法分析 52 回溯法解決數字拆分問題 72.1 問題描述 72.2 問題分析 72.3 算法設計 82.4 算法實現 82.5 結果分析 10參考文獻 101 分治法解決期盼覆問題1.1 問題描述在一個2k x 2k （k 0）個方格組成的棋盤中，恰有一個方格與其他方格不 同，稱該方格為特殊方格。顯然，特殊方格在棋盤中出現的位置有 4k 中情形， 因而有4k中不同的棋盤，圖（a）所示是k=2時16種棋盤中的一個。棋盤覆 蓋問題要求用圖（b）所示的4

5、中不同形狀的L型骨牌覆蓋給定棋盤上除特殊方 格以外的所有方格，且熱河亮哥 L 型骨牌不得重復覆蓋1.2 問題分析用分治策略，可以設計解決棋盤問題的一個簡介算法。當k0時，可以將2Ak *2Ak棋盤分割為4個2Ak-1 *2*1子棋盤。由 棋盤覆蓋問題得知，特殊方格必位于 4 個較小的子棋盤中，其余 3 個子棋盤中 無特殊方格。為了將 3 個無特殊方格的子棋盤轉化為特殊棋盤可以將一個 L 型 骨牌覆蓋這 3 個較小棋盤的會合處，所以，這 3 個子棋盤上被 L 型覆蓋的方格 就成為給棋盤上的特殊方格，從而將原問題轉化為 4 個較小規模的棋盤覆蓋問 題。遞歸的使用這種分割，直至棋盤簡化為 1*1 棋

6、盤為止。1.3 算法設計將 2Ak x 2Ak 的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個中的一個， 構造剩下沒特殊方格三個子棋盤， 將他們中的也假一個方格設為特殊方格。如果是：左上的子棋盤（若不存在特殊方格）特殊方格右上的子棋盤（若不存在特殊方格）特殊方格左下的子棋盤（若不存在特殊方格） 則將該子棋盤右下角的那個方格假設為 則將該子棋盤左下角的那個方格假設為 則將該子棋盤右上角的那個方格假設為特殊方格右下的子棋盤(若不存在特殊方格) 則將該子棋盤左上角的那個方格假設為 特殊方格當然上面四種， 只可能且必定只有三個成立， 那三個假設的特殊方格剛好構成一 個 L 型骨架，我們可以給它們

7、作上相同的標記。 這樣四個子棋盤就分別都和原來 的大棋盤類似，我們就可以用遞歸算法解決。1.4 算法實現#includeint tile=1;int board100100;void chessBoard(int tr, int tc, int dr, int dc, int size)if(size=1)return;int t=tile+;int s=size/2;if(drtr+s & dctc+s)chessBoard(tr, tc, dr, dc, s);elseboardtr+s-1tc+s-1=t;chessBoard(tr, tc, tr+s-1, tc+s-1, s);if(

8、dr=tc+s)chessBoard(tr, tc+s, dr, dc, s);elseboardtr+s-1tc+s=t;chessBoard(tr, tc+s, tr+s-1, tc+s, s); if(dr=tr+s & dc=tr+s & dc=tc+s)chessBoard(tr+s, tc+s, dr, dc, s); elseboardtr+stc+s=t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);int main()int size;coutvv輸入棋盤的size(大小必須是2的n次幕): cinsize;int index_x,index_y

9、;coutindex_xindex_y;chessBoard(0,0,index_x,index_y,size);for(int i=0;isize;i+)for(int j=0;jsize;j+)coutboardijt;cout0解得此遞歸方程可得T(k)=O (4Ak )。由于覆蓋一個2Ak *2Ak棋盤所需的L型牌個數為(4Ak 1 )/3,故算法ChessBoard是一個在漸進意義下最優的算法2 回溯法解決數字拆分問題2.1 問題描述整數的分劃問題。如，對于正整數 n=6 ，可以分劃為：65+14+2, 4+1+13+3, 3+2+1, 3+1+1+12+2+2, 2+2+1+1,

10、2+1+1+1+11+1+1+1+1+1+1用戶從鍵盤輸入 n (圍 110 ) 。2.2 問題分析 很明顯這是一道關于數的組合的問題，但形成組合的數是有一定的限制的。仔 細分析一下題目，我們可以得到以下的結論：(1) 每一組數之和必須等于 n ；(2) 每一組數的個數是不固定的；(3) 等式中后一個數的大小必定大于或等于前一個數，因為這樣做的目的有 兩個：一是 能夠避免等式的重復，例如n=2 2=1+1n=3 3=1+2 3=1+1+13=2+1(可以看出為與1+2 是同一種拆分，因此該式子不能算) 另一個目的是可以減少不必要的搜索，提高程序效率。我們可以將待拆分的數對應路徑圖中的路口，將可

11、拆分的數對應分叉的編號 這樣對于 每個路口而言，它所擁有的分叉號是變化的，規律是：分叉的起始值取決于前 一次所取數，分叉的終止值取決于該路口數的中值。2.3 算法設計在進行算法設計時我們必須要注意兩點： 一是本問題需要解決如何記錄某一路徑中可取數的問題，為了解決這一問題， 本程序加入了一個新的數組 b ，用來記錄每一步所取的數。二是當某一條路走完以后，我們必須回到某一個路口，而路口的值始終保持原 來的數， 因此在遞歸調用中我們所使用的實際參數應是獨立的。本例中使用的 是形式參數 m ，實際參數是 a k ，這樣無論在某一級中 ak 的值怎樣變化， 的值是始終不變的。2.4 算法實現#inclu

12、de是需要拆分的數， m 是拆分的進度用于計數拆分的方法數， x 用于存儲解#include void splitN(int n,int m);/n int x1024=0,total=0 ;/total int main()int n ;printf(please input the natural number n:);scanf(%d,&n);splitN(n,1);printf(There are %d ways to split natural number %d.n,total,n); system(PAUSE);return 0 ; void splitN(int n,int m)/n 是需要拆分的數， m 是拆分的進度int rest,i,j;for(i=1;i=xm-1)/ 拆分的數大于或等于前一個從而保證不重復 xm=i ;/ 將這個數計入結果中。rest=n-i ;/ 剩下的數是 n-i ，如果已經沒有剩下的了，并且進度(總的拆分個數 )大于 1 ，說明已經得到一個結果。if(rest=0&m1)total+;printf(%dt,total);for(j=1;jm;j+)printf(%d+,xj);printf(%dn,xm);e