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

1、 计算机算法设计与分析课程设计 分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题一、课程设计目的本次课程设计可以说是我们学完计算机算法设计与分析这门课程后的一次综合性训练。 本课程设计的训练的目的是：1、 巩固和掌握计算机算法设计和分析课程的基础知识。2、 培养使用计算机基本算法解决实际问题的能力。3、 提升使用程序设计语言对算法程序的开发、调试和测试能力。4、 对一定的实际问题，能够设计求解算法并分析算法的效率。5、提高综合运用算法、程序设计语言等能力。6、掌握文档的书写能力。二、课程设计内容1、 分治法（1） 合并排序2、 动态规划（1） 矩阵连乘

2、（2） 最长公共子序列3、 贪心法（1） 哈夫曼编码三、概要设计1、 分治法基本思想:将规模为n的问题分解为k个规模较小的子问题，使这些子问题相互独立可分别求解，再将k个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。在分治法中,子问题的解法通常与原问题相同。（1） 合并排序问题描述将n个元素排成非递减顺序。算法思路若n为1，算法终止；否则，将n个待排元素分割成k(k=2)个大致相等子集合A, B, 对每一个子集合分别递归排序,再将排好序的子集归并为一个集合。2、 动态规划基本思想：将问题的求解过程化为多步选择，在每一步选择上，列出各种可能的结果(各子问

3、题的可行解)，舍去那些肯定不能成为最优解的局部解。最后一步得到的解必是最优解。求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果，总能得到最优解。（1） 矩阵连乘问题描述给定n个矩阵A1，An，其中Ai与A(i-1)是可相乘的。确定一个计算次序，使计算矩阵连乘积A1An所需计算量最少。例如，三个矩阵连乘，两种计算顺序(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的总时间长度为10100

4、00。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的最优次序，最优解结构设A1:n= A1An，最优计算次序在Ak和A(k+1)间断开，则总计算量=A1:k的计算量+Ak+1:n的计算量+A1:k*Ak+1:n则矩阵子链A1:k和Ak+1:n的计算次序也必最优。递推关系设计算Ai:j=AiAj所需最少次数乘法为mij，A

5、i的维数设为matrixi.row*matrixi.col。构造最优解记mij的断开位置k为sij,在计算出mij后,可由sij递归构造相应的最优解。（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，用cij记录xi与yj的LCS 的长度，bij记录cij是通过哪

6、一个子问题的值求得的，以决定搜索的方向。由自底向上进行递推计算，那么在计算ci,j之前 ci-1j-1，ci-1j与cij-1均已计算出来。此时我们根据xi=yj还是xi!=yj，就可以计算出cij。问题的递归式写成：3、 贪心法基本思想:将问题的求解过程看作一系列选择，每次选择都是当前状态下的局部最优解。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体最优解。（1） 哈夫曼编码问题描述 通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就会降低。要求找到一个编码方案，使

7、传输的数据量最少。哈夫曼编码就是一种最佳编码方案。算法思路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 a0 a1 a2 a3 a4 a5 a6 8 4 7 3 6 5 2 排序后归并到b 4 8 7 3 6 5 2 复制到a 4 8 7 3 6 5 2 排

8、序后归并到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 8C+实现代码为：#include <iostream>using namespace std;void Merge(int a,int b,int l,int m,int r)/合并al:m和bm+1:r存入到bl:r中int i=l,j=m+1,k=l;while (i<=m)&&(j<=r)if (ai<=aj)bk+=ai+;else bk+=

9、aj+;if (i>m)for(int q=j;q<=r;q+)bk+=aq;else for(int q=i;q<=m;q+)bk+=aq;void Copy(int a,int b,int s,int n)for(int i=s;i<=n;i+)ai=bi;void MergeSort(int a,int left,int right)int i;if(left<right)/至少有2个元素 i=(left+right)/2;/取中点int b100;MergeSort(a,left,i);/递归调用分别对两个字问题排序MergeSort(a,i+1,righ

10、t);Merge(a,b,left,i,right);/合并到数组bCopy(a,b,left,right);/复制回数组aint main()int a100;int n,i;cout<<"输入元素个数n:"cin>>n;cout<<"输入一维数组a"<<n<<":"for( i=0;i<n;i+)cin>>ai;MergeSort(a,0,n-1);cout<<"输出排序为:"for ( i=0;i<n;i+)cou

11、t<<ai<<' 'cout<<endl;return 0;运行截图：2、矩阵连乘例：A1A2A3A4A5A630*3535*1515*55*1010*2020*25结果为：(A1(A2A3)(A4A5)A6)C+实现代码：#include<iostream>#define MAX 100using namespace std;struct Matrix /矩阵int row; /矩阵行数int col; /矩阵列数;/矩阵Matrix matrixMAX;/mij存储Ai到Aj的最小乘法次数int mMAXMAX;/sij存储A

12、i到Aj之间加括号的位置int sMAXMAX;/矩阵个数int n;void MaxtrixChain(Matrix matrixMAX,int n,int mMAXMAX,int sMAXMAX)/计算m和sfor(int r=2;r<=n;r+)for(int i=1;i<=n-r+1;i+)int j=i+r-1;mij=mi+1j+matrixi.row*matrixi.col*matrixj.col;sij=i;for(int k=i+1;k<j;k+)int t=mik+mk+1j+matrixi.row*matrixk.col*matrixj.col;if(t

13、<mij)mij=t;sij=k;void matrixMultiply(Matrix matrixMAX,int n)bool flag=false;/标识矩阵的阶数是否要重新输入int i;cout<<"请输入每个矩阵行数与列数:"<<endl;for(i=1;i<=n;i+)cout<<"A"<<i<<"行数："cin>>matrixi.row;cout<<"A"<<i<<"列数：

14、"cin>>matrixi.col; /检查Ai的列数是否等于Ai+1的行数for(i=1;i<n;i+)if(matrixi.col!=matrixi+1.row)cout<<"输入的矩阵不可乘，请重新输入!"<<endl;flag=true;break;if(flag)matrixMultiply(matrix,n);/打印加括号后的void traceback(int i,int j)if(i=j)cout<<"A"<<i;elsecout<<"(&q

15、uot;traceback(i,sij);traceback(sij+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

16、<<endl;运行截图：3、最长公共子序列例：x="cbwdabh" y="sdabwyz" cij： bij：最终结果为：dabC+实现代码：#include<iostream>using namespace std;#define MAX 100void LCSLength(char *x,char *y,int m,int n,int cMAXMAX,int bMAXMAX)/用b对c中的元素分成三类 int i, j; for(i=0;i<=m;i+) ci0=0; for(j=1;j<=n;j+) c0j=0

17、; for(i=1;i<=m;i+) for(j=1;j<=n;j+) if(xi-1=yj-1)/第一类c中的元素 cij=ci-1j-1+1; bij=1; else if(ci-1j>=cij-1)/第二类c中元素 cij=ci-1j; bij=2; else/第三类c中元素 cij=cij-1; bij=3; void LCS(int bMAXMAX,char *x,int i,int j) if(i=0|j=0) return; if(bij=1)/输出第一类元素对应的x LCS(b,x,i-1,j-1); cout<<xi-1; else if(bij

18、=2)/输出第二类元素对应的x LCS(b,x,i-1,j); else/输出第三类元素对应的x LCS(b,x,i,j-1);void main()char xMAX; char yMAX ; cout<<"输入字符串x:"<<endl; cin>>x; cout<<"输入字符串y:"<<endl; cin>>y; int bMAXMAX; int cMAXMAX; int m,n; m=strlen(x); n=strlen(y);LCSLength(x,y,m,n,c,b);c

19、out<<"最长公共子序列为:"<<endl; LCS(b,x,m,n);cout<<endl;运行截图：4、Hufman编码例： a b c d e f频率：45 13 12 16 9 51695141213455525301000001001111acbfed哈夫曼树为：结果为：a:0 b:101 c:100 d:111 e:1101 f:1100C+实现代码：#include<iostream> #include<string>#define MAX 32767;using namespace std;typ

20、edef struct/定义哈夫曼结点结构体int weight;/权值int flag;/标识是否有父母结点int parent;/父母结点int lchild; /左孩子结点int rchild;/右孩子结点 hnodetype;typedef struct /定义哈夫曼编码结构体int bit10;/定义编码数组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 hnodetype2*n-1;/动态分配结构体空间hc

21、odetype *huffcode=new hcodetypen,cd;/定义for(i=0;i<2*n-1;i+) /对哈夫曼结点结构体初始化huffnodei.weight=0;huffnodei.parent=0;huffnodei.flag=0;huffnodei.lchild=-1;huffnodei.rchild=-1;for(i=0;i<n;i+)/给结构体进行赋值huffnodei.weight=mi;/给哈夫曼结点赋权值huffcodei.leaf=chai;/给哈夫曼编码叶子赋字符for(i=0;i<n-1;i+)/找出最小的两个频率树并合并出一个新的树m

22、1=m2=MAX;x1=x2=0;for(j=0;j<n+i;j+)if (huffnodej.weight<=m1&&huffnodej.flag=0)m2=m1; x2=x1; m1=huffnodej.weight; x1=j; else if(huffnodej.weight<=m2&&huffnodej.flag=0) m2=huffnodej.weight; x2=j;huffnodex1.parent=n+i;huffnodex2.parent=n+i;huffnodex1.flag=1;huffnodex2.flag=1;huf

23、fnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2;for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=0)/构建哈夫曼编码权值if(huffnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-;c=p;p=huffnodec.parent; cout<<huffcodei.leaf<<":"for(j=cd.start+1;j<n;j+)/输出编码值huffcodei.bitj=cd.bitj;cout<<cd.bitj;cout<<endl;huffcodei.start=cd.start;delete huffcode;/释放空间delete huffnode;/释放空间void main()int i=0,n,m100,k;char cha100;cout<<"输入的总字符n:"cin>>n;k=n;for(i