算法设计及实验报告

1、 算法设计及实验报告实验报告1 递归算法一、实验目的掌握递归算法的基本思想；掌握该算法的时间复杂度分析；二、实验环境电脑一台，Turbo C 运行环境三、实验内容、步骤和结果分析 以下是四个递归算法的应用例子：用C语言实现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); /执行n-1次return s;阶乘的递归式很快，是个线性时间，

2、因此在最坏情况下时间复杂度为O(n)。2. Fibonacci 数列：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数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的时间复杂度T(n)是O(2n)，该数列的规律就是不停的赋值，使用的内存空间也随着函

3、数调用栈的增长而增长。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;二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行一次while循环，数组大小减少一半，因此在最坏情况下，while循环被执行了O（logn）次。而循环体内部只需运算O（1）的时间，因此该算法在最坏情况下的时间复杂度为O（logn+1），即O（logn）。4. 合并排序（分治法） MergeSort(int low,int high,int *array)int middle

5、=(high+low)/2; /将数组划分为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用于临时存储合并后的数组while(i<=high1&&j<=high2) /对两个有序数组进行合并 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+)/将合并后的数组,复制到array中

7、arrayi=tempj;free (temp);return true;这是一种分治算法。是先进行长度为1的排序，再合并成长度为2的排序，递归直到长度为n。而快速排序是先进行划分，然后排序，不需要额为的空间，合并排序需要N的额外空间。是一种稳定的排序。将数组划分为小数组,通过局部的有序合并,解决问题。算法平均时间复杂度: O(nlogn)递归算法的时间复杂度求法：用通用公式：T(n)=fT（n-1）    f(x)是递归函数的时间复查性函数！    如下面这个简单递归是：     void   Digui()  

8、         1-; /*假设该语句的复查性是a*/       2-; /*假设该语句的复查性是b*/       for() /*循环M次*/         -; /*假设该语句的复查性是c*/           Digui();       由上分析，它的时间复杂性计算公式是：T(n)=a+b+M*T(n-1);  另外，求算法的运行时间，可通过上一个实

9、验那种方法，嵌入那个求时间的算法即可求出运行时间！四总结通过本次实验，使我了解了递归算法的思想，以及掌握对该算法复杂度的分析。对递归算法的几个典型实例算法进行了程序语言实现，使我更加掌握了递归算法的内涵，同时也初步掌握了分治法的基本思想。相比与第一次实验，对算法的分析方面，显得更加深入理解！往后的学习中再强化深入。实验报告2 动态规划一、实验目的掌握动态规划算法的基本思想和要素；掌握该算法的的设计步骤；二、实验环境电脑一台，VC+ 运行环境三、实验内容、步骤和结果分析 以下通过动态规划的两个实例应用算法来加深对动态规划算法的理解：自身编程能力有限，此实现程序引用网上资料.1. 矩阵连乘问题 给

10、定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2,n-1。考察这n个矩阵的连乘积A1A2An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。若A是一个p×q矩阵，B是一个q×r矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。下面使用动态规划法找出矩阵连乘积的最优计算次序。void MatrixChain(int *p,int n,int *m,int *s)

11、for(int i=1;i<=n;i+)mii=0;/单个矩阵相乘，所需数乘次数/以下两个循环是关键之一，以个数组为例(为描述方便，mij用ij代替)/需按照如下次序计算/01 12 23 34 45/02 13 24 35/03 14 25/04 15/05/下面行的计算结果将会直接用到上面的结果。例如要计算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-1）断开，即（Ai.Ak)*（Ak+1.Aj）int t=mik+mk+1j+pi-1*pk*pj;if(t<mij)/找到更好的断开方法mij=t;/记录最少数乘次数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;/矩阵的个数int *p=new intn+1;/p0:第一个矩阵的行数/p1:第一个矩阵的列数，第二个矩阵的行数/p2:第二个矩阵的列数，第三个矩阵的行数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;算法复杂度分析：算法 matrixChain 的主要计算量取决于算法

16、中对 r ， i 和 k 的 3 重循环。循环体内的计算量为 O(1) ，而 3 重循环的总次数为 O(n3 ) 。因此算法的计算时间上界为 O(n 3 ) 。算法所占用的空间显然为 O(n 2 ) 。2. 0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。程序实现如下：#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");算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要(n2n)计算时间。四总结通过本次实验，使我了解了动态规划算法的思想以及该算法的设计步骤。对动态规划算法的两个个典型实例算法通过搜索资料找实现程序，大体上读懂实现程序，使我更加深了对动态规划机

22、制的了解。但实验也存在着不足之处是自己无法用所学语言实现这两个算法，是自己学的不够深入，对程序设计方面不够熟练，在今后的学习中将不断加强自己这方面 的努力。实验报告3 贪心算法一、实验目的掌握贪心算法的基本思想和要素；掌握贪心算法的的设计步骤；二、实验环境电脑一台，VC+ 运行环境三、实验内容、步骤和结果分析 通过贪心算法的两个实例应用算法来加深对贪心算法的理解：3. 活动安排问题 以下是用C语言编写的程序实现活动安排问题#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 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;当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。对于活动安排

24、问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。4. 哈夫曼编码问题由于自身编程能力有限无法实现本该问题，以下程序是参考网上资料编写C语言实现#include <stdio.h> #define N 7 /*叶子数目,需要时更改此值即可*/ #define M 2*N-1 /*节点总数*/ 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"); /*输入信源数据*/ for(i=0;i<N;i+) /*输入前n个节点的

26、权值*/ scanf("%f",&f); treei.weight=f; for(i=N;i<M;i+) /* 进行n-1次合并，产生n-1个新的节点*/ p1=0,p2=0; small1=1;small2=1; for(j=0;j<=i-1;j+) /*从所有的节点中，选出两个权值最小的根节点*/ if(treej.parent=0) /*parent值为0，则显示根节点，否则便是非根节点*/ if(treej.weight<small1) small2=small1; /*改变最小权，次小权及对应的位置*/ small1=treej.weig

27、ht; p2=p1; /*p1、p2记住这两个根节点在向量tree中的下标*/ p1=j; else if(treej.weight<small2) small2=treej.weight;/*次小权及位置*/ p2=j; treep1.parent=i+1; /*节点分量与下标之间差值为1*/ treep2.parent=i+1; /*节点的标号i+1*/ treei.lchild=p1+1; /*最小值根节点是新节点的左孩子，分量标号是其下标加1*/ treei.rchild=p2+1; /*次小权根节点是新节点的右孩子*/ treei.weight=treep1.weight+tr

28、eep2.weight; /*HUFFMANTREE()*/ void HUFFMANCODE(code1,tree1) /*根据哈夫曼树求出哈夫曼编码*/ 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; /*从叶节点出发向上回溯*/ 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"); 该算法在最坏情况下的时间复杂度为O(nlogn)。四总结通过本次实验，使我了解了贪心算法的思想以及该算法的设计步骤。实现贪心规划算法的两个实例算法，使我更加深了对动态规划机制的了解。但还是对编程这方面存在不足，无法实现哈夫曼编码，在今后的学习中将不断加强自己这方面的努力。实验报告4 回溯算法一、实验目的掌握回溯法的基本思想和要素；掌握回溯法的的设计步骤；二、实验环境电脑一台，VC+ 运行环境三、实验内容、步骤和结果分析 回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的

32、方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 运用回溯法解题通常包含以下三个步骤： a. 针对所给问题，定义问题的解空间； b. 确定易于搜索的解空间结构； c. 以深度优先的方式搜索解

33、空间，并且在搜索过程中用剪枝函数避免无效搜索；下面是通过实例0-1背包问题的实现，来加深对回溯法的理解：0-1背包问题本程序是摘自网上，自身编程能力有限，无法实现这个算法。通过读这个程序的主要实现模块，大致理解了这个算法的基本思想。#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; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/当前最优解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