《算法設計與分析》實驗指導書

1、算法設計與分析實驗指導書本書是為配合 算法分析與設計實踐教學大綱而編寫的上機指導，其目的是使學生消化理論知識，加深對講授容的理解，尤其是一些算法的實現及其應用， 培養(yǎng)學生獨立編程和調試程序的能力，使學生對算法的分析與設計有更深刻的認識。上機實驗一般應包括以下幾個步驟：（ 1）、準備好上機所需的程序。 手編程序應書寫整齊， 并經人工檢查無誤后才能上機。（ 2）、上機輸入和調試自己所編的程序。一人一組，獨立上機調試，上機時出現的問題，最好獨立解決。（ 3）、上機結束后，整理出實驗報告。實驗報告應包括：題目、程序清單、運行結果、對運行情況所作的分析。目錄實驗一統(tǒng)計數字及字符編碼（2學時）.1實驗二蠻

2、力法（ 2 學時） .3實驗三遞歸與分治法（ 2 學時）.5實驗四貪心算法（ 2 學時） .8實驗五回溯算法（ 2 學時） .10實驗六分支限界法（ 2 學時） .12實驗七動態(tài)規(guī)劃算法（ 3 學時）.15實驗一統(tǒng)計數字及字符編碼（2 學時）一、實驗目的與要求1、掌握算法的計算復雜性概念。2、掌握算法漸近復雜性的數學表述。3、掌握用C+ 語言描述算法的方法。4實現具體的編程與上機實驗驗證算法的時間復雜性函數二、實驗容1、統(tǒng)計數字問題1）問題描述一本書的頁碼從自然數1 開始順序編碼直到自然數n。書的頁碼按照通常的習慣編排，每個頁碼都不含多余的前導數字0。例如，第6 頁用數字6 表示而不是06 或

3、 006等。數字計數問題要求對給定書的總頁碼 n 計算出書的全部頁碼中分別用到多少次數字 0、1、 2、 9。2）編程任務給定表示書的總頁碼的 10 進制整數 n (1n 109) 。編程計算書的全部頁碼中分別用到多少次數字 0、 1、2、 9。3）程序算法將頁碼數除以10，得到一個整數商和余數，商就代表頁碼數減余數外有多少個1 9 作為個位數，余數代表有 1余數本身這么多個數作為剩余的個位數。此外，商還代表 1商本身這些數出現了 10 次，余數還代表剩余的沒有計算的商的大小的數的個數。把這些結果統(tǒng)計起來即可。2、字典序問題1）問題描述在數據加密和數據壓縮中常需要對特殊的字符串進行編碼。給定的

4、字母表A 由寫英文字母組成A=a,b, ,z 。該字母表產生的升序字符串是指字符串中字母按照從左到出現的次序與字母在字母表中出現的次序相同，且每個字符最多出現1 次。例如，26個小右a,b,ab,bc,xyz等字符串都是升序字符串?，F在對字母表A 產生的所有長度不超過6 的升序字符串按照字典序排列并編碼如下。12262728abzabac對于任意長度不超過6 的升序字符串，迅速計算出它在上述字典中的編碼。算法設計：對于給定的長度不超過6 的升序字符串，計算出它在上述字典中的編碼。數據輸入：輸入數據由文件名為k，表示接下來共有k 行。接下來的input.txt 的文本文件提供。文件的第一行是一個

5、正整數k 行中，每行給出一個字符串。結果輸出：將計算結果輸出到文件output.txt中。文件共有k 行，每行對應于一個字符串的編碼。實驗二蠻力法（ 2 學時）一、實驗目的與要求1、 掌握蠻力法的基本思想2、 使用蠻力法解決具體問題（通常，問題規(guī)模比較小時，此方法才有意義）二、實驗容1、用 C+/C 編寫程序實現BF 算法，進行模式匹配。以下是該算法的偽代碼，請進行調試。int BF(char S , char T )i=0; j=0;while (i<strlen(S) && j<strlen(T)if (Si=Tj) i+; j+;else i=i-j+1; j

6、=0; if (j>=strlen(T) return (i-j);else return 0;2、用 C+/C 編寫程序實現KMP算法，進行模式匹配。求模式串 T 的 Next 數組void GetNext(char T , int next )next1=0;j=1; k=0;while (j<T0)if (k= =0)| |(Tj= =Tk) j+;k+;nextj=k;else k=nextk; KMP 算法偽代碼1. 在串 S 和串 T 中分別設比較的起始下標i 和 j ；2. 循環(huán)直到 S 中所剩字符長度小于 T 的長度或 T 中所有字符均比較完畢2.1如果 Si=Tj

7、 ，則繼續(xù)比較 S 和 T 的下一個字符；否則2.2將 j 向右滑動到 nextj 位置，即 j=nextj ；2.3如果 j=0 ，則將 i i+1 ， j=1 ，準備下一趟比較；3. 如果 T 中所有字符均比較完畢，則返回匹配的起始下標；否則返回03、以源串“ ababcabccabccacbab ”和模式串 ”abccac ”w 為例，編寫程序，給出采用BF 算法和 KMP算法進行串匹配過程中的字符比較次數。實驗三遞歸與分治法（2 學時）基本題一：基本遞歸算法一、實驗目的與要求1、 熟悉 C/C+ 語言的集成開發(fā)環(huán)境；2、 通過本實驗加深對遞歸過程的理解二、 實驗容：掌握遞歸算法的概念和

8、基本思想，分析并掌握“整數劃分”問題的遞歸算法。三、實驗題任意輸入一個整數，輸出結果能夠用遞歸方法實現整數的劃分。四、實驗步驟1 理解算法思想和問題要求；2 編程實現題目要求；3 上機輸入和調試自己所編的程序；4 驗證分析實驗結果；5 整理出實驗報告。基本題二：棋盤覆蓋問題一、實驗目的與要求1、掌握棋盤覆蓋問題的算法；2、初步掌握分治算法二、實驗題：kk方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4 種不同形態(tài)的 L 型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2 個 L 型骨牌不得重疊覆蓋。三、實驗提示void chessBoard(int tr, i

9、nt tc, int dr, int dc, int size)if (size = 1) return;int t = tile+,/ L 型骨牌號s = size/2;/ 分割棋盤/ 覆蓋左上角子棋盤if (dr < tr + s && dc < tc + s)/ 特殊方格在此棋盤中chessBoard(tr, tc, dr, dc, s);else /此棋盤中無特殊方格/ 用 t 號 L 型骨牌覆蓋右下角boardtr + s - 1tc + s - 1 = t;/ 覆蓋其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);/ 覆

10、蓋右上角子棋盤if (dr < tr + s && dc >= tc + s)/ 特殊方格在此棋盤中chessBoard(tr, tc+s, dr, dc, s);else /此棋盤中無特殊方格/ 用 t 號 L 型骨牌覆蓋左下角boardtr + s - 1tc + s = t;/ 覆蓋其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);/ 覆蓋左下角子棋盤if (dr >= tr + s && dc < tc + s)/ 特殊方格在此棋盤中chessBoard(tr+s, tc, dr, dc, s);

11、else /用 t 號 L 型骨牌覆蓋右上角boardtr + stc + s - 1 = t;/ 覆蓋其余方格chessBoard(tr+s, tc, tr+s, tc+s-1, s);/ 覆蓋右下角子棋盤if (dr >= tr + s && dc >= tc + s)/ 特殊方格在此棋盤中chessBoard(tr+s, tc+s, dr, dc, s);else /用 t 號 L 型骨牌覆蓋左上角boardtr + stc + s = t;/ 覆蓋其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);提高題一：二分搜索一、實驗目

12、的與要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、實驗題1、設 a0:n-1 是一個已排好序的數組。請改寫二分搜索算法，時，返回小于x 的最大元素的位置I 和大于 x 的最小元素位置和 j 相同，均為x 在數組中的位置。使得當搜索元素x 不在數組中j 。當搜索元素在數組中時，I2、設有n 個不同的整數排好序后存放于t0:n-1中，若存在一個下標I ，0 i n，使得ti=i，設計一個有效的算法找到這個下標。要求算法在最壞的情況下的計算時間為三、實驗提示O（ logn ）。1、用 I ， j 做參數，且采用傳遞引用或指針的形式帶回值。bool BinarySearch(int a,int

13、n,int x,int& i,int& j)int left=0;int right=n-1;while(left<right)int mid=(left+right)/2;if(x=amid)i=j=mid;return true;if(x>amid)left=mid+1;elseright=mid-1;i=right;j=left;return false;int SearchTag(int a,int n,int x)int left=0;int right=n-1;while(left<right)int mid=(left+right)/2;if(x

14、=amid) return mid;if(x>amid)right=mid-1;elseleft=mid+1;return -1;提高題二：用分治法實現元素選擇一、實驗要求與目的1、了解分治法的基本思想，掌握遞歸程序編寫方法；2、使用分治法編程，求解線形序列中第k 小元素。二、實驗容1、 給定線形序列集中n 個元素和一個整數k，1 k n，輸出這n 個元素中第k 小元素的值及其位置。2、 簡述該算法的原理、步驟。對該算法與直接排序查找進行比較。3、 編寫并調試程序。測試要求：元素個數不少于100；分三種情況：k=1、 k=n 和 k= 中位數。實驗四貪心算法（ 2 學時）基本題一：多機調

15、度問題一、實驗目的與要求1、熟悉多機調度問題的算法；2、初步掌握貪心算法；二、實驗題要求給出一種作業(yè)調度方案，使所給的n 個作業(yè)在盡可能短的時間由m 臺機器加工處理完成。 約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。三、實驗提示1、把作業(yè)按加工所用的時間從大到小排序2、如果作業(yè)數目比機器的數目少或相等，則直接把作業(yè)分配下去3、 如果作業(yè)數目比機器的數目多，則每臺機器上先分配一個作業(yè)，如下的作業(yè)分配時，是選那個表頭上 s 最小的鏈表加入新作業(yè)。typedef struct Jobint ID;/ 作業(yè)號int time;/ 作業(yè)所花費的時間J

16、ob;typedef struct JobNode / 作業(yè)鏈表的節(jié)點int ID;int time;JobNode *next;JobNode,*pJobNode;typedef struct Header/ 鏈表的表頭int s;pJobNode next;Header,pHeader;int SelectMin(Header* M,int m)int k=0;for(int i=1;i<m;i+)if(Mi.s<mk.s)k=i;return k;提高題一： 用貪心算法求解最小生成樹一、實驗要求與目的1、 熟悉貪心算法的基本原理與適用圍。2、 使用貪心算法編程，求解最小生成樹

17、問題。二、實驗容1、 任選一種貪心算法 （Prim 或 Kruskal ），求解最小生成樹。 對算法進行描述和復雜性分析。編程實現，并給出測試實例提高題二：汽車加油問題一、實驗目的與要求1、掌握汽車加油問題的算法；2、進一步掌握貪心算法；二、實驗題一輛汽車加滿油后可以行駛N 千米。旅途中有若干個加油站。若要使沿途的加油次數最少，設計一個有效的算法，指出應在那些加油站?？考佑?。并證明你的算法能產生一個最優(yōu)解。三、實驗提示把兩加油站的距離放在數組中，a1.n 表示從起始位置開始跑，經過n 個加油站， ak 表示第 k 1 個加油站到第 k 個加油站的距離。汽車在運行的過程中如果能跑到下一個站則不加

18、油，否則要加油。 （算法略）實驗五回溯算法（ 2 學時）基本題一：符號三角形問題一、實驗目的與要求1、掌握符號三角形問題的算法；2、初步掌握回溯算法；二、實驗題 圖下面都是 “ -”。 下圖是由14 個“ +”和14 個“-”組成的符號三角形。2 個同號下面都是 “ +”，2 個異號下面都是“-”。+-+-+-+-+-+-+-+在一般情況下，符號三角形的第一行有n 個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“ -”的個數相同。三、實驗提示void Triangle: Backtrack (int t)if (count>half)|(t*(t

19、-1)/2-count>half) return;if (t>n) sum+;elsefor (int i=0;i<2;i+) p1t=i;count+=i;for (int j=2;j<=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;Backtrack(t+1);for (int j=2;j<=t;j+)count-=pjt-j+1;count-=i;基本題二： 01 背包問題一、實驗目的與要求1、掌握 0 1 背包問題的回溯算法；2、進一步掌握回溯算法；二、實驗題：給定 n 種物品和一背包。物品i 的重量是wi

20、 ，其價值為vi ，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?三、實驗提示template<class Typew, class Typep>Typep Knap<Typew, Typep>:Bound(int i)/計算上界Typew cleft = c - cw;/ 剩余容量Typep b = cp;/ 以物品單位重量價值遞減序裝入物品while (i <= n && wi <= cleft) cleft -= wi;b += pi;i+;/ 裝滿背包if (i <= n) b += pi/wi *

21、 cleft;return b;提高題一：用回溯法求解跳馬問題一、實驗要求與目的1、 掌握回溯法的基本原理。2、 使用回溯法編程，求解跳馬問題二、實驗容1、 問題描述： 在 N*N 棋盤上有 N2 個格子， 馬在初始位置 （ X 0，Y 0），按照象棋中馬走 “日”的規(guī)則，使馬走遍全部格子且每個格子僅經過一次。編程輸出馬的走法。2、 給出算法描述。編程實現，給出N=5 ，（ X 0， Y 0） =（ 1， 1）時的運行結果。實驗六分支限界法（ 2 學時）基本題一：旅行商售貨員問題的分支限界算法一、實驗目的與要求1、掌握旅行商售貨員問題的分支限界算法；2、區(qū)分分支限界算法與回溯算法的區(qū)別，加深對

22、分支限界法的理解。二、實驗題：某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費 )。他要選定一條從駐地出發(fā)，經過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費 )最小。三、實驗提示旅行商問題的解空間是一個排列樹。有兩種實現的方法。第一種是只使用一個優(yōu)先隊列，隊列中的每個元素 中都包含到達根的路徑。 另一種是保留一個部分解空間樹和一個優(yōu)先隊列，優(yōu)先隊列中 的元素并不包含到達根的路徑。以下為第一種方法。由于我們要尋找的是最小耗費的旅行路徑，因此可以使用最小耗費分枝定界法。在實現過程中，使用一個最小優(yōu)先隊列來記錄活節(jié)點，隊列中每個節(jié)點的類型為MinHeapNode。每個節(jié)點包括如

23、下區(qū)域：x （從 1 到 n 的整數排列，其中x0 = 1 ），s（一個整數，使得從排列樹的根節(jié)點到當前節(jié)點的路徑定義了旅行路徑的前綴x0:s,而剩余待訪問的節(jié)點是x s + 1 : n - 1 ），cc （旅行路徑前綴，即解空間樹中從根節(jié)點到當前節(jié)點的耗費）， lcost（該節(jié)點子樹中任意葉節(jié)點中的最小耗費）， rcost （從頂點 xs : n - 1出發(fā)的所有邊的最小耗費之和） 。當類型為 MinHeapNode( T ) 的數據被轉換成為類型T 時，其結果即為 lcost的值。分枝定界算法的代碼見程序程序首先生成一個容量為100 的最小堆，用來表示活節(jié)點的最小優(yōu)先隊列?；罟?jié)點按 lco

24、st值從最小堆中取出。接下來，計算有向圖中從每個頂點出發(fā)的邊中耗費最小的邊所具有的耗費 MinOut 。如果某些頂點沒有出邊，則有向圖中沒有旅行路徑，搜索終止。如果所有的頂點都有出邊，則可以啟動最小耗費分枝定界搜索。根的孩子B 作為第一個E- 節(jié)點，在此節(jié)點上，所生成的旅行路徑前綴只有一個頂點1，因此 s=0, x0=1, x1:n-1是剩余的頂點（即頂點 2 ， 3， . ， n）。旅行路徑前綴1 的開銷為 0 ，即 cc = 0，并且， rcost=n&& i=1 時 MinOut。在程序中， bestc給出了當前能找到的最少的耗費值。初始時， 由于沒有找到任何旅行路徑，因

25、此 bestc的值被設為 NoEdge。旅行商問題的最小耗費分枝定界算法templateT AdjacencyWDigraph:BBTSP(int v)/旅行商問題的最小耗費分枝定界算法/定義一個最多可容納1000 個活節(jié)點的最小堆MinHeap > H(1000);T *MinOut = new T n+1;/計算 MinOut =離開頂點 i 的最小耗費邊的耗費T MinSum = 0; /離開頂點 i 的最小耗費邊的數目for (int i = 1; i <= n; i+) T Min = NoEdge;for (int j = 1; j <= n; j+)if (aj

26、 != NoEdge && (aj < Min | Min = NoEdge)Min = aj;if (Min = NoEdge) return NoEdge; /此路不通MinOut = Min;MinSum += Min;/ 把 E- 節(jié)點初始化為樹根MinHeapNode E;E.x = new int n;for (i = 0; i < n; i+)E.x = i + 1;E.s = 0; /局部旅行路徑為x 1 : 0 E.cc = 0; /其耗費為0E.rcost = MinSum;T bestc = NoEdge; /目前沒有找到旅行路徑/搜索排列樹w

27、hile (E.s < n - 1) /不是葉子if (E.s = n - 2) /葉子的父節(jié)點/ 通過添加兩條邊來完成旅行/ 檢查新的旅行路徑是不是更好if (aE.xn-2E.xn-1 != NoEdge && aE.xn-11 != NoEdge && (E.cc + aE.xn-2E.xn-1 + aE.xn-11 < bestc | bestc = NoEdge)/ 找到更優(yōu)的旅行路徑bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11;E.cc = bestc;H . I n s e r t ( E ) ; el

28、se delete E.x;else /產生孩子for (int i = E.s + 1; i < n; i+)if (aE.xE.sE.x != NoEdge)/ 可行的孩子 , 限定了路徑的耗費if (b < bestc | bestc = NoEdge) / 子樹可能有更好的葉子/ 把根保存到最大堆中MinHeapNode N;N.x = new int n;for (int j = 0; j < n; j+)N.xj = E.xj;N.xE.s+1 = E.x;N.x = E.xE.s+1;N.cc = cc;N.s = E.s + 1;N.lcost = b;N.r

29、cost = rcost;H . I n s e r t ( N ) ; /結束可行的孩子delete E.x; /對本節(jié)點的處理結束try H.DeleteMin(E); /取下一個 E- 節(jié)點catch (OutOfBounds) break; /沒有未處理的節(jié)點if (bestc = NoEdge) return NoEdge; /沒有旅行路徑/ 將最優(yōu)路徑復制到 v1:n 中for (i = 0; i < n; i+)vi+1 = E.x;while (true) /釋放最小堆中的所有節(jié)點delete E.x;try H.DeleteMin(E);catch (OutOfBoun

30、ds) break;return bestc;實驗七動態(tài)規(guī)劃算法（3 學時）基本題一：最長公共子序列問題一、實驗目的與要求1、熟悉最長公共子序列問題的算法；2、初步掌握動態(tài)規(guī)劃算法；二、實驗題若給定序列X=x1,x2,嚴格遞增下標序列i1,i2, ,xm ，則另一序列 ,ik 使得對于所有Z=z1,z2, j=1,2, ,k,zk ，是 X 的子序列是指存在一個有： zj=xij 。例如， 序列 Z=B ，C，D ，B 是序列 X=A ， B， C，B ， D， A ， B 的子序列，相應的遞增下標序列為2 ， 3， 5， 7 。給定 2 個序列X 和 Y ，當另一序列Z 既是 X 的子序列又是Y 的子序列時，稱Z 是序列 X和 Y 的公共子序列。給定 2 個序列 X=x1,x2, ,xm 和 Y=y1,y2, ,yn ，找出 X 和 Y 的最長公共子序列。三、實驗提示include "stdlib.h"#include "string.h"void LCSLength(char *x ,char *y,int m,int n, int *c, int *b)int i ,j;for (i = 1; i <= m; i+) ci0 = 0;for (i = 1;