算法設(shè)計及實驗報告

1、 算法設(shè)計及實驗報告實驗報告1 遞歸算法一、實驗?zāi)康恼莆者f歸算法的基本思想；掌握該算法的時間復(fù)雜度分析；二、實驗環(huán)境電腦一臺，Turbo C 運行環(huán)境三、實驗內(nèi)容、步驟和結(jié)果分析 以下是四個遞歸算法的應(yīng)用例子：用C語言實現(xiàn)1. 階乘：main()int i,k;scanf("%dn",&i);k= factorial(i); printf("%dn",k);int factorial(int n) int s;if(n=0) s=1;else s=n*factorial(n-1); /執(zhí)行n-1次return s;階乘的遞歸式很快，是個線性時間，

2、因此在最壞情況下時間復(fù)雜度為O(n)。2. Fibonacci 數(shù)列：main()int i,m;scanf("%dn",&i); m=fb(i); printf("%d",m);int fb(int n)int s; if(n<=1)return 1; else s=fb(n-1)+fb(n-2); return s;Fibonacci數(shù)列則是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由遞歸方程式可以知道他的時間復(fù)雜度T(n)是O(2n)，該數(shù)列的規(guī)律就是不停的賦值，使用的內(nèi)存空間也隨著函

3、數(shù)調(diào)用棧的增長而增長。3. 二分查找（分治法）#include<stdio.h>#define const 8main()int a=0,1,2,3,4,5,6,7,8,9; int n=sizeof(a); int s; s=BinSearch(a,const,n); printf("suo cha de shu shi di %d ge",s); BinSearch(int a,int x,int n)int left,right,middle=0; left=0;right=n-1; whlie(left<=right) middle=(left+r

4、ight)/2; if(x=amiddle) return middle; if(x>amiddle) left=middle+1; else right=middle-1; return -1;二分搜索算法利用了元素間的次序關(guān)系，采用分治策略，由上程序可知，每執(zhí)行一次while循環(huán)，數(shù)組大小減少一半，因此在最壞情況下，while循環(huán)被執(zhí)行了O（logn）次。而循環(huán)體內(nèi)部只需運算O（1）的時間，因此該算法在最壞情況下的時間復(fù)雜度為O（logn+1），即O（logn）。4. 合并排序（分治法） MergeSort(int low,int high,int *array)int middle

5、=(high+low)/2; /將數(shù)組劃分為2分if(low<high) MergeSort(low,middle,array); /對前一部分進行遞歸處理 MergeSort(middle+1,high,array); /對后一部分進行遞歸處理 HeBing(low,middle,middle+1,high,array); /將排序后的,前后兩部分,進行合并return true;HeBing(int low1,int high1,int low2,int high2,int *array)int *temp, i=low1, j=low2, k=0;temp=(int *)mallo

6、c(high2-low1+1)*sizeof(int); /temp用于臨時存儲合并后的數(shù)組while(i<=high1&&j<=high2) /對兩個有序數(shù)組進行合并 if(arrayi<arrayj) tempk+=arrayi;i+; else tempk+=arrayj;j+; if(i<=high1) while(i<=high1)tempk+=arrayi+;else while(j<=high2)tempk+=arrayj+;for(i=low1,j=0;i<=high2;i+,j+)/將合并后的數(shù)組,復(fù)制到array中

7、arrayi=tempj;free (temp);return true;這是一種分治算法。是先進行長度為1的排序，再合并成長度為2的排序，遞歸直到長度為n。而快速排序是先進行劃分，然后排序，不需要額為的空間，合并排序需要N的額外空間。是一種穩(wěn)定的排序。將數(shù)組劃分為小數(shù)組,通過局部的有序合并,解決問題。算法平均時間復(fù)雜度: O(nlogn)遞歸算法的時間復(fù)雜度求法：用通用公式：T(n)=fT（n-1）    f(x)是遞歸函數(shù)的時間復(fù)查性函數(shù)！    如下面這個簡單遞歸是：     void   Digui()  

8、         1-; /*假設(shè)該語句的復(fù)查性是a*/       2-; /*假設(shè)該語句的復(fù)查性是b*/       for() /*循環(huán)M次*/         -; /*假設(shè)該語句的復(fù)查性是c*/           Digui();       由上分析，它的時間復(fù)雜性計算公式是：T(n)=a+b+M*T(n-1);  另外，求算法的運行時間，可通過上一個實

9、驗?zāi)欠N方法，嵌入那個求時間的算法即可求出運行時間！四總結(jié)通過本次實驗，使我了解了遞歸算法的思想，以及掌握對該算法復(fù)雜度的分析。對遞歸算法的幾個典型實例算法進行了程序語言實現(xiàn)，使我更加掌握了遞歸算法的內(nèi)涵，同時也初步掌握了分治法的基本思想。相比與第一次實驗，對算法的分析方面，顯得更加深入理解！往后的學(xué)習(xí)中再強化深入。實驗報告2 動態(tài)規(guī)劃一、實驗?zāi)康恼莆談討B(tài)規(guī)劃算法的基本思想和要素；掌握該算法的的設(shè)計步驟；二、實驗環(huán)境電腦一臺，VC+ 運行環(huán)境三、實驗內(nèi)容、步驟和結(jié)果分析 以下通過動態(tài)規(guī)劃的兩個實例應(yīng)用算法來加深對動態(tài)規(guī)劃算法的理解：自身編程能力有限，此實現(xiàn)程序引用網(wǎng)上資料.1. 矩陣連乘問題 給

10、定n個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2,n-1。考察這n個矩陣的連乘積A1A2An。由于矩陣乘法滿足結(jié)合律，故計算矩陣的連乘積可以有許多不同的計算次序，這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標準算法（有改進的方法，這里不考慮）計算出矩陣連乘積。若A是一個p×q矩陣，B是一個q×r矩陣，則計算其乘積C=AB的標準算法中，需要進行pqr次數(shù)乘。下面使用動態(tài)規(guī)劃法找出矩陣連乘積的最優(yōu)計算次序。void MatrixChain(int *p,int n,int *m,int *s)

11、for(int i=1;i<=n;i+)mii=0;/單個矩陣相乘，所需數(shù)乘次數(shù)/以下兩個循環(huán)是關(guān)鍵之一，以個數(shù)組為例(為描述方便，mij用ij代替)/需按照如下次序計算/01 12 23 34 45/02 13 24 35/03 14 25/04 15/05/下面行的計算結(jié)果將會直接用到上面的結(jié)果。例如要計算13，就會用到12和23。for(int r=2;r<=n;r+)for(int i=1;i<n-r+1;i+)int j=i+r-1;/首先在i斷開，即（Ai*（Ai+1.Aj）mij=mi+1j+ +pi-1*pi*pj;sij=i;for(int k=i+1;k&

12、lt;j;k+)/然后在k（從i+1開始遍歷到j(luò)-1）斷開，即（Ai.Ak)*（Ak+1.Aj）int t=mik+mk+1j+pi-1*pk*pj;if(t<mij)/找到更好的斷開方法mij=t;/記錄最少數(shù)乘次數(shù)sij=k;/記錄斷開位置 /Traceback打印Ai:j的加括號方式void Traceback(int i,int j,int *s) /sij記錄了斷開的位置，即計算Ai:j的加括號方式為：/(Ai:sij)*(Asij+1:j)if(i=j)return;Traceback(i,sij,s);/遞歸打印Ai:sij的加括號方式Traceback(sij+1,j,s

13、);/遞歸打印Asij+1:j的加括號方式/能走到這里說明i等于sij，sij+1等于j/也就是說這里其實只剩下兩個矩陣，不必再分了cout<<"A"<<i<<"和A"<<(sij+1)<<"相乘"<<endl;int _tmain(int argc, _TCHAR* argv) int n=6;/矩陣的個數(shù)int *p=new intn+1;/p0:第一個矩陣的行數(shù)/p1:第一個矩陣的列數(shù)，第二個矩陣的行數(shù)/p2:第二個矩陣的列數(shù)，第三個矩陣的行數(shù)p0=30;p

14、1=35;p2=15;p3=5;p4=10;p5=20;p6=25;int *m,*s;m=new int*n;for( int i=0;i<n;i+)mi=new intn;s=new int*n;for(int i=0;i<n;i+)si=new intn;MatrixChain(p,n,m,s);Traceback(0,n-1,s);     for(int i=0;i<n;i+)         delete mi;   mi=N

15、ULL;    delete si;   si=NULL;       delete m;     m=NULL;    delete s;     s = NULL;   delete p;     p = NULL;  return 0;算法復(fù)雜度分析：算法 matrixChain 的主要計算量取決于算法

16、中對 r ， i 和 k 的 3 重循環(huán)。循環(huán)體內(nèi)的計算量為 O(1) ，而 3 重循環(huán)的總次數(shù)為 O(n3 ) 。因此算法的計算時間上界為 O(n 3 ) 。算法所占用的空間顯然為 O(n 2 ) 。2. 0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。程序?qū)崿F(xiàn)如下：#define N 12void Knapsack(int v,int w,int c,int n,int m6N) int i,j,jMax,k; jMax=(wn-1<c)

17、?wn-1:c; for(i=0;i<=jMax;i+) mni=0; for(i=wn;i<=c;i+) mni=vn; for(i=n-1;i>1;i-)  jMax=(wi-1<c)?wi-1:c;  for(j=0;j<=jMax;j+)    mij=mi+1j;    for(j=wi;j<=c;j+)   k=j-wi;   i

18、f(mi+1j<mi+1k+vi)   mij=mi+1k+vi;   else   mij=mi+1j;  m1c=m2c; if(c>=w1)  k=c-w1;  m1c=(m2c>m2k+v1)?m2c:m2k+v1;void Traceback(int m6N,int w,int c,int n,int x) int i; for(i=1;i<n;i+) if(mic=mi+

19、1c)   xi=0;  else  xi=1;   c-=wi;   xn=(mnc)?1:0;main() int i,c=10,n=5,w=0,2,2,6,5,4,v=0,6,3,5,4,6;      int m6N=0;      int x6=0;      int j;   

20、   Knapsack(v,w,c,n,m);      for(i=1;i<=n;i+)   for(j=1;j<=c;j+) printf("%3d",mij); printf("n");        Traceback(m,w,c,n,x);      for(i=1;i<=n;i+)  &#

21、160;    if(xi)  printf("%4d:%4d",i,vi);      printf("n");算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要(n2n)計算時間。四總結(jié)通過本次實驗，使我了解了動態(tài)規(guī)劃算法的思想以及該算法的設(shè)計步驟。對動態(tài)規(guī)劃算法的兩個個典型實例算法通過搜索資料找實現(xiàn)程序，大體上讀懂實現(xiàn)程序，使我更加深了對動態(tài)規(guī)劃機

22、制的了解。但實驗也存在著不足之處是自己無法用所學(xué)語言實現(xiàn)這兩個算法，是自己學(xué)的不夠深入，對程序設(shè)計方面不夠熟練，在今后的學(xué)習(xí)中將不斷加強自己這方面 的努力。實驗報告3 貪心算法一、實驗?zāi)康恼莆肇澬乃惴ǖ幕舅枷牒鸵?；掌握貪心算法的的設(shè)計步驟；二、實驗環(huán)境電腦一臺，VC+ 運行環(huán)境三、實驗內(nèi)容、步驟和結(jié)果分析 通過貪心算法的兩個實例應(yīng)用算法來加深對貪心算法的理解：3. 活動安排問題 以下是用C語言編寫的程序?qū)崿F(xiàn)活動安排問題#include <stdio.h>main()int s8=2,3,0,5,3,5,8,7;  int f8=6,7,8,9,10,11,1

23、2;C=GreedySelector(s,f);Printf(“算出有%d個活動安排”,C);int GreedySelector(int a,int c) int n=8;  char b2=T，F(xiàn) b0=T; int j=1; int c=1; for (int i=2;i<=n;i+) if (ai>=cj) ai=b0; j=i; c+; else ai=b1; return c;當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。對于活動安排

24、問題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。4. 哈夫曼編碼問題由于自身編程能力有限無法實現(xiàn)本該問題，以下程序是參考網(wǎng)上資料編寫C語言實現(xiàn)#include <stdio.h> #define N 7 /*葉子數(shù)目,需要時更改此值即可*/ #define M 2*N-1 /*節(jié)點總數(shù)*/ typedef struct char bitsN;/*編碼存儲，位串*/ int start; /*編碼在位串中的位置*/ codetype; typedef struct float weight; int lchild,rchild,parent; hufm

25、tree; void HUFFMAN(tree1) hufmtree tree1; int i,j,p1,p2; float small1,small2,f; hufmtree *tree; tree=tree1; for(i=0;i<M;i+) /*初始化*/ treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0.0; printf("please input a possible data weight:n"); /*輸入信源數(shù)據(jù)*/ for(i=0;i<N;i+) /*輸入前n個節(jié)點的

26、權(quán)值*/ scanf("%f",&f); treei.weight=f; for(i=N;i<M;i+) /* 進行n-1次合并，產(chǎn)生n-1個新的節(jié)點*/ p1=0,p2=0; small1=1;small2=1; for(j=0;j<=i-1;j+) /*從所有的節(jié)點中，選出兩個權(quán)值最小的根節(jié)點*/ if(treej.parent=0) /*parent值為0，則顯示根節(jié)點，否則便是非根節(jié)點*/ if(treej.weight<small1) small2=small1; /*改變最小權(quán)，次小權(quán)及對應(yīng)的位置*/ small1=treej.weig

27、ht; p2=p1; /*p1、p2記住這兩個根節(jié)點在向量tree中的下標*/ p1=j; else if(treej.weight<small2) small2=treej.weight;/*次小權(quán)及位置*/ p2=j; treep1.parent=i+1; /*節(jié)點分量與下標之間差值為1*/ treep2.parent=i+1; /*節(jié)點的標號i+1*/ treei.lchild=p1+1; /*最小值根節(jié)點是新節(jié)點的左孩子，分量標號是其下標加1*/ treei.rchild=p2+1; /*次小權(quán)根節(jié)點是新節(jié)點的右孩子*/ treei.weight=treep1.weight+tr

28、eep2.weight; /*HUFFMANTREE()*/ void HUFFMANCODE(code1,tree1) /*根據(jù)哈夫曼樹求出哈夫曼編碼*/ codetype code1; /*求出的哈夫曼編碼所在*/ hufmtree tree1;/*已知的哈夫曼樹*/ int i,j,c,p; codetype cd;/*緩沖變量*/ codetype *code; hufmtree *tree; code=code1; tree=tree1; for(i=0;i<N;i+) cd.start=N; c=i+1; /*從葉節(jié)點出發(fā)向上回溯*/ p=treei.parent;/*tre

29、ep-1是treei的雙親*/ while(p!=0) cd.start-; if(treep-1.lchild=c) cd.bitscd.start='0' /*treei是左子樹。生成代碼'0'*/ else cd.bitscd.start='1' /*否則treei是右子樹。生成代碼'1'*/ c=p; p=treep-1.parent; codei=cd; /*第i+1個字符的編碼存入codei*/ /*HUFFMANCODE*/ #include "stdio.h" main() int k1,k2;

30、 hufmtree tree_finaM; hufmtree *p11=tree_fina; codetype code_finaN; codetype *p21=code_fina; HUFFMAN(p11); /*建立huffman樹*/ HUFFMANCODE(p21,p11); /*haffman碼*/ for(k1=0;k1<N;k1+) /*輸出編碼*/ printf("number %d haffmancode: ",k1+1); for(k2=code_finak1.start;k2<N;k2+) printf(" %c",c

31、ode_finak1.bitsk2); printf("n"); 該算法在最壞情況下的時間復(fù)雜度為O(nlogn)。四總結(jié)通過本次實驗，使我了解了貪心算法的思想以及該算法的設(shè)計步驟。實現(xiàn)貪心規(guī)劃算法的兩個實例算法，使我更加深了對動態(tài)規(guī)劃機制的了解。但還是對編程這方面存在不足，無法實現(xiàn)哈夫曼編碼，在今后的學(xué)習(xí)中將不斷加強自己這方面的努力。實驗報告4 回溯算法一、實驗?zāi)康恼莆栈厮莘ǖ幕舅枷牒鸵?；掌握回溯法的的設(shè)計步驟；二、實驗環(huán)境電腦一臺，VC+ 運行環(huán)境三、實驗內(nèi)容、步驟和結(jié)果分析 回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的

32、方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當前的擴展結(jié)點。在當前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當前擴展結(jié)點。如果在當前的擴展結(jié)點處不能再向縱深方向移動，則當前擴展結(jié)點就成為死結(jié)點。換句話說，這個結(jié)點不再是一個活結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當前的擴展結(jié)點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。 運用回溯法解題通常包含以下三個步驟： a. 針對所給問題，定義問題的解空間； b. 確定易于搜索的解空間結(jié)構(gòu)； c. 以深度優(yōu)先的方式搜索解

33、空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索；下面是通過實例0-1背包問題的實現(xiàn)，來加深對回溯法的理解：0-1背包問題本程序是摘自網(wǎng)上，自身編程能力有限，無法實現(xiàn)這個算法。通過讀這個程序的主要實現(xiàn)模塊，大致理解了這個算法的基本思想。#include<iostream>using namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n );public:void print()    for(int m=1;m<=n;m+)    

34、0;  cout<<bestxm<<" "      cout<<endl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量int n; /物品數(shù)int *w;/物品重量數(shù)組int *p;/物品價值數(shù)組int cw;/當前重量int cp;/當前價值int bestp;/當前最優(yōu)值int *bestx;/當前最優(yōu)解int *x;/當前解;int Knap:Bound(int i)/計算上界int cleft=c-cw;/剩

35、余容量int b=cp;/以物品單位重量價值遞減序裝入物品while(i<=n&&wi<=cleft)cleft-=wi;   b+=pi;   i+;/裝滿背包if(i<=n)   b+=pi/wi*cleft;return b;void Knap:Backtrack(int i)if(i>n) if(bestp<cp)         for(int j=1;j<=n;j+)   

36、  bestxj=xj;     bestp=cp;return;if(cw+wi<=c) /搜索左子樹                   xi=1;   cw+=wi;   cp+=pi;   Backtrack(i+1);   cw-=wi;   cp-=pi;

37、60;  if(Bound(i+1)>bestp)/搜索右子樹          xi=0;    Backtrack(i+1);   class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator<=(Object a)constreturn (d>=a.d);private:int ID;float d;int Knapsack(int p,in

38、t w,int c,int n)/為Knap:Backtrack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn;for(i=1;i<=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W<=c)   return P;/裝入所有物品/依物品單位重量排序float f;for( i=0;i<n;i+)for(int j=i;j<n;j+)   if(Qi.d<Qj.d)        f=Qi.d;   Qi.d=Qj.d;   Qj.d=f;   Knap K;K.p = new intn+1;    K.w = new intn+1;K.x