计算机算法设计与分析课程设计
《计算机算法设计与分析课程设计》由会员分享,可在线阅读,更多相关《计算机算法设计与分析课程设计(14页珍藏版)》请在毕设资料网上搜索。
1、用分治法解决快速排序问题及用动态规划用分治法解决快速排序问题及用动态规划 法解决最优二叉搜索树问题及用回溯法解法解决最优二叉搜索树问题及用回溯法解 决图的着色问题决图的着色问题 一、一、 课程设计目的:课程设计目的: 计算机算法设计与分析 这门课程是一门实践性非常强的课程, 要求我们能够将所学 的算法应用到实际中,灵活解决实际问题。通过这次课程设计,能够培养我们独立思考、综 合分析与动手的能力, 并能加深对课堂所学理论和概念的理解, 可以训练我们算法设计的思 维和培养算法的分析能力。 二、课程设计内容:二、课程设计内容: 1、分治法: (2)快速排序; 2、动态规划: (4)最优二叉搜索树;
2、3、回溯法: (2)图的着色。 三、概要设计:三、概要设计: 分治法快速排序: 分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题, 这些子问题 互相独立且与原问题相同。 递归地解这些子问题, 然后将各个子问题的解合并得到原问题的 解。分治法的条件: (1) 该问题的规模缩小到一定的程度就可以容易地解决; (2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3) 利用该问题分解出的子问题的解可以合并为该问题的解; (4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 抽象的讲,分治法有两个重要步骤: (1)将问题
3、拆开; 计算机算法设计与分析课程设计报告 2 (2)将答案合并; 动态规划最优二叉搜索树: 动态规划的基本思想是将问题分解为若干个小问题, 解子问题, 然后从子问题得到原问 题的解。设计动态规划法的步骤: (1)找出最优解的性质,并刻画其结构特征; (2)递归地定义最优值(写出动态规划方程) ; (3)以自底向上的方式计算出最优值; (4)根据计算最优值时得到的信息,构造一个最优解。 回溯法图的着色 回溯法的基本思想是确定了解空间的组织结构后,回溯法就是从开始节点(根结点)出 发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点,同时也成为当前 的扩展结点。在当前的扩展结点处,搜索
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中设计图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 设计 分析 课程设计
