《算法設(shè)計(jì)與分析》實(shí)驗(yàn)指導(dǎo)書.doc

算法設(shè)計(jì)與分析實(shí)驗(yàn)指導(dǎo)書本書是為配合算法分析與設(shè)計(jì)實(shí)踐教學(xué)大綱而編寫的上機(jī)指導(dǎo)，其目的是使學(xué)生消化理論知識，加深對講授內(nèi)容的理解，尤其是一些算法的實(shí)現(xiàn)及其應(yīng)用，培養(yǎng)學(xué)生獨(dú)立編程和調(diào)試程序的能力，使學(xué)生對算法的分析與設(shè)計(jì)有更深刻的認(rèn)識。上機(jī)實(shí)驗(yàn)一般應(yīng)包括以下幾個步驟：（1）、準(zhǔn)備好上機(jī)所需的程序。手編程序應(yīng)書寫整齊，并經(jīng)人工檢查無誤后才能上機(jī)。（2）、上機(jī)輸入和調(diào)試自己所編的程序。一人一組，獨(dú)立上機(jī)調(diào)試，上機(jī)時(shí)出現(xiàn)的問題，最好獨(dú)立解決。（3）、上機(jī)結(jié)束后，整理出實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)報(bào)告應(yīng)包括：題目、程序清單、運(yùn)行結(jié)果、對運(yùn)行情況所作的分析。目錄實(shí)驗(yàn)一 統(tǒng)計(jì)數(shù)字及字符編碼（2學(xué)時(shí)）1實(shí)驗(yàn)二 蠻力法（2學(xué)時(shí)）3實(shí)驗(yàn)三 遞歸與分治法（2學(xué)時(shí)）5實(shí)驗(yàn)四 貪心算法（2學(xué)時(shí)）8實(shí)驗(yàn)五 回溯算法（2學(xué)時(shí)）10實(shí)驗(yàn)六 分支限界法（2學(xué)時(shí)）12實(shí)驗(yàn)七 動態(tài)規(guī)劃算法（3學(xué)時(shí)）15實(shí)驗(yàn)一 統(tǒng)計(jì)數(shù)字及字符編碼（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握算法的計(jì)算復(fù)雜性概念。 2、掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。 3、掌握用C+語言描述算法的方法。 4實(shí)現(xiàn)具體的編程與上機(jī)實(shí)驗(yàn)驗(yàn)證算法的時(shí)間復(fù)雜性函數(shù)二、實(shí)驗(yàn)內(nèi)容 1、統(tǒng)計(jì)數(shù)字問題 1）問題描述一本書的頁碼從自然數(shù)1 開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示而不是06或006等。數(shù)字計(jì)數(shù)問題要求對給定書的總頁碼n計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0、1、2、9。 2）編程任務(wù)給定表示書的總頁碼的10 進(jìn)制整數(shù)n (1n109) 。編程計(jì)算書的全部頁碼中分別用到多少次數(shù)字0、1、2、9。3）程序算法將頁碼數(shù)除以10，得到一個整數(shù)商和余數(shù)，商就代表頁碼數(shù)減余數(shù)外有多少個19作為個位數(shù)，余數(shù)代表有1余數(shù)本身這么多個數(shù)作為剩余的個位數(shù)。此外，商還代表1商本身這些數(shù)出現(xiàn)了10次，余數(shù)還代表剩余的沒有計(jì)算的商的大小的數(shù)的個數(shù)。把這些結(jié)果統(tǒng)計(jì)起來即可。2、字典序問題1）問題描述在數(shù)據(jù)加密和數(shù)據(jù)壓縮中常需要對特殊的字符串進(jìn)行編碼。給定的字母表A 由26 個小 寫英文字母組成A=a,b,z。該字母表產(chǎn)生的升序字符串是指字符串中字母按照從左到 右出現(xiàn)的次序與字母在字母表中出現(xiàn)的次序相同，且每個字符最多出現(xiàn)1 次。例如， a,b,ab,bc,xyz 等字符串都是升序字符串?，F(xiàn)在對字母表A 產(chǎn)生的所有長度不超過6 的升序 字符串按照字典序排列并編碼如下。12262728abzabac對于任意長度不超過6 的升序字符串，迅速計(jì)算出它在上述字典中的編碼。算法設(shè)計(jì)：對于給定的長度不超過6 的升序字符串，計(jì)算出它在上述字典中的編碼。 數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為input.txt的文本文件提供。文件的第一行是一個正整數(shù)k，表示接 下來共有k行。接下來的k 行中，每行給出一個字符串。結(jié)果輸出：將計(jì)算結(jié)果輸出到文件output.txt中。文件共有k 行，每行對應(yīng)于一個字符串的編碼。實(shí)驗(yàn)二 蠻力法（2學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康呐c要求1、 掌握蠻力法的基本思想2、 使用蠻力法解決具體問題（通常，問題規(guī)模比較小時(shí)，此方法才有意義）二、實(shí)驗(yàn)內(nèi)容 1、用C+/C編寫程序?qū)崿F(xiàn)BF算法，進(jìn)行模式匹配。以下是該算法的偽代碼，請進(jìn)行調(diào)試。int BF(char S , char T ) i=0; j=0; while (istrlen(S) & j=strlen(T) return (i-j); else return 0;2、用C+/C編寫程序?qū)崿F(xiàn)KMP算法，進(jìn)行模式匹配。 求模式串T的Next數(shù)組void GetNext(char T , int next ) next1=0; j=1; k=0; while (jT0) if (k= =0)| |(Tj= =Tk) j+; k+; nextj=k; else k=nextk; KMP算法偽代碼1. 在串S和串T中分別設(shè)比較的起始下標(biāo)i和j； 2. 循環(huán)直到S中所剩字符長度小于T的長度或T中所有字符均比較完畢 2.1 如果Si=Tj，則繼續(xù)比較S和T的下一個字符；否則 2.2 將j向右滑動到nextj位置，即j=nextj； 2.3 如果j=0，則將ii+1，j=1，準(zhǔn)備下一趟比較； 3. 如果T中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回03、以源串“ababcabccabccacbab”和模式串”abccac”w為例，編寫程序，給出采用BF算法和KMP算法進(jìn)行串匹配過程中的字符比較次數(shù)。實(shí)驗(yàn)三 遞歸與分治法（2學(xué)時(shí)）基本題一：基本遞歸算法一、實(shí)驗(yàn)?zāi)康呐c要求1、 熟悉C/C+語言的集成開發(fā)環(huán)境；2、 通過本實(shí)驗(yàn)加深對遞歸過程的理解二、實(shí)驗(yàn)內(nèi)容：掌握遞歸算法的概念和基本思想，分析并掌握“整數(shù)劃分”問題的遞歸算法。三、實(shí)驗(yàn)題任意輸入一個整數(shù)，輸出結(jié)果能夠用遞歸方法實(shí)現(xiàn)整數(shù)的劃分。四、實(shí)驗(yàn)步驟1 理解算法思想和問題要求；2 編程實(shí)現(xiàn)題目要求；3 上機(jī)輸入和調(diào)試自己所編的程序；4 驗(yàn)證分析實(shí)驗(yàn)結(jié)果；5 整理出實(shí)驗(yàn)報(bào)告。基本題二：棋盤覆蓋問題一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握棋盤覆蓋問題的算法；2、初步掌握分治算法二、實(shí)驗(yàn)題： 盤覆蓋問題：在一個2k2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。三、實(shí)驗(yàn)提示void chessBoard(int tr, int 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); / 覆蓋右上角子棋盤 if (dr = 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 = 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); 提高題一：二分搜索一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、實(shí)驗(yàn)題1、設(shè)a0:n-1是一個已排好序的數(shù)組。請改寫二分搜索算法，使得當(dāng)搜索元素x不在數(shù)組中時(shí)，返回小于x的最大元素的位置I和大于x的最小元素位置j。當(dāng)搜索元素在數(shù)組中時(shí)，I和j相同，均為x在數(shù)組中的位置。2、設(shè)有n個不同的整數(shù)排好序后存放于t0:n-1中，若存在一個下標(biāo)I，0in，使得ti=i，設(shè)計(jì)一個有效的算法找到這個下標(biāo)。要求算法在最壞的情況下的計(jì)算時(shí)間為O（logn）。三、實(shí)驗(yàn)提示1、用I，j做參數(shù)，且采用傳遞引用或指針的形式帶回值。bool BinarySearch(int a,int n,int x,int& i,int& j) int left=0; int right=n-1; while(leftamid) left=mid+1; else right=mid-1; i=right; j=left; return false;int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(leftamid) right=mid-1; else left=mid+1; return -1;提高題二： 用分治法實(shí)現(xiàn)元素選擇一、實(shí)驗(yàn)要求與目的1、了解分治法的基本思想，掌握遞歸程序編寫方法；2、使用分治法編程，求解線形序列中第k小元素。二、實(shí)驗(yàn)內(nèi)容1、 給定線形序列集中n個元素和一個整數(shù)k，1kn，輸出這n個元素中第k小元素的值及其位置。2、 簡述該算法的原理、步驟。對該算法與直接排序查找進(jìn)行比較。3、 編寫并調(diào)試程序。測試要求：元素個數(shù)不少于100；分三種情況：k=1、k=n和k=中位數(shù)。實(shí)驗(yàn)四 貪心算法（2學(xué)時(shí)）基本題一：多機(jī)調(diào)度問題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉多機(jī)調(diào)度問題的算法；2、初步掌握貪心算法；二、實(shí)驗(yàn)題 要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時(shí)間內(nèi)由m臺機(jī)器加工處理完成。約定，每個作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。三、實(shí)驗(yàn)提示1、把作業(yè)按加工所用的時(shí)間從大到小排序2、如果作業(yè)數(shù)目比機(jī)器的數(shù)目少或相等，則直接把作業(yè)分配下去3、如果作業(yè)數(shù)目比機(jī)器的數(shù)目多，則每臺機(jī)器上先分配一個作業(yè)，如下的作業(yè)分配時(shí)，是選那個表頭上s最小的鏈表加入新作業(yè)。typedef struct Job int ID;/作業(yè)號 int time;/作業(yè)所花費(fèi)的時(shí)間Job;typedef struct JobNode /作業(yè)鏈表的節(jié)點(diǎn) 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;im;i+) if(Mi.shalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;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背包問題一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握01背包問題的回溯算法；2、進(jìn)一步掌握回溯算法；二、實(shí)驗(yàn)題：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?三、實(shí)驗(yàn)提示templateTypep Knap:Bound(int i)/ 計(jì)算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量價(jià)值遞減序裝入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 裝滿背包 if (i H(1000); T *MinOut = new T n+1; / 計(jì)算MinOut = 離開頂點(diǎn)i的最小耗費(fèi)邊的耗費(fèi) T MinSum = 0; / 離開頂點(diǎn)i的最小耗費(fèi)邊的數(shù)目 for (int i = 1; i = n; i+) T Min = NoEdge; for (int j = 1; j = n; j+) if (aj != NoEdge & (aj Min | Min = NoEdge) Min = aj;if (Min = NoEdge) return NoEdge; / 此路不通 MinOut = Min; MinSum += Min; / 把E-節(jié)點(diǎn)初始化為樹根 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; / 其耗費(fèi)為0E.rcost = MinSum; T bestc = NoEdge; / 目前沒有找到旅行路徑 / 搜索排列樹 while (E.s n - 1) / 不是葉子 if (E.s = n - 2) / 葉子的父節(jié)點(diǎn) / 通過添加兩條邊來完成旅行 / 檢查新的旅行路徑是不是更好 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; E.lcost = bestc; E . s + + ; H . I n s e r t ( E ) ; else delete E.x; else / 產(chǎn)生孩子 for (int i = E.s + 1; i n; i+) if (aE.xE.sE.x != NoEdge) / 可行的孩子, 限定了路徑的耗費(fèi) T cc = E.cc + aE.xE.sE.x; T rcost = E.rcost - MinOutE.xE.s; T b = cc + rcost; /下限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.rcost = rcost; H . I n s e r t ( N ) ; / 結(jié)束可行的孩子 delete E.x; / 對本節(jié)點(diǎn)的處理結(jié)束 try H.DeleteMin(E); / 取下一個E-節(jié)點(diǎn) catch (OutOfBounds) break; / 沒有未處理的節(jié)點(diǎn) if (bestc = NoEdge) return NoEdge; / 沒有旅行路徑 / 將最優(yōu)路徑復(fù)制到v1:n 中for (i = 0; i n; i+) vi+1 = E.x; while (true) /釋放最小堆中的所有節(jié)點(diǎn) delete E.x; try H.DeleteMin(E); catch (OutOfBounds) break; return bestc; 實(shí)驗(yàn)七 動態(tài)規(guī)劃算法（3學(xué)時(shí)）基本題一：最長公共子序列問題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長公共子序列問題的算法；2、初步掌握動態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題 若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 三、實(shí)驗(yàn)提示include stdlib.h#include string.hvoid 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; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int