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

《算法分析与设计实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、****院系：计算机科学学院专业：计算机科学与技术年级：课程名称：算法设计与分析基础班号：组号：指导教师：年月日可编辑word,供参考版！组员学号姓名实验名称算法实验整体框架的构建实验室实验目的或要求1.实验题目算法实验主菜单的设计。2．实验目的⑴熟悉实验环境VC＋＋6.0；⑵复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度；3.实验要求1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：－－－－－－－－－－－－－－－－－－－－－－－－－《算法设计与分析》实验－－－－－－－－－－－－－－－－－－－－－－－－－1.

2、算法分析基础——Fibonacci序列问题2.分治法在数值问题中的应用——最近点对问题3.减治法在组合问题中的应用——8枚硬币问题4.变治法在排序问题中的应用——堆排序问题5.动态规划法在图问题中的应用——全源最短路径问题99.退出本实验－－－－－－－－－－－－－－－－－－－－－－－－－请输入您所要执行的操作（1，2，3，4，5，99）：2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；3）可以反复执行，直到退出实验。可编辑word,供参考版！程序代码voidMeun(){printf("tt－－－－－－－－－－－－－－－－－－－－－－－－－"

3、);printf("tt《算法设计与分析》实验");printf("tt－－－－－－－－－－－－－－－－－－－－－－－－－");printf("tt1、算法分析基础——Fibonacci序列问题");printf("tt2、分治法在数值问题中的应用——矩阵相乘问题");printf("tt3、减治法在组合问题中的应用——枚硬币问题");printf("tt4、变治法在排序问题中的应用——堆排序问题");Printf("tt4、动态规划法在图问题中的应用——全源最短路径问题");动态

4、规划法在图问题中的应用——全源最短路径问题printf("tt99、退出本实验");printf("tt－－－－－－－－－－－－－－－－－－－－－－－－－");printf("tt请输入您所要执行的操作（1，2，3，4，5，99）：");}voidmain(){inta;while(1){Meun();//调用菜单函数显示菜单scanf("%d",&a);switch(a){case1:{printf("ttFibonacci序列问题tt");fibonacci();break;}case2:{printf("t

5、t分治法在数值问题中的应用——矩阵相乘问题tt");matrix();break;}case3:{printf("tt减治法在组合问题中的应用——8枚硬币问题tt");COINFAKE();break;}case4:{可编辑word,供参考版！printf("tt变治法在排序问题中的应用——堆排序问题tt");HEAP();break;}case5:{printf("tt动态规划法在图问题中的应用——全源最短路径问题tt");break;}case99:{printf("你选择退出本实验‘");exit(

6、0);}}}}实验结果及分析可编辑word,供参考版！实验名称算法分析基础——Fibonacci序列问题实验室实验目的或要求实验题目给定一个非负整数n，计算第n个Fibonacci数实验目的1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法；3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；实验要求1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得第n个Fibonacci数不超过计算机所能表示的最大整数，

7、并给出具体的执行时间；2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较；3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数；4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为Θ(1)；5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。可编辑word,供参考版！实验原理（算法基本思想）1、递归法基本思想递归就是定义一个函数，让它自己调用自己。Fib（intn）//输入整数n，输出第n个斐波那契数{if(n=0)return0;Elseif(n=1)retur

8、n1;El