算法设计实验题目

4 7 20202006 AlgorithmDesignandAnalysis SCUEC1 1 实验题目算法实验主菜单的设计 2 实验目的 熟悉实验环境VC 6 0 复习C C 语言以及数据结构课程的相关知识 实现课程间的平滑过度 1算法实验整体框架的构建 4 7 20202006 AlgorithmDesignandAnalysis SCUEC2 3 实验要求1 设计的主菜单可以是图形模式的 也可以是控制台模式的 以控制台为例 主菜单大致如下 算法设计与分析 实验 算法分析基础 Fibonacci序列问题分治法在数值问题中的应用 最近点对问题减治法在组合问题中的应用 8枚硬币问题变治法在排序问题中的应用 堆排序问题动态规划法在图问题中的应用 全源最短路径问题99 退出本实验 请输入您所要执行的操作 1 2 3 4 5 99 2 点击操作后进入相应的实验项目或是相应项目的下一级菜单 3 可以反复执行 直到退出实验 1算法实验整体框架的构建 4 7 20202006 AlgorithmDesignandAnalysis SCUEC3 2算法分析基础 1 实验题目给定一个非负整数n 计算第n个Fibonacci数2 实验目的1 理解递归算法和迭代算法的设计思想以及递归程序的调式技术2 掌握并应用递归算法和迭代算法效率的理论分析 前验分析 和实际分析 后验分析 方法 3 理解这样一个观点 不同的算法可以解决相同的问题 这些算法的解题思路不同 复杂程度不同 效率也不同 4 7 20202006 AlgorithmDesignandAnalysis SCUEC4 3 实验要求1 使用教材2 5节中介绍的迭代算法Fib n 找出最大的n 使得第n个Fibonacci数不超过计算机所能表示的最大整数 并给出具体的执行时间 2 对于要求1 使用教材2 5节中介绍的递归算法F n 进行计算 同样给出具体的执行时间 并同1 的执行时间进行比较 3 对于输入同样的非负整数n 比较上述两种算法基本操作的执行次数 4 对1 中的迭代算法进行改进 使得改进后的迭代算法其空间复杂度为 1 5 设计可供用户选择算法的交互式菜单 放在相应的主菜单下 2算法分析基础 4 7 20202006 AlgorithmDesignandAnalysis SCUEC5 1 实验题目设p1 x1 y1 p2 x1 y2 pn xn yn 是平面上n个点构成的集合S 设计算法找出集合S中距离最近的点对 2 实验目的1 提高应用蛮力法设计算法的技能 2 深刻理解并掌握分治法的设计思想 3 理解这样一个观点 用蛮力法设计的算法 一般来说 经过适度的努力后 都可以对其进行改进 以提高算法的效率 3分治法在数值问题中的应用 最近点对问题 4 7 20202006 AlgorithmDesignandAnalysis SCUEC6 3 实验要求1 设计并实现用BF方法求解最近点对问题的算法 2 设计并实现用DAC方法求解最近点对问题的算法 3 以上两种算法的输入既可以手动输入 也可以自动生成 4 算法不仅要输出最近点对的距离 还要输出最近点对的两个点 5 对上述两个算法进行时间复杂性分析 并设计实验程序验证分析结果 6 设计可供用户选择算法的交互式菜单 放在相应的主菜单下 3分治法在数值问题中的应用 最近点对问题 4 7 20202006 AlgorithmDesignandAnalysis SCUEC7 1 实验题目在8枚外观相同的硬币中 有一枚是假币 并且已知假币与真币的重量不同 但不知道假币与真币相比较轻还是较重 可以通过一架天平来任意比较两组硬币 设计一个高效的算法来检测这枚假币 2 实验目的1 深刻理解并掌握减治法的设计思想并理解它与分治法的区别 2 提高应用减治法设计算法的技能 3 理解这样一个观点 建立正角的模型对于问题的求解是非常重要的 4减治法在组合问题中的应用 8枚硬币问题 4 7 20202006 AlgorithmDesignandAnalysis SCUEC8 3 实验要求1 设计减治算法实现8枚硬币问题 2 设计实验程序 考察用减治技术设计的算法是否高效 3 扩展算法 使之能处理n枚硬币中有一枚假币的问题 4 实现提示假设用一个数组B n 表示硬币 元素B i 中存放第i枚硬币的重量 其中n 1个元素的值都是相同的 只有一个元素与其他元素值不同 则当n 8时即代表8枚硬币问题 由于8枚硬币问题限制只允许使用天平比较轻重 所以 算法中只能出现元素相加和比较的语句 4减治法在组合问题中的应用 8枚硬币问题 4 7 20202006 AlgorithmDesignandAnalysis SCUEC9 1 实验题目用基于变治法的堆排序算法对任意一组给定的数据进行排序2 实验目的1 深刻理解并掌握变治法的设计思想 2 掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆 3 提高应用变治法设计算法的技能 5变治法在排序问题中的应用 堆排序 4 7 20202006 AlgorithmDesignandAnalysis SCUEC10 3 实验要求1 设计与实现堆排序算法 2 待排序的数据可以手工输入 通常规模比较小 10个数据左右 用以检测程序的正确性 也可以计算机随机生成 通常规模比较大 1500 3000个数据左右 用以检验 用计数法 堆排序算法的时间效率 5变治法在排序问题中的应用 堆排序 4 7 20202006 AlgorithmDesignandAnalysis SCUEC11 1 实验题目给定一个加权连通图 无向的或有向的 要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度 2 实验目的 1 深刻掌握动态规划法的设计思想并能熟练运用 理解它与分治法的区别 2 掌握最优性原理和最优子结构性质 3 理解这样一个观点 用动态规划方法求解问题的关键在于确定动态规划函数的递推式 6动态规划法在图问题中的应用 全源最短路径问题 4 7 20202006 AlgorithmDesignandAnalysis SCUEC12 3 实验要求 1 实现F