《算法设计及实验报告》由会员分享，可在线阅读，更多相关《算法设计及实验报告（14页珍藏版）》请在金锄头文库上搜索。
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;阶乘的递归式很快，是个线性时间，因此在最坏情况下时间复杂度为 O(n)。2. Fibona
2、cci 数列：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-l)+T(n-2)+0(l)的操作，也就是 T(n)=2T(n)+0(l),由 递归方程式可以知道他的时间复杂度T(n)是0(2n),该数列的规律就是不停的赋 值，使用的内存空间也随着函数调用栈的增长而增长。3. 二分查找(分治法) #include#define const 8main()int a=0
3、,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(leftamiddle) left=middle+1;else right=middle-1;return -1; 二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行 一次while循环，数组大小减少一半，因此在最坏情况下，
4、while循环被执行了O (logn)次。而循环体内部只需运算0 (1)的时间，因此该算法在最坏情况下 的时间复杂度为0 (logn+1)，即0(logn)。4. 合并排序(分治法)MergeSor t(in t low,i nt high ,int *array)int middle=(high+low)/2; /将数组划分为2分 if(lowhigh)MergeSort(low,middle,array); /对前一部分进行递归处理 MergeSort(middle+1,high,array); /对后一部分进行递归处理 HeBing(low,middle,middle+1,high,ar
5、ray); /将排序后的,前后两部分,进行合并return true;HeBing(int low1,int high1,int low2,int high2,int *array) int *temp,i=low1,j=low2,k=0;temp=(int *)malloc(high2Tow1+1)*sizeof(int); /temp 用于临时存储 合并后的数组while(i=high1&j=high2)/对两个有序数组进行合并 if(arrayiarrayj)tempk+=arrayi;i+;elsetempk+=arrayj;j+;if(i=high1)while(i=high1)te
6、mpk+=arrayi+;elsewhile(j=high2)tempk+=arrayj+;for(i=low1,j=0;i=high2;i+,j+)将合并后的数组,复制到array中arrayi=tempj;free (temp);return true; 这是一种分治算法。是先进行长度为1的排序，再合并成长度为2的排序， 递归直到长度为n。而快速排序是先进行划分，然后排序，不需要额为的空 间，合并排序需要N的额外空间。是一种稳定的排序。将数组划分为小数细 通过局部的有序合并,解决问题。算法平均时间复杂度: O(nlogn)递归算法的时间复杂度求法：用通用公式：T(n)=fT (n-1) f
7、(X)是递归函数的时间复查性函数! 如下面这个简单递归是：void Digui()1-；/*假设该语句的复查性是a*/2;/*假设该语句的复查性是b*/for()/*循环 M 次*/-；/*假设该语句的复查性是c*/Digui()；由上分析，它的时间复杂性计算公式是：T(n)=a+b+M*T(n-1);另外，求算法的运行时间，可通过上一个实验那种方法，嵌入那个求时间的算法 即可求出运行时间!四总结通过本次实验，使我了解了递归算法的思想，以及掌握对该算法复杂度的分析。 对递归算法的几个典型实例算法进行了程序语言实现，使我更加掌握了递归算法 的内涵，同时也初步掌握了分治法的基本思想。相比与第一次实
8、验，对算法的分 析方面，显得更加深入理解!往后的学习中再强化深入。实验报告 2 动态规划一、实验目的掌握动态规划算法的基本思想和要素；掌握该算法的的设计步骤；二、实验环境电脑一台， VC+ 运行环境三、实验内容、步骤和结果分析以下通过动态规划的两个实例应用算法来加深对动态规划算法的理解： 自身编程能力有限，此实现程序引用网上资料.1. 矩阵连乘问题给定n个矩阵A,A,-,A，其中A与A】是可乘的，i=l,2,n-1。考察 这n个矩阵的连乘积AAA。由于矩阵乘法满足结合律，故计算矩阵的连乘积1 2 n可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个 矩阵连乘积的计算次序完全
9、确定，则可以依此次序反复调用2个矩阵相乘的标准 算法(有改进的方法，这里不考虑)计算出矩阵连乘积。若A是一个pXq矩阵, B是一个qXr矩阵，则计算其乘积C=AB的标准算法中，需要进行pqr次数乘。F面使用动态规划法找出矩阵连乘积的最优计算次序。 void Matr ixChain (int *p,i nt n,int *m,i nt *s) for(int i=l;i二n;i+)mii=0;/单个矩阵相乘，所需数乘次数/以下两个循环是关键之一，以个数组为例(为描述方便，mij用j代替) /需按照如下次序计算/01122334 45/02132435/031425/0415/05/下面行的计算
10、结果将会直接用到上面的结果。例如要计算13,就会用到12和23。 for(int r=2;r二n;r+)for(int i=1;in-r+1;i+) int j二i+rT;/首先在i断开，即(A*(A .A)ii+1jmij=mi+1j+ +piT*pi*pj;sij=i;for(int k=i+1;kj;k+)/然后在k (从i+1开始遍历到j-1)断开，即(A.A)*(A .A )ikk+1jint t =mik+mk+1j+pi-1* pk* p j;if( tmij)/找到更好的断开方法mij= t; /记录最少数乘次数sij=k;/记录断开位置/Traceback打印Ai:j的加括号
11、方式void Traceback(i nt 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);/递归打印 Asij+1:j的加括号方式/能走到这里说明i等于sij，sij+1等于j/也就是说这里其实只剩下两个矩阵，不必再分了coutAi和 A(sij+1)相乘endl; int _tmain(int argc, _TCHAR* argv) int n=6;/矩阵的个数int
12、*p=new intn+1;/p0：第一个矩阵的行数/p1：第一个矩阵的列数，第二个矩阵的行数/p2:第二个矩阵的列数，第三个矩阵的行数p0=30;讥1=35;p2=15;p3=5;p4=10;讥5=20;讥6=25;int *m,*s;m二new int*n;for( int i=O;in;i+)mi=new intn;s=new int*n;for(int i=O;in;i+)si=new intn;Matr ixChain(p,n,m,s);Traceback(O,nT,s);for(int i=O;in;i+) dele te mi;mi=NULL;dele te si;si=NULL
13、; dele te m;m=NULL;dele te s;s = NULL;dele te p;p = NULL;return 0;算法复杂度分析：算法matrixChain的主要计算量取决于算法中对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=(wnTc)?wnT:c;for(i=0;i二jMax;i+)mni=0;for(i=wn;i二c;i+)mni=vn;for(i二nT;il;i) jMa
