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

1、算法設(shè)計與分析實驗指導(dǎo)王歧編實驗一：遞歸與分治1. 二分查找2. 合并排序3. 快速排序?qū)嶒灦夯厮?. 0-1背包問題2. 裝載問題3. 堡壘問題(zoj1002)4. *翻硬幣問題5. 8皇后問題6. 素數(shù)壞問題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. 凸多邊

2、形的最優(yōu)三角剖分4. 防衛(wèi)導(dǎo)彈5. *石了合并6. *最小代價了母樹7. 竊旅游預(yù)算& *皇宮看守9. *游戲室問題10. *基因問題11. *出忌賽馬實驗五：貪心與隨機(jī)算法1. 背包問題2. 搬桌子問題3. *照亮的山景4. *用隨即算法求解8皇后問題5. 素數(shù)測試實驗一：遞歸與分治實驗fl的理解遞歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫 遞歸程序。學(xué)握分治算法的思想，對給泄的問題能設(shè)計出分治算法了以解決。實驗預(yù)習(xí)內(nèi)容編程實現(xiàn)講過的例題：二分搜索、合并排序、快速排序。對本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。試驗內(nèi)容和步驟1. 二分查找在對線性表的操作中，經(jīng)常需要查找某一個元索在

3、線性表中 的位置。此問題的輸入是待查元素x和線性表l,輸出為x在l 中的位置或者x不在l中的信息。程序略2. 合并排序程序略3. 快速排序程序略實驗總結(jié)及思考合并排序的遞歸程序執(zhí)行的過程實驗二：回溯算法實驗?zāi)康模菏炀氄莆栈厮菟惴▽嶒瀮?nèi)容：回溯算法的兒種形式a) 用i叫溯算法搜索子集樹的一般模式void search(int m)if(m>n)/遞歸結(jié)束條件output();相應(yīng)的處理(輸出結(jié)果)elseam=0;設(shè)置狀態(tài)：0表示不耍該物品search(m+1);遞歸搜索：繼續(xù)確定下一個物品am=l;設(shè)置狀態(tài)：1表示要該物品search(m+l);遞歸搜索：繼續(xù)確定下一個物品b) 用回溯算

4、法搜索子集樹的一般模式void scarch(int m)if(m>n)/遞歸結(jié)束條件output();相應(yīng)的處理(輸出結(jié)果)elsefbr(i=m;i<=n;i+4-)swap(m,i);交換 am和 aiif()if(canplace(m) 如果m處可放置search(m+l); /搜索下一層swpa(m,i);交換 am和 ai(換回來)習(xí)題1.01背包問題在0/1背包問題屮，需對容量為c的背包進(jìn)行裝載。從n個 物品中選取裝入背包的物品，每件物品i的重量為wi ,價值為pi。對丁可行的背包裝載，背包屮物品的總重量不能超過背包的 容量，最佳裝載是指所裝入的物甜價值最高。程序如下

5、：#include <stdio.h>/c：背包容量；m物品數(shù)wi、vi：第i件物品的重量和價/a數(shù)組存放當(dāng)両解各物詁選収情況；void readdata(); void scarch(int); void checkmax(); void printresult(); int c=35, n=10;int w10, v10; 值int a10, max; max：記錄最人價值/ai=0表示不選第i件物品,ai=l表示選第i件物品int main()readdata();讀入數(shù)據(jù)search(o);遞歸搜索printresult();void scarch(int m)if(m&g

6、t;=n)checkmax();檢查當(dāng)前解是否是可行解，若是則把它的價值與max比較elseam=0;不選第m件物品search(m+l); 遞歸搜索下一件物品 am=l;/不選第m件物品search(m+l); /遞歸搜索下一件物品void checkmax()int i, wcight=0, valuc=0;fbr(i=o;i<n;i+)if(ai=l)如果選取了該物品累加重量累加價值若為可行解/h價值大于max替換max讀入笫i件物品重weight = weight + vvi; value = value + vi;if(weight<=c)if(valuc>max)

7、max=value;void readdata()int i;for(i=0;i<n;i+)scanf(,%d%dh,&wi,&vi);量和價值void printresult()printf(h%dn,max);2.裝載問題冇兩艘船，載重量分別是cl、c2, n個集裝箱，重屋是w (i=l.n),且所有集裝箱的總重量不超過cl+c2。確定是否有at能 將所有集裝箱全部裝入兩艘船。提示：求出不超過cl的最大值max,若總重量一max < c2 則能裝入到兩艘船。3.堡壘問題（zoj1002）如圖城堡是一個4x4的方格，為了 保衛(wèi)城堡，現(xiàn)需要在某些格子里修建一些 堡壘

8、。城堡中的某些格子是墻，其余格子 都是空格，堡壘只能建在空格里，每個堡 壘都可以向上下左右四個方向射擊，如果 兩個堡壘在同一行或同一列，月中間沒冇 墻相隔，則兩個堡壘都會把對方打掉。問 對于給定的一種狀態(tài)，最多能夠修建兒個scarch(m+l);if(canplace(m)place(m); scarch(m+l); takeout(m);該位置不放堡壘遞歸搜索下一/判斷笫m個格子是否能放堡壘在第m個格了上放置一個堡壘遞歸搜索下一個位置去掉第m個格子上放置的堡壘堡壘。程序主耍部分如下： int main()readdata(); search(o); printresult(); void s

9、carch(int m)int row, col; row=m/n; col=m%n;ifm>=n*n) checkmax();是則把它的價值與max比較 else讀入數(shù)據(jù)/遞!tj搜索求第m個格了的行號求第ni個格子的列號檢查當(dāng)前解是否是可行解，若翻便幣問題把硬幣擺放成32x9的矩陣，傷呵以隨意翻轉(zhuǎn)矩陣屮的某些 行和某些列，問正面朝上的硬幣最多有多少枚？提示：（1）任意一行或一列，翻兩次等于沒有翻；（2）對于9列的任何一種翻轉(zhuǎn)的情況，每一行翻與不 翻相互獨立。5.8皇后問題在一個8 x 8的棋盤里放置8個皇后，要求這8個皇后兩兩 之間互相都不“沖突”。#include <stdi

10、o.h>#include <math.h>4.void scarch(int); void printresult(); int canplace(intjnt); void place(intjnt);打印結(jié)果判斷該位直能否放直皇后在該位置能否放置皇后/遞歸搜索/當(dāng)己經(jīng)找出一組解時輸出當(dāng)前結(jié)果/對當(dāng)前行0到7列的每一判斷第m個格了是否能放/在(m,i)格子上放置一個皇遞歸搜索下一行把(m,i)格子上的皇后去掉void takeout(int,int);把該位置放置皇示去掉int a8;ai存放第i個皇后的位置int main()search(o);void search(i

11、nt m)int i;if(m>=8)printresult();elsefbr(i=o;i<8;i+) 個位置if(canplacc(m,i) 堡壘place(m,i); 后scarch(m+l); takeout(m,i);int canplace(int row, int col)int i;fdr(i=0;i<row;i+) if(abs(i-row)=abs(ai-col)|ai=col) retum(o);rctum(l);void place(int row, int col)arow=col;void takeout(int row, int col)arow

12、=-l;void printrcsult()int i,j；for(i=0;i<8;i+)fbrg=o;j<8;j+)if(ai=j)printf(n a ”)；printf(m . n); printfnnn);printf(nnm);6.素數(shù)環(huán)問題把從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和 是一個素數(shù)。分析：用冋溯算法，程序如下:#include <stdio.h>#include <math.h>考察所有可能的排列。void scarch(int); void init();void printresult(); int isprime(i

13、nt); void swap(); int a21;int main()init()； scarch(2);int isprime(int num)初始化/打印結(jié)果判斷該數(shù)是否是素數(shù)交換am和ai/a數(shù)組存放素數(shù)環(huán)遞歸捜索int i,k;k=sqrt(nuiti); for(i=2;i<=k;i+) ifnum%i=o) return(o);retiirn(l);void printresult()int i;fbr(i=l ;i<=20;i+) printf(n%3dn,ai);printffn”);void search(int m)int i;當(dāng)已經(jīng)搜索到葉結(jié)如

14、果 al+a20也/輸出當(dāng)前解ifim>20)點時 if(isprime(al +a20) 是素數(shù)printrcsult(); return;fbr(i=m;i<=20;i+)（排列樹）svvap(m,i);交換 am和 aiif(isprime(am-1 +am) 判斷 am-l+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;i<21;i+)ai=i；7. 迷宮問題給一個20x20的

15、迷宮、起點坐標(biāo)和終點坐標(biāo)，問從起點是否能到達(dá)終點。輸入數(shù)據(jù)：.'表示空格；x，表示墻。 程序如下：讀入數(shù)據(jù)打印結(jié)果/a數(shù)組存放迷宮#include <stdio.h> include <math.h> void search(intjnt); int canplace(intjnt); void readdata(); void printresult(); int a2020;int s,t;int main()int row, col;readdata();row=s/20;col=s%20;search(row,col);遞歸搜索printresult()

16、;void search(int row, int col) 左int r,c; arowcol=l;r=row;c=col-l;判斷(r,c)位置是否已經(jīng)走過遞歸搜索(r,c)下判斷(r,c)位證是否已經(jīng)走過遞歸搜索(r,c)右判斷(i;c)位置是否已經(jīng)走過遞歸搜索(r,c)上判斷(r,c)位置是否已經(jīng)走過遞歸搜索(“)ircanplace(r,c) scarch(r.c);r=row+l; c=col; if(canplace(r9c) search(r.c);r=row; c=col+l; if(canplace(r,c) search(r,c);r=row-l; c=col; if(c

17、anplace(r?c) search(r,c);void printresult()int i,j;fbr(i=0;i<20;i+)for(j=0;j<20;j +) printf(n%3dn,aij)； printfinnn);void readdata()int i,j； for(i=0;i<20;i+)for0=o;j<2o;j+) scanf(”d”,&aij);int canplace(int row, int col)if(row>=0&&row<20&&col>=0&&col<

18、;20&&a row col =0)return 1;elsereturn 0;8. 農(nóng)場灌溉問題(zoj2412)一農(nóng)場山圖所示的十一種小方塊組成，藍(lán)色線條為灌溉渠。 若相鄰兩塊的灌溉渠相連則只需一口水井灌溉。給出若干由字母 表示的最人不超過50x50具體由(m, n)表示，的農(nóng)場圖，編程求 出最小需要打的井?dāng)?shù)。每個測例的輸出占一行。當(dāng)m=n=-1時結(jié) 束程序。efgsample inputdkhf33adcfjkihe-1 -1sample output23提示：參考迷宮問題，實現(xiàn)時關(guān)鍵要解決好各塊的表示問題。9. 求圖像的周長（zoj1047）給一個用和x表示的圖形，圖形

19、在上、下、左、右、左上、 左下、右上、右下8個方向都被看作是連通的，并且圖像中間不 會出現(xiàn)空洞，求這個圖形的邊長。輸入：首先給出m、門、x、y四個正整數(shù)，下面給出mxn的圖形, x y表示點擊的位置，全0表示結(jié)束。輸出：點擊的圖形的周長。xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.xxx.xxxxxxxxxxxxxxx.xxxxxxx xxx.x xxxxsample input2 222xxxx642 3xxx.xxx.xxx.x.x.x.0000sample output18提示：參考迷宮問題，區(qū)別在于它是向8個方向填。10骨牌矩陣多米諾骨牌是一個小正方形方塊，每個

20、骨牌都標(biāo)有一個數(shù)字 （06）,現(xiàn)在冇28組骨牌，每組兩個，各組編號為128,每組 編號對應(yīng)的兩個骨牌數(shù)值如下：00010203040506111213141516222324252633343536444546555666現(xiàn)將這28組骨牌排成一個7x8矩陣，此時只能看到每個骨 牌上的數(shù)字（06）,而不能知道每組的組號（如左下圖所示）。 請編程序?qū)⒚拷M骨牌分辨出來（如右卜-圖所示）。7x8骨牌矩陣骨牌組編號矩陣6626524128281471717111113201034101014722212313246654841625251321231043211284161515139951360455

21、12122222552626554026032724243318119605342032766202018119void search(int n)杏找下一個還沒放置骨牌的位置（x,y）;若沒有，則表示已經(jīng)找到一個解，輸出并且返冋;嘗試放置骨牌；兩次嘗試都失敗，進(jìn)行回溯；嘗試放置骨牌 把在(x,y)處的骨牌作為當(dāng)前骨牌紐的一個骨牌； 把(x+l,y)處的骨牌作為當(dāng)前骨牌組的另一個骨牌； 判斷當(dāng)前骨牌組是夠未被使用，如果未被使用則遞歸放 置下一個骨牌組： 把(x,y+l)處的骨牌作為當(dāng)前骨牌組的另一個骨牌； 判斷當(dāng)前骨牌組是否未被使用，如果未被使用則遞歸放 置下一個骨牌組；11. 字母轉(zhuǎn)換(zo

22、j1003)通過棧交換字母順序。給定兩個字符串，要求所冇的進(jìn)棧和出棧 序列(i表示進(jìn)棧，o表示出棧)，使得字符串2在求得的進(jìn)出棧 序列的操作下，變成字符串1。輸出結(jié)果需滿足字典序。例如trot 到 tort:iiiiooooioiiooiosample inputmadamadammbahamabahama long short eric ricesample outputiiiioooioo iiiiooooio iioioioioo iioioiooio ioiiiooiiooo ioiiioooioio ioioioiiiooo ioioioioioio iioioioo12. 踩氣球(

23、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)先搜索搜索

24、算法的一般模式：void search（）closed表初始化為空； open表初始化為空； 起點加入到open表； while（ open 表非空）取open表中的一個結(jié)點u; 從open表小刪除u;u進(jìn)入closed表；for（對擴(kuò)展結(jié)點u得到的每個新結(jié)點vi）if（vi是目標(biāo)結(jié)點） 輸出結(jié)果并返回； if vi的狀態(tài)少closed表和open表中的結(jié)點的狀態(tài)都不相同vi進(jìn)入 open 表;搜索算法關(guān)鍵耍解決好狀態(tài)判重的問題，這樣可省略closed 表，一般模式可改為：void search（）open表初始化為空；起點加入到open表；while（ open 表非空）取open表中的一個

25、結(jié)點u;從open表屮刪除u;for（對擴(kuò)展結(jié)點u得到的每個新結(jié)點vi）if（vi是目標(biāo)結(jié)點）輸出結(jié)果并返回；if（notused（vi）vi進(jìn)入open表；1. floodfill給一個20x20的迷宮和一個起點坐標(biāo)，用廣度優(yōu)先捜索填 充所有的可到達(dá)的格子。提示：參考笫2題。2. 電子老鼠闖迷宮如下圖12x12方格圖，找出一條自入口（2, 9）到岀口 （11,8）的最短路徑。#include<stdio.h>void rcaddata();void init();int search();每一個空格出填上最小步數(shù)int emptyopen();oo讀入數(shù)據(jù)初始化廣搜，并在每一個可

26、到達(dá)的判棧是否為空：空：1;非空:int takeoutofopen();從棧中取出一個元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動到該方向，并 帶回坐標(biāo)(r,c)int isaim(int row, int col); int used(int,int);void addtoopcn(int,int);判斷該點是否是目標(biāo)/判斷該點是否c經(jīng)走過把該點加入到open表int a1212;a存放迷宮，0表示空格，2表示墻。廣搜時，未找到目標(biāo)以前到達(dá)的空格,填上到達(dá)該點的最小步數(shù)int n;/為迷宮邊長，注：若人于12,必須修/o

27、pen 表起點和終點改一些參數(shù)，如a的大小int open20,head,tail,openlen=20; int s,t;int main()int number; readdata(); init(); numbei-search(); printf(n%du,number);讀取數(shù)據(jù)初始化/廣搜并返回最小步數(shù)打印結(jié)果int search()int u, row, col, r, c, i, num;while(! emptyopen()當(dāng)棧非空u=takeoutofopen();把該元索從棧中刪除row=u/n; col=u%n; num=arowcol;fbr(i=0;i<4;i

28、+)從棧屮取出一個元素，并計算該點的坐標(biāo)取得該點的步數(shù)if(canmoveto(row,cot&r,&c,i)判能否移動到該方向，并帶回處標(biāo)(r,c)點到達(dá)過小步數(shù)open 表ifisaim(r,c)retum(num+l);if(!used(r,c)arc=num+l;addtoopen(r,c);如果是冃標(biāo)結(jié)返回最小步數(shù)如果(r,c)還未記錄該點的最把該點加入到int emptyopen()if(head=tail) rctum(l);elsereturn(o);int takeoutofbpen()int u;if(head=tail)printf(nerrer: sta

29、ck is empty11); rctum(-l);u=ope nhead+;head=head%openlen;retum(u);int canmoveto(int row, int col, int *p, int *q, int direction) int r,c;r=row;c=col;switch(directio n)case 0: c; break;case 1: r+; break;case 2: c卄； break;case 3: r;*p=r；*q=c;ifr<0| |r>=n| |c<0| |c>=n) retum(o);if(arc=o)ret

30、um(l);retum(o);int isaim(int row, int col)if(row*n+col=t) return(l);else左下右上如果越界返凹0如果是空格返回1其余情況返回0retum(o);if(arowcol=0)0表示空格int used(int row, int col)retum(o);elserctum(l);void addtoopen(int row, int col)int u;u=row*n+col;opentail+= u;tail=tail%openlen;void readdata()int ij,row,col;char str20;scanf

31、(”d”,&n);scanf(,'%d%d',&rovv,&col); 起點坐標(biāo) s=row*n+col;scanf("%d%d",&row,&col); /終點坐標(biāo) t=row* n+col;gets(str);fbr(i=o;i<n;i 卄)gets(str); foro=0;j<n;j+) if(stru=7)aiu=o;0表示空格elseaij=-2; /-2 表示墻void init()hcad=0;tail=l;open0=s;測試數(shù)據(jù)如下：12 107 1 8xxxxxxxxxxxxx.x.x

32、xxx.x.xx.xx.x.xx.xxx.xxx.x.xx.xxxxxxxxxxx.x.x.xx.xxx.xxxxx.x.xxxx.xxxx.x.xxxxxxxx.xxxxxxxxxxxxxxx注：測試數(shù)據(jù)可在運(yùn)行時粘貼上去(點擊窗口最左上角按鈕,在菜單中選則“編輯” / “粘貼”即可）。想一想：此程序都存在哪些問題，如果opcnlcn太小程序會 不會h i錯,加入代碼便程序能自動報111此類錯誤。3. 跳馬給一個200x200的棋盤，問國際象棋的馬從給定的起點到給 定的終點最少需要幾步。sample input 0011 sample output 4狀態(tài)：馬所在的行、列。 程序如下：#in

33、clude<stdio.h>void readdata();void init();int search();int emptyopen();非空：0olong takeoutofopen();把該元索從棧中刪除讀入數(shù)據(jù)/初始化廣度優(yōu)先搜索判棧是否為空：空：1;從棧屮取出一個元素，并判能否移動到該方向，判斷該點是否是口判斷該點是否已/把該點加入到/a存放棋盤，nint canmoveto(int,int,int*,int*,int); 并帶回坐標(biāo)(t,c)int isaim(int row, int col);標(biāo)int uscd(int,int);經(jīng)走過void addtoopen

34、(int,int);open 表int a200200,n=200;為迷宮邊長long open2000,head,tail,openlen=2000; /open 表 1367 long s,t;起點和終點int search()long u;int row, col, r, c, i, num;while(!emptyopen()當(dāng)棧非空if(!used(r,c)u=takeoutofopen();從棧中取出一個元素,動到該方向，row=u/n;計算該點所在的行col=u%n;計算該點所在的列num=arowcol;取得該點的步數(shù)for(i=0;i<8;i+)if(canmoveto

35、(row,col,&r,&c,i)/ 判 能否移并帶回坐標(biāo)(r,c)/結(jié)點1if(isaim(r,c)如果是目標(biāo)return(num+1);返回最小步并把該元素從棧中刪除數(shù)如果(r,c)還未到達(dá)過最小步數(shù)addtoopen(r,c);把該點加入到open表return 1;int main()main函數(shù)換了以下最上血讀起來更方便int number; readdata();init(); number=search(); printf(n%dn,number);int emptyopen()if(hcad=tail) retum( 1);else為了讓search()顯示在一

36、頁內(nèi)和一般的算法程序main函數(shù)寫在讀取數(shù)據(jù)初始化/廣搜并返回最小步數(shù)打印結(jié)果retum(o);long takeoutofopen()long u; if(head=tail)printf(nerrer: stack is empty11); rctum(-l);u=openhead+;head=head%openlen;retum(u);int used(int row, int col)if(arowcol=0) retum(o);elseretum(l);void addtoopen(int row, int col)int u;if(head-tail)%openlen=l)prin

37、tf(hopen table overflow11);u=row;u=u*n+col;opentail+= u;tail=tail%opcnlcn;void readdata()long row,col;scanf(n%ld%ldn,&row,&col); 起點坐標(biāo) s=row* n+col;scanf("%ld%ld",&row,&col); 終點坐標(biāo) t=row*n+col;void init()head=0;tail=l;open0=s;int isaim(int row, int col)if(row*n+col=t) retum(l

38、);elsereturn(o);思考：參考第4題，改為用結(jié)構(gòu)體表示狀態(tài)寫此程序。4. 獨倫車獨輪車的輪了上冇5種顏色，每走一格顏色變化 一次，獨輪車只能往前推，也可以在原地旋轉(zhuǎn)，每走c -格，需要一個單位的時間，每轉(zhuǎn)90度需要一個單 位的時間，轉(zhuǎn)180度需要兩個單位的時間?，F(xiàn)給定一 個20x20的迷宮、一個起點、一個終點和到達(dá)終點 的顏色，問獨輪車最少需要多少時間到達(dá)。狀態(tài)：獨輪車所在的行、列、當(dāng)前顏色、方向。另外為了方便在結(jié)點中加上到達(dá)該點的最小步數(shù)。 程序如f:#include<stdio.h>struct colomodeint used(stmct colomode v);

39、判斷該結(jié)點是否是到達(dá)過的int row;int col;int color;int direction; int num;i該狀態(tài)的行/列/顏色/方向/最小步數(shù)hint search();小步數(shù)void rcaddata(); void init();廣搜返回口標(biāo)結(jié)點的最讀入數(shù)據(jù)初始化struct colornode moveahead(stmct colornode u); 返回 u 向前走一 格得到的結(jié)點結(jié)點_ void addtoopcn(struct colomodc v); 力fl入至u open 表int islegal(struct colornode v);如果該結(jié)點是合法的結(jié)

40、點(未越界且是空格)int isaim(struct colomode v);判斷該結(jié)點是否是目標(biāo)結(jié)點struct colomodc takcoutofopcn(); 從 open 表中取出一個結(jié)點 并把該結(jié)點從open表中刪除struct colornode turntoleft(struct colornode u);/u 向左轉(zhuǎn)得至u新結(jié)點vstruct colomode tumtoright(struct colomode u);/u 向左車令得至9新結(jié)點vstruct colornode s,t;s:起始結(jié)點；t fl 標(biāo)結(jié)點struct colornode open200;/ope

41、n 表int head,tail,openlen=200;/open 表相關(guān)數(shù)據(jù)int direct42=0,-l,l,0,0,l,-l,0;/向左、下、右、上四 個方向轉(zhuǎn)時，行列的增加值int a2020,n=20;/a數(shù)組表示迷宮；n為迷宮邊長int b202054;/b數(shù)組表示搜索時的所有狀態(tài)（0：未訪問；1：已訪問）int main()int number; readdata();廣搜返回目標(biāo)結(jié)點的最/u向前走一格得到新結(jié)點如果該結(jié)點是合法的判是否是目標(biāo)結(jié)點如果是未到達(dá)過的結(jié)加入到open表/u向左轉(zhuǎn)得到新結(jié)點v/u向右轉(zhuǎn)得到新結(jié)點vnumber=search(); printf(n%

42、diin,number);int search()小步數(shù)struct colornode u,v;while(head!=tail)u=takeoutofopen(); v=moveahead(u);vif(islegal(v)結(jié)點(未越界且是空格) if(isaim(v) return(venum);if(!used(v)點addtoopen(v);v=turntoleft(u);if(!used(v) addtoopen(v);v=turntoright(u);if(!used(v)addtoopen(v);int used(struct colornode v)/判斷該結(jié)點是否是到達(dá)過的

43、結(jié)點ifbv.rowv.colv.colorv.direction=0)rctum(o);elsereturn(l);void addtoopcn(struct colomodc v) 力口入至lj open 表opentail+=v;tail=tail%openlen;bv.rowv.colv.colorv.direction=l;struct colornode takeoutofopen()從 open 表中取出一個結(jié)點并把該結(jié)點從open表中刪除stmet colornode v; v=openhead+; hcad=hcad%opcnlcn; return(v);/初始化int i,

44、j,k,l;for(i=0;i<n;i+)所有狀態(tài)初始化fbru=o;j<n;j+)for(k=0;k<5;k-h-) for(l=0;l<4;l-h-)biljkl=o;hcad=o;taii=o; addtoopen(s);void rcaddata()char str5o; int i,j; for(i=0;i<n;i+)gets(str); for(j=0;j<n;j+4-) if(stru=7) aiu=0;else把起始點加入到open表讀入數(shù)據(jù)讀入數(shù)據(jù)t表示空格/存儲時0：表示空格/1:表示墻scanf(”d%d%d%d”,&s.row

45、,&s.col,&s.color,&s.direction); /讀入起始結(jié)點信息scanf("%d%d%d",&t.row,&t.col,&t.color);讀入目標(biāo)結(jié)點信息int isaim(struct colornode v)判斷該結(jié)點是否是口標(biāo)結(jié)點if(v.row=t.row&&v.col=t.col&&v.color=t color) return 1;elsereturn 0;int islegal(struct colomode v)如果該結(jié)點是合法的結(jié)點(未越界且是空格)if(

46、v. row<0|v. rovv>=n|v.col<0|v.co l>=n) /若越界 return 0;if(av.rowv,col=0)/0：表示空格return 1;return 0;struct colornode moveahead(struct colornode u) 返回 u 向前走一 格得到的結(jié)點struct colomode v; v.row=u.row+dircctu.dircction0; v.col=u.col+directu.directionl; v.color=(u.color+l)%5; v.direction=u.direction;

47、/u向左轉(zhuǎn)得到/u向左轉(zhuǎn)得到v.num=u.num+l;retum(v);struct colornode turntoleft(struct colornode u) 新結(jié)點vstruct colornode v;v=u;v.direction=(v.direction+1 )%4;v.num=v.num+l;retum(v);stmct colornode turntoright(struct colornode u) 新結(jié)點vstruct colornode v;v=u;v.direction=(v.direction+3)%4;v.num=v.num+l;return(v);測試數(shù)據(jù)：

48、xxxxxxxxxxxxxxxxxxxx.xxxxx.xxxxx.xx.xx.xxx.xx.x.xx.xxx.xxx.xx.xx.xxx.xx.x.xx.xxx.x .x.xxx.x.xx.x.x.x.x.x .xxxx.x.xxx.xxxxx.xxxxxxx .xxxxxx.xxx.xx.xx.x.x.xxxxxxx.xxxxxxxx.xx.x.x.x.x.x.xxxx.x.xxx.xxxxx.xxxx.x.xxxxx.xxxx.x.x.x.xx.xxx.xxxx.xx11114815. 皇宮小偷有一個小偷要到皇宮里偷取寶物，經(jīng)過仔細(xì)的偵察，他發(fā)現(xiàn) 皇宮實際上是一個20x20的迷宮，并且有一

49、名衛(wèi)兵巡邏，衛(wèi)兵巡 邏的路線是固定的，每單位時間移動一格，每4個單位時間循環(huán) i次。小偷每單位時i'可移動一格或在原地不動。任何時刻，小偷 和衛(wèi)兵在同i格，或衛(wèi)兵能看到小偷，小偷將會被衛(wèi)兵殺死?，F(xiàn) 在小偷已經(jīng)得到了皇宮的地圖，衛(wèi)兵巡邏的起點，衛(wèi)兵連續(xù)四次 移動的方向和寶物的位置，請你設(shè)計一個程序判斷小偷能否偷得 寶物。提示：參考第3題、第4題6. 分酒問題有一酒瓶裝有8斤酒，沒有量器，只有分別裝5斤和3斤的 空灑瓶。設(shè)計一程序?qū)?斤酒分成兩個4斤，并以最少的步驟給 出答案。7. *找倍數(shù)對于每個輸入的數(shù)字（如:2）,則要求 給出一個由1, 0構(gòu)成 的十進(jìn)制整數(shù)，且該整數(shù)為輸入數(shù)字的某個

50、倍數(shù)（如2對應(yīng)的10, 6 的倍數(shù) 100100100100100100）o&*8數(shù)碼難題由左圖變到右圖最少需要幾步，并演示移動過程。2758416312345678實驗四：動態(tài)規(guī)劃實驗?zāi)康模豪斫鈩討B(tài)規(guī)劃的基木思想，理解動態(tài)規(guī)劃算法的兩個 基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌 握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的 一般方法，對較簡單的問題能止確分析，設(shè)計出動態(tài)規(guī) 劃算法，并能快速編程實現(xiàn)。實驗內(nèi)容：編程實現(xiàn)講過的例題：最長公共子序列問題、矩陣連 乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線問題等。 本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。習(xí)題1. 最長公共子序列一個給定序列的了序列是在該序列屮刪去若干元素示得到 的序列。確切地說,若給定序列x=<xi,x2,.,xm>,則另一序列 z=<z1,彳,，zk>是x的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序