分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题.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的一个严格递增下标序列<i0，i1，…，i(k-1)>，使得对所有的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 <iostream>
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(left<right)//至少有2个元素
{
i=(left+right)/2;//取中点
int b[100];
MergeSort(a,left,i);//递归调用分别对两个字问题排序
MergeSort(a,i+1,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["<<n<<"]:";
for( i=0;i<n;i++)
cin>>a[i];
MergeSort(a,0,n-1);
cout<<"输出排序为:";
for ( i=0;i<n;i++)
cout<<a[i]<<' ';
cout<<endl;
return 0;
}
运行截图：

2、矩阵连乘
例：
A1
A2
A3
A4
A5
A6
30*35
35*15
15*5
5*10
10*20
20*25

结果为：((A1(A2A3))((A4A5)A6))
C++实现代码：
#include<iostream>
#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<j;k++)
{
int t=m[i][k]+m[k+1][j]+matrix[i].row*matrix[k].col*matrix[j].col;
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
void matrixMultiply(Matrix matrix[MAX],int n)
{
bool flag=false;//标识矩阵的阶数是否要重新输入
int i;
cout<<"请输入每个矩阵行数与列数:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"A"<<i<<"行数：";
cin>>matrix[i].row;
cout<<"A"<<i<<"列数：";
cin>>matrix[i].col;
}
//检查Ai的列数是否等于Ai+1的行数
for(i=1;i<n;i++)
{
if(matrix[i].col!=matrix[i+1].row)
{
cout<<"输入的矩阵不可乘，请重新输入!"<<endl;
flag=true;
break;
}
}
if(flag)
{
matrixMultiply(matrix,n);
}

}
//打印加括号后的
void traceback(int i,int j)
{
if(i==j)
{
cout<<"A"<<i;
}
else
{
cout<<"(";
traceback(i,s[i][j]);
traceback(s[i][j]+1,j);
cout<<")";
}
}
void main()
{
//变量m,s初始化
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
cout<<"请输入矩阵的个数:"<<endl;
cin>>n;
matrixMultiply(matrix,n);
MaxtrixChain(matrix,n,m,s);
cout<<"加括号之后:"<<endl;
traceback(1,n);
cout<<endl;
}
运行截图：

3、最长公共子序列
例：
x="cbwdabh" y="sdabwyz"
c[i][j]： b[i][j]：

最终结果为：dab
C++实现代码：
#include<iostream>
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<<x[i-1];
}
else if(b[i][j]==2)//输出第二类元素对应的x[]
LCS(b,x,i-1,j);
else//输出第三类元素对应的x[]
LCS(b,x,i,j-1);
}
void main()
{
char x[MAX];
char y[MAX] ;
cout<<"输入字符串x:"<<endl;
cin>>x;
cout<<"输入字符串y:"<<endl;
cin>>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<<"最长公共子序列为:"<<endl;
LCS(b,x,m,n);
cout<<endl;
}
运行截图：

4、Hufman编码
例：
a b c d 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<iostream>
#include<string>
#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;i<n;i++)//给结构体进行赋值
{
huffnode[i].weight=m[i];//给哈夫曼结点赋权值
huffcode[i].leaf=cha[i];//给哈夫曼编码叶子赋字符
}
for(i=0;i<n-1;i++)//找出最小的两个频率树并合并出一个新的树
{
m1=m2=MAX;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if (huffnode[j].weight<=m1&&huffnode[j].flag==0)
{
m2=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].flag=1;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while(p!=0)//构建哈夫曼编码权值
{
if(huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
cout<<huffcode[i].leaf<<":";
for(j=cd.start+1;j<n;j++)//输出编码值
{
huffcode[i].bit[j]=cd.bit[j];
cout<<cd.bit[j];
}
cout<<endl;
huffcode[i].start=cd.start;
}
delete[] huffcode;//释放空间
delete[] huffnode;//释放空间
}
void main()
{
int i=0,n,m[100],k;
char cha[100];
cout<<"输入的总字符n:";
cin>>n;
k=n;
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"个字符为:";
cin>>cha[i];
cout<<"字符"<<cha[i]<<"的个数:";
cin>>m[i];
}
cout<<"每个字符的哈夫曼编码是:"<<endl;
huffman(cha,m,k);
}
运行截图：

五、总结
经过两个星期的计算机算法设计与分析课程设计，终于顺利完成这次课程设计。通过这次课程设计，收获颇丰。
1、对算法理解更深
通过该课程设计，掌握了计算机算法程序，以及算法的运行原理。通过VC++ 6.0编译器编译算法程序，将书上的算法实现在计算机上，把原来以为很深奥的书本知识变的更为简单，对算法原理有更深的理解。
2、对该算法理论在实践中的应用有深刻的理解
通过把算法程序在计算机上实现，知道和理解了算法在计算机中是怎样执行的，对算法理论在实践中的应用有深刻的理解。
3、激发了学习的积极性
通过该课程设计，全面系统的理解了算法的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机算法的知识得到了强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对算法理论知识的理解。以前对与计算机算法的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了算法的作用，对计算机编程能力也有了进一步的提升。
4、理解了该知识点以及学科之间的融合渗透
本次课程设计程序部分是用C++语言编写的，把《数据结构》 《计算机算法设计与分析》 《C++程序设计》三门学科联系起来，把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机学科知识的认识更加深刻，进一步加深了对这三门课程的认识。
3、通过活动，使学生养成博览群书的好习惯。
B比率分析法和比较分析法不能测算出各因素的影响程度。√
C采用约当产量比例法，分配原材料费用与分配加工费用所用的完工率都是一致的。Ｘ
C采用直接分配法分配辅助生产费用时，应考虑各辅助生产车间之间相互提供产品或劳务的情况。错
C产品的实际生产成本包括废品损失和停工损失。√
C成本报表是对外报告的会计报表。×
C成本分析的首要程序是发现问题、分析原因。×
C成本会计的对象是指成本核算。×
C成本计算的辅助方法一般应与基本方法结合使用而不单独使用。√
C成本计算方法中的最基本的方法是分步法。X
D当车间生产多种产品时，“废品损失”、“停工损失”的借方余额，月末均直接记入该产品的产品成本
中。×
D定额法是为了简化成本计算而采用的一种成本计算方法。×
F“废品损失”账户月末没有余额。√
F废品损失是指在生产过程中发现和入库后发现的不可修复废品的生产成本和可修复废品的修复费用。Ｘ
F分步法的一个重要特点是各步骤之间要进行成本结转。(√)
G各月末在产品数量变化不大的产品，可不计算月末在产品成本。错
G工资费用就是成本项目。(×)
G归集在基本生产车间的制造费用最后均应分配计入产品成本中。对
J计算计时工资费用，应以考勤记录中的工作时间记录为依据。(√)
J简化的分批法就是不计算在产品成本的分批法。(×)
J简化分批法是不分批计算在产品成本的方法。对
J加班加点工资既可能是直接计人费用，又可能是间接计人费用。√
J接生产工艺过程的特点，工业企业的生产可分为大量生产、成批生产和单件生产三种，X
K可修复废品是指技术上可以修复使用的废品。错
K可修复废品是指经过修理可以使用，而不管修复费用在经济上是否合算的废品。Ｘ
P品种法只适用于大量大批的单步骤生产的企业。×
Q企业的制造费用一定要通过“制造费用”科目核算。Ｘ
Q企业职工的医药费、医务部门、职工浴室等部门职工的工资，均应通过“应付工资”科目核算。Ｘ
S生产车间耗用的材料，全部计入“直接材料”成本项目。Ｘ
S适应生产特点和管理要求，采用适当的成本计算方法，是成本核算的基础工作。(×)
W完工产品费用等于月初在产品费用加本月生产费用减月末在产品费用。对
Y“预提费用”可能出现借方余额，其性质属于资产，实际上是待摊费用。对
Y引起资产和负债同时减少的支出是费用性支出。X
Y以应付票据去偿付购买材料的费用，是成本性支出。X
Y原材料分工序一次投入与原材料在每道工序陆续投入，其完工率的计算方法是完全一致的。Ｘ
Y运用连环替代法进行分析，即使随意改变各构成因素的替换顺序，各因素的影响结果加总后仍等于指标的总差异，因此更换各因索替换顺序，不会影响分析的结果。(×)
Z在产品品种规格繁多的情况下，应该采用分类法计算产品成本。对
Z直接生产费用就是直接计人费用。X
Z逐步结转分步法也称为计列半成品分步法。√

A按年度计划分配率分配制造费用，“制造费用”账户月末(可能有月末余额/可能有借方余额/可能有贷方余额/可能无月末余额)。
A按年度计划分配率分配制造费用的方法适用于(季节性生产企业)

- 16 -