西北工業(yè)大學(xué) 算法設(shè)計與分析實驗指導(dǎo).doc

算法設(shè)計與分析實驗指導(dǎo)王歧 編實驗一：遞歸與分治1. 二分查找2. 合并排序3. 快速排序?qū)嶒灦夯厮?. 0-1背包問題2. 裝載問題3. 堡壘問題（ZOJ1002）4. *翻硬幣問題5. 8皇后問題6. 素數(shù)環(huán)問題7. 迷宮問題8. *農(nóng)場灌溉問題（ZOJ2412）9. *求圖像的周長（ZOJ1047）10. *骨牌矩陣11. *字母轉(zhuǎn)換（ZOJ1003）12. *踩氣球（ZOJ1004）實驗三：搜索1. Floodfill2. 電子老鼠闖迷宮3. 跳馬4. 獨輪車5. 皇宮小偷6. 分酒問題7. *找倍數(shù)8. *8數(shù)碼難題實驗四：動態(tài)規(guī)劃1. 最長公共子序列2. 計算矩陣連乘積3. 凸多邊形的最優(yōu)三角剖分4. 防衛(wèi)導(dǎo)彈5. *石子合并6. *最小代價子母樹7. *旅游預(yù)算8. *皇宮看守9. *游戲室問題10. *基因問題11. *田忌賽馬實驗五：貪心與隨機算法1. 背包問題2. 搬桌子問題3. *照亮的山景4. *用隨即算法求解8皇后問題5. 素數(shù)測試實驗一：遞歸與分治實驗?zāi)康睦斫膺f歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對給定的問題能設(shè)計出分治算法予以解決。實驗預(yù)習(xí)內(nèi)容編程實現(xiàn)講過的例題：二分搜索、合并排序、快速排序。對本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。試驗內(nèi)容和步驟1 二分查找在對線性表的操作中，經(jīng)常需要查找某一個元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。程序略2 合并排序程序略3 快速排序程序略實驗總結(jié)及思考合并排序的遞歸程序執(zhí)行的過程實驗二：回溯算法實驗?zāi)康模菏炀氄莆栈厮菟惴▽嶒瀮?nèi)容：回溯算法的幾種形式a) 用回溯算法搜索子集樹的一般模式void search(int m)if(mn) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)elseam=0; /設(shè)置狀態(tài)：0表示不要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個物品am=1; /設(shè)置狀態(tài)：1表示要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個物品b) 用回溯算法搜索子集樹的一般模式void search(int m)if(mn) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)elsefor(i=m;i=n;i+)swap(m,i); /交換am和aiif()if(canplace(m) /如果m處可放置search(m+1); /搜索下一層swpa(m,i); /交換am和ai(換回來)習(xí)題1 0-1背包問題在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高。 程序如下：#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; /c： 背包容量；n：物品數(shù)int w10, v10; /wi、vi：第i件物品的重量和價值int a10, max; /a數(shù)組存放當(dāng)前解各物品選取情況；max：記錄最大價值 /ai=0表示不選第i件物品，ai=1表示選第i件物品int main()readdata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)if(m=n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價值與max比較elseam=0; /不選第m件物品search(m+1); /遞歸搜索下一件物品am=1; /不選第m件物品search(m+1); /遞歸搜索下一件物品void checkmax()int i, weight=0, value=0;for(i=0;in;i+)if(ai=1) /如果選取了該物品weight = weight + wi; /累加重量value = value + vi; /累加價值if(weightmax) /且價值大于maxmax=value; /替換maxvoid readdata()int i;for(i=0;in;i+)scanf(%d%d,&wi,&vi); /讀入第i件物品重量和價值void printresult()printf(%d,max);2 裝載問題有兩艘船，載重量分別是c1、 c2，n個集裝箱，重量是wi (i=1n)，且所有集裝箱的總重量不超過c1+c2。確定是否有可能將所有集裝箱全部裝入兩艘船。提示：求出不超過c1的最大值max，若總重量max =n*n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價值與max比較elsesearch(m+1); /該位置不放堡壘遞歸搜索下一個位置if(canplace(m) /判斷第m個格子是否能放堡壘place(m); /在第m個格子上放置一個堡壘search(m+1); /遞歸搜索下一個位置takeout(m); /去掉第m個格子上放置的堡壘4 翻硬幣問題把硬幣擺放成329的矩陣，你可以隨意翻轉(zhuǎn)矩陣中的某些行和某些列，問正面朝上的硬幣最多有多少枚？提示：（1）任意一行或一列，翻兩次等于沒有翻； （2）對于9列的任何一種翻轉(zhuǎn)的情況，每一行翻與不翻相互獨立。5 8皇后問題在一個的棋盤里放置個皇后，要求這8個皇后兩兩之間互相都不“沖突”。#include #include void search(int);void printresult(); /打印結(jié)果int canplace(int,int); /判斷該位置能否放置皇后void place(int,int); /在該位置能否放置皇后void takeout(int,int); /把該位置放置皇后去掉int a8; /ai存放第i個皇后的位置int main()search(0); /遞歸搜索void search(int m)int i;if(m=8) /當(dāng)已經(jīng)找出一組解時printresult(); /輸出當(dāng)前結(jié)果elsefor(i=0;i8;i+) /對當(dāng)前行0到7列的每一個位置if(canplace(m,i) /判斷第m個格子是否能放堡壘place(m,i); /在(m,i)格子上放置一個皇后search(m+1); /遞歸搜索下一行takeout(m,i); /把(m,i)格子上的皇后去掉int canplace(int row, int col)int i;for(i=0;irow;i+)if(abs(i-row)=abs(ai-col)|ai=col)return(0);return(1);void place(int row, int col)arow=col;void takeout(int row, int col)arow=-1;void printresult()int i,j;for(i=0;i8;i+)for(j=0;j8;j+)if(ai=j)printf( A );elseprintf( . );printf(n);printf(n);6 素數(shù)環(huán)問題把從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素數(shù)。分析：用回溯算法，考察所有可能的排列。程序如下：#include #include void search(int);void init(); /初始化void printresult(); /打印結(jié)果int isprime(int); /判斷該數(shù)是否是素數(shù)void swap(int,int); /交換am和aiint a21; /a數(shù)組存放素數(shù)環(huán)int main()init();search(2); /遞歸搜索int isprime(int num)int i,k;k=sqrt(num);for(i=2;i=k;i+)if(num%i=0)return(0);return(1);void printresult()int i;for(i=1;i20) /當(dāng)已經(jīng)搜索到葉結(jié)點時if(isprime(a1+a20) /如果a1+a20也是素數(shù)printresult(); /輸出當(dāng)前解return;elsefor(i=m;i=20;i+) /(排列樹)swap(m,i); /交換am和aiif(isprime(am-1+am) /判斷am-1+am是否是素數(shù)search(m+1); /遞歸搜索下一個位置swap(m,i); /把am和ai換回來void swap(int m, int i)int t;t=am;am=ai;ai=t;void init()int i;for(i=0;i21;i+)ai=i;7 迷宮問題給一個2020的迷宮、起點坐標(biāo)和終點坐標(biāo)，問從起點是否能到達終點。輸入數(shù)據(jù)：.表示空格；X表示墻。程序如下：#include #include void search(int,int);int canplace(int,int);void readdata(); /讀入數(shù)據(jù)void printresult(); /打印結(jié)果int a2020; /a數(shù)組存放迷宮int s,t;int main()int row, col;readdata();row=s/20;col=s%20;search(row,col); /遞歸搜索printresult();void search(int row, int col)int r,c;arowcol=1;r=row; /左c=col-1;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row+1; /下c=col;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row; /右c=col+1;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row-1; /上c=col;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)void printresult()int i,j;for(i=0;i20;i+)for(j=0;j20;j+)printf(%3d,aij);printf(n);void readdata()int i,j;for(i=0;i20;i+)for(j=0;j=0&row=0&col20&arowcol=0)return 1;elsereturn 0;8 農(nóng)場灌溉問題（ZOJ2412）一農(nóng)場由圖所示的十一種小方塊組成，藍色線條為灌溉渠。若相鄰兩塊的灌溉渠相連則只需一口水井灌溉。給出若干由字母表示的最大不超過5050具體由(m，n)表示，的農(nóng)場圖，編程求出最小需要打的井?dāng)?shù)。每個測例的輸出占一行。當(dāng)M=N=-1時結(jié)束程序。Sample Input2 2DKHF3 3ADCFJKIHE-1 -1Sample Output23 提示：參考迷宮問題，實現(xiàn)時關(guān)鍵要解決好各塊的表示問題。9 求圖像的周長（ZOJ1047）給一個用 . 和X表示的圖形，圖形在上、下、左、右、左上、左下、右上、右下8個方向都被看作是連通的，并且圖像中間不會出現(xiàn)空洞，求這個圖形的邊長。輸入：首先給出m、n、x、y四個正整數(shù)，下面給出mn的圖形，x、y表示點擊的位置，全0表示結(jié)束。輸出：點擊的圖形的周長。 Sample Input2 2 2 2XXXX6 4 2 3.XXX.XXX.XXX.X.X.X.0 0 0 0 Sample output818提示：參考迷宮問題，區(qū)別在于它是向8個方向填。10 骨牌矩陣多米諾骨牌是一個小正方形方塊，每個骨牌都標(biāo)有一個數(shù)字（06），現(xiàn)在有28組骨牌，每組兩個，各組編號為128，每組編號對應(yīng)的兩個骨牌數(shù)值如下：00 01 02 03 04 05 0611 12 13 14 15 16 2223 24 25 26 33 34 3536 44 45 46 55 56 66現(xiàn)將這28組骨牌排成一個78矩陣，此時只能看到每個骨牌上的數(shù)字（06），而不能知道每組的組號（如左下圖所示）。請編程序?qū)⒚拷M骨牌分辨出來（如右下圖所示）。7X8骨牌矩陣 骨牌組編號矩陣66265241 28 28 14 7 17 17 11 1113201034 10 10 14 7 2 2 21 2313246654 8 4 16 25 25 13 21 2310432112 8 4 16 15 15 13 9 951360455 12 12 22 22 5 5 26 2655402603 27 24 24 3 3 18 1 1960534203 27 6 6 20 20 18 1 19void search(int n) 查找下一個還沒放置骨牌的位置(x,y); 若沒有，則表示已經(jīng)找到一個解，輸出并且返回； 嘗試放置骨牌； 兩次嘗試都失敗，進行回溯；嘗試放置骨牌l 把在(x,y)處的骨牌作為當(dāng)前骨牌組的一個骨牌；l 把(x+1,y)處的骨牌作為當(dāng)前骨牌組的另一個骨牌；l 判斷當(dāng)前骨牌組是夠未被使用，如果未被使用則遞歸放置下一個骨牌組；l 把(x,y +1)處的骨牌作為當(dāng)前骨牌組的另一個骨牌；l 判斷當(dāng)前骨牌組是否未被使用，如果未被使用則遞歸放置下一個骨牌組；11 字母轉(zhuǎn)換（ZOJ1003）通過棧交換字母順序。給定兩個字符串，要求所有的進棧和出棧序列（i表示進棧，o表示出棧），使得字符串2在求得的進出棧序列的操作下，變成字符串1。輸出結(jié)果需滿足字典序。例如TROT 到 TORT: i i i i o o o oi o i i o o i oSample InputmadamadammbahamabahamalongshortericriceSample Outputi i i i o o o i o o i i i i o o o o i o i i o i o i o i o o i i o i o i o o i o i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o i i o i o i o o 12 踩氣球（ZOJ1004）六一兒童節(jié)，小朋友們做踩氣球游戲，氣球的編號是1100，兩位小朋友各踩了一些氣球，要求他們報出自己所踩氣球的編號的乘積?，F(xiàn)在需要你編一個程序來判斷他們的勝負(fù)，判斷的規(guī)則是這樣的：如果兩人都說了真話，數(shù)字大的人贏；如果兩人都說了假話，數(shù)字大的人贏；如果報小數(shù)字的人說的是真話而報大數(shù)字的人說謊，則報小數(shù)字的人贏（注意：只要所報的小數(shù)字是有可能的，即認(rèn)為此人說了真話）。輸入為兩個數(shù)字，0 0表示結(jié)束；輸出為獲勝的數(shù)字。Sample Input36 6249 3430 0Sample Output6249實驗三：搜索算法實驗?zāi)康模菏炀氄莆账阉魉惴▽嶒瀮?nèi)容：廣度優(yōu)先搜索搜索算法的一般模式：void search()closed表初始化為空;open表初始化為空;起點加入到open表;while( open表非空 )取open表中的一個結(jié)點u;從open表中刪除u;u進入closed表;for( 對擴展結(jié)點u得到的每個新結(jié)點vi )if(vi是目標(biāo)結(jié)點)輸出結(jié)果并返回;if vi 的狀態(tài)與closed表和open表中的結(jié)點的狀態(tài)都不相同vi進入open表;搜索算法關(guān)鍵要解決好狀態(tài)判重的問題，這樣可省略closed表，一般模式可改為：void search()open表初始化為空;起點加入到open表;while( open表非空 )取open表中的一個結(jié)點u;從open表中刪除u;for( 對擴展結(jié)點u得到的每個新結(jié)點vi )if(vi是目標(biāo)結(jié)點)輸出結(jié)果并返回;If(notused(vi)vi進入open表;1. Floodfill給一個2020的迷宮和一個起點坐標(biāo)，用廣度優(yōu)先搜索填充所有的可到達的格子。提示：參考第2題。2. 電子老鼠闖迷宮如下圖1212方格圖，找出一條自入口（2，9）到出口（11，8）的最短路徑。本題給出完整的程序和一組測試數(shù)據(jù)。狀態(tài)：老鼠所在的行、列。程序如下：#includevoid readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣搜，并在每一個可到達的每一個空格出填上最小步數(shù)int emptyopen(); /判棧是否為空：空：1；非空：0。int takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動到該方向，并帶回坐標(biāo)(r,c)int isaim(int row, int col); /判斷該點是否是目標(biāo)int used(int,int); /判斷該點是否已經(jīng)走過void addtoopen(int,int); /把該點加入到open表int a1212; /a存放迷宮，0表示空格，-2表示墻。 /廣搜時，未找到目標(biāo)以前到達的空格，填上到達該點的最小步數(shù)int n; /n為迷宮邊長，注：若大于12，必須修改一些參數(shù)，如a的大小int open20,head,tail,openlen=20; /open表int s,t; /起點和終點int main()int number;readdata(); /讀取數(shù)據(jù)init(); /初始化number=search(); /廣搜并返回最小步數(shù)printf(%d,number); /打印結(jié)果int search()int u, row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除row=u/n; /計算該點的坐標(biāo)col=u%n;num=arowcol; /取得該點的步數(shù)for(i=0;i4;i+)if(canmoveto(row,col,&r,&c,i) /判能否移動到該方向，并帶回坐標(biāo)(r,c)if(isaim(r,c) /如果是目標(biāo)結(jié)點return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達過arc=num+1; /記錄該點的最小步數(shù)addtoopen(r,c); /把該點加入到open表int emptyopen()if(head=tail)return(1);elsereturn(0);int takeoutofopen()int u;if(head=tail)printf(errer: stack is empty);return(-1);u=openhead+;head=head%openlen;return(u);int canmoveto(int row, int col, int *p, int *q, int direction)int r,c;r=row;c=col;switch(direction)case 0: c-; /左break;case 1: r+; /下break;case 2: c+; /右break;case 3: r-; /上*p=r;*q=c;if(r=n|c=n) /如果越界返回0return(0);if(arc=0) /如果是空格返回1return(1);return(0); /其余情況返回0int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);int used(int row, int col)if(arowcol=0) / 0表示空格return(0);elsereturn(1);void addtoopen(int row, int col)int u;u=row*n+col;opentail+= u;tail=tail%openlen;void readdata()int i,j,row,col;char str20;scanf(%d,&n);scanf(%d%d,&row,&col); /起點坐標(biāo)s=row*n+col;scanf(%d%d,&row,&col); /終點坐標(biāo)t=row*n+col;gets(str);for(i=0;in;i+)gets(str);for(j=0;jn;j+)if(strj=.)aij=0; /0表示空格elseaij=-2; /2表示墻void init()head=0;tail=1;open0=s;測試數(shù)據(jù)如下：12 10 7 1 8XXXXXXXXXXXXX.X.XXXX.X.XX.XX.X.XX.XXX.XX.X.X.XX.XXXXXXXXXXX.X.X.XX.XXX.XXXXX.X.XXXX.XXXX.X.XXXXXXXX.XXXXXXXXXXXXXXX注：測試數(shù)據(jù)可在運行時粘貼上去（點擊窗口最左上角按鈕，在菜單中選則“編輯”/“粘貼”即可）。想一想：此程序都存在哪些問題，如果openlen太小程序會不會出錯，加入代碼使程序能自動報出此類錯誤。3. 跳馬給一個200200的棋盤，問國際象棋的馬從給定的起點到給定的終點最少需要幾步。Sample Input 0 0 1 1 Sample output 4狀態(tài)：馬所在的行、列。程序如下：#includevoid readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣度優(yōu)先搜索int emptyopen(); /判棧是否為空：空：1；非空：0。long takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動到該方向，并帶回坐標(biāo)(r,c)int isaim(int row, int col); /判斷該點是否是目標(biāo)int used(int,int); /判斷該點是否已經(jīng)走過void addtoopen(int,int); /把該點加入到open表int a200200,n=200; /a存放棋盤，n為迷宮邊長long open2000,head,tail,openlen=2000; /open表1367long s,t; /起點和終點int search()long u;int row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除row=u/n; /計算該點所在的行col=u%n; /計算該點所在的列num=arowcol; /取得該點的步數(shù)for(i=0;i8;i+)if(canmoveto(row,col,&r,&c,i) /判能否移動到該方向，并帶回坐標(biāo)(r,c)if(isaim(r,c) /如果是目標(biāo)結(jié)點return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達過arc=num+1; /記錄該點的最小步數(shù)addtoopen(r,c); /把該點加入到open表return -1;int main() /為了讓search()顯示在一頁內(nèi)和main函數(shù)換了以下 /一般的算法程序main函數(shù)寫在最上面讀起來更方便int number;readdata(); /讀取數(shù)據(jù)init(); /初始化number=search(); /廣搜并返回最小步數(shù)printf(%d,number); /打印結(jié)果int emptyopen()if(head=tail)return(1);elsereturn(0);long takeoutofopen()long u;if(head=tail)printf(errer: stack is empty);return(-1);u=openhead+;head=head%openlen;return(u);int used(int row, int col)if(arowcol=0)return(0);elsereturn(1);void addtoopen(int row, int col)int u;if(head-tail)%openlen=1)printf(open table overflow);u=row;u=u*n+col;opentail+= u;tail=tail%openlen;void readdata()long row,col;scanf(%ld%ld,&row,&col); /起點坐標(biāo)s=row*n+col;scanf(%ld%ld,&row,&col); /終點坐標(biāo)t=row*n+col;void init()head=0;tail=1;open0=s;int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);思考：參考第4題，改為用結(jié)構(gòu)體表示狀態(tài)寫此程序。4. 獨輪車獨輪車的輪子上有5種顏色，每走一格顏色變化一次，獨輪車只能往前推，也可以在原地旋轉(zhuǎn)，每走一格，需要一個單位的時間，每轉(zhuǎn)90度需要一個單位的時間，轉(zhuǎn)180度需要兩個單位的時間?，F(xiàn)給定一個2020的迷宮、一個起點、一個終點和到達終點的顏色，問獨輪車最少需要多少時間到達。狀態(tài)：獨輪車所在的行、列、當(dāng)前顏色、方向。另外為了方便在結(jié)點中加上到達該點的最小步數(shù)。程序如下：#includestruct colornodeint row; /該狀態(tài)的行int col; / 列int color; / 顏色int direction; / 方向int num; / 最小步數(shù);int search(); /廣搜返回目標(biāo)結(jié)點的最小步數(shù)void readdata(); /讀入數(shù)據(jù)void init(); /初始化struct colornode moveahead(struct colornode u); /返回u向前走一格得到的結(jié)點int used(struct colornode v); /判斷該結(jié)點是否是到達過的結(jié)點void addtoopen(struct colornode v); /加入到open表int islegal(struct colornode v); /如果該結(jié)點是合法的結(jié)點(未越界且是空格)int isaim(struct colornode v); /判斷該結(jié)點是否是目標(biāo)結(jié)點struct colornode takeoutofopen(); /從open表中取出一個結(jié)點并把該結(jié)點從open表中刪除struct colornode turntoleft(struct colornode u); /u向左轉(zhuǎn)得到新結(jié)點vstruct colornode turntoright(struct colornode u); /u向左轉(zhuǎn)得到新結(jié)點vstruct colornode s,t; /s:起始結(jié)點；t目標(biāo)結(jié)點struct colornode open200; /open表int head,tail,openlen=200; /open表相關(guān)數(shù)據(jù)int direct42=0,-1,1,0,0,1,-1,0;/向左、下、右、上四個方向轉(zhuǎn)時，行列的增加值int a2020,n=20; /a數(shù)組表示迷宮；n為迷宮邊長int b202054; /b數(shù)組表示搜索時的所有狀態(tài)(0：未訪問；1：已訪問)int main()int number;readdata();init();number=search();printf(%dn,number);int search() /廣搜返回目標(biāo)結(jié)點的最小步數(shù)struct colornode u,v;while(head!=tail)u=takeoutofopen();v=moveahead(u); /u向前走一格得到新結(jié)點vif(islegal(v) /如果該結(jié)點是合法的結(jié)點(未越界且是空格)if(isaim(v) /判是否是目標(biāo)結(jié)點return(v.num);if(!used(v) /如果是未到達過的結(jié)點addtoopen(v); /加入到open表v=turntoleft(u); /u向左轉(zhuǎn)得到新結(jié)點vif(!used(v)addtoopen(v);v=turntoright(u); /u向右轉(zhuǎn)得到新結(jié)點vif(!used(v)addtoopen(v);int used(struct