《分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题》由会员分享，可在线阅读，更多相关《分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题（15页珍藏版）》请在金锄头文库上搜索。
1、 计算机算法设计与分析课程设计 - 1 -分治法解决合并排序问题及动态规划解决分治法解决合并排序问题及动态规划解决 矩阵连乘和最长公共子序列问题及贪心法矩阵连乘和最长公共子序列问题及贪心法 解决哈夫曼编码问题解决哈夫曼编码问题一、课程设计目的一、课程设计目的本次课程设计可以说是我们学完计算机算法设计与分析这门课程后的一次综合性训练。 本课程设计的训练的目的是：1、巩固和掌握计算机算法设计和分析课程的基础知识。2、培养使用计算机基本算法解决实际问题的能力。3、提升使用程序设计语言对算法程序的开发、调试和测试能力。4、对一定的实际问题，能够设计求解算法并分析算法的效率。5、提高综合运用算法、程序设
2、计语言等能力。6、掌握文档的书写能力。二、课程设计内容二、课程设计内容1、分治法（1）合并排序2、动态规划（1）矩阵连乘（2）最长公共子序列3、贪心法（1）哈夫曼编码三、概要设计三、概要设计1、分治法基本思想:计算机算法设计与分析课程设计 - 2 -将规模为 n 的问题分解为 k 个规模较小的子问题，使这些子问题相互独立可分别求解，再将 k 个子问题的解合并成原问题的解。如子问题的规模仍很大，则反复分解直到问题小到可直接求解为止。在分治法中,子问题的解法通常与原问题相同。（1）合并排序问题描述将 n 个元素排成非递减顺序。算法思路若 n 为 1，算法终止；否则，将 n 个待排元素分割成 k(k
3、=2)个大致相等子集合 A, B, 对每一个子集合分别递归排序,再将排好序的子集归并为一个集合。2、动态规划基本思想：将问题的求解过程化为多步选择，在每一步选择上，列出各种可能的结果(各子问题的可行解)，舍去那些肯定不能成为最优解的局部解。最后一步得到的解必是最优解。求解过程多为自底向上,求解过程产生多个选择序列, 下一步的选择依赖上一步的结果，总能得到最优解。（1）矩阵连乘问题描述给定 n 个矩阵A1，An，其中 Ai 与 A(i-1)是可相乘的。确定一个计算次序，使计算矩阵连乘积 A1An 所需计算量最少。例如，三个矩阵连乘，两种计算顺序(A*B)*C，A*(B*C)。设 A 为 100*
4、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 的最优计算次序，链
5、长为 2 的最优次序，最优解结构计算机算法设计与分析课程设计 - 3 -设 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，Ai 的维数设为 matrixi.row*matrixi.col。 jijijimjkicolmatrixj.colmatrixk.rowmatrixi.1jmkmikmin0 构造最优解记 mij的断开位置 k 为 sij,在计算出 mij后,可由 sij递归
6、构造相应的最优解。（2）最长公共子序列问题描述字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 x=“x0，x1，x(m-1)” ，序列 y=“y0，y1，y(k-1)”是 x 的子序列，存在 x 的一个严格递增下标序列，使得对所有的 j=0，1，k-1，有 xij=yj。算法思路引进一个二维数组 c，用 cij记录 xi与 yj的 LCS 的长度，bij记录 cij是通过哪一个子问题的值求得的，以决定搜索的方向。由自底向上进行递推计算，那么在计算ci,j之前 ci-1j-1，ci-1j与 cij-1均已计算出来。此
7、时我们根据 xi=yj还是 xi!=yj，就可以计算出 cij。问题的递归式写成：jiji yxyxjandandorjijiiifififjicjicjicjic00,0,0), 1,1,max(1 1, 10,3、贪心法基本思想:计算机算法设计与分析课程设计 - 4 -将问题的求解过程看作一系列选择，每次选择都是当前状态下的局部最优解。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体最优解。（1）哈夫曼编码问题描述 通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就
8、会降低。要求找到一个编码方案，使传输的数据量最少。哈夫曼编码就是一种最佳编码方案。算法思路1)以 n 个字母为结点构成 n 棵仅含一个点的二叉树集合，字母的频率即为结点的权。2)每次从二叉树集合中找出两个权最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。3) 反复进行步骤 2)直到只剩一棵树为止。四、详细设计与实现四、详细设计与实现1、合并排序例： 序列分解过程： 8 4 7 3 6 5 28 4 7 3 6 5 28 4 7 3 6 5 2初始序列 a a0 a1 a2 a3 a4 a5 a68 4 7 3 6 5 2 排序后归并到 b 4 8 7
9、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 8C+实现代码为：计算机算法设计与分析课程设计 - 5 -#include 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 (im) for(int q=j
10、;qn; coutai; MergeSort(a,0,n-1); cout #define MAX 100 using namespace std; struct Matrix /矩阵 int row; /矩阵行数 int col; /矩阵列数 ; /矩阵 Matrix matrixMAX; /mij存储 Ai 到 Aj 的最小乘法次数 int mMAXMAX; /sij存储 Ai 到 Aj 之间加括号的位置A1A2A3A4A5A630*3535*1515*55*1010*2020*25计算机算法设计与分析课程设计 - 7 -int sMAXMAX; /矩阵个数 int n; void Max
11、trixChain(Matrix matrixMAX,int n,int mMAXMAX,int sMAXMAX) /计算 m和 s for(int r=2;rmatrixi.row; coutmatrixi.col; /检查 Ai 的列数是否等于 Ai+1 的行数 for(i=1;in; matrixMultiply(matrix,n); MaxtrixChain(matrix,n,m,s); cout using namespace std; #define MAX 100 void LCSLength(char *x,char *y,int m,int n,int cMAXMAX,int
12、 bMAXMAX) /用 b对 c中的元素分成三类int i, j; for(i=0;i=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)/输出第一类元素对应的 xLCS(b,x,i-1,j-1);coutx;计算机算法设计与分析课程设计 - 11 -couty;int bMAXMAX;int cMAXMAX;int m,n; m=strlen(x);n=strlen(y); LCSL
13、ength(x,y,m,n,c,b); cout #include #define MAX 32767; using namespace std; typedef 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;/动态分配结构体空间 hcodetype *huffcode=new hcodetypen,cd;/定义 for(i=0;in; k=n; for(i=0;ichai; coutmi;
