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

院 系： 计算机科学学院 专 业：计算机科学与技术 年 级： 课程名称：算法设计与分析基础 班 号： 组 号： 指导教师： 年 月 日 组员 学号 姓名 实验名称 算法实验整体框架的构建 实验室 实验题目 算法实验主菜单的设计。 实验目的 ⑴熟悉实验环境VC ++ 6.0 ； （2）复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度； 实验要求 1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大 致如下： 《算法设计与分析；》实验 . 算法分析基础一一 Fibonacci序列问题 2 分治法在数值问题中的应用- 最近点对冋题 . 减治法在组合问题中的应用- --8枚硬币问题 变治法在排序问题中的应用- --堆排序问题 动态规划法在图问题中的应用一 一全源最短路径问题 99.退出本实验 请输入您所要执行的操 2）点击操作后进入相应的实验项冃或是相应项目的下一级菜单； 3）可以反其执行，直到退出实验。 void Meunl) \rT): 《算法设计与分析》实验打); 、算法分析基础-- F蛔g序列问题W); 、分治法在数值问题中的应用矩阵相乘问题\rT:、减治法在组合问题中的应用一一枚硬币问题\仍：、变治法在排序问题中的应用堆排序问题、动态规划法在图问题中的应用一一全源最短路径问题 、分治法在数值问题中的应用 矩阵相乘问题 \rT: 、减治法在组合问题中的应用一一枚硬币问题 \仍： 、变治法在排序问题中的应用 堆排序问题 、动态规划法在图问题中的应用一一全源最短路径问题 W)： 动态规划法在图问题中的应用一一全源最短路径问题 P rintfC\n\t\t99 、退出本实验\宀: *): 请输入您所要执行的操作(1, 2, 3. 4, 5, 99): void maxnO int a; whiled) 程 序 代 码 MeunO : sc8nf(%d”, a)： switch(a) case 1: 调用菜单函数显示菜单 Pnntf (*\n\t\tFibonacci  序列问题\成\仍: fibonacciO; break: case 2: 分治法在数值问题中的应用一一矩阵相乘问题 case 3: matrix(): break: 减治法在组合问题中的应用 COINFAKE 0; break: case 4: printfr\n\t\t 变治法在排序问题中的应用一一堆排序问题 \t\t\~ : HEA P0: break; case 5: 动态规划法在图问题中的应用一一全源最短路径问题 break： case 99: printfC 你选择退出本实验’\n exit(0: 算法分析基础一一 Fibonacci序列问 实验名称 题 实验室 实验题目 给定一个非负整数 n计算第n个Fibonacci数 实验目的 1） 理解递归算法和迭代算法的设计思想以及递归程序的调式技术 2） 掌握并应用递归算法和迭代算法效率的理论分析 （前验分析）和实际分析（后验分 析）方法； 3） 理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同， 复杂程度不同，效率也不同； 实验要求 1） 使用教材2. 5节中介绍的迭代算法 Fib （n）,找出最大的n,使得第n个Fib on acci 数不超过计算机所能表示的最大整数，并给出具体的执行时间； 2） 对于要求1），使用教材2. 5节中介绍的递归算法 F （n）进行计算，同样给出具体的执 行时间，并同1）的执行时间进行比较； 对于输入同样的非负整数n,比较上.述两种算法基本操作的执行次数； 对1）中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为。 （1）； 设计可供用户选择算法的交互式菜单（放在相应的主菜单下）。 1、递归法基本思想 递归就是定义一个函数，让它自己调用自己。 Fib ( int n ) //输入整数n,输出第n个斐波那契数 {if(n=0)return 0; Else if(n=l)return 1; (算 Else return Fib( nT)+Fib( n-2) 2、迭代法 但代码相对就要夏杂些了。这种方法相对于递归法来说在时间复杂度上减小了不少, 但代码相对就要夏杂些了。 Fib ( int n ) 〃输入整数n,输岀第n个斐波那契数 想) (if(n=0)return 0; Else if(n=l)return 1; Else F0 J 0; Fl for(i=2;i n-2;i++) F2二fl+fO; 表示当前的值 F0 J Fl Fl J F2; Retur n F2; int Fib(int i) ifi2) return i: else return Fib(iT)+Fib(i-2 ： vo