算法实验题目

《算法实验题目》由会员分享，可在线阅读，更多相关《算法实验题目（12页珍藏版）》请在金锄头文库上搜索。

1、12/11/2018,1. 实验题目 算法实验主菜单的设计。 2实验目的 熟悉实验环境VC6.0 ； 复习C、C+语言以及数据结构课程的相关知识， 实现课程间的平滑过度；,1 算法实验整体框架的构建,12/11/2018,3. 实验要求 1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： 算法设计与分析实验 算法分析基础Fibonacci序列问题 分治法在数值问题中的应用最近点对问题 减治法在组合问题中的应用8枚硬币问题 变治法在排序问题中的应用堆排序问题 动态规划法在图问题中的应用全源最短路径问题 99. 退出本实验 请输入您所要执行的操作（1，2，3，4

2、，5，99）： 2）点击操作后进入相应的实验项目或是相应项目的下一级菜单； 3）可以反复执行，直到退出实验。,1 算法实验整体框架的构建,12/11/2018,2 算法分析基础,1. 实验题目 给定一个非负整数n，计算第n个Fibonacci数 2实验目的 1）理解递归算法和迭代算法的设计思想以及递归程序的 调式技术 2）掌握并应用递归算法和迭代算法效率的理论分析(前验分 析)和实际分析(后验分析)方法； 3）理解这样一个观点：不同的算法可以解决相同的问题， 这些算法的解题思路不同，复杂程度不同，效率也不同；,12/11/2018,3. 实验要求 1）使用教材2.5节中介绍的迭代算法Fib(n

3、),找出最大的n,使得 第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间； 2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较； 3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数； 4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为(1)； 5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。,2 算法分析基础,12/11/2018,1. 实验题目 设p1 = (x1,y1), p2 = (x1, y2), , pn= (xn, yn)是平面上n个点构成的集

4、合S，设计算法找出集合S中距离最近的点对。 2实验目的 1）提高应用蛮力法设计算法的技能； 2）深刻理解并掌握分治法的设计思想； 3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。,3 分治法在数值问题中的应用 最近点对问题,12/11/2018,3. 实验要求 1）设计并实现用BF方法求解最近点对问题的算法； 2）设计并实现用DAC方法求解最近点对问题的算法； 3）以上两种算法的输入既可以手动输入，也可以自动生成； 4）算法不仅要输出最近点对的距离，还要输出最近点对的 两个点； 5）对上述两个算法进行时间复杂性分析，并设计实验程序验证

5、 分析结果； 6）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。,3 分治法在数值问题中的应用 最近点对问题,12/11/2018,1. 实验题目 在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。 2.实验目的 1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别； 2）提高应用减治法设计算法的技能。 3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。,4 减治法在组合问题中的应用 8枚硬币问题,12/11/2018,3. 实验要求 1）设计

6、减治算法实现8枚硬币问题； 2）设计实验程序，考察用减治技术设计的算法是否高效； 3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。,4. 实现提示 假设用一个数组Bn表示硬币，元素Bi中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句。,4 减治法在组合问题中的应用 8枚硬币问题,12/11/2018,1. 实验题目 用基于变治法的堆排序算法对任意一组给定的数据进行排序 2实验目的 1）深刻理解并掌握变治法的设计思想； 2）掌握堆的概念以及

7、如何用变治法把任意给定的一组数据改变成堆； 3）提高应用变治法设计算法的技能。,5 变治法在排序问题中的应用 堆排序,12/11/2018,3. 实验要求 1）设计与实现堆排序算法； 2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，15003000个数据左右），用以检验(用计数法)堆排序算法的时间效率。,5 变治法在排序问题中的应用 堆排序,12/11/2018,1. 实验题目 给定一个加权连通图(无向的或有向的)，要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度。 2实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用，理解它与分治法的区别； （2）掌握最优性原理和最优子结构性质； （3）理解这样一个观点：用动态规划方法求解问题的关键在于确定动态规划函数的递推式。,6 动态规划法在图问题中的应用 全源最短路径问题,12/11/2018,3. 实验要求 （1）实现Floyd算法； （2）算法的输入可以手动输入，也可以自动生成； （3）算法不仅要输出从每个顶点到其他所有顶点之间的最短路径，还有输出最短路径的长度； （4）设计一个权重为负的图或有向图的例子，对于它，Floyd算法不能输出正确的结果。,6 动态规划法在图问题中的应用 全源最短路径问题,