《算法分析教(学)案设计实验报告(共33页).doc》由会员分享，可在线阅读，更多相关《算法分析教(学)案设计实验报告(共33页).doc（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上* 院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 课程名称： 算法设计与分析基础 班 号： 组 号： 指导教师： 年 月 日组员学号 姓名 实验名称 算法实验整体框架的构建 实验室实验目的或要求1. 实验题目 算法实验主菜单的设计。 2实验目的 熟悉实验环境VC6.0 ； 复习C、C+语言以及数据结构课程的相关知识，实现课程间的平滑过度；3. 实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： 算法设计与分析实验1. 算法分析基础Fibonacci序列问题2. 分治法在数值问题中的应用最近点对问题3. 减治
2、法在组合问题中的应用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、减治法在组合问题中的应用枚硬币问
3、题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(
4、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，计算
5、第n个Fibonacci数 实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同； 实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得 第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述
6、两种算法基本操作的执行次数；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
7、 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(); shu
8、0=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数列所用的时间，可以发现迭代法
9、的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。实验名称分治法在数值问题中的应用矩阵相乘问题 实验室实验目的或要求实验题目设M1和M2是两个nn的矩阵，设计算法计算M1M2 的乘积。实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）
10、对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）1）蛮力法求解蛮力法比较简单，直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案2）分治法求解分治法思想 将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DAC（A，B，n） If n=2 使用7次乘法的方法求得解 Else Divide（A）/把A分成4块Di
11、vide（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;QueryPerfo
12、rmanceCounter(&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
13、,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, MM
14、1NN,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); S
15、TRASSEN(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_A
16、DD(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_AD
17、D(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+)sca
18、nf(%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
19、)(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(输入矩阵阶数
20、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=
21、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; wh
22、ile(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
23、(n); ;break;case 2:printf(输入要排序的数：n);for(i=1;i1)Dui_1(a,m);for(i=1;i=n;i+)printf(%d ,ai);printf(n);t=a1;a1=am;am=t;m=m-1;for(i=1;i=n;i+) printf(%d ,ai); printf(n);printf(输出排序的结果:);for(i=1;i=n;i+)printf(%d ,ai);system(pause);实验结果及分析 经过这次实验，理解了变治法的设计思想，同时还掌握了堆的概念以及如何用变治法把任意给定的一组数据改变成堆。心得体会经过这几次的实验，对算法
24、的分析能力有了较大的提高。算法分析对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法,采用不同的分析方法。说说Fibonacci序列问题，这个实验让我们更好的理解递归算法和迭代算法的设计思想以及递归程序的调式技术，并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法。 这次实验也让我们理解了蛮力法、分治法、减治法、变治法的设计思想，提高应用蛮力法、分治法、减治法、变治法设计算法的技能。并且理解了几个重要观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。建立正角的模型对于问题的