算法設(shè)計實(shí)驗(yàn)報告

算法設(shè)計與分析實(shí)驗(yàn)報告一實(shí)驗(yàn)名稱統(tǒng)計數(shù)字問題評分實(shí)驗(yàn)日期年月日指導(dǎo)教師劉長松老師姓名覃宇星專業(yè)班級0901學(xué)號02一.實(shí)驗(yàn)要求1、掌握算法的計算復(fù)雜性概念。2、掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。3、掌握用C++語言描述算法的方法。4．實(shí)現(xiàn)具體的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時間復(fù)雜性函數(shù)。二.實(shí)驗(yàn)內(nèi)容統(tǒng)計數(shù)字問題1、問題描述一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示，而不是06或006等。數(shù)字計數(shù)問題要求對給定書的總頁碼n，計算出書的全部頁碼中分別用到多少次數(shù)字0，1，2，…，9。2、編程任務(wù)給定表示書的總頁碼的10進(jìn)制整數(shù)n(1≤n≤109)。編程計算書的全部頁碼中分別用到多少次數(shù)字0，1，2，…，9。程序算法將頁碼數(shù)除以10，得到一個整數(shù)商和余數(shù)，商就代表頁碼數(shù)減余數(shù)外有多少個1—9作為個位數(shù)，余數(shù)代表有1—余數(shù)本身這么多個數(shù)作為剩余的個位數(shù)，此外，商還代表1—商本身這些數(shù)出現(xiàn)了10次，余數(shù)還代表剩余的沒有計算的商的大小的數(shù)的個數(shù)。把這些結(jié)果統(tǒng)計起來即可。程序代碼#include<iostream.h>ints[10];//記錄0~9出現(xiàn)的次數(shù)inta[10];//a[i]記錄n位數(shù)的規(guī)律voidsum(intn,intl,intm){if(m==1){intzero=1;for(inti=0;i<=l;i++)//去除前綴0{s[0]-=zero;zero*=10;}}if(n<10){for(inti=0;i<=n;i++){s[i]+=1;}return;}//位數(shù)為1位時,出現(xiàn)次數(shù)加1//位數(shù)大于1時的出現(xiàn)次數(shù)for(intt=1;t<=l;t++)//計算規(guī)律f(n)=n*10^(n-1){m=1;inti;for(i=1;i<t;i++)m=m*10;a[t]=t*m;}intzero=1;for(inti=0;i<l;i++){zero*=10;}//求出輸入數(shù)為10的n次方intyushu=n%zero;//求出最高位以后的數(shù)intzuigao=n/zero;//求出最高位zuigaofor(i=0;i<zuigao;i++){s[i]+=zero;}//求出0~zuigao-1位的數(shù)的出現(xiàn)次數(shù)for(i=0;i<10;i++){s[i]+=zuigao*a[l];}//求出與余數(shù)位數(shù)相同的0~zuigao-1位中0~9出現(xiàn)的次數(shù)//如果余數(shù)是0,則程序可結(jié)束,不為0則補(bǔ)上所缺的0數(shù),和最高位對應(yīng)所缺的數(shù)if(yushu==0)//補(bǔ)上所缺的0數(shù),并且最高位加1{s[zuigao]++;s[0]+=l;}else{i=0;while((zero/=10)>yushu){i++;}s[0]+=i*(yushu+1);//補(bǔ)回因作模操作丟失的0s[zuigao]+=(yushu+1);//補(bǔ)回最高位丟失的數(shù)目sum(yushu,l-i-1,m+1);//處理余位數(shù)}}voidmain(){inti,m,n,N,l;cout<<"輸入數(shù)字要查詢的數(shù)字:";cin>>N;cout<<'\n';n=N;for(i=0;n>=10;i++){n/=10;}//求出N的位數(shù)n-1l=i;sum(N,l,1);for(i=0;i<10;i++){cout<<"數(shù)字"<<i<<"出現(xiàn)了:"<<s[i]<<"次"<<'\n';}}程序調(diào)試中的問題調(diào)試過程中總是有這樣那樣的問題，通過一步步的修改，最終得以實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果算法設(shè)計與分析實(shí)驗(yàn)報告二實(shí)驗(yàn)名稱分治法實(shí)現(xiàn)歸并排序算法評分實(shí)驗(yàn)日期年月日指導(dǎo)教師劉長松姓名覃宇星專業(yè)班級計算機(jī)0901班學(xué)號02一.實(shí)驗(yàn)要求1.了解用分治法求解的問題：當(dāng)要求解一個輸入規(guī)模為n，且n的取值相當(dāng)大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨(dú)立求解的子問題，其中1<k≤n，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。那末，對于這類問題分治法是十分有效的。2.掌握分治法的一般控制流程。DanC(p,q)globaln，A[1:n];integerm,p,q;//1￡p￡q￡nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//p￡m<qreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC3．實(shí)現(xiàn)典型的分治算法的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時間復(fù)雜性函數(shù)。二.實(shí)驗(yàn)內(nèi)容1.編程實(shí)現(xiàn)歸并排序算法，程序中加入比較次數(shù)的計數(shù)功能，輸出排序結(jié)果和比較次數(shù)。2.輸入10組相同的數(shù)據(jù)，驗(yàn)證排序結(jié)果和完成排序的比較次數(shù)。3.與復(fù)雜性函數(shù)所計算的比較次數(shù)比較。4.用表格列出比較結(jié)果。5.給出文字分析。三.程序算法1.歸并排序算法procedureMERGESORT(low，high)//A(low；high)是一個全程數(shù)組，它含有high-low+1≥0個待排序的元素//integerlow，high；iflow<high；thenmid←，//求這個集合的分割點(diǎn)//callMERGESORT(low，mid)//將一個子集合排序//callMERGESORT(mid+1，high)//將另一個子集合排序callMERGE(low，mid，high)//歸并兩個已排序的子集合//endifendMERGESORT歸并兩個已排序的集合procedureMERGE(low，mid，high)//A(low：high)是一個全程數(shù)組////輔助數(shù)組B(low；high)//integerh，i，j，k；h←low；i←low；j←mid+1；whileh≤midandj≤highdo//當(dāng)兩個集合都沒取盡時//ifA(h)≤A(j)thenB(i)←A(h)；h←h+1elseB(i)←A(j)；j←j+1endifi←i+1repeatifh>midthenfork←jtohighdo//處理剩余的元素//B(i)←A(k)；i←i+1repeatelsefork←htomiddoB(i)←A(k)；i←i+1repeatendif將已歸并的集合復(fù)制到AendMERGE2.快速排序算法QuickSort(p,q)//將數(shù)組A[1:n]中的元素A[p],A[p+1],?,A[q]按不降次序排列，并假定A[n+1]是一個確定的、且大于A[1:n]中所有的數(shù)。//intp,q;globaln,A[1:n];ifp<qthenj=Partition(p,q+1);//劃分后j成為劃分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifendQuickSortprocedurePARTITION(m，p)//退出過程時，p帶著劃分元素所在的下標(biāo)位置。//integerm，p，i；globalA(m：p-1)v←A(m)；i←m//A(m)是劃分元素//looploopi←i+1untilA(i)≥vrepeat//i由左向右移//loopp←p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i)，A(p))//A(i)和A(p)換位//elseexitendifrepeatA(m)←A(p)；A(p)←v//劃分元素在位置p//EndPARTITION程序代碼歸并排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineM11typedefintKeyType;typedefintElemType;structrec{ KeyTypekey; ElemTypedata;};typedefrecsqlist[M];classguibing{public: guibing(sqlistb) { for(inti=0;i<M;i++) r[i]=b[i]; } voidoutput(sqlistr,intn) { for(inti=0;i<n;i++) cout<<setw(4)<<r[i].key; cout<<endl; } voidxuanze(sqlistb,intm,intn) { inti,j,k; for(i=m;i<n-1;i++) { k=i; for(j=i;j<n;j++) if(b[k].key>b[j].key)k=j; if(k!=i) { rectemp=b[k]; b[k]=b[i]; b[i]=temp; } } } voidmerge(intl,intm,inth,sqlistr2) { xuanze(r,l,m); xuanze(r,m,h); output(r,M); inti,j,k; k=i=l; for(j=m;i<m&&j<h;k++) { if(r[i].key<=r[j].key) { r2[k]=r[i]; i++; } else { r2[k]=r[j]; j++; } output(r2,M); } while(j<h) { r2[k]=r[j]; j++; k++; } while(i<=m) { r2[k]=r[i]; i++; k++; } output(r2,M); }private: sqlistr; }; voidmain() { cout<<"guibingfa1運(yùn)行結(jié)果:\n"; sqlista,b; inti,j=0,k=M/2,n=M; srand(time(0)); for(i=0;i<M;i++) { a[i].key=rand()%80;b[i].key=0; } guibinggx(a); cout<<"排序前數(shù)組:\n"; gx.output(a,M); cout<<"數(shù)組排序過程演示:\n"; gx.merge(j,k,n,b); cout<<"排序后數(shù)組:\n"; gx.output(b,M); cin.get(); }快速排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#defineMAXI10typedefintKeyType;typedefintElemType;structrec{ KeyTypekey; ElemTypedata;};typedefrecsqlist[MAXI];classkuaisu{public: kuaisu(sqlista,intm):n(m) { for(inti=0;i<n;i++)b[i]=a[i]; } voidquicksort(ints,intt) { inti; if(s<t){ i=part(s,t); quicksort(s,i-1); quicksort(i+1,t); } elsereturn; } intpart(ints,intt) { inti,j; recp; i=s;j=t;p=b[s]; while(i<j) { while(i<j&&b[j].key>=p.key)j--; b[i]=b[j]; while(i<j&&b[i].key<=p.key)i++; b[j]=b[i]; } b[i]=p; output(); returni; } voidoutput() { for(inti=0;i<n;i++) cout<<setw(4)<<b[i].key; cout<<endl; }private: sqlistb; intn;};voidmain(){ cout<<"kuaisu1.cpp運(yùn)行結(jié)果:\n"; sqlista1; inti,n=MAXI,low=0,high=9; srand(time(0)); for(i=0;i<n;i++) a1[i].key=rand()%80; kuaisupx(a1,n); cout<<"數(shù)組排序過程演示:\n"; px.quicksort(low,high); cout<<"排序后數(shù)組:\n"; px.output(); cin.get();}程序調(diào)試中的問題挺簡單，沒問題六.實(shí)驗(yàn)結(jié)果歸并排序快速排序算法設(shè)計與分析實(shí)驗(yàn)報告三實(shí)驗(yàn)名稱動態(tài)規(guī)劃算法實(shí)現(xiàn)多段圖的最短路徑問題評分實(shí)驗(yàn)日期年月日指導(dǎo)教師劉長松老師姓名覃宇星專業(yè)班級計算機(jī)0901班學(xué)號02一.實(shí)驗(yàn)要求1.理解最優(yōu)子結(jié)構(gòu)的問題。有一類問題的活動過程可以分成若干個階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程如何達(dá)到這種狀態(tài)的方式無關(guān)。這類問題的解決是多階段的決策過程。在50年代，貝爾曼（RichardBellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法－動態(tài)規(guī)劃。對于一個多階段過程問題，是否可以分段實(shí)現(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)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)是采用動態(tài)規(guī)劃算法的兩個基本要素。2.理解分段決策Bellman方程。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長度。即當(dāng)前最優(yōu)只與上一步有關(guān)。Us初始值，uj第j段的最優(yōu)值。3.一般方法找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；以自底向上的方式計算出最優(yōu)值；根據(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)解。二.實(shí)驗(yàn)內(nèi)容1.編程實(shí)現(xiàn)多段圖的最短路徑問題的動態(tài)規(guī)劃算法。2.圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表。3.要求用文件裝入5個多段圖數(shù)據(jù)，編寫從文件到鄰接表的函數(shù)。4.驗(yàn)證算法的時間復(fù)雜性。三.程序算法多段圖算法：ProcedureFGRAPH（E,k,n,P）//輸入是按段的順序給結(jié)點(diǎn)編號的，有n個結(jié)點(diǎn)的k段圖。E是邊集，c（i，j）是邊<i，j>的成本。P（1：k）是最小成本路徑。//realCOST(n),integer(n-1),P(k),r,j,k,nCOST(n)<-0forj<-n-1to1by-1do//計算COST（j）//設(shè)r是一個這樣的結(jié)點(diǎn)，（j，r）E且使c（j，r）+COST（r）取最小值COST（j）<-c（j，r）+COST（r）;D(j)<-r;Repeat//向前對j-1進(jìn)行決策//P（1）<-1;P（k）<-n;forj<-2tok-1do//找路徑上的第j個節(jié)點(diǎn)//P（j）<-D(P(j-1));repeat;endFGRAPH程序代碼#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<iostream.h>#defineMAX100#definen12/*頂點(diǎn)數(shù)*/#definek5/*段數(shù)*/intc[n][n];voidinit(intcost[])//初始化圖{ inti,j; for(i=0;i<13;i++) { for(j=0;j<13;j++) { c[i][j]=MAX; } } c[1][2]=9; c[1][3]=7; c[1][4]=3; c[1][5]=2; c[2][6]=4; c[2][7]=2; c[2][8]=1; c[3][6]=2; c[3][7]=7; c[4][8]=11; c[5][7]=11; c[5][8]=8; c[6][9]=6; c[6][10]=5; c[7][9]=4; c[7][10]=3; c[8][10]=5; c[8][11]=6; c[9][12]=4; c[10][12]=2;c[11][12]=5;}voidfgraph(intcost[],intpath[],intd[])//使用向前遞推算法求多段圖的最短路徑{ intr,j,temp,min; for(j=0;j<=n;j++) cost[j]=0; for(j=n-1;j>=1;j--) { temp=0; min=c[j][temp]+cost[temp];//初始化最小值 for(r=0;r<=n;r++) { if(c[j][r]!=MAX) { if((c[j][r]+cost[r])<min)//找到最小的r { min=c[j][r]+cost[r]; temp=r; } } } cost[j]=c[j][temp]+cost[temp]; d[j]=temp; } path[1]=1; path[k]=n; for(j=2;j<k;j++) path[j]=d[path[j-1]];}voidbgraph(intbcost[],intpath1[],intd[])//使用向后遞推算法求多段圖的最短路徑{ intr,j,temp,min; for(j=0;j<=n;j++) bcost[j]=0; for(j=2;j<=n;j++) { temp=12; min=c[temp][j]+bcost[temp];//初始化最小值 for(r=0;r<=n;r++) { if(c[r][j]!=MAX) { if((c[r][j]+bcost[r])<min)//找到最小的r { min=c[r][j]+bcost[r]; temp=r; } } } bcost[j]=c[temp][j]+bcost[temp]; d[j]=temp; } path1[1]=1; path1[k]=n; for(inti=4;i>=2;i--) { path1[i]=d[path1[i+1]]; }}voidmain(){intcur=-1; intcost[13],d[12],bcost[13]; intpath[k];intpath1[k]; cout<<"\t\t\t動態(tài)規(guī)劃解多段圖問題"<<endl; cout<<"\n\n";init(cost);fgraph(cost,path,d);cout<<"輸出使用向前遞推算法后的最短路徑:\n\n"; for(inti=1;i<=5;i++) { cout<<path[i]<<""; } cout<<"\n"; cout<<endl<<"最短路徑為長度:"<<cost[1]<<endl; cout<<"\n";cout<<"\n輸出使用向后遞推算法后的最短路徑:\n\n"; bgraph(bcost,path1,d); for(i=1;i<=5;i++) { cout<<path1[i]<<""; } cout<<"\n"; cout<<endl<<"最短路徑為長度:"<<bcost[12]<<endl; cout<<"\n";}程序調(diào)試中的問題在這次實(shí)驗(yàn)中，確實(shí)遇到了一些小問題，但都解決啦。六.實(shí)驗(yàn)結(jié)果1、數(shù)據(jù)的五段圖11234567811100912973281111653552464421112*程序中的數(shù)據(jù)以次圖為標(biāo)準(zhǔn)72、實(shí)驗(yàn)結(jié)果如下：算法設(shè)計與分析實(shí)驗(yàn)報告四實(shí)驗(yàn)名稱貪心算法實(shí)現(xiàn)背包問題評分實(shí)驗(yàn)日期年月日指導(dǎo)教師劉長松老師姓名覃宇星專業(yè)班級計算機(jī)0901班學(xué)號02一.實(shí)驗(yàn)要求1.優(yōu)化問題有n個輸入，而它的解就由這n個輸入滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解?？尚薪庖话銇碚f是不唯一的。那些使目標(biāo)函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。2.貪心法求優(yōu)化問題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪心決策的依據(jù)稱為貪心準(zhǔn)則（greedycriterion）。3.一般方法1）根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。2）按這種量度標(biāo)準(zhǔn)對這n個輸入排序3）依次選擇輸入量加入部分解中。如果當(dāng)前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。procedureGREEDY(A，n)/*貪心法一般控制流程*///A(1：n)包含n個輸入//solutions←φ//將解向量solution初始化為空／fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)endifrepeatreturn(solution)endGREEDY4.實(shí)現(xiàn)典型的貪心算法的編程與上機(jī)實(shí)驗(yàn)，驗(yàn)證算法的時間復(fù)雜性函數(shù)。二.實(shí)驗(yàn)內(nèi)容1.編程實(shí)現(xiàn)背包問題貪心算法。通過具體算法理解如何通過局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，并驗(yàn)證算法的時間復(fù)雜性。2.輸入5個的圖的鄰接矩陣，程序加入統(tǒng)計prim算法訪問圖的節(jié)點(diǎn)數(shù)和邊數(shù)的語句。3.將統(tǒng)計數(shù)與復(fù)雜性函數(shù)所計算的比較次數(shù)比較，用表格列比較結(jié)果，給出文字分析。三.程序算法背包問題的貪心算法procedureKNAPSACK(P，W，M，X，n)//P(1：n)和W(1；n)分別含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1：n)是解向量realP(1：n)，W(1：n)，X(1：n)，M，cu；integeri，n；X←0//將解向量初始化為零cu←M//cu是背包剩余容量fori←1tondoifW(i)>cuthenexitendifX(i)←1cu←cu-W(i)repeatifi≤nthenX(i)←cu/W(i)endifendGREEDY-KNAPSACKprocedureprim(G,)status←“unseen”//T為空status[1]←“treenode”//將1放入Tforeachedge(1,w)dostatus[w]←“fringe”//找到T的鄰接點(diǎn)dad[w]←1;//w通過1與T建立聯(lián)系dist[w]←weight(1,w)//w到T的距離repeatwhilestatus[t]≠“treenode”dopickafringeuwithmindist[w]//選取到T最近的節(jié)點(diǎn)status[u]←“treenode”foreachedge(u,w)do修改w和T的關(guān)系repeatrepeatPrim算法PrimMST(G，T，r){

//求圖G的以r為根的MST，結(jié)果放在T=(U，TE)中

InitCandidateSet(…)；//初始化：設(shè)置初始的輕邊候選集，并置T=({r}，￠)

for(k=0；k<n-1；k++){//求T的n-1條樹邊

(u，v)=SelectLiShtEdge(…)；//選取輕邊(u，v)；

T←T∪{(u，v)}；//擴(kuò)充T，即(u，v)涂紅加入TE，藍(lán)點(diǎn)v并人紅點(diǎn)集U

ModifyCandidateSet(…)；//根據(jù)新紅點(diǎn)v調(diào)整候選輕邊集

}

}程序代碼背包問題貪心算法#include<iostream.h>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品該放的數(shù)量intflag;//物品編號};//物品信息結(jié)構(gòu)體voidInsertionsort(goodinfogoods[],intn