算法实验报告(第38组)

院系：计算机科学学院专业：软件工程年级：2009级课程名称：算法设计与分析基础班号：5组号：38指导教师：邢光林2011年11月4日组员学号姓名08065019李霖08065047汪国志08065109王李健实验名称算法实验整体框架的构建实验室9#204实验目的或要求1.实验题目算法实验主菜单的设计。2．实验目的⑴熟悉实验环境VC＋＋6.0；⑵复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度；3.实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：－－－－－－－－－－－－－－－－－－－－－－－－－《算法设计与分析》实验－－－－－－－－－－－－－－－－－－－－－－－－－1.算法分析基础——Fibonacci序列问题2.分治法在数值问题中的应用——最近点对问题3.减治法在组合问题中的应用——8枚硬币问题4.变治法在排序问题中的应用——堆排序问题5.动态规划法在图问题中的应用——全源最短路径问题99.退出本实验－－－－－－－－－－－－－－－－－－－－－－－－－请输入您所要执行的操作（1，2，3，4，5，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。程序代码voidMeun(){printf(\n\t\t－－－－－－－－－－－－－－－－－－－－－－－－－\n);printf(\n\t\t《算法设计与分析》实验\n);printf(\n\t\t－－－－－－－－－－－－－－－－－－－－－－－－－\n);printf(\n\t\t1、算法分析基础——Fibonacci序列问题\n);printf(\n\t\t2、分治法在数值问题中的应用——矩阵相乘问题\n);printf(\n\t\t3、减治法在组合问题中的应用——枚硬币问题\n);printf(\n\t\t4、变治法在排序问题中的应用——堆排序问题\n);printf(\n\t\t99、退出本实验\n);printf(\n\t\t－－－－－－－－－－－－－－－－－－－－－－－－－);printf(\n\t\t请输入您所要执行的操作（，，，，，）：);}voidmain(){inta;while(1){Meun();//调用菜单函数显示菜单scanf(%d,&a);switch(a){case1:{printf(\n\t\tFibonacci序列问题\t\t\n);fibonacci();break;}case2:{printf(\n\t\t分治法在数值问题中的应用——矩阵相乘问题\t\t\n);matrix();break;}case3:{printf(\n\t\t减治法在组合问题中的应用——8枚硬币问题\t\t\n);COINFAKE();break;}case4:{printf(\n\t\t变治法在排序问题中的应用——堆排序问题\t\t\n);HEAP();break;}case5:{printf(\n\t\t动态规划法在图问题中的应用——全源最短路径问题\t\t\n);break;}case99:{printf(你选择退出本实验‘\n);exit(0);}}}}实验结果及分析实验名称算法分析基础——Fibonacci序列问题实验室9#204实验目的或要求实验题目给定一个非负整数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（intn）//输入整数n，输出第n个斐波那契数{if(n=0)return0;Elseif(n=1)return1;ElsereturnFib(n-1)+Fib(n-2)}2、迭代法这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。Fib（intn）//输入整数n，输出第n个斐波那契数{if(n=0)return0;Elseif(n=1)return1;ElseF0←0;F1←1;for(i=2;in-2;i++){F2=f1+f0;//f1表示当前的值F0←F1F1←F2;}ReturnF2;}程序代码//Fibonacci数列intFi(inti){if(i=1)returni;elsereturnFi(i-1)+Fi(i-2);}voidFn(){inti=0,j=0;do{j=Fi(i);if(j=0)printf(%d,j);++i;}while(j=0);printf(\n计算机所能计算的最大整数是第%d个fibonacci整数。\n,i-1);}voidFib(){inti=1,f[3]={0,1};printf(%d,f[0]);do{printf(%d,f[1]);f[2]=f[1]+f[0];f[0]=f[1];f[1]=f[2];i++;}while(f[1]=f[0]);printf(\n\t计算机所能表示的最大fibonacci整数是第%d个fibonacci整数。\n,i);}voidfibonacci(){doublestart;start=clock();Fib();printf(\t迭代所用时间是%lf\n\n,clock()-start);start=clock();Fn();printf(\t递归所用时间是%lf\n\n,clock()-start);}实验结果及分析通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。实验名称分治法在数值问题中的应用——矩阵相乘问题实验室9#204实验目的或要求实验题目设M1和M2是两个n×n的矩阵，设计算法计算M1×M2的乘积。实验目的1）提高应用蛮力法设计算法的技能；2）深刻理解并掌握分治法的设计思想；3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。实验要求1）设计并实现用BF方法求解矩阵相乘问题的算法；2）设计并实现用DAC方法求解矩阵相乘问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。实验原理（算法基本思想）1）蛮力法求解蛮力法比较简单，直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案2）分治法求解分治法思想将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。求解矩阵相乘的DAC算法，使用了strassen算法。DAC（A[]，B[]，n）{Ifn=2使用7次乘法的方法求得解ElseDivide（A）//把A分成4块Divide（B）//把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回}程序代码//矩阵相乘问题voidPrintIn(ArrayA,ArrayB){intn=A.n;inti,j;printf(请输入A数据：\n);for(i=0;in;i++)for(j=0;jn;j++)cinA.a[i*n+j];printf(请输入B数据：\n);for(i=0;in;i++)for(j=0;jn;j++)cinB.a[i*n+j];}voidRandomIn(ArrayA,ArrayB){intn=A.n;srand((unsigned)time(NULL));inti,j;for(i=0;in;i++)for(j=0;jn;j++)A.a[i*n+j]=rand()%10;for(i=0;in;i++)for(j=0;jn;j++)B.a[i*n+j]=rand()%10;}voidPrintOut(ArrayA){intn=A.n;inti,j;for(i=0;in;i++){for(j=0;jn;j++)coutA.a[i*n+j]'';printf(\n);}}voiddivide(Arrayd,Arrayd00,Arrayd01,Arrayd10,Arrayd11)/*分割矩阵*/{intn=d00.n;inti,j;for(i=0;in;i++){for(j=0;jn;j++){d00.a[n*i+j]=d.a[2*n*i+j];d01.a[n*i+j]=d.a[2*n*i+n+j];d10.a[n*i+j]=d.a[2*n*n+2*n*i+j];d11.a[n*i+j]=d.a[2*n*n+2*n*i+n+j];}}}Arraymerge(Arrayd00,Arrayd01,Arrayd10,Arrayd11){intn=d00.n;inti,j;Arrayd;d.a=(int*)malloc(sizeof(int)*(4*n*n));for(i=0;in;i++){for(j=0;jn;j++){d.a[2*n*i+j]=d00.a[n*i+j];d.a[2*n*i+n+j]=d01.a[n*i+j];d.a[2*n*n+2*n*i+j]=d10.a[n*i+j];d.a[2*n*n+2*n*i+n+j]=d11.a[n*i+j];}}d.n=2*n;returnd;}Arrayoperator+(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));for(inti=0;in*n;i++)C.a[i]=A.a[i]+B.a[i];C.n=A.n;returnC;}Arrayoperator-(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));for(inti=0;in*n;i++)C.a[i]=A.a[i]-B.a[i];C.n=A.n;returnC;}Arraystrassen(ArrayA,ArrayB){intn=A.n;ArrayC;C.a=(int*)malloc(sizeof(int)*(n*n));C.n=n;if(n==2){intm1,m2,m3,m4,m5,m6,m7;m1=(A.a[0]+A.a[3])*(B.a[0]+B.a[3]);m2=(A.a[2]+A.a[3])*B.a[0];m3=A.a[0]*(B.a[1]-B.a[3]);m4=A.a[3]*(B.a[2]-B.a[0]);m5=(A.a[0]+A.a[1])*B.a[3];m6=(A.a[2]-A.a[0])*(B.a[0]+B.a[1]);m7=(A.a[1]-A.a[3])*(B.a[2]+B.a[3]);C.a[0]=m1+m4-m5+m7;C.a[1]=m3+m5;C.a[2]=m2+m4;C.a[3]=m1+m3-m2+m6;returnC;}else{n=n/2;Arraya00,a01,a10,a11;Array