《计算机算法设计与分析》课程设计
分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法
解决哈夫曼编码问题
一、课程设计目的
本次课程设计可以说是我们学完《计算机算法设计与分析》这门课程后的一次综合性训练。
本课程设计的训练的目的是：
1、巩固和掌握计算机算法设计和分析课程的基础知识。 2、培养使用计算机基本算法解决实际问题的能力。
3、提升使用程序设计语言对算法程序的开发、调试和测试能力。 4、对一定的实际问题，能够设计求解算法并分析算法的效率。 5、提高综合运用算法、程序设计语言等能力。 6、掌握文档的书写能力。
二、课程设计内容
1、分治法 （1）合并排序 2、动态规划 （1）矩阵连乘 （2）最长公共子序列 3、贪心法 （1）哈夫曼编码
三、概要设计
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的最优次序，?
[最优解结构]
- 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。
0?i?j?m[i][j]??min{m[i][k]?m[k?1][j]?matrix[i].row?matrix[k].col?matrix[j].col}i?j??i?k?j
[构造最优解]
记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的一个严格递增下标序列
[算法思路]
引进一个二维数组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]。
问题的递归式写成：
0ifi?0orj?0??c[i,j]??c[i?1,j?1]?1ifi,j?0andxi?yj
?max(c[i,j?1],c[i?1,j])ifi,j?0andx?yij?
3、贪心法 基本思想:
- 3 -
分治法解决合并排序问题及动态规划解决矩阵连乘和最长公共子序列问题及贪心法解决哈夫曼编码问题
