1、 计算机算法设计与分析课程设计 - 1 -分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题一、课程设计目的本次课程设计可以说是我们学完计算机算法设计与分析这门课程后的一次综合性训练。 本课程设计的训练的目的是：1、巩固和掌握计算机算法设计和分析课程的基础知识。2、培养使用计算机基本算法解决实际问题的能力。3、提升使用程序设计语言对算法程序的开发、调试和测试能力。4、对一定的实际问题，能够设计求解算法并分析算法的效率。5、提高综合运用算法、程序设计语言等能力。6、掌握文档的书写能力。二、课程设计内容1、分治法（1）合并排序2、动态规划（1）矩阵连乘（2）
2、最长公共子序列3、贪心法（1）哈夫曼编码三、概要设计1、分治法基本思想:计算机算法设计与分析课程设计 - 2 -将规模为 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 的矩阵, 需乘法次数为 100
4、00, 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 的最优次序，最优解结构计算机算法设计与分析课程设计 - 3 -设 A1:n= A1An，最优计算次序在 Ak 和 A(k+1
5、)间断开，则总计算量=A1:k 的计算量+Ak+1:n的计算量+A1:k*Ak+1:n则矩阵子链 A1:k和 Ak+1:n的计算次序也必最优。递推关系设计算 Ai:j=AiAj 所需最少次数乘法为 mij，Ai 的维数设为 matrixi.row*matrixi.col。 jijimjki colmatrixj.colatrixk.rowmatix.1jkin0构造最优解记 mij的断开位置 k 为 sij,在计算出 mij后,可由 sij递归构造相应的最优解。（2）最长公共子序列问题描述字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序
6、列。令给定的字符序列 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均已计算出来。此时我们根据 xi=yj还是 xi!=yj，就可以计算出 cij。问题的递归式写成： jiyxjandorjiifficjijic 0,),1,m
7、ax(0,3、贪心法基本思想:计算机算法设计与分析课程设计 - 4 -将问题的求解过程看作一系列选择，每次选择都是当前状态下的局部最优解。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体最优解。（1）哈夫曼编码问题描述 通讯过程中需将传输的信息转换为二进制码。由于英文字母使用频率不同，若频率高的字母对应短的编码，频率低的字母对应长的编码，传输的数据总量就会降低。要求找到一个编码方案，使传输的数据量最少。哈夫曼编码就是一种最佳编码方案。算法思路1)以 n 个字母为结点构成 n 棵仅含一个点的二叉树集合，字母的频率即为结点的权。2)每次从二叉树集合中找出两个
8、权最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。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 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
9、 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;qn;coutai;MergeSort(a,0,n-1);cout#define MAX 100using namespace std;struct Matrix /矩阵int row; /矩阵行数int col; /矩阵列数;/
10、矩阵Matrix matrixMAX;/mij存储 Ai 到 Aj 的最小乘法次数int mMAXMAX;/sij存储 Ai 到 Aj 之间加括号的位置A1 A2 A3 A4 A5 A630*35 35*15 15*5 5*10 10*20 20*25计算机算法设计与分析课程设计 - 7 -int sMAXMAX;/矩阵个数int n;void MaxtrixChain(Matrix matrixMAX,int n,int mMAXMAX,int sMAXMAX)/计算 m和 sfor(int r=2;rmatrixi.row;coutmatrixi.col;/检查 Ai 的列数是否等于 Ai
11、+1 的行数for(i=1;in;matrixMultiply(matrix,n);MaxtrixChain(matrix,n,m,s);coutusing 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=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;
