1、用分治法解决快速排序问题及用动态规划用分治法解决快速排序问题及用动态规划 法解决最优二叉搜索树问题及用回溯法解法解决最优二叉搜索树问题及用回溯法解 决图的着色问题决图的着色问题 一、一、 课程设计目的：课程设计目的： 计算机算法设计与分析 这门课程是一门实践性非常强的课程， 要求我们能够将所学 的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综 合分析与动手的能力， 并能加深对课堂所学理论和概念的理解， 可以训练我们算法设计的思 维和培养算法的分析能力。 二、课程设计内容：二、课程设计内容： 1、分治法： （2）快速排序； 2、动态规划： （4）最优二叉搜索树；
2、3、回溯法： （2）图的着色。 三、概要设计：三、概要设计： 分治法快速排序： 分治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题， 这些子问题 互相独立且与原问题相同。 递归地解这些子问题， 然后将各个子问题的解合并得到原问题的 解。分治法的条件： （1) 该问题的规模缩小到一定的程度就可以容易地解决； （2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3) 利用该问题分解出的子问题的解可以合并为该问题的解； （4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤： （1）将问题
3、拆开； 计算机算法设计与分析课程设计报告 2 （2）将答案合并； 动态规划最优二叉搜索树： 动态规划的基本思想是将问题分解为若干个小问题， 解子问题， 然后从子问题得到原问 题的解。设计动态规划法的步骤： （1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值（写出动态规划方程） ； （3）以自底向上的方式计算出最优值； （4）根据计算最优值时得到的信息，构造一个最优解。 回溯法图的着色 回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出 发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前 的扩展结点。在当前的扩展结点处，搜索
4、向纵深方向移至一个新结点。这个新结点就成为一 个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则 当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时， 应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即 以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。 四、详细设计与实现：四、详细设计与实现： 分治法快速排序 快速排序是基于分治策略的另一个排序算法 。 其基本思想是， 对于输入的子数组rpa:, 按以下三个步骤进行排序： （1） 、分解(divide) 以元素 pa为基准元素
5、将rpa:划分为三段1:qpa， qa 和，rqa:1使得1:qpa中任何一个元素都小于 qa，而rqa:1中任何一个元素 大于等于 qa，下标q在划分过程中确定。 （2） 、 递归求解(conquer) 通过递归调用快速排序算法分别对1:qpa和rqa:1 进行排序。 （3） 、合并(merge) 由于1:qpa和rqa:1的排序都是在原位置进行的，所以不 必进行任何合并操作就已经排好序了。 计算机算法设计与分析课程设计报告 3 算法实现题算法实现题: 现将数列23 21 34 45 65 76 86 46 30 39 89 20 2 3 8 47 38 54 59 40进行快速排序。 源程
6、序如下： #include using namespace std; #define size 20 int partition(int data,int p,int r) int n=datap,i=p+1,j=r,temp; /将n 的元素交换到右边区域 while(true) while(datain) -j; if(i=j) break; temp=datai; datai=dataj; dataj=temp; datap=dataj; dataj=n; return j; void quick_sort(int data,int p,int r) if(p=r) return; int q=partition(data,p,r); quick_sort(data,p,q-1); /对左半段排序 quick_sort(data,q+1,r); /
