算法實(shí)驗(yàn)報告

1、貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)系上機(jī)實(shí)驗(yàn)報告課程名稱：算法設(shè)計與分析班級：軟件101實(shí)驗(yàn)日期：2012-10-23姓名：學(xué)號：指導(dǎo)教師：實(shí)驗(yàn)序號：一實(shí)驗(yàn)成績：一、實(shí)驗(yàn)名稱分治算法實(shí)驗(yàn)-棋盤覆蓋問題二、實(shí)驗(yàn)?zāi)康募耙?、熟悉遞歸算法編寫；2、理解分治算法的特點(diǎn)；3、掌握分治算法的基本結(jié)構(gòu)。三、實(shí)驗(yàn)環(huán)境Visual C+四、實(shí)驗(yàn)內(nèi)容根據(jù)教材上分析的棋盤覆蓋問題的求解思路，進(jìn)行驗(yàn)證性實(shí)驗(yàn)；要求完成棋盤覆蓋問題的輸入、分治求解、輸出。有余力的同學(xué) 嘗試消去遞歸求解。五、算法描述及實(shí)驗(yàn)步驟分治算法原理：分治算法將大的分解成形狀結(jié)構(gòu)相同的子問題，并且不斷遞歸地分解，直到 子問題規(guī)模小到可以直

2、接求解。棋盤覆蓋問題描述：在一個2k x 2k個方格組成的棋盤中恰有一個方格與其他的不同稱為特殊方 格，想要求利用四種L型骨牌（每個骨牌可覆蓋三個方格）不相互重疊覆蓋的 將除了特殊方格外的其他方格覆蓋。實(shí)驗(yàn)步驟：1、定義用于輸入和輸出的數(shù)據(jù)結(jié)構(gòu)；2、完成分治算法的編寫；3、測試記錄結(jié)構(gòu)；4、有余力的同學(xué)嘗試不改變輸入輸出結(jié)構(gòu)，將遞歸消除，并說明能 否不用棧，直接消除遞歸，為什么？六、調(diào)試過程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。 記錄程序執(zhí)行的結(jié)果。七、總結(jié)對上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問題回答，上機(jī)的心得體會及改進(jìn)意見。通過對本實(shí)驗(yàn)的學(xué)習(xí)，對分治算法有了進(jìn)一步的認(rèn)識，對棋盤覆蓋問

3、題和其他分治問題進(jìn)行了對比。八、附錄源程序(核心代碼)清單或使用說明書，可另附紙/覆蓋左下角子棋盤if(dr=tr+s&dc=tr+s&dc=tc+s) chessboard(tr+s,tc+s,dr,dc,s);else(boardtr+stc+s=t;chessboard(tr+s,tc+s,tr+s,tc+s,s);int main()(int k,tr,tc,size,i,j;cinktrtc;size=pow(2,k);chessboard(0,0,tr,tc,size);for(i=0;isize;i+)(for(j=0;jsize;j+) coutboardij; coutend

4、l;#include#include#includeusing namespace std;int board100100,tile=1;void chessboard(int tr,int tc,int dr,int dc,int size)/tr 棋盤左上角方格的行號，tc棋盤左上角方格的列號。 dr特殊方格所在的行號。dc特殊方格所在的列號。size棋盤的大小2Ak.(int s;if(size=1)return ;int t=tile+;s=size/2;覆蓋左上角棋盤if(drtr+s&dctc+s)chessboard(tr,tc,dr,dc,s);else(boardtr+s-1

5、tc+s-1=t;chessboard(tr,tc,tr+s-1,tc+s-1,s);覆蓋右上角棋盤if(dr=tc+s)chessboard(tr,tc+s,dr,dc,s);else(boardtr+s-1tc+s=t;chessboard(tr,tc+s,tr+s-1,tc+s,s);貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)系上機(jī)實(shí)驗(yàn)報告課程名稱：算法設(shè)計與分析班級：軟件101實(shí)驗(yàn)日期：2012-11-6姓名：學(xué)號：指導(dǎo)教師：實(shí)驗(yàn)序號：二實(shí)驗(yàn)成績：一、實(shí)驗(yàn)名稱動態(tài)規(guī)劃實(shí)驗(yàn)-滑雪問題二、實(shí)驗(yàn)?zāi)康募耙?、學(xué)會使用在線測評的算法題目評分系統(tǒng)；2、通過直觀的應(yīng)用問題，加深對動態(tài)規(guī)劃算法的理

6、解；三、實(shí)驗(yàn)環(huán)境任意C或C+編寫調(diào)試工具，北京大學(xué)ICPC在線測評系統(tǒng)POJ四、實(shí)驗(yàn)內(nèi)容1、找到題號為1088的題目-滑雪，閱讀題目，建立其最優(yōu)解的遞歸 表達(dá)式；3、使用備忘錄式的動態(tài)規(guī)劃算法，實(shí)現(xiàn)本題；4、進(jìn)行簡單測試，完成之后提交到POJ系統(tǒng)。五、算法描述及實(shí)驗(yàn)步驟動態(tài)規(guī)劃算法原理：分治算法將大的問題變成小的問題來解決，但是如果劃分過程中出現(xiàn)重疊子 問題，就可能導(dǎo)致大量的重復(fù)計算。為了避免這些重復(fù)的計算，可以考慮的一個 辦法就是動態(tài)規(guī)劃算法。為了使用動態(tài)規(guī)劃算法，問題還必須具備最優(yōu)子結(jié)構(gòu)，即問題的最優(yōu)解包含 了子問題的最優(yōu)解?；﹩栴}描述：Michael喜歡滑雪百這并不奇怪，因?yàn)榛┑拇_很

7、刺激。可是為了獲得速度， 滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降 機(jī)來載你。Michael想知道載一個區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給出。 數(shù)組的每個數(shù)字代表點(diǎn)的高度。下面是一個例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一個人可以從某個點(diǎn)滑向上下左右相鄰四個點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-.-3-2-1更長。事實(shí)上，這是最長的一條。Input輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 = R,C = 10

8、0)。下面是R行， 每行有C個整數(shù)，代表高度h，0=h=10000。Output輸出最長區(qū)域的長度。實(shí)驗(yàn)步驟：1、建立滑雪問題的解的遞歸表達(dá)式遞歸表達(dá)式如下：if(dpij l- 口L 2 34 5LB1718196IS24ssaa714%5221RIM1511偵925Presc any cj tc continue七、總結(jié)對上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問題回答，上機(jī)的心得體會及改進(jìn)意見。通過本實(shí)驗(yàn)的學(xué)習(xí)，我對遞歸算法有了進(jìn)一步的了解，在驗(yàn)證試驗(yàn)結(jié)果時， 首先輸入5行5列的數(shù)組大小和數(shù)據(jù)，主函數(shù)調(diào)用DP(inti,intj)函數(shù)，求出最 長的路徑；該算法的在時間復(fù)雜度上得進(jìn)一步改進(jìn)，如果對于大一點(diǎn)的

9、數(shù)據(jù)，遍 歷效率就不高了。八、附錄源程序(核心代碼)清單或使用說明書，可另附紙#include #include #include using namespace std;const int M = 110;int a42 = -1,0,1,0,0,-1,0,1;int dpMM;int mapMM;int ans,tmp;int R,C;int DP(int i, int j)if (dpij 0)return dpij;for (int k = 0; k = 1) & (i+ak0 = R) & (j+ak1 =1) & map i+ak0 j+ak1 mapij)if(dpij R C;

10、for (i = 1; i = R; i+)for(int j = 1; j = C; j+) scanf(%d”,&mapij);for (i = 1; i = R; i+)for(int j = 1; j = C; j+)int aa = DP(i,j);if (ans aa)ans = aa;cout ans + 1 y) N += (b - y + 8 ) / 9;x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b;if(a x) N += ( a - x + 35 ) / 36;3、分析出算法復(fù)雜度該算法只需計算一下產(chǎn)品存放的空

11、間，不滿足則裝在另外的箱子里，滿足則 放入箱子，只需進(jìn)行簡單的比較即可，故所需的時間復(fù)雜度為O（n）。六、調(diào)試過程及實(shí)驗(yàn)結(jié)果詳細(xì)記錄程序在調(diào)試過程中出現(xiàn)的問題及解決方法。記錄程序執(zhí)行的結(jié)果。按輸入示例輸入數(shù)據(jù)如下：七、總結(jié)對上機(jī)實(shí)踐結(jié)果進(jìn)行分析，問題回答，上機(jī)的心得體會及改進(jìn)意見。通過對本實(shí)驗(yàn)的學(xué)習(xí)，我解決問題的思路很重要，一個清晰的解題思路，可以帶來高效的解題效率；但是對于貪心算法，我還不太熟 悉，在以后的學(xué)習(xí)中要對該算法多加練習(xí)，直到掌握。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙#include void main()int N, a, b, c, d, e, f, y, x;

12、int u4 = 0, 5, 3, 1);while (1)scanf(%d%d%d%d%d%d”, &a, &b, &c, &d, &e, &f);if (a = 0 & b = 0 &c=0&d= 0&e= 0 & f = 0) break;N = f + e + d + (c + 3)/4;y = 5 * d + uc % 4;if (b y) N += (b - y +8) / 9;x = 36 * N - 36 * f - 25* e-16*d - 9*c-4 * b;if (a x) N += ( a - x + 35 ) / 36;printf(%dn”, N);)貴州大學(xué)計算機(jī)

13、科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)系上機(jī)實(shí)驗(yàn)報告課程名稱：算法設(shè)計與分析班級：軟件101實(shí)驗(yàn)日期：2012-12-4姓名：學(xué)號：指導(dǎo)教師：實(shí)驗(yàn)序號：四實(shí)驗(yàn)成績：一、實(shí)驗(yàn)名稱回溯算法實(shí)驗(yàn)-頻道分配問題二、實(shí)驗(yàn)?zāi)康募耙?、使用在線測評的算法題目評分系統(tǒng)來測試所寫代碼；2、通過直觀的應(yīng)用問題，加深對回溯算法的理解；三、實(shí)驗(yàn)環(huán)境任意C或C+編寫調(diào)試工具，北京大學(xué)ICPC在線測評系統(tǒng)POJ四、實(shí)驗(yàn)內(nèi)容1、登陸POJ系統(tǒng)，找到題號為1129的題目-頻道分配；2、閱讀題目，分析出求解該問題的思路；3、使用回溯算法，實(shí)現(xiàn)本題；4、進(jìn)行簡單測試，完成之后提交到POJ系統(tǒng)。五、算法描述及實(shí)驗(yàn)步驟回溯算法原理：回溯法

14、是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法，用它可以系統(tǒng)地搜索 一個問題的所有解或任一解。它在問題的解空間樹中，按深度優(yōu)先的策略，從根 結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索全解空間樹的任一結(jié)點(diǎn)時，先判斷該結(jié)點(diǎn)是否 包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的搜索，逐層向 其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥栴}的所有解時，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已經(jīng)被搜索 遍才結(jié)束。回溯法求問題的一個解時，只要搜索到問題的一個解就可結(jié)束。頻道分配問題描述：當(dāng)個無線站廣播覆蓋個非常大的區(qū)域時，需要使用轉(zhuǎn)發(fā)器轉(zhuǎn)發(fā)增強(qiáng)信 號。然而，每個轉(zhuǎn)發(fā)器使用的頻道數(shù)必須仔細(xì)的選擇，以

15、使得相鄰的轉(zhuǎn)發(fā)器之間 不會相互干擾。它們相互不干擾的條件是相鄰的轉(zhuǎn)發(fā)器使用不同的頻道。因?yàn)闊o線頻譜是非常稀有的資源，因此，所給的轉(zhuǎn)發(fā)器網(wǎng)絡(luò)使用的頻道數(shù)量 必須最小化。你需要寫一個程序讀出轉(zhuǎn)發(fā)器網(wǎng)絡(luò)的描述，然后算出最小需要的頻 道數(shù)量。注意：鄰接關(guān)系具有對稱性，如果A鄰接B，則B鄰接A。另外，因?yàn)檗D(zhuǎn) 發(fā)器網(wǎng)絡(luò)是平面的，所以通道不會交叉。輸入輸入由若干轉(zhuǎn)發(fā)器網(wǎng)絡(luò)的地圖組成。每個地圖的第一個行是轉(zhuǎn)發(fā)器數(shù)量（1 至26，用0表示輸入結(jié)束）。每個轉(zhuǎn)發(fā)器由字母A至Z標(biāo)識，每行列出和一個轉(zhuǎn)發(fā) 器鄰接的相鄰轉(zhuǎn)發(fā)器。輸出對于每一個轉(zhuǎn)發(fā)器網(wǎng)絡(luò)地圖，輸出最少占用的頻道數(shù)量（注意單復(fù)數(shù)）。例子輸入2A:B:4A:BC

16、B:ACDC:ABDD:BC4A:BCDB:ACDC:ABDD:ABC0例子輸出1 channel needed.channels needed.channels needed.實(shí)驗(yàn)步驟：1、建立頻道分配問題的解題思路首先構(gòu)建回溯算法的基本框架，對每輸入的若干轉(zhuǎn)發(fā)器網(wǎng)絡(luò)的地圖（行數(shù): lines），都對其所有可能的路徑進(jìn)行比較，找出相鄰路徑不同的組合即可。2、構(gòu)造算法框架構(gòu)造頻道分配問題回溯算法如下:回溯算法實(shí)現(xiàn)void backtrack(int x)if (x = lines)int get=0;for (int i=0;iget)get = resulti;if(getm)m = get

17、;return;int j;for (int i=1;i=4;i+)for(j=0;jlines&lines)主函數(shù)調(diào)用實(shí)現(xiàn)while (cinlines&lines)int step = 1;m = 5;memset(set,0, sizeof (set);memset(result,0, sizeof (result);for (int i=0;ich;for(int j=2;chj!=0 ;j+) setichj-A=1;result0 = 1;backtrack(1);根據(jù)該算法的調(diào)度可知，每輸入一個行數(shù)，遍歷整個子樹需要樹的深度時間， 即O（N）時間，找到一個滿足條件的值就跳出。六、

18、調(diào)試過程及實(shí)驗(yàn)結(jié)果 按照輸入示例輸入數(shù)據(jù)如下:E Cz- Documents and SeHinWascTDebiJ叭klj.exe- X2A：B：1 channel needed.4A：BCB：ACDC：ABDD：BCchannels needed.4A： BCDB：ACDC：ABDD：ABCchannels needed.Ppess any key to continue由此可知，調(diào)試結(jié)果與預(yù)期結(jié)論一致。七、總結(jié)通過對本實(shí)驗(yàn)的學(xué)習(xí)，我對回溯算法有了進(jìn)一步的理解，在解決 問題和分析問題上的能力得到了一定的鍛煉。不過，在本次實(shí)驗(yàn)過程 中，也遇到一些困難，比如，剛開始在算法邏輯上沒有考慮周全，使

19、 得調(diào)試結(jié)果屢次出錯，后通過同學(xué)的查找，我發(fā)現(xiàn)了錯誤并給予解決。八、附錄源程序（核心代碼）清單或使用說明書，可另附紙#includeusing namespace std;#define MAX 27int setMAXMAX;int resultMAX;int lines;int m;void backtrack(int x)if (x = lines)int get=0;for (int i=0;iget)get = resulti;if (getm)m = get;return;int j;for(int i=1;i=4;i+)for(j=0;jlines;j+)if (setxj=1&

20、resultj=i) break;if (j=lines)(resultx = i;backtrack(x+1);int main()貴州大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)系上機(jī)實(shí)驗(yàn)報告課程名稱：算法設(shè)計與分析班級：軟件101實(shí)驗(yàn)日期：2012-12-4姓名：學(xué)號：指導(dǎo)教師：實(shí)驗(yàn)序號：五實(shí)驗(yàn)成績：一、實(shí)驗(yàn)名稱動態(tài)規(guī)劃算法-郵局問題二、實(shí)驗(yàn)?zāi)康募耙?、使用在線測評的算法題目評分系統(tǒng)來測試所寫代碼；2、通過直觀的應(yīng)用問題，加深對動態(tài)規(guī)劃算法的理解；三、實(shí)驗(yàn)環(huán)境C+編寫調(diào)試工具，北京大學(xué)ICPC在線測評系統(tǒng)POJ四、實(shí)驗(yàn)內(nèi)容1、登陸POJ系統(tǒng)，找到題號為1160號題目-郵局問題；2、閱讀題目

21、，分析出求解該問題的思路；3、使用動態(tài)規(guī)劃算法，實(shí)現(xiàn)本題；4、進(jìn)行簡單測試，完成之后提交到POJ系統(tǒng)。五、算法描述及實(shí)驗(yàn)步驟動態(tài)規(guī)劃算法原理：分治算法將大的問題變成小的問題來解決，但是如果劃分過程中出現(xiàn)重疊子問題， 就可能導(dǎo)致大量的重復(fù)計算。為了避免這些重復(fù)的計算，可以考慮的一個辦法就是動態(tài) 規(guī)劃算法。為了使用動態(tài)規(guī)劃算法，問題還必須具備最優(yōu)子結(jié)構(gòu)，即問題的最優(yōu)解包含了子問 題的最優(yōu)解。郵局問題描述：There is a straight highway with villages alongside the highway. The highway is represented as an

22、integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.Post offices will be built in some, but not necessari

23、ly all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.You are to write a program which, given the positions

24、 of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.【題日大意】：用數(shù)軸描述一條高速公路，有V個村莊，每一個村莊坐落在 數(shù)軸的某個點(diǎn)上，需要選擇P個村莊在其中建立郵局，要求每個村莊到最 近郵局的距離和最小。OutputThe first line contains one integer S, which is the sum of all distanc

25、es between each village and its nearest post office.Sample Input10 51 2 3 6 7 9 11 22 44 50Sample Output9實(shí)驗(yàn)步驟:1、建立郵局問題的解題思路【題日大意】：用數(shù)軸描述一條高速公路，有V個村莊，每一個村莊坐落 在數(shù)軸的某個點(diǎn)上，需要選擇P個村莊在其中建立郵局，要求每個村莊到 最近郵局的距離和最小。【解題分析】：就假設(shè)有m個村莊，分別為V1V2 V3Vm，要建n個郵 局，分別為P1 P2 P3Pn。1、考慮在m個村莊中只建立【一個】郵局的情況，顯然可以知道，將郵局 建立在中間的那個村莊即可。也就

26、是在V1到Vm間建立一個郵局，若使消 耗最小，則應(yīng)該將郵局建立在(V+Vm)/2這個村莊上。2、接下來考慮建立【多個】郵局的問題。不妨設(shè)，該郵局建在Vk+i.Vm之 間的某個村莊里，而且規(guī)定Vk+1.Vm之間再不允許建立其他郵局了。因此， 剩下的n-1個郵局必然出現(xiàn)在Vi.Vk之間的村莊內(nèi)，這樣問題就轉(zhuǎn)換成： 在前k個村莊里選n-1個郵局的問題。3、狀態(tài)表示，由上面的討論，可以設(shè)兩個數(shù)組設(shè)dp( m,n )表示在VVm之間建立n個郵局時的最短距離。L( i, j )表示在V；Vj之間建立一個郵局的最短距離。dp(k,n-1)L(k+1,m)1K K+1mdp(m,n)注：dp(m,n)表示前m個村莊中選n個郵局dp(k,n-1)表示前k個村莊中選n-1個郵局L (k+1, m)表示在Vk+1.Vm之間再建立一個郵局2、構(gòu)造算法框架DP