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

* 院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 课程名称： 算法设计与分析基础 班 号： 组 号： 指导教师： 年 月 日组员学号 姓名 实验名称 算法实验整体框架的构建 实验室实验目的或要求1. 实验题目 算法实验主菜单的设计。 2实验目的 熟悉实验环境VC6.0 ； 复习C、C+语言以及数据结构课程的相关知识，实现课程间的平滑过度；3. 实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： 算法设计与分析实验1. 算法分析基础Fibonacci序列问题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、分治法在数值问题中的应用矩阵相乘问题n);printf(ntt3、减治法在组合问题中的应用枚硬币问题n);printf(ntt4、变治法在排序问题中的应用堆排序问题n);Printf(ntt4、动态规划法在图问题中的应用全源最短路径问题n);动态规划法在图问题中的应用全源最短路径问题printf(ntt99、退出本实验n);printf(ntt);printf(ntt请输入您所要执行的操作（1，2，3，4，5，99）：);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();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序列问题实验室实验目的或要求实验题目 给定一个非负整数n，计算第n个Fibonacci数 实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同； 实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得 第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为(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; Else F00; F11;for(i=2;in-2;i+) F2=f1+f0; /f1表示当前的值 F0F1 F1F2; Return F2;程序代码int Fib(int i)if(i=0)t=f; f=Fib(i); printf(%d ,f);i+;printf(n计算机最大可表示第%d个斐波拉契数n,i);end=clock(); printf(运行时间为%f秒n,(end-start)/1000);void DieDai() long shu3,count; double start,end; start=clock(); shu0=0; shu1=1; printf(%ld ,shu0); for(count=1;shu1=shu0;count+)printf(%ld ,shu1); shu2=shu1+shu0; shu0=shu1; shu1=shu2; printf(n计算机最大可表示第%d个斐波拉契数n,count);end=clock(); printf(运行时间为%f毫秒n,end-start);void Fibonacci()printf(n迭代算法：n);DieDai();printf(n递归算法：n);DiGui(); 实验结果及分析通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。实验名称分治法在数值问题中的应用矩阵相乘问题 实验室实验目的或要求实验题目设M1和M2是两个nn的矩阵，设计算法计算M1M2 的乘积。实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）1）蛮力法求解蛮力法比较简单，直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案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 matric(int n,float ANN,float BNN,float CNN) LARGE_INTEGER startTime; LARGE_INTEGER endTime;QueryPerformanceCounter(&startTime);int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)Cij=0; for(i=0;in;i+) for(j=0;jn;j+) for(k=0;kn;k+)Cij+=Aik*Bkj;QueryPerformanceCounter(&endTime); LARGE_INTEGER totalTime; totalTime.QuadPart = endTime.QuadPart - startTime.QuadPart; printf(%ldn, totalTime.QuadPart); void MATRIX_MULTIPLY(float AN,float BN,float CN) /按通常的矩阵乘法计算C=AB的子算法(仅做2阶) int i,j,t; for(i=0;iC for(j=0;j2;j+) Cij=0; /计算完一个Cij，Cij应重新赋值为零 for(t=0;tZ int i,j; for(i=0;in;i+) for(j=0;jZ int i,j; for(i=0;in;i+) for(j=0;jn;j+) Zij=Xij-Yij;void STRASSEN(int n, float AN, float BN, float CN) float A11NN, A12NN, A21NN, A22NN; float B11NN, B12NN, B21NN, B22NN; float C11NN, C12NN, C21NN, C22NN; float m1NN, m2NN,m3NN, m4NN, m5NN, m6NN,m7NN; float AANN, BBNN, MM1NN,MM2NN; int i, j; if (n=2) MATRIX_MULTIPLY(A, B, C); else for (i=0; in/2; i+) for (j=0; jn/2; j+) A11ij = Aij; A12ij = Aij+n/2; A21ij = Ai+n/2j; A22ij = Ai+n/2j+n/2; B11ij = Bij; B12ij = Bij+n/2; B21ij = Bi+n/2j; B22ij = Bi+n/2j+n/2; MATRIX_ADD(n/2, A11, A22, AA); MATRIX_ADD(n/2, B11, B22, BB); STRASSEN(n/2, AA, BB, m1); MATRIX_ADD(n/2, A21, A22, AA); STRASSEN(n/2, AA, B11, m2); MATRIX_SUB(n/2, B12, B22, BB); STRASSEN(n/2, A11, BB, m3); MATRIX_SUB(n/2, B21, B11, BB); STRASSEN(n/2, A22, BB, m4); MATRIX_ADD(n/2, A11,A12, AA); STRASSEN(n/2, AA, B22, m5); MATRIX_SUB(n/2, A21, A11, AA); MATRIX_ADD(n/2, B11, B12, BB); STRASSEN(n/2, AA, BB, m6); MATRIX_SUB(n/2, A12, A22, AA); MATRIX_ADD(n/2, B21, B22, BB); STRASSEN(n/2, AA, BB, m7); MATRIX_ADD(n/2, m1, m4, MM1); MATRIX_SUB(n/2, m5, m7, MM2); MATRIX_SUB(n/2, MM1, MM2, C11); MATRIX_ADD(n/2, m3, m5, C12); MATRIX_ADD(n/2, m2, m4, C21); MATRIX_ADD(n/2, m1, m3, MM1); MATRIX_SUB(n/2, m2, m6, MM2); MATRIX_SUB(n/2, MM1, MM2, C22); for (i=0; in/2; i+) for (j=0; jn/2; j+) Cij = C11ij; Cij+n/2 = C12ij; Ci+n/2j = C21ij; Ci+n/2j+n/2 = C22ij; / else finished void SHUru(int n,float ANN,float BNN)int i,j;printf(请输入A数据：n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%f,&Aij); printf(请输入B数据：n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%f,&Bij); void SHUIji(int n,float ANN,float BNN)int i,j;for(i=0;in;i+)for(j=0;jn;j+)Aij=(float)(n*rand()/(RAND_MAX+1.0) ; printf(数组A中数据为：n);for(i=0;in;i+) for(j=0;jn;j+)printf(%4f ,Aij); printf(n); for(i=0;in;i+)for(j=0;jn;j+)Bij=(float)(n*rand()/(RAND_MAX+1.0) ; printf(数组B中数据为：n);for(i=0;in;i+) for(j=0;jn;j+)printf(%4f ,Bij); printf(n); void print1(int n,float CNN)int i ,j;printf(结果数组C中数据为：n); for(i=0;in;i+) for(j=0;jn;j+)printf(%4f ,Cij); printf(n); void Jz() int n;float ANN,BNN,CNN;int i,j;printf(本程序用于计算M1M2 的乘积n);printf(输入矩阵阶数n:n);scanf(%d,&n);char flag; for(i=0;in;i+)for(j=0;j1) if(coinl=coin1) printf(第%d枚硬币是假的，它的重量是%d。,h,coinh); else printf(第%d枚硬币是假的，它的重量是%d。,l,coinl); else if(hn) if(coinh=coinn) printf(第%d枚硬币是假的，它的重量是%d。,l,coinl); else printf(第%d枚硬币是假的，它的重量是%d。,h,coinh); elseif(lh) ps=(h-l+1)/3; sum1=0; sum2=0; for(i=1;i=ps;i+) sum1+=coinl+i-1; sum2+=coinh-i+1; if(sum1=sum2) FakeCoin_1(coin,n,l+ps,h-ps); else if(sum1=coinl+ps*ps) FakeCoin_1(coin,n,h-ps+1,h); else FakeCoin_1(coin,n,l,l+ps-1);void FakeCoin()int i=1,n, coin100; printf(请输入硬币的个数: );scanf(%d,&n); printf(请输入硬币的重量:n);for(i=1;i0;i-) k=i; v=hk; heap=0; while(heap=0)&(2*k=n) j=2*k; if(jn) if(hjhj) heap=1; else hk=hj; k=j; hk=v; void Dui() int aM,i,n,m,t,choice; printf(输入要排序的个数n：);scanf(%d,&n);while(1)printf(n 1.自动生成 2.手动输入 3.结束n);scanf(%d,&choice);switch(choice) case 1: for(i=1;i=n;i+) ai=rand(); printf(产生的随机数为:);for(i=1;i=n;i+) printf(%d ,ai);printf(n); ;break;case 2:printf(输入要排序的数：n);for(i=1;i1)Dui_1(a,m);for(i=1;i=n;i+)printf(%d ,ai)