1、第 1 页 共 10 页 用分治法解决快速排序问题及用回溯法解用分治法解决快速排序问题及用回溯法解 决决 0 0- -1 1 背包背包问题问题 一、一、 课程设计目的：课程设计目的： 计算机算法设计与分析这门课程是一门实践性非常强的课程，要求我们能够将所 学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、 综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计 的思维和培养算法的分析能力。 二、课程设计内容：二、课程设计内容： 1、分治法： （2）快速排序； 2、回溯法： （2）图的着色。 三、概要设计：三、概要设计： 分治法快速排序： 分
2、治法的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问 题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问 题的解。分治法的条件： （1) 该问题的规模缩小到一定的程度就可以容易地解决； （2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3) 利用该问题分解出的子问题的解可以合并为该问题的解； （4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤： （1）将问题拆开； （2）将答案合并； 回溯法0-1 背包问题 第 2 页 共 10 页 回溯法的基
3、本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点） 出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为 当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就 成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向 移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结 点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结 点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以 无活结点为止。 四、详细设计与实现：四、详细设计与实现
4、： 分治法快速排序 快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组 rpa:,按以下三个步骤进行排序： （1） 、 分解(divide) 以元素 pa为基准元素将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的排序都是在原位置进行的，所以 不必进行任何合并操作就已经排好序了。 算法实现题算
5、法实现题: 现将数列12 21 31 45 36 76 66 46 30 7 89 20 2 5 99 47 23 54 51 73进行快速排序。 源程序如下： #include using namespace std; #define size 20 int partition(int data,int p,int r) 第 3 页 共 10 页 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;
6、 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); /对右半段排序 int main() int i,n,datasize; printf(“请输入要排列的数目（(gj-1.pc/gj-1.wc) temp=gj.pc; gj.pc=gj-1.pc; gj-1.pc=temp; 第 11 页 共 10 页 temp=gj.wc; gj.wc=gj-1.wc; gj-1.wc=temp; void backt
