院系：计算机科学学院专业：计算机科学与技术年级：2010级课程名称：算法设计与分析基础班号：软工（1）班组号：3指导教师：邢光林2012年12月30日组员学号姓名10065016李继强10065034罗园10065005李敏实验名称算法实验整体框架的构建实验室9#205实验目的或要求1.实验题目算法实验主菜单的设计。2．实验目的⑴熟悉实验环境VC＋＋6.0；⑵复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度；3.实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：－－－－－－－－－－－－－－－－－－－－－－－－－《算法设计与分析》实验－－－－－－－－－－－－－－－－－－－－－－－－－算法分析基础——Fibonacci序列问题分治法在数值问题中的应用——最近点对问题减治法在组合问题中的应用——8枚硬币问题变治法在排序问题中的应用——堆排序问题动态规划法在图问题中的应用——全源最短路径问题99.退出本实验－－－－－－－－－－－－－－－－－－－－－－－－－请输入您所要执行的操作（1，2，3，4，5，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。程序代码voidmenu();intmain(){FibonaccifibonacciImpl;HeapsortheapsortImpl;MartrixmartrixImpl;ThecointhecoinImpl;intchose;menu();cin>>chose;while(chose!=99){switch(chose){case1:{fibonacciImpl.fib1();cout<<endl;fibonacciImpl.fib2();break;}case2:{martrixImpl.martrix();break;}case3:{thecoinImpl.Fake_coin();break;}case4:{heapsortImpl.heapsort();break;}case5:{break;}default:cout<<"请按序号输入操作"<<endl;}menu();cin>>chose;}return0;}voidmenu(){cout<<"---------------------------------------"<<endl;cout<<"《《算法设计与分析》》实验"<<endl;cout<<"---------------------------------------"<<endl;cout<<"1.算法分析基础——Fibonacci序列问题"<<endl;cout<<"2.分治法在数值问题中的应用——矩阵相乘问题"<<endl;cout<<"3.减治法在组合问题中的应用——8枚硬币问题"<<endl;cout<<"4.变治法在排序问题中的应用——堆排序问题"<<endl;cout<<"5.动态规划法在图问题中的应用——全源最短路径问题"<<endl;cout<<"99.退出本实验"<<endl;}实验结果及分析实验名称算法分析基础——Fibonacci序列问题实验室9#205实验目的或要求实验题目给定一个非负整数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(