算法設計與分析實驗報告

1、算法設計與分析實驗報告指導老師：沙莎學院：信息科學與工程學院班級：計科0508姓名：戚婕學號：10完成日期：2007年12月 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 實驗一分治法2實驗要求2 HYPERLINK l bookmark1 o Current Document 實驗內(nèi)容 2核心算法2 HYPERLINK l bookmark25 o Current Document 程序代碼4實驗結(jié)果 8 HYPERLINK l bookmark34 o Current Document 實驗二貪心法10實驗要求10 HYPER

2、LINK l bookmark47 o Current Document 實驗內(nèi)容 10核心算法10 HYPERLINK l bookmark56 o Current Document 程序代碼12實驗結(jié)果 18 HYPERLINK l bookmark66 o Current Document 實驗三動態(tài)規(guī)劃20實驗要求20實驗內(nèi)容20核心算法20 HYPERLINK l bookmark95 o Current Document 程序代碼21實驗結(jié)果 24 HYPERLINK l bookmark98 o Current Document 實驗四深度優(yōu)先搜索26實驗要求26實驗內(nèi)容26核心

3、算法26程序代碼 27實驗結(jié)果 28 HYPERLINK l bookmark119 o Current Document 實驗五回溯法30實驗要求30實驗內(nèi)容30核心算法30程序代碼31實驗結(jié)果 33實驗一分治法實驗要求了解用分治法求解的問題：當要求解一個輸入規(guī)模為n,且n的取值相當大的問題時， 如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1kWn,而 且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對于這類 問題分治法是十分有效的。掌握分治法的一般控制流程。DanC (p,q)global n， A1:ninteger m,p,q;驗內(nèi)容編程

4、實現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計數(shù)功能，輸出排 序結(jié)果和比較次數(shù)。輸入10組相同的數(shù)據(jù)，驗證排序結(jié)果和完成排序的比較次數(shù)。與復雜性函數(shù)所計算的比較次數(shù)比較。用表格列出比較結(jié)果。給出文字分析。三.程序算法歸并排序算法procedure MERGESORT(low, high)快速排序算法QuickSort(p,q)序代碼1. 歸并排序#include#include#include#include#define M 11typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data;t

5、ypedef rec sqlistM;class guibingpublic:guibing(sqlist b)for(int i=0;iM;i+)ri=bi;void output(sqlist r,int n)for(int i=0;in;i+)coutsetw(4)ri.key;coutendl;void xuanze(sqlist b,int m,int n)int i,j,k;for(i=m;in-1;i+)k=i;for(j=i;jbj.key) k=j;if(k!=i)rec temp=bk;bk=bi;bi=temp;void merge(int l,int m,int h,s

6、qlist r2)xuanze(r,l,m);xuanze(r,m,h);output(r,M);int i,j,k;k=i=l;for(j=m;im&jh;k+)if(ri.key=rj.key)r2k=ri;i+;elser2k=rj;j+;output(r2,M);while(jh)r2k=rj;j+；k+;while(i=m)r2k=ri;i+;k+;output(r2,M);private:sqlist r;void main()coutguibingfa1 運行結(jié)果:n”;sqlist a,b;int i,j=0,k=M/2,n=M;srand(time(0);for(i=0;iM

7、;i+)ai.key=rand()%80;bi.key=0;guibing gx(a);cout排序前數(shù)組:n”;(a,M);cout數(shù)組排序過程演示:n;(j,k,n,b);cout排序后數(shù)組:n”;(b,M);();快速排序#include#include#include#include#define MAXI 10typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data;typedef rec sqlistMAXI;class kuaisupublic:kuaisu(sqlist a,int

8、m):n(m)for(int i=0;in;i+) bi=ai;void quicksort(int s,int t)int i;if(st)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);else return;int part(int s,int t)int i,j;rec p;i=s;j=t;p=bs;while(ij)while(i=j;bi=bj;while(ij&bi.key=i+;bj=bi;bi=p;output();return i;void output()for(int i=0;in;i+)coutsetw(4)bi.key;c

9、outendl;private:sqlist b;int n;void main()cout運行結(jié)果：n”;sqlist a1;int i,n=MAXI,low=0,high=9;srand(time(0);for(i=0;in;i+)a1i.key=rand()%80;kuaisu px(a1,n);cout數(shù)組排序過程演示:n”;(low,high);cout排序后數(shù)組：n；();();五.實驗結(jié)果歸并排序e *F:、算錯賣驗I分治法Debugguibingf a 1 - esegu il)in gf M 運行結(jié)果； 就序前數(shù)組；23 22 71 23數(shù)組排序過總演示二1364214123

10、6321322232371221234163642000000000021300000000021321000000002132122000000021321222300000021321222323000002132122232323aaaa213212223232341aaa213212223232341G3aa213212223232341G3G4a213212223232341G3G471排序后數(shù)組，213212223232341G3G471快速排序g *F八算法賣驗、分治法.Debug：.kuaisufal. exe kii此gud. - cpp運行結(jié)果二險組批序過程演示二39222

11、241637764747556222239416377647475弱222239416377G47475弱22223941弱63G47475?22223941粕63647475?2222394156636474757722223941566364747577腓序后數(shù)組二22223941566364747577實驗二貪心法實驗要求優(yōu)化問題有n個輸入，而它的解就由這n個輸入滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解?？尚薪庖话銇碚f是不唯一的。那些 使目標函數(shù)取極值（極大或極小）的可行解，稱為最優(yōu)解。貪心法求優(yōu)化問題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方

12、法。在每個階段，都作出一個看 上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪心決策的 依據(jù)稱為貪心準則（greedy criterion）。一般方法1）根據(jù)題意，選取一種量度標準。2）按這種量度標準對這n個輸入排序3）依次選擇輸入量加入部分解中。如果當前這個輸入量的加入，不滿足約束條件，則 不把此輸入加到這部分解中。procedure GREEDY（A，n） /*貪心法一般控制流程*/驗內(nèi)容編程實現(xiàn)背包問題貪心算法和最小生成樹prim算法。通過具體算法理解如何通過局 部最優(yōu)實現(xiàn)全局最優(yōu)，并驗證算法的時間復雜性。輸入5個的圖的鄰接矩陣，程序加入統(tǒng)計prim算法訪問圖的節(jié)點數(shù)

13、和邊數(shù)的語句。將統(tǒng)計數(shù)與復雜性函數(shù)所計算的比較次數(shù)比較，用表格列出比較結(jié)果，給出文字分 析。三.程序算法1.背包問題的貪心算法procedure KNAPSACK(P, W, M, X, n)序代碼1. 背包問題貪心算法#include struct goodinfofloat p; goodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;=0;cu=M; cu)=1;cu=cu-goodsi.w;=cu/goodsi.w;laggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout最優(yōu)解為:endl;for(i=

14、1;i=n;i+)cout第i件物品要放:；coutgoodsi.Xendl;void main()cout|運用貪心法解背包問題|endl;cout|endl;int j；int n;float M;goodinfo *goods;lag=i;cout請輸入第igoodsi.w;cout請輸入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;dj;cout;coutendl;MiniSpanTree_PRIM(G, a);void CreateGraph(MGraph &G)int weigh;int i, j = 0, k = 0;char hand, tide;

15、cout;for(i = 0; i ; i+)for(j = 0; j ; j+)j.adj = 88;coutendl;coutinputchar for vexs:;for(i=0; i i;coutendl;coutinput”arc(char,char,weigh):endl;j = 0;k = 0;for(i=0; i ; i+)coutihand;cintide;cinweigh;while (hand != j)j+;while (tide != k)k+;jk.adj = weigh;kj.adj = weigh;j = 0;k = 0;coutendl;void MiniSp

16、anTree_PRIM(MGraph G,VerTexType u)int i, j, k = 0;closedge close;k = LocateVex ( G, u );for ( j = 0; j ; j+ )if (j != k)closej.adjvex = k;closej.lowcost = kj.adj;closej.lowcost = 88;closej.adjvex = 0;closek.lowcost = 0;closek.adjvex = u;for (i = 1; i ; i+)k = minimum(close);coutclosek.adjvex;cout;co

17、utk;coutclosek.lowcostendl;closek.lowcost = 0;for (j=0; j; j+)if kj.adj closej1.lowcost & closej1.lowcost != 0) client = closej1.lowcost;j2 = j1;j1+；return j2;五.實驗結(jié)果背包問題貪心算法* F:算法賣驗、貪心法DetnigKirapmc匕exe運用貪心法解背包問題隋逾入物品的總數(shù)量M 睛幕入背包的最大容量，20請:請:1件物品的重量以4 1神物品的效益湖請:請:2件物品的重量=32神物品的效益名請:請:4件物品的重量泅4律物品的效益二5

18、請請5件物品的重量25律物品的效益次請請0 1 1 0 1 U X bos bos bos bos bos .方一.方一.方一.方一.方-o O 要要要要要11 狹品品品品品10 臂物物物物； 01 2 3 4 5 e e 最WWW皿皿2. Prim算法實驗三動態(tài)規(guī)劃實驗要求理解最優(yōu)子結(jié)構(gòu)的問題。有一類問題的活動過程可以分成若干個階段，而且在任一階段后的行為依賴于該階段 的狀態(tài)，與該階段之前的過程如何達到這種狀態(tài)的方式無關。這類問題的解決是多階段的決 策過程。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題的“最優(yōu)化原理”， 從而創(chuàng)建了最優(yōu)化問題的一種新的算法設計方法

19、一動態(tài)規(guī)劃。對于一個多階段過程問題，是否可以分段實現(xiàn)最優(yōu)決策，依賴于該問題是否有最優(yōu)子 結(jié)構(gòu)性質(zhì)，能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。子問題重疊性質(zhì)：每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。理解分段決策Bellman方程。每一點最優(yōu)都是上一點最優(yōu)加上這段長度。即當前最優(yōu)只與上一步有關。us = 0,u = minu + w .I j詳 j ijus初始值，第j段的最優(yōu)值。一般方法1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2）遞歸

20、地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3）以自底向上的方式計算出最優(yōu)值；4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。步驟1-3是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略， 步驟3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4,步 驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。實驗內(nèi)容編程實現(xiàn)多段圖的最短路徑問題的動態(tài)規(guī)劃算法。圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。要求用文件裝入5個多段圖數(shù)據(jù)，編寫從文件到鄰接表的函數(shù)。驗證算法的時間復雜性。核心算法多段圖算法procedure FGRAPH(E, k, n, P)序代碼多段圖問題#include#include#incl

21、ude#define MAX_VERTEX_NUM 50typedef struct ArcNodeint adjvex; ata = m;G-verticesm.firstArc = NULL;for(m = 1; m adjvex = h;p-value = v;p-nextarc = NULL;while(G-verticesi.data != t) i+; irstArc) irstArc = p; else irstArc; q-nextarc; q = q-nextarc);q-nextarc = p; irstArc;printf(%d”,i);while(p)printf(-%

22、d,%d”,p-adjvex,p-value);irstArc;min = p-value+costp-adjvex; 驗結(jié)果多段圖問題g -FZ算實驗動態(tài)規(guī)切I噸trn叭多段囹?qū)崿F(xiàn).eze艾入圖25 llAlAlAlAlAlA段- la弧尾，權(quán)值）實驗四深度優(yōu)先搜索實驗要求理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的 頂點V,如果邊(v,w)是還未探測的邊，則沿(v,w)繼續(xù)搜索下去。當所有的邊(v,w)都己 被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點V的頂點。這一過程一直進行到回到源點為止。如果 還存在未被發(fā)現(xiàn)的頂點，則選擇其中一個作為源結(jié)點并重復以上

23、過程，整個進程反復進 行直到所有結(jié)點都被發(fā)現(xiàn)為止。理解深度優(yōu)先搜索過程中頂點的三種狀態(tài)：還未到達的頂點，當前路徑上經(jīng)過的頂點，深度優(yōu)先在搜索過程中也為結(jié)點著色以 表示結(jié)點的狀態(tài)。每個頂點開始均為白色，搜索中被發(fā)現(xiàn)時置為灰色，當其鄰接表被完 全檢索之后又被置成黑色。實驗內(nèi)容編程實現(xiàn)深度優(yōu)先搜索算法。修改算法使之可以找出圖的所有樹。修改算法使之可以判斷圖是否為一棵樹。修改算法使之可以判斷圖是否存在一個環(huán)。核心算法procedure DFS(G);for每個頂點uEG docoloruj White;repeatfor每個頂點uEG doif coloru=Whitethen DFS_Visit(G,u);end;procedure DFS_Visit(u);coloruGray;for (u,w)EE do序代碼#include#define MAX 50 驗結(jié)果e八算法賣登、注度優(yōu)先搜耋ID停Im叭判評 em有一 y 其指其指其指其指其捐其指共是an JAJAJAJAJAJAJAJAJAJAJAJA s 請&請請請請請請請請請