算法实验报告(第38组)(共24页)

1、精选优质文档-倾情为你奉上 院 系： 计算机科学学院 专 业： 软件工程 年 级： 2009级 课程名称： 算法设计与分析基础 班 号： 5 组 号： 38 指导教师： 邢光林 2011年 11 月 4 日组员学号 姓名 李霖 汪国志 王李健实验名称 算法实验整体框架的构建 实验室9#204实验目的或要求1. 实验题目 算法实验主菜单的设计。 2实验目的 熟悉实验环境VC6.0 ； 复习C、C+语言以及数据结构课程的相关知识，实现课程间的平滑过度；3. 实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： 算法设计与分析实验1. 算法分析基础Fibon

2、acci序列问题2. 分治法在数值问题中的应用最近点对问题3. 减治法在组合问题中的应用8枚硬币问题4. 变治法在排序问题中的应用堆排序问题5. 动态规划法在图问题中的应用全源最短路径问题99. 退出本实验 请输入您所要执行的操作（1，2，3，4，5，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。程序代码void Meun()printf(nttn);printf(ntt 算法设计与分析实验n);printf(nttn);printf(ntt1、算法分析基础Fibonacci序列问题n);printf(ntt2、分治法在数值问题中的应用矩阵相

3、乘问题n);printf(ntt3、减治法在组合问题中的应用枚硬币问题n);printf(ntt4、变治法在排序问题中的应用堆排序问题n);printf(ntt99、退出本实验n);printf(ntt);printf(ntt请输入您所要执行的操作（，）：);void main()int a; while(1)Meun(); /调用菜单函数显示菜单 scanf(%d,&a);switch(a)case 1:printf(nttFibonacci序列问题ttn);fibonacci(); break;case 2:printf(ntt分治法在数值问题中的应用矩阵相乘问题ttn);matrix()

4、;break;case 3:printf(ntt减治法在组合问题中的应用8枚硬币问题ttn);COINFAKE(); break;case 4: printf(ntt变治法在排序问题中的应用堆排序问题ttn); HEAP(); break; case 5:printf(ntt动态规划法在图问题中的应用全源最短路径问题ttn); break;case 99: printf(你选择退出本实验n ); exit(0); 实验结果及分析实验名称算法分析基础Fibonacci序列问题实验室9#204实验目的或要求实验题目 给定一个非负整数n，计算第n个Fibonacci数 实验目的1）理解递归算法和迭代

5、算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同； 实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得 第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进

6、，使得改进后的迭代算法其空间复杂度为(1)；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。 实验原理（算法基本思想）1、递归法基本思想递归就是定义一个函数，让它自己调用自己。Fib（int n）/输入整数n，输出第n个斐波那契数if(n=0)return 0; Else if(n=1)return 1; Else return Fib(n-1)+Fib(n-2)2、迭代法这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。Fib（int n）/输入整数n，输出第n个斐波那契数if(n=0)return 0; Else if(n=1)return 1; Els

7、e F00; F11;for(i=2;in-2;i+) F2=f1+f0; /f1表示当前的值 F0F1 F1F2; Return F2;程序代码/Fibonacci数列int Fi(int i)if(i=0)printf(%d ,j);+i;while(j=0);printf(n计算机所能计算的最大整数是第%d个fibonacci整数。n,i-1);void Fib() int i=1,f3=0,1;printf(%d ,f0);doprintf(%d ,f1);f2=f1+f0;f0=f1;f1=f2;i+;while(f1=f0);printf(nt计算机所能表示的最大fibonacci

8、整数是第%d个fibonacci整数。n,i);void fibonacci()double start;start=clock();Fib();printf(t迭代所用时间是%lf nn,clock()-start);start=clock();Fn();printf(t递归所用时间是%lf nn,clock()-start);实验结果及分析通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。实验名称分治法在数值问题中的应用矩阵相乘问题 实验室9#204实验目的或要

9、求实验题目设M1和M2是两个nn的矩阵，设计算法计算M1M2 的乘积。实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）1）蛮力法求解蛮力法比较简单，

10、直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案2）分治法求解分治法思想 将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DAC（A，B，n） If n=2 使用7次乘法的方法求得解 Else Divide（A）/把A分成4块Divide（B）/把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回程序代码/矩阵相乘问题void PrintIn(Array A,Array B)int

11、n=A.n;int i,j;printf(请输入A数据：n);for(i=0;in;i+) for(j=0;jA.ai*n+j; printf(请输入B数据：n);for(i=0;in;i+) for(j=0;jB.ai*n+j;void RandomIn(Array A,Array B)int n=A.n;srand(unsigned)time(NULL);int i,j;for(i=0;in;i+)for(j=0;jn;j+)A.ai*n+j=rand()%10;for(i=0;in;i+) for(j=0;jn;j+) B.ai*n+j=rand()%10;void PrintOut(A

12、rray A) int n=A.n;int i,j;for(i=0;in;i+) for(j=0;jn;j+) coutA.ai*n+j ; printf(n); void divide(Array d,Array d00,Array d01,Array d10,Array d11) /*分割矩阵*/int n=d00.n; int i,j; for(i=0;in;i+) for(j=0;jn;j+) d00.an*i+j=d.a2*n*i+j; d01.an*i+j=d.a2*n*i+n+j; d10.an*i+j=d.a2*n*n+2*n*i+j; d11.an*i+j=d.a2*n*n+

13、2*n*i+n+j; Array merge(Array d00,Array d01,Array d10,Array d11) int n=d00.n; int i,j; Array d; d.a=(int *)malloc(sizeof(int)*(4*n*n); for(i=0;in;i+) for(j=0;jn;j+) d.a2*n*i+j=d00.an*i+j; d.a2*n*i+n+j=d01.an*i+j; d.a2*n*n+2*n*i+j=d10.an*i+j; d.a2*n*n+2*n*i+n+j=d11.an*i+j; d.n=2*n; return d;Array oper

14、ator +(Array A,Array B)int n=A.n;Array C;C.a=(int *)malloc(sizeof(int)*(n*n);for(int i=0;in*n;i+)C.ai=A.ai+B.ai;C.n=A.n;return C;Array operator -(Array A,Array B)int n=A.n;Array C;C.a=(int *)malloc(sizeof(int)*(n*n);for(int i=0;in*n;i+)C.ai=A.ai-B.ai;C.n=A.n;return C;Array strassen(Array A,Array B)

15、int n=A.n; Array C; C.a=(int *)malloc(sizeof(int)*(n*n); C.n=n; if(n=2) int m1,m2,m3,m4,m5,m6,m7; m1=(A.a0+A.a3)*(B.a0+B.a3); m2=(A.a2+A.a3)*B.a0; m3=A.a0*(B.a1-B.a3); m4=A.a3*(B.a2-B.a0); m5=(A.a0+A.a1)*B.a3; m6=(A.a2-A.a0)*(B.a0+B.a1); m7=(A.a1-A.a3)*(B.a2+B.a3); C.a0=m1+m4-m5+m7; C.a1=m3+m5; C.a2

16、=m2+m4; C.a3=m1+m3-m2+m6; return C; else n=n/2; Array a00,a01,a10,a11; Array b00,b01,b10,b11; Array c00,c01,c10,c11; Array s1,s2,s3,s4,s5,s6,s7; a00.a=(int *)malloc(sizeof(int)* (n*n);a00.n=n; a01.a=(int *)malloc(sizeof(int)* (n*n);a01.n=n; a10.a=(int *)malloc(sizeof(int)* (n*n);a10.n=n; a11.a=(int

17、*)malloc(sizeof(int)* (n*n);a11.n=n; b00.a=(int *)malloc(sizeof(int)* (n*n);b00.n=n; b01.a=(int *)malloc(sizeof(int)* (n*n);b01.n=n; b10.a=(int *)malloc(sizeof(int)* (n*n);b10.n=n; b11.a=(int *)malloc(sizeof(int)* (n*n);b11.n=n; divide(A,a00,a01,a10,a11); divide(B,b00,b01,b10,b11); s1=strassen(a00+a

18、11,b00+b11);s2=strassen(a10+a11,b00); s3=strassen(a00,b01-b11); s5=strassen(a00+a01,b11); s4=strassen(a11,b10-b00); s6=strassen(a10-a00,b00+b01); s7=strassen(a01-a11,b10+b11); c00=s1+s4-s5+s7; c01=s3+s5; c10=s2+s4; c11=s1+s3-s2+s6; C=merge(c00,c01,c10,c11); return C; Array mul(Array A,Array B) /普通的矩

19、阵乘法计算int n=A.n;Array C;C.a=(int *)malloc(sizeof(int)*(n*n);C.n=n; int i,j,k; for(i=0;in;i+) for(j=0;jn;j+) C.ai*n+j=0; for(k=0;kn; A.a=(int *)malloc(sizeof(int)* (n*n);A.n=n; B.a=(int *)malloc(sizeof(int)* (n*n);B.n=n; C.a=(int *)malloc(sizeof(int)* (n*n); C.n=n; printf(tt-1 手动输入-n); printf(tt-2 随机生

20、成-n); printf(tt请选择nn); ch=getch();switch(ch) case 1: printf(手动输入n); PrintIn(A,B); printf(n); break; case 2: printf(自动生成n); RandomIn(A,B); break; default:printf(按键错误n);break; printf(结果数组A中数据为：n); PrintOut(A); printf(结果数组B中数据为：n); PrintOut(B); cout1)if(Bl=B1)printf(硬币%d 是假币n,h);elseprintf(硬币%d 是假币n,l)

21、; else if(hn) if(Bh=Bn) printf(硬币%d 是假币n,l); else printf(硬币%d 是假币n,h);elseif(lh)ps=(h-l+1)/3;sum1=0;sum2=0;for(int i=1;i=ps;i+)sum1+=Bl+i-1;sum2+=Bh-i+1;if(sum1=sum2)FakeCoin(B,n,l+ps,h-ps);elseif(sum1=Bl+ps*ps)FakeCoin(B,n,h-ps+1,h); elseFakeCoin(B,n,l,l+ps-1);void COINFAKE()int BN,n;printf(n请输入硬币总

22、数n:);scanf(%d,&n);printf(n请输入n个数字：);for(int i=1;i=n;i+)scanf(%d,&Bi);for(i=1;i=n;i+)printf(%d ,Bi);printf(n); FakeCoin(B,n,1,n);实验结果及分析通过这个实验，理解并掌握了减治法的设计思想并理解了它与分治法的区别。在写这个算法前，一定要建立正确的求解模型。实验名称变治法在排序问题中的应用堆排序问题实验室9#204实验目的或要求实验题目用基于变治法的堆排序算法对任意一组给定的数据进行排序实验目的1）深刻理解并掌握变治法的设计思想；2）掌握堆的概念以及如何用变治法把任意给定的

23、一组数据改变成堆；3）提高应用变治法设计算法的技能。 实验要求1）设计与实现堆排序算法；2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，15003000个数据左右），用以检验(用计数法)堆排序算法的时间效率。实验原理（算法基本思想）堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想（2）大根堆排序算法的基本操作特点:堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将Rl.n看成是一棵完全

24、二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。它是不稳定的排序方法。程序代码/堆排序void in(int hN,int n)int i;printf(手动输入要排序的数：);for(i=1;i=n;i+)scanf(%d,&hi);void random(int hN,int n)int i; for(i=1;i=n;i+)hi=rand(); printf(随机产生要排序的数如下所示:n); for(i=1;i0;i-)

25、k=i; v=hk; heap=0; while(heap=0)&(2*k=n)j=2*k;if(jn)if(hjhj)heap=1;elsehk=hj;k=j;hk=v;void HEAP()int hN=0,i,n,elem,m; double start, finish; char ch= ; printf(ntt输入要排序的数的规模：);scanf(%d,&n); printf(n-1 手动输入-n); printf(-2 自动生成-n); printf(请选择:);doch=getch();if(ch=1)in(h,n);if(ch=2)random(h,n);elseprintf(n输入出错，请重输：);while(ch!=1&ch!=2);start=clock();m=n;while(m1) HeapBottomUp(h,m); /for(i=1;i=n;i+) /p