用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题

用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题一、课程设计目的：《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。二、课程设计内容：1、分治法：（2）快速排序；2、动态规划：（4）最优二叉搜索树；3、回溯法：（2）图的着色。三、概要设计：分治法—快速排序：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题些子问题，然后将各个子问题的解合并得到原问题的相同。递归地解这解。分治法的条件：（1)问该题的规模缩小到一定的程（2)问该题可以分解为若干个规模较小的（3)利用问该题分解出的子问题的解可以合并为问该题的解；（4)问该题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。抽象的讲，分治法有两个重要步骤：（1）将问题拆开；（2）将答案合并；度就可以容易地解决；相同问题，即该问题具有最优子结构性质；

《计算机算法设计与分析》课程设计报告动态规划—最优二叉搜索树：动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。回溯法—图的着色回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。不能再向纵深方向移动，当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。则应往四、详细设计与实现：分治法—快速排序快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组apr:,按以下三个步骤进行排序：（1）、分解(divide)以元素ap为基准元素将apr:划分为三段ap:q1aq，1:aq1:r中任何一个元素中任何一个元素都小于，而aq和，aqr使得ap:q1大于等于，下标在划分q过程中确定。aq（2）、递归求解(conquer)通过递归调用快速排序算法分别对ap:q1aq和1:r进行排序。1:r的排序都是在原位置进行的，所以不（3）、合并(merge)由于ap:q1aq和必进行任何合并操作就已经排好序了。算法实现题:现将数列{23213445657686463039892022《计算机算法设计与分析》课程设计报告384738545940}进行快速排序。源程序如下：#include<iostream>usingnamespacestd;#definesize20intpartition(intdata[],intp,intr){intn=data[p],i=p+1,j=r,temp;//将<n的元素交换到左边区域//将>n的元素交换到右边区域while(true){while(data[i]<n)++i;while(data[j]>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;intq=partition(data,p,r);quick_sort(data,p,q-1);//对左半段排序quick_sort(data,q+1,r);//对右半段排序}intmain()3{inti,n,data[size];printf("请输入要排列的数目（<=20）：");scanf("%d",&n);printf("请输入要排列的数列：\n");for(i=0;i<n;++i)scanf("%d",&data[i]);quick_sort(data,0,n-1);printf("排列后的数列为：\n");for(i=0;i<n;++i)printf("%d",data[i]);printf("\n");return0;}运行结果如下：图1动态规划—最优二叉搜索树1、最优二叉搜索树问题描述和分析：设Sxx,,,x是有序集，且xxnx，表示有序集S的二叉搜索树利12n12用二叉树的结点存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x大于其4《计算机算法设计与分析》课程设计报告左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉树的叶结点x,x的开区间，在表示是形如S的二叉搜索树中搜索元素x，返回的结果有两种情况：ii1xx。（1）在二叉搜索树的内结点中找到i（2）在二叉搜索树的叶结点中确定xx,x。ii1xx,xii1设在第(1)中情形中找到元素xx的概率为；在第b(2)种情形中确定的iia。其中约定x,x。显然有：概率为i0n1a0,0in;b0,1jn;nnb1jaijii0a,b,a,,b,a称为集合S的存取概率分布。j1011nn在表示S的二叉搜索树T中，设存储元素x的结点深度为c；叶结点x,x的结点iijj1深度为d，则：jpnb1cinadjiji1j0表示在二叉搜索树T中进行一次搜索所需要的平均比较次数，p又成为二叉搜索树T的平均路长。在一般情况下，不同的二叉搜索树的平均路长是不相同的。S及其存取概率分布ababa，在所有,,,,,最优二叉搜索树问题是对于有序集011nn表示有序集S的二叉搜索树中找到一棵具有最小平均路长的二叉搜索树。2、最优子结构性质：x,x,,x,xi1j1ij,,x和叶结点j二叉搜索树T的一棵含有结点xi的子树可以看作是有序集xx关于全集合j,,x,,xi1j1的一棵二叉搜索树，其存取概率为以下的i条件概率：bb/wikjkkijaa/wi1hjhhijwa式中，ijbba,1ijn。ijji15《计算机算法设计与分析》课程设计报告a,b,,b,a的一棵最优二叉搜索树，设T是有序集xx关于存取概率ij,,iji1ijj其平均路长为T和T的平均路长分别为p。T的根结点存储元素x。其左右子树p和ijijmlrlp。由于T和T中结点深度是它们在T中的结点深度减1，故有：rrlijwpwwpwlpi,ji,ji,ji,m1m1,jrT是关于集合x,,x的一棵二叉搜索树，故pp。若pp由于，则i,m1im1li,m1ll用T替换i,m1T可得到平均路长比T更小的二叉搜索树。这与T是最优二叉搜索树矛盾。ijijl故T是一棵最优二叉搜索树。同理可证T也是一棵最优二叉搜索树。因此最优二叉搜索树lr问题具有最优子结构性质。3、递归计算最优值：最优二叉搜索树T的平均路长为p，则所求的最优值为p。由最优二叉搜索树问题1,nijij的最优子结构性质可建立计算p的递归式如下：ijmin,ijwpwi,ji,jwpwpk1,jk1,ji,ji,k1i,k1ikj0,1in。初始时，pi,i1记wp为mij，则m1,nwpp为所求的最优值。1,n1,n1,n,i,ji,j,mij的递归式为：计算mi,k1mk1,j,ijminmi,jwi,jikjmi,i10,1in据此，可设计出解最优二叉搜索树问题的动态规划算法。算法实现题:给出标识符集{1,2,3}={do,if,stop}存取概率，若b1=0.4b2=0.2b3=0.05a0=0.2a1=0.05a2=0.05a3=0.05构造一棵最优二叉搜索树源程序如下：#include<iostream>usingnamespacestd;voidOptimalBinarySearchTree(floata[],floatb[],intn,floatm[][20],ints[][20],floatw[][20])6《计算机算法设计与分析》课程设计报告{//求解最优值的方法inti,r,k;floatt;for(i=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;}//搜索不到的点,最优解为0for(r=0;r<n;r++)for(i=1;i<=n-r;i++){intj=i+r;//左子树为空w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i+1][j];s[i][j]=i;for(k=i+1;k<=j;k++){t=m[i][k-1]+m[k+1][j];if(t<m[i][j]){//以k为根节点，左子树不为空m[i][j]=t;s[i][j]=k;}}m[i][j]+=w[i][j];}for(i=1;i<=n;i++)for(intj=1;j<=n;j++)cout<<"s["<<i<<"]["<<j<<"]="<<s[i][j]<<endl;}voidprint(inti,intj,ints[][20],intS[])//递归输出结果{if(j>=i){intk=s[i][j];7《计算机算法设计与分析》课程设计报告cout<<"(";print(i,k-1,s,S);cout<<")";cout<<""<<S[k]<<"";cout<<"(";print(k+1,j,s,S);cout<<")";}}intmain(){//主函数intn,i;floata[20],b[20],m[20][20],w[20][20];ints[20][20],S[20];cout<<"请输入有序集元素的个数n："<<endl;cin>>n;cout<<"请输入有序集各元素的值S[i](一共"<<n<<"个):"<<endl;for(i=1;i<=n;i++)cin>>S[i];cout<<"请输入概率数组a的各元素的值a[i](一共"<<n+1<<"个):"<<endl;for(i=0;i<=n;i++)cin>>a[i];cout<<"请输入概率数组b的各元素的值b[i](一共"<<n<<"个):"<<endl;for(i=1;i<=n;i++)cin>>b[i];OptimalBinarySearchTree(a,b,n,m,s,w);cout<<"最优值即平均步长为："<<m[1][n]<<endl;}运行结果如下：8图2回溯法—图的着色1、图的m着色问题描述：G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图2、算法设计：给定无向连通图的色数。求一个图的色数m的问题称为图的m可着色优化问题。,GVE和m种颜色，如果这一般连通图的可着色法问题并不仅限于平面图。给定图个图不是m可着色，则给出否定答案；如果这个图是m可着色的，找出所有不同的着色方法下面根据回朔法的递归描述框架Backtrack设计图的m着色算法。用图的邻接矩阵aaij1，否则,i,jGVE。若属于图的边集E，则GV,E表示无向量连通图aij0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用xi表示，数组x1:n是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第i1in层中每一结点都有m个儿子，每个儿子相应于xi的m个可能的着色一之。第n+1层结点均为叶结点。9《计算机算法设计与分析》课程设计报告在下面的解图的m可着色问题的回溯法中，类Color的数据成员记录解空间中前已找到的m着色方案数。Backtracki搜索解空间中第i层子树。结点信息，以减少传给Backtrack的参数。sum记录当Backtrack中，当in时，算法搜索m着色方案数sum则增1。而当in时,当前扩展结点Z的每一个解空间中内部结点.在算法至叶结点，得到新的m着色方案，当前找到的该结点有xi1,2,,m共m个儿子结点.对当前扩展结点Z的每一儿子结点,有方法ok检行性,并以深度优先的方式递归的对可行子树搜索,或减去不可行树。一个无向连通图G，现有4种不同的颜色，用这4种一种颜色。要求：G中每条边的2个顶点着查其可算法实现题:给定如图3所示的颜色为图G的各顶点着色，每个顶点着有不同的颜色。问一共有多少种着色方案？13425图3源程序如下：#include<iostream>usingnamespacestd;intn;//图的顶点个数intm;//可用颜色数inti,j;inta[10][10];intx[10];//程序中使用时从下标1开始;程序中用于存储图的邻接矩阵//用于存储当前解longsum;//当前已找到的可着色方案数10《计算机算法设计与分析》课程设计报告boolOk(intk){for(intj=1;j<=n;j++){if((a[k][j]==1)&&(x[j]==x[k]))//a[k][j]==1表示的是第k点和第j点是相连的returnfalse;}returntrue;}voidBacktrack(intt){if(t>n){//t是表示的第t行叶结点；图的m着色共有n个结点sum++;cout<<"第"<<sum<<"种解决方案为：\n";for(inti=1;i<=n;i++){cout<<x[i]<<"";}cout<<endl;}else{for(inti=1;i<=m;i++){x[t]=i;if(Ok(t)){Backtrack(t+1);//判断t+1结点的颜色是不是正确}11《计算机算法设计与分析》课程设计报告x[t]=0;//把t+1结点的颜色换一种}}}longmColoring(intmm){m=mm;sum=0;Backtrack(1);returnsum;}voidmain(){cout<<"\n\t==========图的m着色问题============\n";cout<<"输入图的顶点数与可用的颜色数:\n";cin>>n>>m;cout<<"\n==========输入图的邻接矩阵\n";for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];cout<<"\n==========判断可着色性\n";mColoring(m);if(sum==0)cout<<"无可行方案！"<<endl;cout<<"-------------------------------------------------------------------------------"<<endl;cout<<n<<"个顶点"<<"按所给的邻接关系着"<<m<<"种颜色，总的着色方案有"<<sum<<"个\n";}运行结果如下：12图4图5五、总结：通过本次课程设计，使我对快速排序、最优二叉搜索树以及图的m着色设计的基本过程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c++语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终13《计算机算法设计与分析》课程设计报告能运用到实际案例中去。对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。而这次的课程设计，正好给了我们一个机会让我们找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型期。14《计算机算法设计与分析》课