算法設計與分析實驗指導王歧編實驗一：遞歸與分治二分查找合并排序快速排序實驗二：回溯0-1背包問題裝載問題堡壘問題（ZOJ1002）*翻硬幣問題8皇后問題素數(shù)環(huán)問題迷宮問題*農(nóng)場灌溉問題（ZOJ2412）*求圖像的周長（ZOJ1047）*骨牌矩陣*字母轉換（ZOJ1003）*踩氣球（ZOJ1004）實驗三：搜索Floodfill電子老鼠闖迷宮跳馬獨輪車皇宮小偷分酒問題*找倍數(shù)*8數(shù)碼難題實驗四：動態(tài)規(guī)劃最長公共子序列計算矩陣連乘積凸多邊形的最優(yōu)三角剖分防衛(wèi)導彈*石子合并*最小代價子母樹*旅游預算*皇宮看守*游戲室問題*基因問題*田忌賽馬實驗五：貪心與隨機算法背包問題搬桌子問題*照亮的山景*用隨即算法求解8皇后問題素數(shù)測試實驗一：遞歸與分治實驗目的理解遞歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對給定的問題能設計出分治算法予以解決。實驗預習內(nèi)容編程實現(xiàn)講過的例題：二分搜索、合并排序、快速排序。對本實驗中的問題，設計出算法并編程實現(xiàn)。試驗內(nèi)容和步驟二分查找在對線性表的操作中，經(jīng)常需要查找某一個元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。程序略合并排序程序略快速排序程序略實驗總結及思考合并排序的遞歸程序執(zhí)行的過程實驗二：回溯算法實驗目的：熟練掌握回溯算法實驗內(nèi)容：回溯算法的幾種形式用回溯算法搜索子集樹的一般模式voidsearch(intm){if(m>n)〃遞歸結束條件output();//相應的處理(輸出結果)else{a[m]=0;〃設置狀態(tài)：0表示不要該物品search(m+1);〃遞歸搜索：繼續(xù)確定下一個物品a[m]=1;〃設置狀態(tài)：1表示要該物品search(m+1);//遞歸搜索：繼續(xù)確定下一個物品}}用回溯算法搜索子集樹的一般模式voidsearch(intm){if(m>n)//遞歸結束條件output();//相應的處理(輸出結果)elsefor(i=m;i<=n;i++){swap(m,i);〃交換a[m]和a[i]if()if(canplace(m))〃如果m處可放置search(m+1);//搜索下一層swpa(m,i);〃交換a[m]和a[i](換回來)}}習題1.0-1背包問題在0/1背包問題中，需對容量為c的背包進行裝載。從n個物品中選取裝入背包的物品，每件物品i的重量為wi,價值為pi。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高。程序如下：#include<stdio.h>voidreaddata();voidsearch(int);voidcheckmax();

voidprintresult();intc=35,n=10;intw[10],voidprintresult();intc=35,n=10;intw[10],v[10];inta[10],max;intmain(){readdata();search(0);printresult();}voidsearch(intm){if(m>=n)checkmax();else{a[m]=0;search(m+1);a[m]=1;search(m+1);}//c：背包容量；n：物品數(shù)//w[i]、v[i]：第i件物品的重量和價值//a數(shù)組存放當前解各物品選取情況；max:記錄最大價值//a[i]=0表示不選第i件物品，a[i]=1表示選第i件物品〃讀入數(shù)據(jù)〃遞歸搜索〃檢查當前解是否是可行解，若是則把它的價值與max比較〃不選第m件物品〃遞歸搜索下一件物品〃不選第m件物品//遞歸搜索下一件物品voidcheckmax(){inti,weight=0,value=0;for(i=0;i<n;i++){if(a[i]==1){weight=weight+w[i];value=value+v[i];}}if(weight<=c)if(value>max)max=value;}voidreaddata(){inti;for(i=0;i<n;i++)〃如果選取了該物品〃累加重量〃累加價值〃若為可行解//且價值大于〃如果選取了該物品〃累加重量〃累加價值〃若為可行解//且價值大于max〃替換max〃讀入第i件物品重量和價值}2.裝載問題有兩艘船，載重量分別是c1、c2,n個集裝箱，重量是Wj(i=1???n)，且所有集裝箱的總重量不超過c1+c2。確定是否有可能將所有集裝箱全部裝入兩艘船。提示：求出不超過c1的最大值max，若總重量一max<c2則能裝入到兩艘船。3.堡壘問題(ZOJ1002)如圖城堡是一個4X4的方格，為了保衛(wèi)城堡，現(xiàn)需要在某些格子里修建一些堡壘。城堡中的某些格子是墻，其余格子都是空格，堡壘只能建在空格里，每個堡壘都可以向上下左右四個方向射擊，如果兩個堡壘在同一行或同一列，且中間沒有墻相隔，則兩個堡壘都會把對方打掉。問對于給定的一種狀態(tài)，最多能夠修建幾個堡壘。程序主要部分如下：intmain(){readdata();〃讀入數(shù)據(jù)search(0);〃遞歸搜索printresult();}voidsearch(intm){introW,col;row=m/n;〃求第m個格子的行號col=m%n;〃求第m個格子的列號if(m>=n*n)checkmax();〃檢查當前解是否是可行解，若是則把它的價值與max比較else{search(m+1);〃該位置不放堡壘遞歸搜索下一個位置if(canplace(m))//判斷第m個格子是否能放堡壘{place(m);//在第m個格子上放置一個堡壘search(m+1);//遞歸搜索下一個位置takeout(m);〃去掉第m個格子上放置的堡壘}翻硬幣問題把硬幣擺放成32X9的矩陣，你可以隨意翻轉矩陣中的某些行和某些列，問正面朝上的硬幣最多有多少枚？提示：(1)任意一行或一列，翻兩次等于沒有翻；(2)對于9列的任何一種翻轉的情況，每一行翻與不翻相互獨立。5.8皇后問題在一個8X8的棋盤里放置8個皇后，要求這8個皇后兩兩之間互相都不“沖突”。#include<stdio.h>#include<math.h>voidsearch(int);voidprintresult();intcanplace(int,int);voidplace(int,int);voidtakeout(int,int);inta[8];intmain(){search(0);}voidsearch(intm){inti;if(m>=8)printresult();else{for(i=0;i<8;i++){if(canplace(m,i)){place(m,i);search(m+1);takeout(m,i);}}}}intcanplace(introw,intcol){inti;〃打印結果//判斷該位置能否放置皇后//在該位置能否放置皇后〃把該位置放置皇后去掉//a[i]存放第i個皇后的位置〃遞歸搜索〃當已經(jīng)找出一組解時〃輸出當前結果〃對當前行0到7列的每一個位置//判斷第m個格子是否能放堡壘//在(m,i)格子上放置一個皇后〃遞歸搜索下一行〃把(m,i)格子上的皇后去掉for(i=0;i<row;i++)if(abs(i-row)==abs(a[i]-col)||a[i]==col)return(0);return(1);}voidplace(introw,intcol){a[row]=col;voidtakeout(introw,intcol){a[row]=-1;}voidprintresult(){inti,j;for(i=0;i<8;i++){for(j=0;j<8;j++)if(a[i]==j)printf("A");elseprintf(".”);printf("\n");}printf("\n");}6.素數(shù)環(huán)問題把從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素數(shù)。考察所有可能的排列。分析：用回溯算法，考察所有可能的排列。程序如下：#include<stdio.h>#include<math.h>voidsearch(int);〃初始化〃打印結果〃判斷該數(shù)是否是素數(shù)〃初始化〃打印結果〃判斷該數(shù)是否是素數(shù)//交換a[m]和a[i]//a數(shù)組存放素數(shù)環(huán)voidprintresult();intisprime(int);voidswap(int,int);inta[21];intmain(){init();〃遞歸搜索search(2);〃遞歸搜索}intisprime(intnum){inti,k;k=sqrt(num);for(i=2;i<=k;i++)if(num%i==0)return(0);return(1);voidprintresult(){inti;for(i=1;i<=20;i++)printf("%3d”,a[i]);printf("\n");}voidsearch(intm){inti;if(m>20){if(isprime(a[1]+a[20]))

printresult();return;}else{for(i=m;i<=20;i++){swap(m,i);if(isprime(a[m-1]+a[m]))search(m+1);swap(m,i);}}}voidswap(intm,inti){intt;t=a[m];〃當已經(jīng)搜索到葉結點時〃如果a[1]+a[20]也是素數(shù)〃輸出當前解〃(排列樹)//交換a[m]和a[i]〃判斷a[m-1]+a[m]是否是素數(shù)〃遞歸搜索下一個位置//把a[m]和a[i]換回來a[m]=a[i];a[i]=t;}voidinit(){inti;for(i=0;i<21;i++)a[i]=i;}7.迷宮問題給一個20X20的迷宮、起點坐標和終點坐標，輸入數(shù)據(jù)：’.’表示空格；’X’表示墻。程序如下：問從起點是否能到達終點#include<stdio.h>#include<math.h>voidsearch(int,int);intcanplace(int,int);voidreaddata();voidprintresult();inta[20][20];intcanplace(int,int);voidreaddata();voidprintresult();inta[20][20];ints,t;intmain(){introw,col;〃讀入數(shù)據(jù)//打印結果//a數(shù)組存放迷宮}voidsearch(introw,intcol){intr,c;a[row][col]=1;r=row;〃左c=col-1;if(canplace(r,c))//判斷。,6位置是否已經(jīng)走過search(r,c);〃遞歸搜索(r,c)r=row+1;〃下c=col;if(canplace(r,c))//判斷。,6位置是否已經(jīng)走過search(r,c);〃遞歸搜索(r,c)r=row;//右c=col+1;if(canplace(r,c))//判斷。,6位置是否已經(jīng)走過search(r,c);〃遞歸搜索(r,c)r=row-1;〃上c=col;if(canplace(r,c))//判斷。,6位置是否已經(jīng)走過search(r,c);〃遞歸搜索(r,c)}voidprintresult(){inti,j;for(i=0;i<20;i++){for(j=0;j<20;j++)printf("%3d",a[i][j]);printf("\n");}}voidreaddata(){inti,j;for(i=0;i<20;i++){for(j=0;j<20;j++)scanf("%d",&a[i][j]);}}intcanplace(introw,intcol){if(row>=0&&row<20&&col>=0&&col<20&&a[row][col]==0)return1;elsereturn0;}農(nóng)場灌溉問題(ZOJ2412)一農(nóng)場由圖所示的十一種小方塊組成，藍色線條為灌溉渠。若相鄰兩塊的灌溉渠相連則只需一口水井灌溉。給出若干由字母表示的最大不超過50X50具體由(m，n)表示的農(nóng)場圖，編程求出最小需要打的井數(shù)。每個測例的輸出占一行。當M=N=-1時結束程序。SampleInput2DKHF3ADCFJKIHE-1-1SampleOutput23提示：參考迷宮問題，實現(xiàn)時關鍵要解決好各塊的表示問題。求圖像的周長(ZOJ1047)給一個用.和X表示的圖形，圖形在上、下、左、右、左上、左下、右上、右下8個方向都被看作是連通的，并且圖像中間不會出現(xiàn)空洞，求這個圖形的邊長。輸入：首先給出m、n、x、y四個正整數(shù)，下面給出mXn的圖形，x、y表示點擊的位置，全0表示結束。輸出：點擊的圖形的周長。SampleInput

2222XXXX6423.XXX.XXX.XXX...X..X.X...0000Sampleoutput818提示：參考迷宮問題，區(qū)別在于它是向8個方向填。10.骨牌矩陣多米諾骨牌是一個小正方形方塊，每個骨牌都標有一個數(shù)字(0?6)，現(xiàn)在有28組骨牌，每組兩個，各組編號為1~28，每組編號對應的兩個骨牌數(shù)值如下：00010203040506111213141516222324252633343536444546555666現(xiàn)將這28組骨牌排成一個7X8矩陣，此時只能看到每個骨牌上的數(shù)字(0?6)，而不能知道每組的組號(如左下圖所示)。請編程序將每組骨牌分辨出來(如右下圖所示)。{7X8骨牌矩陣骨牌組編號矩陣{2828147171711111010147222123841625251321238416151513991212222255262627242433181192766202018119voidsearch(intn)查找下一個還沒放置骨牌的位置(x,y);若沒有，則表示已經(jīng)找到一個解，輸出并且返回；嘗試放置骨牌；兩次嘗試都失敗，進行回溯；}嘗試放置骨牌把在(x,y)處的骨牌作為當前骨牌組的一個骨牌；把(x+1,y)處的骨牌作為當前骨牌組的另一個骨牌；判斷當前骨牌組是夠未被使用，如果未被使用則遞歸放置下一個骨牌組;把(x,y+1)處的骨牌作為當前骨牌組的另一個骨牌；判斷當前骨牌組是否未被使用，如果未被使用則遞歸放置下一個骨牌組；11.字母轉換（ZOJ1003）通過棧交換字母順序。給定兩個字符串，要求所有的進棧和出棧序列（i表示進棧，o表示出棧），使得字符串2在求得的進出棧序列的操作下，變成字符串1。輸出結果需滿足字典序。例如TROT到TORT:[iiiiooooioiiooio]SampleInputmadamadammbahamabahamalongshortericriceSampleOutput[iiiioooiooiiiiooooioiioioioiooi][ioioiooioioiiiooiioooioiiioooioioioioioiiioooi][][oioioioioioiioioioo]12.踩氣球（ZOJ1004）六一兒童節(jié)，小朋友們做踩氣球游戲，氣球的編號是1?100，兩位小朋友各踩了一些氣球，要求他們報出自己所踩氣球的編號的乘積。現(xiàn)在需要你編一個程序來判斷他們的勝負，判斷的規(guī)則是這樣的：如果兩人都說了真話，數(shù)字大的人贏；如果兩人都說了假話，數(shù)字大的人贏；如果報小數(shù)字的人說的是真話而報大數(shù)字的人說謊，則報小數(shù)字的人贏（注意：只要所報的小數(shù)字是有可能的，即認為此人說了真話）。輸入為兩個數(shù)字，00表示結束；輸出為獲勝的數(shù)字。SampleInput36624934300SampleOutput6249實驗三：搜索算法實驗目的：熟練掌握搜索算法實驗內(nèi)容：廣度優(yōu)先搜索搜索算法的一般模式：voidsearch（）{closed表初始化為空；open表初始化為空；起點加入到open表；while（open表非空）{取open表中的一個結點u;從open表中刪除u;u進入closed表；for（對擴展結點u得到的每個新結點vi）{if（vi是目標結點）輸出結果并返回；ifvi的狀態(tài)與closed表和open表中的結點的狀態(tài)都不相同vi進入open表；}}}搜索算法關鍵要解決好狀態(tài)判重的問題，這樣可省略closed表，一般模式可改為:voidsearch（）{open表初始化為空；起點加入到open表；while（open表非空）{取open表中的一個結點u;從open表中刪除u;for（對擴展結點u得到的每個新結點vi）{if（vi是目標結點）輸出結果并返回；If（notused（vi））vi進入open表；}

Floodfill給一個20X20的迷宮和一個起點坐標，用廣度優(yōu)先搜索填充所有的可到達的格子。提示：參考第2題。電子老鼠闖迷宮#include<stdio.h>voidFloodfill給一個20X20的迷宮和一個起點坐標，用廣度優(yōu)先搜索填充所有的可到達的格子。提示：參考第2題。電子老鼠闖迷宮#include<stdio.h>voidreaddata();voidinit();intsearch();intemptyopen();inttakeoutofopen();〃從棧中取出一個元素，并把該元素從棧中刪除//起點和終點intcanmoveto(int,int,int*,int*,int);〃判能否移動到該方向，并帶回坐標(r,c)intisaim(introw,intcol);//判斷該點是否是目標intused(int,int);//判斷該點是否已經(jīng)走過voidaddtoopen(int,int);//把該點加入到open表inta[12][12];//a存放迷宮，0表示空格，-2//起點和終點//廣搜時，未找到目標以前到達的空格，填上到達該點的最小步數(shù)intn;//n為迷宮邊長，注：若大于12,必須修改一些參數(shù)，如a的大小intopen[20],head,tail,openlen=20;//open表ints,t;intmain(){intnumber;readdata();init();number=search();〃讀取數(shù)據(jù)//初始化//廣搜并返回最小步數(shù)〃讀取數(shù)據(jù)//初始化//廣搜并返回最小步數(shù)〃打印結果intu,row,col,r,c,i,num;〃當棧非空〃從棧中取出一個元素，并把該元素從棧中刪除〃當棧非空〃從棧中取出一個元素，并把該元素從棧中刪除〃計算該點的坐標//取得該點的步數(shù){u=takeoutofopen();row=u/n;col=u%n;num=a[row][col];for(i=0;i<4;i++){if(canmoveto(row,col,&r,&c,i))//判能否移動到該方向，并帶回坐標(r,c){//如果是目標結點//返回最小步數(shù)〃如果(r,c)還未到達過〃記錄該點的最小步數(shù)//把該點加入到//如果是目標結點//返回最小步數(shù)〃如果(r,c)還未到達過〃記錄該點的最小步數(shù)//把該點加入到open表}}intemptyopen(){if(head==tail)return(1);elsereturn(0);}inttakeoutofopen(){intu;if(head==tail){printf("errer:stackisempty");return(-1);}u=open[head++];head=head%openlen;return(u);}intcanmoveto(introw,intcol,int*p,int*q,intdirection)intr,c;r=row;c=col;switch(direction){case0:c--;break;r=row;c=col;switch(direction){case0:c--;break;case1:r++;break;case2:c++;break;case3:r--;}*p=r;*q=c;if(r<0||r>=n||c<0||c>=n)return(0);if(a[r][c]==0)return(1);return(0);}intisaim(introw,intcol){if(row*n+col==t)return(1);elsereturn(0);//左〃下//右〃上〃如果越界返回0//如果是空格返回1//其余情況返回0}intused(introw,intcol){//0表示空格if(a[row][col]==0)return(0);//0表示空格}voidaddtoopen(introw,intcol){intu;u=row*n+col;open[tail++]=u;tail=tail%openlen;}voidreaddata()inti,j,row,col;charstr[20];scanf("%d”,&n);scanf("%d%d”,&row,&col);//起點坐標s=row*n+col;scanf("%d%d”,&row,&col);〃終點坐標t=row*n+col;gets(str);for(i=0;i<n;i++){gets(str);for(j=0;j<n;j++)if(str[j]='.')a[i][j]=0;//0表示空格elsea[i][j]=-2;//—2表示墻}}voidinit(){head=0;tail=1;open[0]=s;}測試數(shù)據(jù)如下：1210718XXXXXXXXXXXXX......X.XXXTOC\o"1-5"\h\zX.XX..XX.XXXXXXXXXXX...X.XXX.XXX...XXXXXXXXXXXXXX..XXXXXXXXXXXXXXX注：測試數(shù)據(jù)可在運行時粘貼上去(點擊窗口最左上角按鈕，在菜單中選則“編輯”/“粘貼”即可)。想一想：此程序都存在哪些問題，如果openlen太小程序會不會出錯，加入代碼使程序能自動報出此類錯誤。3.跳馬給一個200X200的棋盤，問國際象棋的馬從給定的起點到給定的終點最少需要幾步。SampleInput0011Sampleoutput4狀態(tài)：馬所在的行、列。

程序如下：#include<stdio.h>voidreaddata();voidinit();intsearch();intemptyopen();longtakeoutofopen();intcanmoveto(int,int,int*,int*,int);intisaim(introw,intcol);intused(int,int);voidaddtoopen(int,int);inta[200][200],n=200;〃讀入數(shù)據(jù)〃初始化〃廣度優(yōu)先搜索〃判棧是否為空：空：1；非空：〃讀入數(shù)據(jù)〃初始化〃廣度優(yōu)先搜索〃判棧是否為空：空：1；非空：0?！◤臈Ｖ腥〕鲆粋€元素，并把該元素從棧中刪除〃判能否移動到該方向，并帶回坐標(r,c)〃判斷該點是否是目標〃判斷該點是否已經(jīng)走過〃把該點加入到open表//a存放棋盤，n為迷宮邊長longs,t;〃起點和終點intsearch(){longu;introw,col,r,c,i,num;//當棧非空while(!emptyopen())u=takeoutofopen();row=u/n;//當棧非空u=takeoutofopen();row=u/n;col=u%n;num=a[row][col];for(i=0;i<8;i++)〃計算該點所在的行〃計算該點所在的列〃取得該點的步數(shù)//判能否移動到該方向，并帶回坐標(//判能否移動到該方向，并帶回坐標(r,c)if(isaim(r,c))return(num+1);if(!used(r,c))

//如果是目標結點//返回最小步數(shù)//如果(#)還未到達過a[r][c]=num+1;addtoopen(r,c);//記錄該點的最小步數(shù)〃把該點加入到open表〃為了讓search()顯示在一頁內(nèi)和main〃為了讓search()顯示在一頁內(nèi)和main函數(shù)換了以下〃一般的算法程序main函數(shù)寫在最上面讀起來更方便〃讀取數(shù)據(jù)}return-1;}intmain(){intnumber;readdata();init();〃初始化number=search();//廣搜并返回最小步數(shù)printf("%d”,number);〃打印結果}intemptyopen(){if(head==tail)return(1);elsereturn(0);}longtakeoutofopen(){longu;if(head==tail){printf("errer:stackisempty");return(-1);}u=open[head++];head=head%openlen;return(u);}intused(introw,intcol){if(a[row][col]==0)return(0);elsereturn(1);}voidaddtoopen(introw,intcol){intu;if((head-tail)%openlen==1)printf("opentableoverflow");u=row;u=u*n+col;open[tail++]=u;tail=tail%openlen;}voidreaddata(){longrow,col;scanf("%ld%ld",&row,&col);//起點坐標s=row*n+col;scanf("%ld%ld”,&row,&col);〃終點坐標t=row*n+col;}voidinit(){head=0;tail=1;open[0]=s;}intisaim(introw,intcol){if(row*n+col==t)return(1);elsereturn(0);}思考：參考第4題，改為用結構體表示狀態(tài)寫此程序。4.獨輪車獨輪車的輪子上有5種顏色，每走一格顏色變化一次，獨輪車只能往前推，也可以在原地旋轉，每走=一格，需要一個單位的時間，每轉90度需要一個單位的時間，轉180度需要兩個單位的時間?，F(xiàn)給定一個20X20的迷宮、一個起點、一個終點和到達終點的顏色，問獨輪車最少需要多少時間到達。狀態(tài)：獨輪車所在的行、列、當前顏色、方向。另外為了方便在結點中加上到達該點的最小步數(shù)。程序如下：#include<stdio.h>structcolornode{introw;intcol;intcolor;intdirection;intnum;//該狀態(tài)的行//列//顏色//方向//最小步數(shù)};intsearch();voidreaddata();voidinit();〃廣搜返回目標結點的最小步數(shù)〃讀入數(shù)據(jù)//初始化structcolornodemoveahead(structcolornodeu);//返回u向前走一格得到的結點intused(structcolornodev);//判斷該結點是否是到達過的結點voidaddtoopen(structcolornodev);//加入至|open表intislegal(structcolornodev);〃如果該結點是合法的結點(未越界且是空格)

intisaim(structcolornodev);〃判斷該結點是否是目標結點structcolornodetakeoutofopen();〃從open表中取出一個結點并把該結點從open表中刪除structcolornodeturntoleft(structcolornodeu);//u向左轉得到新結點vstructcolornodeturntoright(structcolornodeu);//u向左轉得到新結點vstructcolornodes,t;//s:起始結點；t目標結點structcolornodeopen[200];//open表inthead,tail,openlen=200;//open表相關數(shù)據(jù)//a數(shù)組表示迷宮；n為迷宮邊長//b數(shù)組表示搜索時的所有狀態(tài)（0：未訪問；1：已訪問）intdirect[4]//a數(shù)組表示迷宮；n為迷宮邊長//b數(shù)組表示搜索時的所有狀態(tài)（0：未訪問；1：已訪問）intnumber;readdata();init();number=search();printf("%d\n",number);}//廣搜返回目標結點的最小步數(shù)intsearch()//廣搜返回目標結點的最小步數(shù)structcolornodeu,v;while(head!=tail)u=takeoutofopen();v=moveahead(u);if(islegal(v)){//u向前走一格得到新結點v//如果該結點是合法的結點（u=takeoutofopen();v=moveahead(u);if(islegal(v))//如果是未到達過的結點//如果是未到達過的結點//加入到open表return(v.num);if(!used(v))addtoopen(v);//判是否是目標結點}v=turntoleft(u);if(!used(v))addtoopen(v);v=turntoright(u);if(!used(v))addtoopen(v);//u向左轉得到新結點v//u向右轉得到新結點v}}intused(structcolornodev){if(b[v.row][v.col][v.color][v.direction]==0)return(0);〃判斷該結點是否是到達過的結點elsereturn(1);}voidaddtoopen(structcolornodev)//加入到^open表{open[tail++]=v;tail=tail%openlen;b[v.row][v.col][v.color][v.direction]=1;}structcolornodetakeoutofopen(){structcolornodev;v=open[head++];head=head%openlen;return(v);}voidinit(){inti,j,k,l;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<5;k++)for(l=0;l<4;l++)b[i][j][k][l]=0;〃從open表中取出一個結點并把該結點從open表中刪除〃初始化〃所有狀態(tài)初始化head=0;tail=0;addtoopen(s);}voidreaddata(){charstr[50];〃把起始點加入到open表〃讀入數(shù)據(jù)inti,j;for(i=0;i<n;i++){gets(str);for(j=0;j<n;j++)

if(str[j]=='.')

a[i][j]=0;elsea[i][j]=1;〃讀入數(shù)據(jù)'.'表示空格〃存儲時0：表示空格//1：表示墻}scanf("%d%d%d%d”,&s.row,&s.col,&s.color,&s.direction);〃讀入起始結點信息scanf("%d%d%d”,&t.row,&t.col,&t.color);〃讀入目標結點信息}intisaim(structcolornodev)〃判斷該結點是否是目標結點if(v.row==t.row&&v.col==t.col&&v.color==t.color)return1;elsereturn0;}intislegal(structcolornodev)〃如果該結點是合法的結點(未越界且是空格){if(v.row<0||v.row>=n||v.col<0||v.col>=n)//若越界return0;if(a[v.row][v.col]==0)//0：表示空格return1;return0;}structcolornodemoveahead(structcolornodeu)//返回u向前走一格得到的結點{structcolornodev;v.row=u.row+direct[u.direction][0];v.col=u.col+direct[u.direction][1];v.color=(u.color+1)%5;v.direction=u.direction;v.num=u.num+1;return(v);}structcolornodeturntoleft(structcolornodeu)//u向左轉得到新結點v{structcolornodev;v=u;v.direction=(v.direction+1)%4;v.num=v.num+1;return(v);}structcolornodeturntoright(structcolornodeu)//u向左轉得到新結點v{structcolornodev;v=u;v.direction=(v.direction+3)%4;v.num=v.num+1;return(v);}測試數(shù)據(jù)：XXXXXXXXXXXXXXXXXXXX.....XXXX......X.XXXXX.XXX

XX.XX.....X.X.....XX.X.....X..XTOC\o"1-5"\h\zXX..X...X.XX...XXXXXXXXXXXXXX..XXXX.XXX.XX..XXXXXXXXXXXXXXX.XXX..X...X.XXXXX.XXXXXXXXXXX1111481皇宮小偷有一個小偷要到皇宮里偷取寶物，經(jīng)過仔細的偵察，他發(fā)現(xiàn)皇宮實際上是一個20X20的迷宮，并且有一名衛(wèi)兵巡邏，衛(wèi)兵巡邏的路線是固定的，每單位時間移動一格，每4個單位時間循環(huán)一次。小偷每單位時間移動一格或在原地不動。任何時刻，小偷和衛(wèi)兵在同一格，或衛(wèi)兵能看到小偷，小偷將會被衛(wèi)兵殺死?，F(xiàn)在小偷已經(jīng)得到了皇宮的地圖，衛(wèi)兵巡邏的起點，衛(wèi)兵連續(xù)四次移動的方向和寶物的位置，請你設計一個程序判斷小偷能否偷得寶物。提示：參考第3題、第4題分酒問題有一酒瓶裝有8斤酒，沒有量器，只有分別裝5斤和3斤的空酒瓶。設計一程序將8斤酒分成兩個4斤，并以最少的步驟給出答案。7.*找倍數(shù)對于每個輸入的數(shù)字（如：2），則要求給出一個由1，0構成的十進制整數(shù)，且該整數(shù)為輸入數(shù)字的某個倍數(shù)（如2對應的10，6的倍數(shù)100）。8.*8數(shù)碼難題并演示移動過程。由左圖變到右圖最少需要幾步，

實驗四:動態(tài)規(guī)劃實驗目的：理解動態(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結構性質和子問題的重疊性質。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的一般方法，對較簡單的問題能正確分析，設計出動態(tài)規(guī)劃算法，并能快速編程實現(xiàn)。并演示移動過程。實驗四:動態(tài)規(guī)劃實驗內(nèi)容：編程實現(xiàn)講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線問題等。本實驗中的問題，設計出算法并編程實現(xiàn)。習題最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=<x1,x2,.”xm>，則另一序列Z=<4z2,.”zk>是X的子序列是指存在一個嚴格遞增的下標序列<4”2，…，ik>，使得對于所有戶1,2,...,k有解答如下：最長公共子序列的結構若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。易證最長公共子序列問題也有最優(yōu)子結構性質設序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>的一個最長公共子序列Z=<z1,z2,...,zk>，則：若xm=yn，則zk=xm=yn且Zk1是Xm1和Yn1的最長公共子序列；若乂腿；且zk氣，則Z是Xm-1和Y的最長公共子序列；若x：手y；且zk^y：，則Z是X和Yn-1的最長公共子序列。其中Xm-1=<x1,x2,...,xm-1>，Yn-1=<y1,y2,...,yn-1>，Zk-1=<z1,z2,...,zk-1>。最長公共子序列問題具有最優(yōu)子結構性質。子問題的遞歸結構由最長公共子序列問題的最優(yōu)子結構性質可知，要找出X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm手yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。我們來建立子問題的最優(yōu)值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=<x1,x2,...,xi>，Yj=<y1,y2,...,yj>。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。建立遞歸關系如下：計算最優(yōu)值由于在所考慮的子問題空間中，總共只有O(m*n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>作為輸入。輸出兩個數(shù)組c[0..m,0..n]和b[1..m,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m,n]中。程序如下：#include<stdio.h>#include<string.h>intlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen;while(1){scanf("%s%s",x,y);if(x[0]=='0')〃約定第一個字符串以‘0’開始表示結束break;len=lcs_length(x,y);printf("%d\n",len);}}intlcs_length(charx[],chary[]){intm,n,i,j,l[100][100];m=strlen(x);n=strlen(y);for(i=0;i<m+1;i++)l[i][0]=0;for(j=0;j<n+1;j++)l[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(x[i-1]==y[j-1])//ij從1開始，但字符串是從0開始l[i][j]=l[i-1][j-1]+1;elseif(l[i][j-1]>l[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}由于每個數(shù)組單元的計算耗費0(1)時間，算法lcs_length耗時0(mn)。思考：空間能節(jié)約嗎？計算矩陣連乘積在科學計算中經(jīng)常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個pxq的矩陣，B是一個qxr的矩陣，則其乘積C=AB是一個pxr的矩陣。由該公式知計算C=AB總共需要pqr次的數(shù)乘。其標準計算公式為：現(xiàn)在的問題是，給定n個矩陣{A1,A2,...,An}。其中Ai與Ai+1是可乘的，i=1,2,...,n-1。

要求計算出這n個矩陣的連乘積A1A2...An。要求計算出這n個矩陣的連乘積A1A2...An。f0遞歸公式：m[i][j]=<min{m[i][k]+m[k+1][j]+p1p^p}ivj^i<kvji-J程序如下：intp[101],i,j,k,r,t,n;intm[101][101];ints[101][101];scanf("%d”,&n);for(i=0;i<=n;i++)scanf("%d”,&p[i]);intp[101],i,j,k,r,t,n;intm[101][101];ints[101][101];scanf("%d”,&n);for(i=0;i<=n;i++)scanf("%d”,&p[i]);for(i=1;i<=n;i++)m[i][i]=0;for(r=1;r<n;r++)for(i=1;i<n;i++){j=i+r;〃為了跟講解時保持一致數(shù)組從1開始〃記錄從第i到第j個矩陣連乘的斷開位置〃讀入p[i]的值（注意：p[0]到p[n]共n+1項）〃初始化m[i][i]=0//r為i、j相差的值//i為行//j為列m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];〃給m[i][j]賦初值s[i][j]=i;for(k=i+1;k<j;k++){t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}3.}3.多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內(nèi)的所有點構成了多邊形的內(nèi)部；多邊形本身構成多邊形的邊界；而平面上其余的點構成了多邊形的外部。當一個簡單多邊形及其內(nèi)部構成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內(nèi)部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內(nèi)部或邊界上。通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=<v0,v1,...,vn-1>表示具有n條邊v0v1，v1v2，...,vn-1vn的一個凸多邊形，其中，約定v0=vn。若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形<^,vi+1,...,vj>和<vj,vj+1,...,vi>。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。凸多邊形最優(yōu)三角剖分的問題是：給定一個凸多邊形P=<v0,v1,...,vn-1>以及定義在由多邊形的邊和弦組成的三角形上的權函數(shù)3。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小?？梢远x三角形上各種各樣的權函數(shù)W。例如：定義3(^v.v.v)=lv.v.l+lv.v」+lvv」，。ijk^ijikkj其中，1匕"是點vi到v.的歐氏距離。相應于此權函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。(注意：解決此問題的算法必須適用于任意的權函麴防衛(wèi)導彈一種新型的防衛(wèi)導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發(fā)射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現(xiàn)對這種新型防衛(wèi)導彈進行測試，在每一次測試中，發(fā)射一系列的測試導彈(這些導彈發(fā)射的間隔時間固定，飛行速度相同)，該防衛(wèi)導彈所能獲得的信息包括各進攻導彈的高度，以及它們發(fā)射次序?，F(xiàn)要求編一程序，求在每次測試中，該防衛(wèi)導彈最多能截擊的進攻導彈數(shù)量，一個導彈能被截擊應滿足下列兩個條件之一：它是該次測試中第一個被防衛(wèi)導彈截擊的導彈；它是在上一次被截擊導彈的發(fā)射后發(fā)射，且高度不大于上一次被截擊導彈的高度的導彈。輸入數(shù)據(jù)：第一行是一個整數(shù)n，以后的n各有一個整數(shù)表示導彈的高度。輸出數(shù)據(jù)：截擊導彈的最大數(shù)目。分析：定義l[i]為選擇截擊第i個導彈，從這個導彈開始最多能截擊的導彈數(shù)目。由于選擇了第i枚導彈，所以下一個要截擊的導彈j的高度要小于等于它的高度，所以l[i]應該等于從i+1到n的每一個j，滿足h[j]<=h[i]的j中l(wèi)[j]的最大值。程序如下：#include<stdio.h>intmain(){inti,j,n,max,h[100],l[100];scanf("%d”,&n);for(i=0;i<n;i++)scanf("%d”,&h[i]);l[n-1]=1;for(i=n-2;i>=0;i--){max=0;for(j=i+1;j<n;j++)if(h[i]>h[j]&&max<l[j])max=l[j];l[i]=max+1;}printf("%d",l[0]);}石子合并在一個圓形操場的四周擺放著n堆石子(n<=100),現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選取相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。編一程序，由文件讀入堆棧數(shù)n及每堆棧的石子數(shù)(<=20)。選擇一種合并石子的方案,使得做n-1次合并，得分的總和最??；輸入數(shù)據(jù)：第一行為石子堆數(shù)n；第二行為每堆的石子數(shù)，每兩個數(shù)之間用一個空格分隔。輸出數(shù)據(jù)：從第一至第n行為得分最小的合并方案。第n+1行是空行.從第n+2行到第2n+1行是得分最大合并方案。每種合并方案用n行表示，其中第i行(1v=iv=n)表示第i次合并前各堆的石子數(shù)(依順時針次序輸出，哪一堆先輸出均可)。要求將待合并的兩堆石子數(shù)以相應的負數(shù)表示。SampleInput4594SampleOutput-459-4-8-59-13-9224-5-94-14-4-4-1822最小代價子母樹設有一排數(shù)，共n個，例如：2214713261511。任意2個相鄰的數(shù)可以進行歸并，歸并的代價為該兩個數(shù)的和，經(jīng)過不斷的歸并，最后歸為一堆，而全部歸并代價的和稱為總代價，給出一種歸并算法，使總代價為最小。輸入、輸出數(shù)據(jù)格式與“石子合并”相同。SampleInput4125164SampleOutput-12-516417-16-4—17-2037商店購物某商店中每種商品都有一個價格。例如，一朵花的價格是2ICU(ICU是信息學競賽的貨幣的單位)；一個花瓶的價格是5ICU。為了吸引更多的顧客，商店提供了特殊優(yōu)惠價。特殊優(yōu)惠商品是把一種或幾種商品分成一組。并降價銷售。例如：3朵花的價格不是6而是ICU；2個花瓶加1朵花是10ICU不是12ICU。編一個程序，計算某個顧客所購商品應付的費用。要充分利用優(yōu)惠價以使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數(shù)量，即使增加某些商品會使付款總數(shù)減小也不允許你作出任何變更。假定各種商品價格用優(yōu)惠價如上所述，并且某顧客購買物品為：3朵花和2個花瓶。那么顧客應付款為14ICU因為：1朵花加2個花瓶優(yōu)惠價：10ICU2朵花正常價：4ICU輸入數(shù)據(jù)：第一個文件INPUT.TXT描述顧客所購物品（放在購物筐中）；第二個文件描述商店提供的優(yōu)惠商品及價格（文件名為OFFER.TXT）。兩個文件中都只用整數(shù)。第一個文件INPUT.TXT的格式為:第一行是一個數(shù)字B（0WBW5），表示所購商品種類數(shù)。下面共B行，每行中含3個數(shù)C，K，P。C代表商品的編碼（每種商品有一個唯一的編碼），1WCW999。K代表該種商品購買總數(shù)，1WKW5。P是該種商品的正常單價（每件商品的價格），1WPW999。請注意，購物筐中最多可放5*5=25件商品。第二個文件OFFER.TXT的格式為:第一行是一個數(shù)字S（0WSW99），表示共有S種優(yōu)惠。下面共S行，每一行描述一種優(yōu)惠商品的組合中商品的種類。下面接著是幾個數(shù)字對（C，K），其中C代表商品編碼，1WCW999。K代表該種商品在此組合中的數(shù)量，1WKW5。本行最后一個數(shù)字P（1WPW9999）代表此商品組合的優(yōu)惠價。當然，優(yōu)惠價要低于該組合中商品正常價之總和。輸出數(shù)據(jù)：在輸出文件OUTPUT.TXT中寫一個數(shù)字（占一行），該數(shù)字表示顧客所購商品（輸入文件指明所購商品）應付的最低貨款。旅游預算一個旅行社需要估算乘汽車從某城市到另一城市的最小費用，沿路有若干加油站，每個加油站收費不一定相同。旅游預算有如下規(guī)則：若油箱的油過半，不停車加油，除非油箱中的油不可支持到下一站；每次加油時都加滿；在一個加油站加油時，司機要花費2元買東西吃;司機不必為其他意外情況而準備額外的油；汽車開出時在起點加滿油箱；計算精確到分（1元=100分）。編寫程序估計實際行駛在某路線所需的最小費用。輸入數(shù)據(jù)：從當前目錄下的文本文件“route.dat”讀入數(shù)據(jù)。按以下格式輸入若干旅行路線的情況：第一行為起點到終點的距離（實數(shù)）第二行為三個實數(shù)，后跟一個整數(shù)，每兩個數(shù)據(jù)間用一個空格隔開。其中第一個數(shù)為汽車油箱的容量（升），第二個數(shù)是每升汽油行駛的公里數(shù)，第三個數(shù)是在起點加滿油箱的費用，第四個數(shù)是加油站的數(shù)量。（〈=50）。接下去的每行包括兩個實數(shù)，每個數(shù)據(jù)之間用一個空格分隔，其中第一個數(shù)是該加油站離起點的距離，第二個數(shù)是該加油站每升汽油的價格（元/升）。加油站按它們與起點的距離升序排列。所有的輸入都有一定有解。輸出數(shù)據(jù)：答案輸出到當前目錄下的文本文件“route.out”中。該文件包括兩行。第一行為一個實數(shù)和一個整數(shù)，實數(shù)為旅行的最小費用，以元為單位，精確到分，整數(shù)表示途中加油的站的N。第二行是N個整數(shù)，表示N個加油的站的編號，按升序排列。數(shù)據(jù)間用一個空格分隔，此外沒有多余的空格。SampleInput38.09115.722.120.87321.259297.91.129345.20.999SampleOutput38.0912皇宮看守太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)?；蕦m以午門為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費用不同。可是陸小鳳手上的經(jīng)費不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。請你編程計算幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費的經(jīng)費最少。輸入數(shù)據(jù)：輸入數(shù)據(jù)由文件名為intput.txt的文本文件提供。輸入文件中數(shù)據(jù)表示一棵樹，描述如下：第1行n，表示樹中結點的數(shù)目。第2行至第n+1行，每行描述每個宮殿結點信息，依次為：該宮殿結點標號i(0<i<=n)，在該宮殿安置侍衛(wèi)所需的經(jīng)費k，該邊的兒子數(shù)m，接下來m個數(shù)，分別是這個節(jié)點的m個兒子的標號r1，r2，...，rm。對于一個n(0<n<=1500)個結點的樹，結點標號在1到n之間，且標號不重復。輸出數(shù)據(jù)：輸出到output.txt文件中。輸出文件僅包含一個數(shù)，為所求的最少的經(jīng)費。如右圖的輸入數(shù)據(jù)示例：TOC\o"1-5"\h\zSampleInput.30323421/偵162563450\40lii、七11050SampleOutput25游戲室問題有一個游戲室里有多個游戲室，并且這每個游戲室里還有多個游戲室，每個游戲室里面還有游戲室，依此類推。進入每個游戲室都可得到一定的快樂，每個游戲室的門票價格都大于等于0，都有一個快樂值，并且只有進入了一個游戲室，才可以進入它內(nèi)部的游戲室，小明現(xiàn)在有n元錢，問最大能得到多少的快樂。*基因問題已知兩個基因序列如s：AGTAGT；t：ATTAGo現(xiàn)要你給序列中增加一些空格后，首先使得兩個序列的長度相等，其次兩個串對應符號匹配得到的值最大?；蛑挥兴姆N分別用A、G、C、T表示，匹配中不允許兩個空格相對應，任意兩符號的匹配值由下表給出：AGCT^A5-2-1-2-4G-25-4-3-2C-1-45-5-1T-2-3-55-2^-4-2-1-2提示：定義問題l[i][j]為取第一個序列的前i項，和第二個序列的前j項，這兩個序列加空格匹配的最大值。它的最優(yōu)值與三個子問題有關，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。建立遞歸公式如下：其中m[0][t[j]表示表中空格和t[j]匹配的對應值。思考：本問題的初始化。*田忌賽馬田忌與齊王賽馬，雙方各有n匹馬參賽(n<=100),每場比賽賭注為1兩黃金，現(xiàn)已知齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場，現(xiàn)要你寫一個程序幫助田忌計算他最好的結果是贏多少兩黃金(輸用負數(shù)表示)。分析：先排序，齊王的馬的速度放在數(shù)組a中，田忌的馬的速度放在數(shù)組b中。本問題應用的算法是動態(tài)規(guī)劃和貪心算法相結合解決的。從兩人的最弱的馬入手：若田忌的馬快，就讓這兩匹馬比賽；若田忌的馬慢，干脆就讓他對付齊王最快的馬；若兩匹馬的速度相等，這時有兩種選擇方案，或者它倆比賽，或者對付齊王最快的馬。定義子問題：l(i，j)為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌所獲得的最大收益。^l(i,j-1)當a[i+j-1]<b[j-1]時貝上1(i,j)=<max{l(i+1,j-1),1(i,j-1)}當a[i+j-1]=b[j-1]時^1(i+1,j-1)當a[i+j-1]>b[j-1]時程序具體實現(xiàn)時，為了適合c數(shù)據(jù)從0開始，稍加變動，定義子問題：l(i，j)為齊王的從第i匹馬開始到第i+j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大收益。初始化時：l[i][0]表示齊王的第i匹馬與田忌最快的馬比賽的結果。程序如下：#include<stdio.h>voidreaddata();voidinit();intn,a[100],b[100],l[100][100];intmain(){inti,j;readdata();init();for(i=n-2;i>=0;i--)for(j=1;j<n-i;j++)if(a[i+j]<b[j])l[i][j]=l[i][j-1]+1;elseif(a[i+j]>b[j])l[i][j]=l[i+1][j-1]-1;elseif(l[i+1][j-1]-1>l[i][j-1])l[i][j]=l[i+1][j-1]-1;elsel[i][j]=l[i][j-1];printf("%d”,l[0][n-1]);}voidreaddata()inti;scanf("%d”,&n);for(i=0;i<n;i++)scanf("%d”,&a[i]);for(i=0;i<n;i++)scanf("%d”,&b[i]);}voidinit(){inti;//qsort(a,n);〃略for(i=0;i<n;i++){if(a[i]<b[0])l[i][0]=1;elseif(a[i]==b[0])l[i][0]=0;elsel[i][0]=-1;}}實驗五：貪心算法和隨機算法背包問題有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。物品ABCDEFG重量35306050401025價值10403050354030照亮的山景在一片山的上空，高度為T處有N個處于不同位置的燈泡，如圖。如果山的邊界上某一點于某燈i的連線不經(jīng)過山的其它點，我們稱燈i可以照亮該點。開盡量少的燈，使得整個山景都被照亮。山被表示成有m個轉折點的折線。提示：照亮整個山景相當于照亮每一個轉折點。搬桌子問題某教學大樓一層有n個教室，從左到右依次編號為1、2、…、n?，F(xiàn)在要把一些課桌從某些教室搬到另外一些教室，每張桌子都是從編號較小的教室搬到編號較大的教室，每一趟，都是從左到右走，搬完一張課桌后，可以繼續(xù)從當前位置或往右走搬另一張桌子。輸入數(shù)據(jù)：先輸入n、m，然后緊接著m行輸入這m張要搬課桌的起始教室和目標教室。輸出數(shù)據(jù)：最少需要跑幾趟。SampleInput10513TOC\o"1-5"\h\z96108SampleOutput3分析：貪心算法，把課桌按起點從小到大排序，每次都是搬離當前位置最近的課桌。程序如下：#include<stdio.h>intmain(){struct{intstart;intend;}a[100];inti,j;intn,m,min,num,temp,used[100]={0};scanf("%d%d”,&m,&n);for(i=0;i<n;i++)scanf("%d%d”,&a[