算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1、v1.0可編輯可修改算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告指導(dǎo)老師：沙莎學(xué)院：信息科學(xué)與工程學(xué)院班級(jí)：計(jì)科0508姓名：戚婕學(xué)號(hào)：10完成日期：2007年12月目錄實(shí)驗(yàn)一分治法2實(shí)驗(yàn)要求2實(shí)驗(yàn)內(nèi)容2核心算法2程序代碼4實(shí)驗(yàn)結(jié)果8實(shí)驗(yàn)二貪心法10實(shí)驗(yàn)要求10實(shí)驗(yàn)內(nèi)容10核心算法10程序代碼12實(shí)驗(yàn)結(jié)果18實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃20實(shí)驗(yàn)要求20實(shí)驗(yàn)內(nèi)容20核心算法20程序代碼21實(shí)驗(yàn)結(jié)果24實(shí)驗(yàn)四深度優(yōu)先搜索26實(shí)驗(yàn)要求26實(shí)驗(yàn)內(nèi)容26核心算法26程序代碼2711v1.0可編輯可修改實(shí)驗(yàn)結(jié)果28實(shí)驗(yàn)五回溯法30實(shí)驗(yàn)要求30實(shí)驗(yàn)內(nèi)容30核心算法30程序代碼31實(shí)驗(yàn)結(jié)果33實(shí)驗(yàn)一分治法一.實(shí)驗(yàn)要求1 .了解用分治法求解的問(wèn)題

2、：當(dāng)要求解一個(gè)輸入規(guī)模為n,且n的取值相當(dāng)大的問(wèn)題時(shí)，如果問(wèn)題可以分成k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問(wèn)題，其中1<kwn,而且子問(wèn)題與原問(wèn)題性質(zhì)相同，原問(wèn)題的解可由這些子問(wèn)題的解合并得出。那末，對(duì)于這類問(wèn)題分治法是十分有效的。2 .掌握分治法的一般控制流程。DanQp,q)globaln,A1:n;integerm,p,q;驗(yàn)內(nèi)容1 .編程實(shí)現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計(jì)數(shù)功能，輸出排序結(jié)果和比較次數(shù)。2 .輸入10組相同的數(shù)據(jù)，驗(yàn)證排序結(jié)果和完成排序的比較次數(shù)。3 .與復(fù)雜性函數(shù)所計(jì)算的比較次數(shù)比較。4 .用表格列出比較結(jié)果。5 .給出文字分析。三.

3、程序算法23v1.0可編輯可修改1 .歸并排序算法procedureMERGESORT(low,high)快速排序算法QuickSort(p,q)序代碼2 .歸并排序#include<>#include<>#include<>#include<>#defineM11typedefintKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistM;classguibingpublic:guibing(sqlistb)for(inti=0;i<M;i+

4、)ri=bi;voidoutput(sqlistr,intn)for(inti=0;i<n;i+)cout<<setw(4)<<ri.key;cout<<endl;voidxuanze(sqlistb,intm,intn)inti,j,k;33v1.0可編輯可修改for(i=m;i<n-1;i+)k=i;for(j=i;j<n;j+)if(bk.key>bj.key)k=j;if(k!=i)rectemp=bk;bk=bi；bi=temp;voidmerge(intl,intm,inth,sqlistr2)xuanze(r,l,m);

5、xuanze(r,m,h);output(r,M);inti,j,k;k=i=l;for(j=m;i<m&&j<h;k+)if(ri.key<=rj.key)r2k=ri;i+；elser2止皿j+;output(r2,M);#v1.0可編輯可修改while(j<h)r2k=rj；j+；k+;while(i<=m)r2k=ri；i+；k+;output(r2,M);private:sqlistr;；voidmain()cout<<"guibingfa1運(yùn)行結(jié)果：n"sqlista,b;inti,j=0,k=M/2,n

6、=M;srand(time(0);for(i=0;i<M;i+)ai.key=rand()%80;bi.key=0;guibinggx(a);cout<<"排序前數(shù)組:n"(a,M);cout<<"數(shù)組排序過(guò)程演示：n"(j,k,n,b);cout<<"排序后數(shù)組:n"(b,M);55v1.0可編輯可修改();3 .快速排序#include<>#include<>#include<>#include<>#defineMAXI10typedefin

7、tKeyType;typedefintElemType;structrecKeyTypekey;ElemTypedata;typedefrecsqlistMAXI;classkuaisupublic:kuaisu(sqlista,intm):n(m)for(inti=0;i<n;i+)bi=ai;voidquicksort(ints,intt)inti;if(s<t)i=part(s,t);quicksort(s,i-1);quicksort(i+1,t);elsereturn;intpart(ints,intt)#v1.0可編輯可修改inti,j；recp;i=s/t;p=bs;

8、while(i<j)while(i<j&&bj.key>=j-;bi=bjwhile(i<j&&bi.key<=i+;bj=bi；bi=P；output。；returni;voidoutput。for(inti=0;i<n;i+)cout<<setw(4)<<bi.key;cout<<endl;private:sqlistb;intn;voidmain()cout<<"運(yùn)行結(jié)果:n"sqlista1;inti,n=MAXI,low=0,high=9;srand

9、(time(0);for(i=0;i<n;i+)a1i.key=rand()%80;kuaisupx(a1,n);77v1.0可編輯可修改cout<<"數(shù)組排序過(guò)程演示：n"(low,high);cout<<"排序后數(shù)組:n"()；()；五.實(shí)驗(yàn)結(jié)果1.歸并排序1.F：、算法實(shí)畛、分治法'DubuCgirtbingfal-exeguihinqzfal運(yùn)行結(jié)果二熊序施組;232271231364214123632數(shù)組排序過(guò)程演示二13222323712212341G3642SO0Q0Q00002132100000000

10、313212200000U03132122230Q0Q0Q213212223230B0B021321222323230B0B213212223232341909213212222232241G»02132122232323416364B213212223232341636471排殍后數(shù)組，213212223232341心t4712.快速排序8-F二'算法賣藥'分豐臺(tái)法'DubujAkii看:LmuHhI.exe"上一次"4-mkuaisul.cppiST?nTfc:購(gòu)組排序過(guò)程演示二3?222241637764747556222239416

11、377E4747S5622229941G377G474如GG2222394166E474772222394156636475772222394156636474757?2222394156636474757?腓序后數(shù)組:2222394156636474757?#v1.0可編輯可修改實(shí)驗(yàn)二貪心法一.實(shí)驗(yàn)要求1 .優(yōu)化問(wèn)題有n輸入，而它的解就由這n個(gè)輸入滿足某些事先給定的約束條件的某個(gè)子集組成，而把滿足約束條件的子集稱為該問(wèn)題的可行解?？尚薪庖话銇?lái)說(shuō)是不唯一的。那些使目標(biāo)函數(shù)取極值（極大或極小）的可行解，稱為最優(yōu)解。2 .貪心法求優(yōu)化問(wèn)題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，

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

13、。3 .將統(tǒng)計(jì)數(shù)與復(fù)雜性函數(shù)所計(jì)算的比較次數(shù)比較，用表格列出比較結(jié)果，給出文字分析。三.程序算法99v1.0可編輯可修改1 .背包問(wèn)題的貪心算法procedureKNAPSACK(P,WM,X,n)序代碼2 .背包問(wèn)題貪心算法#include<>structgoodinfofloatp;>goodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;=0;cu=M;>cu)=1;cu=cu-goodsi.w產(chǎn)cu/goodsi.w;lag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cou

14、t<<"最優(yōu)解為:"<<endl;for(i=1;i<=n;i+)cout<<"第"<<i<<"件物品要放："；cout<<goodsi.X<<endl;voidmain()cout<<"|運(yùn)用貪心法解背包問(wèn)題|"<<endl;cout<<"|"<<endl;#v1.0可編輯可修改intj;intn;floatM;goodinfo*goods;lag=i;co

15、ut<<"請(qǐng)輸入第"<<i<<"件物品的重量："；cin>>goodsi.w;cout<<"請(qǐng)輸入第"<<i<<"件物品的效益："；cin>>goodsi.p;goodsi.p=goodsi.p/goodsi.w;dj;cout<<""cout<<endl;MiniSpanTree_PRIM(G,'a');voidCreateGraph(MGraph&G

16、)intweigh;inti,j=0,k=0;charhand,tide;cout<<"inputthenumberforvexnumandarcnum:"cin>>>>for(i=0;i<i+)for(j=0;j<j+)ij.adj=88;cout<<endl;cout<<"input"<<<<"charforvexs:"for(i=0;i<i+)cin>>i;cout<<endl;cout<<&

17、quot;input"<<<<"arc(char,char,weigh):"<<endl;j=0;1111v1.0可編輯可修改k=0;for(i=0;i<i+)cout<<i<<":"cin>>hand;cin>>tide;cin>>weigh;while(hand!=j)j+；while(tide!=k)k+;jk.adj=weigh;kj.adj=weigh;j=0;k=0;cout<<endl;voidMiniSpanTree

18、_PRIM(MGraphG,VerTexTypeu)inti,j,k=0;closedgeclose;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'#v1.0可編輯可修改closek.lowcost=0;closek.adjvex=u;for(i=1;i<i+)k=minimum(close);cout<<closek.adjvex;cout<<">&q

19、uot;cout<<k<<""cout<<closek.lowcost<<endl;closek.lowcost=0;for(j=0;j<j+)ifkj.adj<closej.lowcost)closej.adjvex=k;closej.lowcost=kj.adj;intLocateVex(MGraphG,VerTexTypeu)intk=0;whilek+=u)returnk-1;return0;intminimum(closedgeclose)intj1=0,client=88,j2;while(closej

20、1.adjvex!=''0')if(client>closej1.lowcost&&closej1.lowcost!=0)1313v1.0可編輯可修改client=closej1.lowcost;j2=jl；j1+;returnj2;五.實(shí)驗(yàn)結(jié)果1 .背包問(wèn)題貪心算法-F門(mén)算法實(shí)驗(yàn)、能心法）DetniCKGap5ack.eze運(yùn)用貪心法解背包問(wèn)題匕入物品的總數(shù)量！50人背直的最大容量20D入塞1件物品的重量：14認(rèn)第1柞枷品的效益;8物品的重量二3枷品的豆需二6入繚3件物品的重量;？入福性物品的效益=10道iS。入塞4件物品的重量二8認(rèn)親4性枷品的

21、效益當(dāng)0人集5件物品的重量二彳 認(rèn)第5怦枷品的效益二9為二勿品要欣四第4件物品要牧M 75重5件枷品要破門(mén)press <L> to Pim agianpi*e£s <0> to exit#v1.0可編輯可修改2 .Prim算法5'F：算法賣牛耳后”inputthenumberforuexnumandarcnum：56inpuc5charforvexs：12345inputtiarc(cJi-ar,cli-ai,weigh);,：1241：13S2:144J：2S74:3S6L：45S88454g848See踹75SBSfiB«£4S

22、B6S8«S8S768S81)24141>353>56PressarvkestocontinueH1515v1.0可編輯可修改實(shí)驗(yàn)三動(dòng)態(tài)規(guī)劃1 .實(shí)驗(yàn)要求1 .理解最優(yōu)子結(jié)構(gòu)的問(wèn)題。有一類問(wèn)題的活動(dòng)過(guò)程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過(guò)程如何達(dá)到這種狀態(tài)的方式無(wú)關(guān)。這類問(wèn)題的解決是多階段的決策過(guò)程。在50年代，貝爾曼（RichardBellman）等人提出了解決這類問(wèn)題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法-動(dòng)態(tài)規(guī)劃。對(duì)于一個(gè)多階段過(guò)程問(wèn)題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采

23、用動(dòng)態(tài)規(guī)劃的方法，還要看該問(wèn)題的子問(wèn)題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解。子問(wèn)題重疊性質(zhì)：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素。2 .理解分段決策Bellman方程。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長(zhǎng)度。即當(dāng)前最優(yōu)只與上一步有關(guān)。Us0,*mjUiWj.Us初始值，Uj第j段的最優(yōu)值。3 .一般方法4 ）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；5 ）遞歸地定義最優(yōu)值（寫(xiě)出動(dòng)態(tài)規(guī)劃方程）；6 ）以自底向上的方式計(jì)算出最優(yōu)值；7 ）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步

24、驟1-3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略,步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。2 .實(shí)驗(yàn)內(nèi)容1 .編程實(shí)現(xiàn)多段圖的最短路徑問(wèn)題的動(dòng)態(tài)規(guī)劃算法。2 .圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。3 .要求用文件裝入5個(gè)多段圖數(shù)據(jù)，編寫(xiě)從文件到鄰接表的函數(shù)。4 .驗(yàn)證算法的時(shí)間復(fù)雜性。#v1.0可編輯可修改3 .核心算法多段圖算法procedureFGRAPH(Ek,n,P)序代碼多段圖問(wèn)題#include<>#include<>#include<>#defineMAX

25、_VERTEX_NUM50typedefstructArcNodeintadjvex;ata=m;G->verticesm.firstArc=NULL;for(m=1;m<=a;m+)i=1;printf("輸入第原?。?quot;,m);scanf("%d,%d,%d",&t,&h,&v);p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=h;p->value=v;p->nextarc=NULL;while(G->verticesi.data!=t)i+;irst

26、Arc)irstArc=p;elseirstArc;q->nextarc;q=q->nextarc);q->nextarc=p;irstArc;printf("%d”,i);while(p)printf("->%d,%d",p->adjvex,p->value);irstArc;min=p->value+costp->adjvex;驗(yàn)結(jié)果多段圖問(wèn)題1717v1.0可編輯可修改1818v1.0可編輯可修改實(shí)驗(yàn)四深度優(yōu)先搜索1 .理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)

27、的頂點(diǎn)v,如果邊(v,w)是還未探測(cè)的邊，則沿(v,w)繼續(xù)搜索下去。當(dāng)所有的邊(v,w)都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)結(jié)點(diǎn)v的頂點(diǎn)。這一過(guò)程一直進(jìn)行到回到源點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的頂點(diǎn)，則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。2 .理解深度優(yōu)先搜索過(guò)程中頂點(diǎn)的三種狀態(tài)：還未到達(dá)的頂點(diǎn)，當(dāng)前路徑上經(jīng)過(guò)的頂點(diǎn)，深度優(yōu)先在搜索過(guò)程中也為結(jié)點(diǎn)著色以表示結(jié)點(diǎn)的狀態(tài)。每個(gè)頂點(diǎn)開(kāi)始均為白色，搜索中被發(fā)現(xiàn)時(shí)置為灰色，當(dāng)其鄰接表被完全檢索之后又被置成黑色。2 .實(shí)驗(yàn)內(nèi)容1 .編程實(shí)現(xiàn)深度優(yōu)先搜索算法。2 .修改算法使之可以找出圖的所有樹(shù)。3 .修改算法使之可以判斷圖是否為一棵樹(shù)。4 .修改算法使之可以判斷圖是否存在一個(gè)環(huán)。3 .核心算法procedureDFS(G);for每個(gè)頂點(diǎn)uCGdocoloru.White;repeatfor每個(gè)頂點(diǎn)uCGdoifcoloru=WhitethenDFS_Visit(G,u);end;procedureDFS_Visit(u);coloruGray;for(u,w)CEdo序代碼#include<>#d