算法设计及分析实验报告.doc

《算法设计及分析实验报告.doc》由会员分享，可在线阅读，更多相关《算法设计及分析实验报告.doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .院 系： 计算机科学学院 专 业：年 级：课程名称： 算法设计与分析根底 班 号：组 号：指导教师：年 月 日组员学号XX实验名称 算法分析根底给定一个非负整数n，计算第n个Fibonacci数实验室实验目的或要求一 实验目的1理解递归算法和迭代算法的设计思想以及递归程序的调式技术2)握并应用递归算法和迭代算法效率的理论分析(前验分析)和经历分析(后验分析)法；3)理解这样一个观点：不同的算法可以解决一样的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；二实验要求1使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大

2、整数，并给出具体的执行时间；2对于要求1),使用教材2.5节中介绍的递归算法F(n)进展计算,同样给出具体的执行时间，并同1)的执行时间进展比较；3对于输入同样的非负整数n，比较上述两种算法根本操作的执行次数；4对1)中的迭代算法进展改进，使得改进后的迭代算法其空间复杂度为(1)；5设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理算法基本思想一 迭代算法求最大Fibonacci在数列中位置1.先利用迭代求得计算机能表示的最大数MaxUnsignedInt.unsigned long int MaxUnsignedInt = 1;while ( MaxUnsignedInt*2+

3、1 != MaxUnsignedInt ) MaxUnsignedInt=MaxUnsignedInt*2+1;2. 从1起进展(n-1) +( n-2) = n迭代，直到条件(temp3temp)时发生溢出(及超过最大数)，退出循环。求得此时的迭代次数-1即为最大Fibonacci的位置。unsigned long int n=MaxUnsignedInt;for( i=1; temp=n; i+ )/temptemp)/当temp3temp时，那么发现temp发生溢出，完毕计算break;temp3=temp;temp2=temp1;temp1=temp;二 递归算法1. 根据 / 0 n

4、=0f(n)= 1 n=1 f(n-1)+f(n-2) n=2进展递归调用求解。long FF(unsigned int tt)/use di gui if( tt = 1 )return tt;elsereturn FF(tt-1) + FF(tt-2);三改进空间复杂度为(1)。利用公式：F(n)=(1/5)*(1+5)/2n - (1-5)/2nint fib(int n) double gh5=sqrt(double)5); return (pow(1+gh5),n)-pow(1-gh5),n)/(pow(double)2,n)*gh5); 程序代码void fibo()unsigne

5、d long int MaxUnsignedInt,n,times,t=100;clock_t start = clock();MaxUnsignedInt=1;while ( MaxUnsignedInt*2+1 != MaxUnsignedInt ) MaxUnsignedInt=MaxUnsignedInt*2+1;cout时间消耗：clock() - startendl;n=MaxUnsignedInt;int choose;bool end_this=true;while(end_this)cout*n;cout1. 输入一个你想要判断的数 n;cout2. 判断从0到N的Fibon

6、acci n;cout3. 计算机能判断的最大数 n;cout4. 用递归计算你想要判断的数 n;cout5. 完毕 n;again: coutchoose;if( choose!=1 & choose!=2 & choose!=3 & choose!=4 )/输入菜单检查cout输入错误n;goto again;switch (choose)case 1:coutt;start = clock();times=F(t);coutt是第times个Fibonacci数endl;cout时间消耗：clock() - startendl;break;case 2:start = clock();F

7、(t);cout时间消耗：clock() - startendl;break;case 3:cout最大数是nendl;/times=F(n);start = clock();unsigned long int temp=1,temp1=0,temp2=1,temp3=temp;int i;for( i=1; temp=n; i+ )/temptemp)/当temp3temp时，那么发现temp发生溢出，完毕计算break;temp3=temp;temp2=temp1;temp1=temp;coutn是第i-1个Fibonacci数endl;cout时间消耗：clock() - starten

8、dl;break;case 4:start = clock();int x;coutx;times=FF(x);cout第x个Fibonacci数是timesendl;cout时间消耗：clock() - startendl;break;case 5:end_this=false;break;int F(unsigned int uu)unsigned long int temp=0,temp1=0,temp2=1; int i;/if(uu=0|uu=1)/return uu;for( i=1; i=uu; i+ )temp = temp1 + temp2 ;coutnumberiistem

9、p=uu)return i;temp2 = temp1 ;temp1 = temp ;return 0;long FF(unsigned int tt)/use di gui if( tt = 1 )return tt;elsereturn FF(tt-1) + FF(tt-2);int fib(int n) double gh5=sqrt(double)5); return (pow(1+gh5),n)-pow(1-gh5),n)/(pow(double)2,n)*gh5); 实验结果及分析1. 求最大数2. 递归法与迭代法性能比较递归 迭代3. 改进算法1. 利用公式法对第n项Fibona

10、cci数求解时可能会得出错误结果。主要原因是由于double类型的精度还不够，所以程序算出来的结果会有误差，要把公式展开计算。2. 由于递归调用栈是一个费时的过程，通过递归法和迭代法的比较说明，虽然递归算法的代码更精简更有可读性，但是执行速度无法满足大数问题的求解。3. 在当前计算机的空间较大的情况下，在一些速度较慢的问题中，空间换时间是一个比较全的策略。实验名称分治法在数值问题中的应用矩阵相乘问题实验室实验目的或要求一 实验题目设M1和M2是两个nn的矩阵，设计算法计算M1M2 的乘积。二 实验目的1提高应用蛮力法设计算法的技能；2深刻理解并掌握分治法的设计思想；3理解这样一个观点：用蛮力法

11、设计的算法，一般来说，经过适度的努力后，都可以对其进展改进，以提高算法的效率。 三实验要求1设计并实现用BF法求解矩阵相乘问题的算法；2设计并实现用DAC法求解矩阵相乘问题的算法；3以上两种算法的输入既可以手动输入，也可以自动生成；4对上述两个算法进展时间复杂性分析，并设计实验程序验证 分析结果；5设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理算法基本思想定义：假设 A=(aij), B=(bij) 是 nn的阵，那么对i,j=1,2,n，定义乘积 C=AB中的元素 cij 为：1. 分块解法通常的做法是将矩阵进展分块相乘，如以下图所示：二 Strassen解法分治法思想 将

12、问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DACA，B，nIf n=2 使用7次乘法的法求得解ElseDivideA/把A分成4块DivideB/把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回伪代码Serial_StrassenMultiply(A, B, C) T1 = A0 + A3; T2 = B0 + B3; StrassenMultiply(T1, T2, M1); T1 = A

13、2 + A3; StrassenMultiply(T1, B0, M2); T1 = (B1 - B3); StrassenMultiply (A0, T1, M3); T1 = B2 - B0; StrassenMultiply(A3, T1, M4); T1 = A0 + A1; StrassenMultiply(T1, B3, M5); T1 = A2 A0; T2 = B0 + B1; StrassenMultiply(T1, T2, M6); T1 = A1 A3; T2 = B2 + B3; StrassenMultiply(T1, T2, M7); C0 = M1 + M4 -

14、M5 + M7 C1 = M3 + M5 C2 = M2 + M4 C3 = M1 - M2 + M3 + M6程序代码/矩阵相乘问题void PrintIn(Array A,Array B)int 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+

15、)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(Array 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+) d0

16、0.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+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*

17、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 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 operator -(Array A,Array B)int n=A.n;Array C;C.a=(int *)malloc(sizeof(int

18、)*(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) 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;

19、 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=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 *)mall

20、oc(sizeof(int)* (n*n);a01.n=n; a10.a=(int *)malloc(sizeof(int)* (n*n);a10.n=n; a11.a=(int *)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(in

21、t)* (n*n);b11.n=n; divide(A,a00,a01,a10,a11); divide(B,b00,b01,b10,b11); s1=strassen(a00+a11,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

22、+s4; c11=s1+s3-s2+s6; C=merge(c00,c01,c10,c11);return C; Array mul(Array A,Array B) /普通的矩阵乘法计算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.

23、n=n; C.a=(int *)malloc(sizeof(int)* (n*n); C.n=n; printf(tt-1 手动输入-n); printf(tt-2 随机生成-n); printf(tt请选择nn); ch=getch();switch(ch) case1: printf(手动输入n); PrintIn(A,B); printf(n);break;case2: printf(自动生成n); RandomIn(A,B); break;default:printf(按键错误n);break; printf(结果数组A中数据为：n); PrintOut(A); printf(结果数组

24、B中数据为：n); PrintOut(B); coutendl; do double start, finish,duration; printf(n-1 用BF法-n); printf(-2 用DAC法-n); printf(-3 退出 -n); printf(n请选择:); ch=getch();switch(ch) case1: start = clock(); C=mul(A,B); finish = clock(); duration = (double)(finish - start); printf(n用BF法得出的结果n); PrintOut(C); printf( 用BF法计

25、算矩阵所花费的时间是：%f msn, duration ); printf(n);break;case2: start = clock(); C=strassen(A,B); finish = clock(); duration = (double)(finish - start); printf(用DAC法得出的结果n); PrintOut(C); printf( DAC法计算矩阵所花费的时间是：%f msn, duration ); printf(n);break;case3: exit(0);default: printf(按键错误n); printf(n 你想用另外一种法吗？请输入(Y

26、/N)?：);do ch=getch(); while(ch!=Y&ch!=y&ch!=N&ch!=n); while(ch=Y|ch=y);实验结果及分析时间复杂度1.分块相乘总共用了8次乘法，因而需要 (nlog28) 即 (n3) 的时间复杂度。2.在求解M1，M2，M3，M4，M5，M6，M7时需要使用7次矩阵乘法，其他都是矩阵加法和减法。因此时间复杂度下降为 O(nlog27)=O(n2.807) 。有得必有失，Strassen演算法的数值稳定性较差。实验名称减治法在组合问题中的应用8枚硬币问题实验室实验目的或要求二 实验目的1深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2

27、提高应用减治法设计算法的技能。3理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。二实验要求1设计减治算法实现8枚硬币问题；2设计实验程序，考察用减治技术设计的算法是否高效；3扩展算法，使之能处理n枚硬币中有一枚假币的问题。实验原理算法基本思想减治法原理 假币问题程序代码void fake_coin()int a100;int i,n,p; printf(please input n:);scanf(%d,&n);for(i=0;in;i+) coutaiai; p=check_coin_2(a,0,n-1); /printf(the false coin is %dn,p);cou

28、tthe false coin is pendl;int sum_coin(int a,int from,int to) int i,sum=0; for(i=from;i=to;i+) sum+=ai; return sum; int check_coin_2(int a,int from,int to) int i,n=to-from+1;if(n=1) return from;else if(n%2=0) if(sum_coin(a,from,from+n/2-1)=sum_coin(a,to-n/2+1,to) return from-1;else if(sum_coin(a,from

29、,from+n/2-1)sum_coin(a,to-n/2+1,to) check_coin_2(a,from,from+n/2-1); else check_coin_2(a,to-n/2+1,to); else check_coin_2(a,from+1,to); 实验结果及分析实验结果正确，能够在N枚硬币问题条件下准确查找假币在什么位置。通过硬币问题，让我更加理解了减治法的使用，让我对减治法有了更深的理解，对于以后的编程思想有了更深的研究实验名称变治法在排序问题中的应用堆排序实验室9#204实验目的或要求三 实验目的1深刻理解并掌握变治法的设计思想；2掌握堆的概念以及如用变治法把任意给定

30、的一组数据改变成堆；3提高应用变治法设计算法的技能。二实验要求1设计与实现堆排序算法；2待排序的数据可以手工输入(通常规模比较小，10个数据左右，用以检测程序的正确性；也可以计算机随机生成通常规模比较大，15003000个数据左右，用以检验(用计数法)堆排序算法的时间效率。实验原理算法基本思想1)将初始待排序关键字序列(R1,R2.Rn)构建成大顶堆，此堆为初始的无须区； 2)将堆顶元素R1与最后一个元素Rn交换，此时得到新的无序区(R1,R2,.Rn-1)和新的有序区(Rn),且满足R1,2.n-1=Rn; 3)由于交换后新的堆顶R1可能违反堆的性质，因此需要对当前无序区(R1,R2,.Rn

31、-1)调整为新堆，然后再次将R1与无序区最后一个元素交换，得到新的无序区(R1,R2.Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，那么整个排序过程完成。建堆实验原理例图程序代码void HeapSort() int A50;int i,temp,n;coutn;for(i=1;i=n;i+)coutinput AiAi;for(i=n/2;i=1;i-)FixHeap(A,i,Ai,n);for(i=n;i=2;i-)temp=A1;A1=Ai;Ai=temp;FixHeap(A,1,A1,i-1);cout排序结果为：;for(i=1;i=n;i+)

32、 coutAi ;coutendl;void FixHeap(int A,int index,int value,int size)int valueindex=index,childindex;while(2*valueindex=size)childindex=2*valueindex;if(childindexsize&Achildindex=Achildindex) goto a;elseAvalueindex=Achildindex; valueindex=childindex;a: Avalueindex=value;实验结果及分析实验结果截图因为需要调堆的是堆顶元素，所以运行时间是O(h) = O(floor(logn)。所以循环调堆的运行时间为O(nlogn)。总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。心得体会成绩评定教师签名： 年 月 日教育之通病是教用脑的人不用手，不教用手的人用脑，所以