计算机算法设计与分析课程设计(共14页).docx

《计算机算法设计与分析课程设计(共14页).docx》由会员分享，可在线阅读，更多相关《计算机算法设计与分析课程设计(共14页).docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题一、 课程设计目的：计算机算法设计与分析这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容：1、分治法：（2）快速排序；2、动态规划：（4）最优二叉搜索树；3、回溯法：（2）图的着色。三、概要设计：l 分治法快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这

2、些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法的条件：（1) 该问题的规模缩小到一定的程度就可以容易地解决；（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3) 利用该问题分解出的子问题的解可以合并为该问题的解；（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；l 动态规划最优二叉搜索树： 动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤： （1） 找出最

3、优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。l 回溯法图的着色回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一

4、个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。四、详细设计与实现：l 分治法快速排序快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组,按以下三个步骤进行排序： （1）、分解(divide) 以元素为基准元素将划分为三段，和，使得中任何一个元素都小于，而中任何一个元素大于等于，下标在划分过程中确定。（2）、递归求解(conquer) 通过递归调用快速排序算法分别对和进行排序。（3）、合并(merge) 由于和的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。算法实现题:

5、现将数列23 21 34 45 65 76 86 46 30 39 89 20 2 3 8 47 38 54 59 40进行快速排序。源程序如下：#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;

6、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(请输入要排列的数目（=20）：);scanf(%d,&n);printf(请输入要排列的数列：n); for(i=0;in;+i) scanf(%d,&datai); quick_sort(data,0,n-1);pri

7、ntf(排列后的数列为：n); for(i=0;in;+i) printf( %d ,datai); printf(n);return 0; 运行结果如下：图1l 动态规划最优二叉搜索树1、最优二叉搜索树问题描述和分析：设是有序集，且，表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉树的叶结点是形如的开区间，在表示S的二叉搜索树中搜索元素x，返回的结果有两种情况：（1）在二叉搜索树的内结点中找到。（2）在二叉搜索树的叶结点中确定。设在第(1)中情形中找到元素的概率为；

8、在第(2)种情形中确定的概率为。其中约定。显然有：称为集合S的存取概率分布。在表示S的二叉搜索树T中，设存储元素的结点深度为；叶结点的结点深度为，则：表示在二叉搜索树T中进行一次搜索所需要的平均比较次数，p又成为二叉搜索树T的平均路长。在一般情况下，不同的二叉搜索树的平均路长是不相同的。最优二叉搜索树问题是对于有序集S及其存取概率分布，在所有表示有序集S的二叉搜索树中找到一棵具有最小平均路长的二叉搜索树。2、最优子结构性质：二叉搜索树T的一棵含有结点和叶结点的子树可以看作是有序集关于全集合的一棵二叉搜索树，其存取概率为以下的条件概率：式中，。 设是有序集关于存取概率的一棵最优二叉搜索树，其平均

9、路长为。的根结点存储元素。其左右子树和的平均路长分别为和。由于和中结点深度是它们在中的结点深度减1，故有：由于是关于集合的一棵二叉搜索树，故。若，则用替换可得到平均路长比更小的二叉搜索树。这与是最优二叉搜索树矛盾。故是一棵最优二叉搜索树。同理可证也是一棵最优二叉搜索树。因此最优二叉搜索树问题具有最优子结构性质。3、递归计算最优值：最优二叉搜索树的平均路长为，则所求的最优值为。由最优二叉搜索树问题的最优子结构性质可建立计算的递归式如下：初始时，。记为，则为所求的最优值。计算的递归式为：据此，可设计出解最优二叉搜索树问题的动态规划算法。 算法实现题: 给出标识符集1,2,3=do,if,stop存

10、取概率，若b1=0.4 b2=0.2 b3=0.05 a0=0.2 a1=0.05 a2=0.05 a3=0.05构造一棵最优二叉搜索树源程序如下：#includeusing namespace std;void OptimalBinarySearchTree(float a,float b,int n,float m20,int s20,float w20) /求解最优值的方法int i,r,k; float t; for(i=0;i=n;i+) wi+1i=ai; /搜索不到的点,最优解为0 mi+1i=0; for(r=0;rn;r+) for(i=1;i=n-r;i+) int j=i

11、+r; /左子树为空 wij=wij-1+aj+bj; mij=mi+1j; sij=i; for(k=i+1;k=j;k+) t=mik-1+mk+1j; if(tmij) /以k为根节点，左子树不为空 mij=t; sij=k; mij+=wij; for(i=1;i=n;i+) for(int j=1;j=n;j+) coutsij=sij=i) int k=sij;cout(; print(i,k-1,s,S); cout); cout Sk ; cout(; print(k+1,j,s,S); cout); int main() /主函数int n,i; float a20,b20,

12、m2020,w2020; int s2020,S20; cout请输入有序集元素的个数n：n; cout请输入有序集各元素的值Si(一共n个):endl; for(i=1;iSi; cout请输入概率数组a的各元素的值ai(一共n+1个):endl; for(i=0;iai; cout请输入概率数组b的各元素的值bi(一共n个):endl; for(i=1;ibi; OptimalBinarySearchTree(a,b,n,m,s,w); cout最优值即平均步长为：m1nendl;运行结果如下：图2l 回溯法图的着色 1、图的m着色问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图

13、G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。2、算法设计：一般连通图的可着色法问题并不仅限于平面图。给定图和m种颜色，如果这个图不是m可着色，则给出否定答案；如果这个图是m可着色的，找出所有不同的着色方法下面根据回朔法的递归描述框架设计图的m着色算法。用图的邻接矩阵a表示无向量连通图。若属于图的边集E，则，否则。整数1，2，m用来表示m种不同颜色。顶点所有颜色用表示，数组是问题的解向

14、量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第层中每一结点都有m个儿子，每个儿子相应于的m个可能的着色之一。 第n+1层结点均为叶结点。 在下面的解图的m可着色问题的回溯法中，搜索解空间中第层子树。类的数据成员记录解空间中结点信息，以减少传给的参数。记录当前已找到的m着色方案数。在算法中，当时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数则增1。而当时,当前扩展结点Z的每一个解空间中内部结点.该结点有共m个儿子结点.对当前扩展结点Z的每一儿子结点,有方法ok检查其可行性,并以深度优先的方式递归的对可行子树搜索,或减去不可行树。 算法实现题: 给定如图3所示的

15、一个无向连通图G，现有4种不同的颜色，用这4种颜色为图G的各顶点着色，每个顶点着一种颜色。要求：G中每条边的2个顶点着有不同的颜色。问一共有多少种着色方案？12354图3源程序如下：#include using namespace std;int n; /图的顶点个数int m; /可用颜色数int i,j; int a1010; /程序中使用时从下标1开始;程序中用于存储图的邻接矩阵int x10; /用于存储当前解long sum; /当前已找到的可着色方案数bool Ok(int k)for(int j=1;jn) /t是表示的第t行叶结点；图的m着色共有n个结点 sum+;cout 第

16、sum种解决方案为 ：n;for(int i=1;i=n;i+)coutxi ; coutendl; elsefor(int i=1;i=m;i+)xt=i;if(Ok(t)Backtrack(t+1); /判断t+1结点的颜色是不是正确xt=0; /把t+1结点的颜色换一种long mColoring(int mm) m=mm; sum=0; Backtrack(1); return sum;void main()coutnt=图的m着色问题=n;coutnm;coutn=输入图的邻接矩阵n;for(i=1;i=n;i+)for(j=1;jaij;coutn=判断可着色性n;mColorin

17、g(m);if(sum=0)cout 无可行方案！endl;cout-endl;coutn 个顶点按所给的邻接关系着 m 种颜色，总的着色方案有 sum 个n;运行结果如下：图4图5五、总结：通过本次课程设计，使我对快速排序、最优二叉搜索树以及图的m着色设计的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c+语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终能运用到实际案例中去。 对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。而这次的课程设计，正好给了我们一个机会让我们找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型期。专心-专注-专业