新《计算机算法设计与分析》课程设计new

《新《计算机算法设计与分析》课程设计new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用分治法解决快速排序问题及用回溯法解决0-1背包问题一、课程设计目的：《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容：1、分治法：（2）快速排序；2、回溯法：（2）图的着色。三、概要设计：l分治法—快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然

2、后将各个子问题的解合并得到原问题的解。分治法的条件：（1)该问题的规模缩小到一定的程度就可以容易地解决；（2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3)利用该问题分解出的子问题的解可以合并为该问题的解；（4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；l回溯法—0-1背包问题第14页共10页回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活

3、结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。四、详细设计与实现：l分治法—快速排序快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组,按以下三个步骤进行排序：（1）

4、、分解(divide)以元素为基准元素将划分为三段，和，使得中任何一个元素都小于，而中任何一个元素大于等于，下标在划分过程中确定。（2）、递归求解(conquer)通过递归调用快速排序算法分别对和进行排序。（3）、合并(merge)由于和的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。算法实现题:现将数列{1221314536766646307892025994723545173}进行快速排序。源程序如下：#includeusingnamespacestd;#definesize20intpartition(intd

5、ata[],intp,intr){intn=data[p],i=p+1,j=r,temp;第14页共10页//将n的元素交换到右边区域while(true){while(data[i]n)--j;if(i>=j)break;temp=data[i];data[i]=data[j];data[j]=temp;}data[p]=data[j];data[j]=n;returnj;}voidquick_sort(intdata[],intp,intr){if(p>=r)return;in

6、tq=partition(data,p,r);quick_sort(data,p,q-1);//对左半段排序quick_sort(data,q+1,r);//对右半段排序}intmain(){inti,n,data[size];printf("请输入要排列的数目（<=20）：");scanf("%d",&n);printf("请输入要排列的数列：");for(i=0;i

7、++i)printf("%d",data[i]);printf("");return0;}运行结果如下：图1第14页共10页图5l回溯法—0-1背包问题l回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结

8、束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度