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

一、 课程设计目的：

《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。

二、课程设计内容：

1、分治法： （2）快速排序； 2、动态规划： （4）最优二叉搜索树； 3、回溯法： （2）图的着色。

三、概要设计：

 分治法—快速排序：

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法的条件：

（1) 该问题的规模缩小到一定的程度就可以容易地解决；

（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3) 利用该问题分解出的子问题的解可以合并为该问题的解；

（4) 该问题所分解出的各个子问题是相互的，即子问题之间不包含公共的子子问题。 抽象的讲，分治法有两个重要步骤： （1）将问题拆开；

《计算机算法设计与分析》课程设计报告

（2）将答案合并；

 动态规划—最优二叉搜索树：

动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：

（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值（写出动态规划方程）； （3）以自底向上的方式计算出最优值；

（4）根据计算最优值时得到的信息，构造一个最优解。  回溯法—图的着色

回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。

四、详细设计与实现：

 分治法—快速排序

快速排序是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组ap:r,按以下三个步骤进行排序：

（1）、分解(divide) 以元素ap为基准元素将ap:r划分为三段ap:q1，aq和，aq1:r使得ap:q1中任何一个元素都小于aq，而aq1:r中任何一个元素大于等于aq，下标q在划分过程中确定。

（2）、递归求解(conquer) 通过递归调用快速排序算法分别对ap:q1和aq1:r进行排序。

（3）、合并(merge) 由于ap:q1和aq1:r的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。

2

《计算机算法设计与分析》课程设计报告

算法实现题: 现将数列{23 21 34 45 65 76 86 46 30 39 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=data[p],i=p+1,j=r,temp; //将n的元素交换到右边区域 while(true) {

while(data[i]n) --j;

if(i>=j)

break;

temp=data[i]; data[i]=data[j]; }

data[p]=data[j]; data[j]=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); //对右半段排序

3

data[j]=temp; 《计算机算法设计与分析》课程设计报告

} int main() {

int i,n,data[size];

printf(\"请输入要排列的数目（<=20）：\"); scanf(\"%d\

printf(\"请输入要排列的数列：\\n\");

for(i=0;iprintf(\"排列后的数列为：\\n\");

for(i=0;iprintf( \"%d \

printf(\"\\n\"); }

运行结果如下：

return 0;

图1

 动态规划—最优二叉搜索树 1、最优二叉搜索树问题描述和分析：

4

《计算机算法设计与分析》课程设计报告

设Sx1,x2,,xn是有序集，且x1x2xn，表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉树的叶结点是形如xi,xi1的开区间，在表示S的二叉搜索树中搜索元素x，返回的结果有两种情况：

（1）在二叉搜索树的内结点中找到xxi。

（2）在二叉搜索树的叶结点中确定xxi,xi1。

设在第(1)中情形中找到元素xxi的概率为bi；在第(2)种情形中确定xxi,xi1的概率为ai。其中约定x0,xn1。显然有：

ai0,0in;bj0,1jn;aibj1

i0j1nna0,b1,a1,,bn,an称为集合S的存取概率分布。

在表示S的二叉搜索树T中，设存储元素xi的结点深度为ci；叶结点xj,xj1的结点深度为dj，则：

pbi1ciajdji1j0nn

表示在二叉搜索树T中进行一次搜索所需要的平均比较次数，p又成为二叉搜索树T的平均路长。在一般情况下，不同的二叉搜索树的平均路长是不相同的。

最优二叉搜索树问题是对于有序集S及其存取概率分布a0,b1,a1,,bn,an，在所有表示有序集S的二叉搜索树中找到一棵具有最小平均路长的二叉搜索树。 2、最优子结构性质：

二叉搜索树T的一棵含有结点xi,,xj和叶结点xi1,xi,,xj,xj1的子树可以看作是有序集xi,,xj关于全集合xi1,,xj1的一棵二叉搜索树，其存取概率为以下的条件概率：

bkbk/wijikj

ahah/wiji1hj

5

《计算机算法设计与分析》课程设计报告

式中，wijai1bibjaj,1ijn。

设Tij是有序集xi,,xj关于存取概率ai1,bi,,bj,aj的一棵最优二叉搜索树，其平均路长为pij。Tij的根结点存储元素xm。其左右子树Tl和Tr的平均路长分别为pl和

pr。由于Tl和Tr中结点深度是它们在Tij中的结点深度减1，故有：

wi,jpi,jwi,jwi,m1plwm1,jpr

由于Tl是关于集合xi,,xm1的一棵二叉搜索树，故plpi,m1。若plpi,m1，则用Ti,m1替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。故Tl是一棵最优二叉搜索树。同理可证Tr也是一棵最优二叉搜索树。因此最优二叉搜索树问题具有最优子结构性质。

3、递归计算最优值：

最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下：

wi,jpi,jwi,jminwi,k1pi,k1wk1,jpk1,j,ij

ikj初始时，pi,i10,1in。

记wi,jpi,j为mi,j，则m1,nw1,np1,np1,n为所求的最优值。 计算mi,j的递归式为：

mi,jwi,jminmi,k1mk1,j,ij

ikjmi,i10,1in

据此，可设计出解最优二叉搜索树问题的动态规划算法。

算法实现题: 给出标识符集{1,2,3}={do,if,stop}存取概率，若

b1=0.4 b2=0.2

b3=0.05 a0=0.2 a1=0.05 a2=0.05 a3=0.05构造一棵最优二叉搜索树 源程序如下： #include using namespace std;

6

《计算机算法设计与分析》课程设计报告

void OptimalBinarySearchTree(float a[],float b[],int n,float m[][20],int s[][20],float w[][20]) { //求解最优值的方法 int i,r,k; float t;

for(i=0;i<=n;i++){

w[i+1][i]=a[i]; //搜索不到的点,最优解为0 m[i+1][i]=0; }

for(r=0;rint j=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{ //以k为根节点，左子树不为空 m[i][j]=t;

s[i][j]=k; } }

m[i][j]+=w[i][j]; } for(i=1;i<=n;i++) for(int j=1;j<=n;j++)

cout<<\"s[\"<void print(int i,int j,int s[][20],int S[]) //递归输出结果 {

if(j>=i){

7

《计算机算法设计与分析》课程设计报告

int k=s[i][j]; cout<<\"(\"; print(i,k-1,s,S); cout<<\")\";

cout<<\" \"<{ //主函数 int n,i;

float a[20],b[20],m[20][20],w[20][20]; int s[20][20],S[20];

cout<<\"请输入有序集元素的个数n：\"<>n;

cout<<\"请输入有序集各元素的值S[i](一共\"<>S[i];

cout<<\"请输入概率数组a的各元素的值a[i](一共\"<>a[i];

cout<<\"请输入概率数组b的各元素的值b[i](一共\"<>b[i];

OptimalBinarySearchTree(a,b,n,m,s,w);

cout<<\"最优值即平均步长为：\"<运行结果如下：

8

《计算机算法设计与分析》课程设计报告

图2

 回溯法—图的着色 1、图的m着色问题描述：

给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

2、算法设计：

一般连通图的可着色法问题并不仅限于平面图。给定图GV,E和m种颜色，如果这个图不是m可着色，则给出否定答案；如果这个图是m可着色的，找出所有不同的着色方法

下面根据回朔法的递归描述框架Backtrack设计图的m着色算法。用图的邻接矩阵a表示无向量连通图GV,E。若i,j属于图GV,E的边集E，则aij1，否则

aij0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用xi表示，数组x1:n是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第

i1in层中每一结点都有m个儿子，每个儿子相应于xi的m个可能的着色之一。 第

n+1层结点均为叶结点。

9

《计算机算法设计与分析》课程设计报告

在下面的解图的m可着色问题的回溯法中，Backtracki搜索解空间中第i层子树。类Color的数据成员记录解空间中结点信息，以减少传给Backtrack的参数。sum记录当前已找到的m着色方案数。

在算法Backtrack中，当in时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum则增1。而当in时,当前扩展结点Z的每一个解空间中内部结点.该结点有xi1,2,,m共m个儿子结点.对当前扩展结点Z的每一儿子结点,有方法ok检查其可行性,并以深度优先的方式递归的对可行子树搜索,或减去不可行树。

算法实现题: 给定如图3所示的一个无向连通图G，现有4种不同的颜色，用这4种

颜色为图G的各顶点着色，每个顶点着一种颜色。要求：G中每条边的2个顶点着有不同的颜色。问一共有多少种着色方案？

1 2 3

5 4 图3

源程序如下： #include using namespace std;

int n; //图的顶点个数 int m; //可用颜色数 int i,j;

int a[10][10]; //程序中使用时从下标1开始;程序中用于存储图的邻接矩阵 int x[10]; //用于存储当前解

long sum; //当前已找到的可着色方案数

10

《计算机算法设计与分析》课程设计报告

bool Ok(int k) {

for(int j=1;j<=n;j++) {

if((a[k][j]==1)&&(x[j]==x[k])) //a[k][j]==1表示的是第k点和第j点是相连的

return false;

} }

void Backtrack(int t) {

if(t>n) //t是表示的第t行叶结点；图的m着色共有n个结点 return true;

{

}

sum++;

cout<<\" 第\"<cout<cout<else

{

for(int i=1;i<=m;i++) {

x[t]=i; if(Ok(t)) { }

11

Backtrack(t+1); //判断t+1结点的颜色是不是正确

《计算机算法设计与分析》课程设计报告

}

}

}

x[t]=0; //把t+1结点的颜色换一种

long mColoring(int mm) {

m=mm; sum=0; Backtrack(1); return sum; }

void main() {

cout<<\"\\n\==========图的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<<\" 无可行方案！\"<cout<<\"-------------------------------------------------------------------------------\"<运行结果如下：

12

《计算机算法设计与分析》课程设计报告

图4

图5

五、总结：

通过本次课程设计，使我对快速排序、最优二叉搜索树以及图的m着色设计的基本过

程的设计方法、步骤、思路、有了一定的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是远远不够的，我们还必须要深切的理解每个算法的思想，并且能够利用c++语言去编写相关的代码，经过不断的修改、调试，使之能解决相应的问题，最终

13

《计算机算法设计与分析》课程设计报告

能运用到实际案例中去。

对我们来说，实际能力的培养至关重要，而这种实际能力的培养单靠课堂教学是远远不够的，必须从课堂走向实践。而这次的课程设计，正好给了我们一个机会让我们找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识，为求职与正式工作做好充分的知识、能力准备，从而缩短从校园走向社会的心理转型期。

14