算法设计实验报告

院系：计算机科学学院专业：计算机科学与技术年级：2010级课程名称：算法设计与分析基础班号：组号：3指导教师：邢光林2012年12月30日1组员学号姓名实验名称算法实验整体框架的构建实验室9#205实验目的或要求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）可以反复执行，直到退出实验。2程序代码voidmenu();intmain(){FibonaccifibonacciImpl;HeapsortheapsortImpl;MartrixmartrixImpl;ThecointhecoinImpl;intchose;menu();cinchose;while(chose!=99){switch(chose){case1:{fibonacciImpl.fib1();coutendl;fibonacciImpl.fib2();break;}case2:{martrixImpl.martrix();break;}case3:{thecoinImpl.Fake_coin();break;}case4:{heapsortImpl.heapsort();break;}case5:{break;}default:cout请按序号输入操作endl;}menu();cinchose;}return0;}voidmenu(){cout---------------------------------------endl;cout《《算法设计与分析》》实验endl;cout---------------------------------------endl;cout1.算法分析基础——Fibonacci序列问题endl;cout2.分治法在数值问题中的应用——矩阵相乘问题endl;cout3.减治法在组合问题中的应用——8枚硬币问题endl;cout4.变治法在排序问题中的应用——堆排序问题endl;cout5.动态规划法在图问题中的应用——全源最短路径问题endl;cout99.退出本实验endl;}3实验结果及分析实验名称算法分析基础——Fibonacci序列问题实验室9#205实验目的或要求实验题目给定一个非负整数n，计算第n个Fibonacci数实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；实验要求41）使用教材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++)5{F2=f1+f0;//f1表示当前的值F0←F1F1←F2;}ReturnF2;}程序代码//Fibonacci数列#ifndefFINBONACCI_H//头文件#defineFINBONACCI_HclassFibonacci{public:doublefibonacci(inti,int&count);//计算fibonacciintfib2();intfib1();};#endifintFibonacci::fib2(){inti=1;doublefib=0;intcount;doublex=INT_MAX;while(fibx){6i++;count=1;fib=fibonacci(i,count);coutifibendl;}cout使用迭代算法时endl;cout第i会超过INT所能表示的最大值endl;cout总共进行了count次操作endl;return0;}intFibonacci::fib1(){doublefib=0;doublea=0;doubleb=1;intcount=0;doublex=INT_MAX;inti;for(i=1;fibx;i++){fib=a+b;a=b;b=fib;count++;}i--;cout使用迭代算法时endl;cout第i会超过INT表示的值endl;cout共做count次操作endl;return0;}doubleFibonacci::fibonacci(inti,int&count){count++;if(i=1)return1;return(fibonacci(i-1,count)+fibonacci(i-2,count));}7实验结果及分析通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。8实验名称分治法在数值问题中的应用——矩阵相乘问题实验室9#205实验目的或要求实验题目设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块得到解并返回}9程序代码//矩阵相乘问题#ifndefMARTRIX_H#defineMARTRIX_HstructTSMartrix{intdata[100][100];intmu;//矩阵的行数intnu;//矩阵的列数};classMartrix{public:voidmartrix();//随机生成一个矩阵voidRand_CreateSMartrix(structTSMartrix&M);//输出矩阵到控制台voidOutputSMartrix(structTSMartrixM);//分治法--两个矩阵相乘voidDAC_MultSMatrix(structTSMartrixM,structTSMartrixN,structTSMartrix&Q);//分割矩阵voiddivide(structTSMartrixM,structTSMartrix&M00,structTSMartrix&M01,structTSMartrix&M10,structTSMartrix&M11);//合并矩阵voidmerge(structTSMartrix&Q,structTSMartrixM00,structTSMartrixM01,structTSMartrixM10,structTSMartrixM11);//矩阵相加structTSMartrixAddSMatrix(structTSMartrixM,structTSMartrixN);//矩阵相减structTSMartrixSubSMatrix(structTSMartrixM,structTSMartrixN);private:structTSMartrixM00,M01,M10,M11;structTSMartrixN00,N01,N10,N11;structTSMartrixQ00,Q01,Q10,Q11;structTSMartrixs1,s2,s3,s4,s5,s6,s7;};#endif10voidMartrix::martrix(){longstart,end;structTSMartrixM,N,Q;do{Rand_CreateSMartrix(M);Rand_CreateSMartrix(N);if(M.mu!=N.mu||M.mu!=M.nu||N.mu!=N.nu)printf(两个矩阵不同维，无法用分治法!!!\n);}while(M.nu!=N.mu||M.mu!=M.nu||N.mu!=N.nu);Q.mu=M.mu;Q.nu=M.mu;start=clock();DAC_MultSMatrix(M,N,Q);end=clock();printf(矩阵M：\n);OutputSMartrix(M);printf(矩阵N：\n);OutputSMartrix(N);printf(矩阵M*N：\n);OutputSMartrix(Q);printf(历时%ld毫秒\n,end-start);}//随机生成一个矩阵voidMartrix::Rand_CreateSMartrix(structTSMartrix&M){inti,j;printf(请输入矩阵的行数，列数：);scanf(%d%d,&M.mu,&M.nu);srand((unsigned)time(NULL));for(i=0;iM.mu;i++)for(j=0;jM.nu;j++)M.data[i][j]=rand()%10;printf(生成成功!\n);}//输出矩阵voidMartrix::OutputSMartrix(structTSMartrixM){inti,j;for(i=0;iM.mu;i++){11for(j=0;jM.nu;j+