分治法解决合并排序问题及动态规划解决矩阵连乘与最长公共子序列问题及贪心法解决哈夫曼编码问题.doc

分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题
一、课程设计目的
本次课程设计可以说是我们学完《计算机算法设计与分析》这门课程后的一次综合性训练。
本课程设计的训练的目的是：
1、 巩固和掌握计算机算法设计和分析课程的基础知识。
2、 培养使用计算机基本算法解决实际问题的能力。
3、 提升使用程序设计语言对算法程序的开发、调试和测试能力。
4、 对一定的实际问题，能够设计求解算法并分析算法的效率。
5、提高综合运用算法、程序设计语言等能力。
6、掌握文档的书写能力。
二、课程设计内容
1、 分治法
（1） 合并排序
2、 动态规划
（1） 矩阵连乘
（2） 最长公共子序列
3、 贪心法
（1） 哈夫曼编码
三、概要设计
1、 分治法
基本思想:
将规模为n的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。在分治法中,子问题的解法通常与原问题相同。
（1） 合并排序
[问题描述]
将n个元素排成非递减顺序。
[算法思路]
若n为1，算法终止；否则，将n个待排元素分割成k(k=2)个大致相等子集合A, B, 对每一个子集合分别递归排序,再将排好序的子集归并为一个集合。
2、 动态规划
基本思想：
将问题的求解过程化为多步选择，在每一步选择上，列出各种可能的结果(各子问题的可行解)，舍去那些肯定不能成为最优解的局部解。最后一步得到的解必是最优解。求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果，总能得到最优解。
（1） 矩阵连乘
[问题描述]
给定n个矩阵{A1，…，An}，其中Ai与A(i-1)是可相乘的。确定一个计算次序，使计算矩阵连乘积A1…An所需计算量最少。例如，三个矩阵连乘，两种计算顺序(A*B)*C，A*(B*C)。设A为100*1的矩阵，B为1*100的矩阵，C为100*1的矩阵, 则 D=A*B为100*100的矩阵, 需乘法次数为10000, D与C相乘，所需乘法次数为1000000, 计算(A*B)*C的总时间长度为1010000。E=B*C需乘法次数为10000, B*C为1*1的矩阵，E与A相乘，所需乘法数为100，计算A*(B*C)的时间长度只有10100。计算(A*B)*C时，还需10000个单元来存储A*B，而A*(B*C)计算过程中,只需用1个单元来存储B*C。
[算法思路]
将步骤化为多步,自底向上,先求出矩阵链长为1的最优计算次序，链长为2的最优次序，…
[最优解结构]
设A[1:n]= A1…An，最优计算次序在Ak和A(k+1)间断开，则总计算量=A[1:k]的计算量+A[k+1:n]的计算量+A[1:k]*A[k+1:n]则矩阵子链A[1:k]和A[k+1:n]的计算次序也必最优。
[递推关系]
设计算A[i:j]=Ai…Aj所需最少次数乘法为m[i][j]，Ai的维数设为matrix[i].row*matrix[i].col。

[构造最优解]
记m[i][j]的断开位置k为s[i][j],在计算出m[i][j]后,可由s[i][j]递归构造相应的最优解。
（2） 最长公共子序列
[问题描述]
字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列x=“x0，x1…，x(m-1)”，序列y=“y0，y1，…，y(k-1)”是x的子序列，存在x的一个严格递增下标序列，使得对所有的j=0，1，…，k-1，有xij=yj。
[算法思路]
引进一个二维数组c[][]，用c[i][j]记录x[i]与y[j]的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。由自底向上进行递推计算，那么在计算c[i,j]之前 c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据x[i]=y[j]还是x[i]!=y[j]，就可以计算出c[i][j]。
问题的递归式写成：

3、 贪心法
基本思想:
将问题的求解过程看作一系列选择，每次选择都是当前状态下的局部最优解。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体最优解。
（1） 哈夫曼编码
[问题描述]
通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就会降低。要求找到一个编码方案，使传输的数据量最少。哈夫曼编码就是一种最佳编码方案。
[算法思路]
1)以n个字母为结点构成n棵仅含一个点的二叉树集合，字母的频率即为结点的权。
2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。
3) 反复进行步骤2)直到只剩一棵树为止。
四、详细设计与实现
1、合并排序
例：
序列分解过程： {8 4 7 3 6 5 2}
{8 4 7 3} {6 5 2}
{8 4} {7 3} {6 5} {2}
初始序列a a[0] a[1] a[2] a[3] a[4] a[5] a[6]
{8} {4} {7} {3} {6} {5} {2}
排序后归并到b {4 8} {7 3} {6 5} {2}
复制到a {4 8} {7 3} {6 5} {2}
排序后归并到b {3 4 7 8} {2 5 6}
复制到a {3 4 7 8} {2 5 6}
排序后归并到b {2 3 4 5 6 7 8}
复制到a {2 3 4 5 6 7 8}
最终结果为： {2 3 4 5 6 7 8}
C++实现代码为：
#include
using namespace std;
void Merge(int a[],int b[],int l,int m,int r)
{//合并a[l:m]和b[m+1:r]存入到b[l:r]中
int i=l,j=m+1,k=l;
while ((i<=m)&&(j<=r))
if (a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
if (i>m)
for(int q=j;q<=r;q++)
b[k++]=a[q];
else
for(int q=i;q<=m;q++)
b[k++]=a[q];
}
void Copy(int a[],int b[],int s,int n)
{
for(int i=s;i<=n;i++)
a[i]=b[i];
}
void MergeSort(int a[],int left,int right)
{
int i;
if(left1,right);
Merge(a,b,left,i,right);//合并到数组b
Copy(a,b,left,right);//复制回数组a
}
}
int main()
{
int a[100];
int n,i;
cout<<"输入元素个数n:";
cin>>n;
cout<<"输入一维数组a["<>a[i];
MergeSort(a,0,n-1);
cout<<"输出排序为:";
for ( i=0;i
#define MAX 100
using namespace std;
struct Matrix //矩阵
{
int row; //矩阵行数
int col; //矩阵列数
};
//矩阵
Matrix matrix[MAX];
//m[i][j]存储Ai到Aj的最小乘法次数
int m[MAX][MAX];
//s[i][j]存储Ai到Aj之间加括号的位置
int s[MAX][MAX];
//矩阵个数
int n;
void MaxtrixChain(Matrix matrix[MAX],int n,int m[MAX][MAX],int s[MAX][MAX])
{//计算m[][]和s[][]
for(int r=2;r<=n;r++)
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
m[i][j]m[i+1][j]+matrix[i].row*matrix[i].col*matrix[j].col;
s[i][j]=i;
for(int k=i+1;k)
{
bool flag=false;//标识矩阵的阶数是否要重新输入
int i;
cout<<"请输入每个矩阵行数与列数:"<>matrix[i].row;
cout<<"A"<>matrix[i].col;
}
//检查Ai的列数是否等于Ai+1的行数
for(i=1;iut<<"输入的矩阵不可乘，请重新输入!"<in()
{
//变量m,s初始化
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
cout<<"请输入矩阵的个数:"<>n;
matrixMultiply(matrix,n);
MaxtrixChain(matrix,n,m,s);
cout<<"加括号之后:"< b[i][j]：

最终结果为：dab
C++实现代码：
#include
using namespace std;
#define MAX 100
void LCSLength(char *x,char *y,int m,int n,int c[MAX][MAX],int b[MAX][MAX])
{//用b[][]对c[][]中的元素分成三类
int i, j;
for(i=0;i<=m;i++)
c[i][0]=0;
for(j=1;j<=n;j++)
c[0][j]=0;
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])//第一类c[][]中的元素
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])//第二类c[][]中元素
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else//第三类c[][]中元素
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
}
void LCS(int b[MAX][MAX],char *x,int i,int j)
{
if(i==0||j==0)
return;
if(b[i][j]==1)//输出第一类元素对应的x[]
{
LCS(b,x,i-1,j-1);
cout<endl;
cin>>x;
cout<<"输入字符串y:"<>y;
int b[MAX][MAX];
int c[MAX][MAX];
int m,n;
m=strlen(x);
n=strlen(y);
LCSLength(x,y,m,n,c,b);
cout<<"最长公共子序列为:"< e f
频率：45 13 12 16 9 5
16
9
5
14
12
13
45
55
25
30
100
0
0
0
1
0
0
1
1
1
1
a
c
b
f
e
d
哈夫曼树为：
结果为：a:0
b:101
c:100
d:111
e:1101
f:1100
C++实现代码：
#include
#include
#define MAX 32767;
using namespace std;
typedef struct//定义哈夫曼结点结构体
{
int weight;//权值
int flag;//标识是否有父母结点
int parent;//父母结点
int lchild; //左孩子结点
int rchild;//右孩子结点
}hnodetype;
typedef struct //定义哈夫曼编码结构体
{
int bit[10];//定义编码数组
int start;
char leaf;
}hcodetype;
void huffman(char cha[]int m[],int n)
{
int i,j,m1,m2,x1,x2,c,p;
hnodetype *huffnode=new hnodetype[2*n-1];//动态分配结构体空间
hcodetype *huffcode=new hcodetype[n],cd;//定义
for(i=0;i<2*n-1;i++) //对哈夫曼结点结构体初始化
{
huffnode[i].weight=0;
huffnode[i].parent=0;
huffnode[i].flag=0;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
{
m2=huffnode[j].weight;
x2=j;
}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[x1].flag=1;
huffnode[x2].flag1;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<
delete[] huffnode;//释放空间
}
void main()
{
int i=0,n,m[100],k;
char cha[100];
cout<<"输入的总字符n:";
cin>>n;
k=n;
for(i=0;i>cha[i];
cout<<"字符"<>m[i];
}
cout<<"每个字符的哈夫曼编码是:"<}
运行截图：

五、总结
经过两个星期的计算机算法设计与分析课程设计，终于顺利完成这次课程设计。通过这次课程设计，收获颇丰。
1、对算法理解更深
通过该课程设计，掌握了计算机算法程序，以及算法的运行原理。通过VC++ 6.0编译器编译算法程序，将书上的算法实现在计算机上，把原来以为很深奥的书本知识变的更为简单，对算法原理有更深的理解。
2、对该算法理论在实践中的应用有深刻的理解
通过把算法程序在计算机上实现，知道和理解了算法在计算机中是怎样执行的，对算法理论在实践中的应用有深刻的理解。
3、激发了学习的积极性
通过该课程设计，全面系统的理解了算法的一般原理和基本实现方法把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机算法的知识得到了强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对算法理论知识的理解。以前对与计算机算法的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了算法的作用，对计算机编程能力也有了进一步的提升。
4、理解了该知识点以及学科之间的融合渗透
本次课程设计程序部分是用C++语言编写的，把《数据结构》 《计算机算法设计与分析》 《C++程序设计》三门学科联系起来，把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机学科知识的认识更加深刻，进一步加深了对这三门课程的认识。

- 14 - / 14