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

计算机算法设计与分析 课程设计 1 分治法解决合并排序问题及动态规划解决 矩阵连乘和最长公共子序列问题及贪心法 解决哈夫曼编码问题 一 课程设计目的 本次课程设计可以说是我们学完 计算机算法设计与分析 这门课程后的一次综合性 训练 本课程设计的训练的目的是 1 巩固和掌握计算机算法设计和分析课程的基础知识 2 培养使用计算机基本算法解决实际问题的能力 3 提升使用程序设计语言对算法程序的开发 调试和测试能力 4 对一定的实际问题 能够设计求解算法并分析算法的效率 5 提高综合运用算法 程序设计语言等能力 6 掌握文档的书写能力 二 课程设计内容 1 分治法 1 合并排序 2 动态规划 1 矩阵连乘 2 最长公共子序列 3 贪心法 1 哈夫曼编码 三 概要设计 1 分治法 基本思想 计算机算法设计与分析 课程设计 2 将规模为 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 的最优次序 最优解结构 计算机算法设计与分析 课程设计 3 设 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 jijimjki colmatrix j colatrix k rowmatix 1 jk i n0 构造最优解 记 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 的一个严格递增下标序列 使得对所有的 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 问题的递归式写成 jiyxjandorjiifficjijic 0 1 max 0 3 贪心法 基本思想 计算机算法设计与分析 课程设计 4 将问题的求解过程看作一系列选择 每次选择都是当前状态下的局部最优解 每作一 次选择后 所求问题会简化为一个规模更小的子问题 从而通过每一步的最优解逐步达到 整体最优解 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 实现代码为 计算机算法设计与分析 课程设计 5 include 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 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 cout 输入一维数组 a n for i 0 i a i MergeSort a 0 n 1 cout 输出排序为 计算机算法设计与分析 课程设计 6 for i 0 i n i cout a i cout endl return 0 运行截图 2 矩阵连乘 例 结果为 A1 A2A3 A4A5 A6 C 实现代码 include 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 之间加括号的位置 A1 A2 A3 A4 A5 A6 30 35 35 15 15 5 5 10 10 20 20 25 计算机算法设计与分析 课程设计 7 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 matrix i row cout A i 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 计算机算法设计与分析 课程设计 8 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 请输入矩阵的个数 n matrixMultiply matrix n MaxtrixChain matrix n m s cout 加括号之后 endl traceback 1 n cout endl 运行截图 计算机算法设计与分析 课程设计 9 3 最长公共子序列 例 x cbwdabh y sdabwyz c i j b i j 最终结果为 dab C 实现代码 include 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 计算机算法设计与分析 课程设计 10 for j 1 j n j c 0 j 0 for i 1 i m i for j 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 x 计算机算法设计与分析 课程设计 11 cout 输入字符串 y 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 哈夫曼树为 结果为 a 0 b 101 16 95 1412 13 45 55 25 30 100 0 0 0 1 0 0 1 1 1 1 a c b f e d 计算机算法设计与分析 课程设计 12 c 100 d 111 e 1101 f 1100 C 实现代码 include include 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 找出最小的两个频率树并合并出一个新的树 计算机算法设计与分析 课程设计 13 m1 m2 MAX x1 x2 0 for j 0 j n i j if huffnode j weight m1 x2 x1 m1 huffnode j weight x1 j else if huffnode j weight m2 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 输出编码值 计算机算法设计与分析 课程设计 14 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 k n for i 0 i n i cout 第 i 1 cha i cout 字符 cha i m i cout 每个字符的哈夫曼编码是 endl huffman cha m k 运行截图 五 总结 经过两个星期的计算机算法设计与分析课程设计 终于顺利完成这次课程设计 通过 这次课程设计 收获颇丰 计算机算法设计与分析 课程设计 15 1 对算法理解更深 通过该课程设计 掌握了计算机算法程序 以及算法的运行原理 通过 VC 6 0 编译 器编译算法程序 将书上的算法实现在计算机上 把原来以为很深奥的书本知识变的更为 简单 对算法原理有更深的理解 2 对该算法理论在实践中的应用有深刻的理解 通过把算法程序在计算机上实现 知道和理解了算法在计算机中是怎样执行的 对算 法理论在实践中的应用有深刻的理解 3 激发了学习的积极性 通过该课程设计 全面系统的理解了算法的一般原理和基本实现方法 把死板的课本 知识变得生动有趣 激发了学习的积极性 把学过的计算机算法的知识得到了强化 能够 把课堂上学的知识通过自己设计的程序表示出来 加深了对算法理论知识的理解 以前对 与计算机算法的认识是模糊的 概念上的 现在通过自己动手做实验 从实践上认识了算 法的作用 对计算机编程能力也有了进一步的提升 4 理解了该知识点以及学科之间的融合渗透 本次课程设计程序部分是用 C 语言编写的 把 数据结构 计算机算法设计与分 析 C 程序设计 三门学科联系起来 把各个学科之间的知识融合起来 把各门课程 的知识联系起来 对计算机学科知识的认识更加深刻 进一步加深了对这三门课程的认识