算法设计与分析实验指导书.docx

本文格式为Word版，下载可任意编辑算法设计与分析实验指导书 测验一——串匹配问题 1．测验题目 给定一个文本，在该文本中查找并定位任意给定字符串 2．测验目的 ⑴ 深刻理解并掌管蛮力法的设计思想； ⑵ 提高应用蛮力法设计算法的技能； ⑶ 理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本举行确定程度的革新，提升其时间性能 3．测验要求 ⑴ 实现BF算法； ⑵ 实现BF算法的提升算法：KMP算法和BM算法； ⑶ 对上述三个算法举行时间繁杂性分析，并设计测验程序验证分析结果 4．实现提示 BF算法、KMP算法和BM算法都是串匹配问题中的经典算法，BF算法和KMP算法请参见本章第2节下面介绍BM算法 BM（Boyer-Moore）算法是Boyer和Moore共同设计的快速串匹配算法BM算法与KMP算法的主要识别是匹配操作的方向不同虽然BM算法仅把匹配操作的字符对比依次改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化 为了便当议论，假设字符表∑＝{a, b, …, y, z}，BM算法的关键是，对给定的模式T=\t1t2 … tm\，定义一个从字符到正整数的映射： dist: c→{1, 2,… , m} （c∈∑） 函数dist称为滑动距离函数，它给出了正文中可能展现的任意字符在模式中的位置。

函数dist定义如下： ?m?jdist(c)???mj?max{j|tj?c且1?j?m?1}若c不展现在模式中或tm?c 例如，T＝\pattern\，那么dist(p)=6，dist(a)=5，dist(t)=3，dist(e)=2，dist(r)=1，dist(n)=7，字符表∑中的其他字符ch的dist(ch)=7 BM算法的根本思想是：假设将主串中自位置i起往左的一个子串与模式举行从右到左的匹配过程中，若察觉不匹配，那么下次应从主串的i+dist(si)位置开头重新举行新一轮的匹配，其效果相当于把模式和主串均向右滑过一段距离dist(si)，即跳过dist(si)个字符而无需举行对比 例如，给定主串S=\ababcabcacbab\，模式T=\abcac\，那么dist(a)=1，dist(b)=3，dist(c)=5，BM算法的匹配过程如图3.19所示 1 第1趟匹配，i=4，j=4失败， dist(b)=3，i滑动到7的位置 第 2趟匹配，i=7，j=5失败， dist(b)=3，i滑动到10的位置 1 2 3 4 5 6 7 8 910111213 a b a b c a b c a c b a b a b c a c a b a b c a b c a c b a b a b c a c a b a b c a b c a c b a b 3趟匹配，T中全部字符 第 都对比完毕，匹配告成 a b c a c 图3.19 BM算法的匹配过程例如 由于在实际应用中，字符表中大片面字符不展现在模式串中，所以，应用BM算法可以大大加快串匹配的速度。

算法3.12——BM算法 int BM(char S[ ], char T[ ], int n, int m) { //主串的长度为n，模式串的长度为m，主串和模式的数组下标从1开头 i=m; while (i0 i=i-1; } if (j= =0) return i+1; else i=i+dist(S[i]); //dist函数请读者自行设计 } return 0; } 测验工程二——最近对问题 1．测验题目 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对 2 2．测验目的 （1）进一步掌管递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中 3．测验要求 （1）分别用蛮力法和分治法求解最近对问题； （2）分析算法的时间性能，设计测验程序验证分析结论 4．实现提示 蛮力法实现最近对问题的算法请参考3.6.1节，下面给出基于4.5.1节议论的分治法求解最近对问题的算法。

算法4.10——最近对问题 int ClosestPoints(S) //S为平面上n个点的坐标组成的集合 { 1．if (n0时，b( j )=b(j-1)+aj，否那么，b( j )=aj可得如下递推式： ??b(j?1)?ajb(j)??aj??b(j?1)?0b(j?1)?0(1?j?n) 测验五——哈夫曼编码 1．测验题目 设需要编码的字符集为{d1, d2, …, dn}，它们展现的频率为{w1, w2, …, wn}，应用 哈夫曼树构造最短的不等长编码方案 2．测验目的 （1）了解前缀编码的概念，理解数据压缩的根本方法； （2）掌管最优子布局性质的证明方法； （3）掌管贪心法的设计思想并能纯熟运用 3．测验要求 （1）证明哈夫曼树得志最优子布局性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档 4．实现提示 设需要编码的字符集为{d1, d2, …, dn}，它们展现的频率为{w1, w2, …, wn}，以d1, d2, …, dn作为叶子结点，w1, w2, …, wn作为叶子结点的权值，构造一棵哈夫曼编码树，规定哈夫曼编码树的左分支代表0，右分支代表1，那么从根结点到每个叶子结点所经过的路径组成的0和1的序列便为该叶子结点对应字符的编码即为哈夫曼编码。

考虑到哈夫曼树中共有2n-1个结点，并且举行n-1次合并操作，为了便于选取根结点权值最小的二叉树以及合并操作，设置一个数组huffTree[2n-1]保存哈夫曼树中各结点的信息，数组元素的结点布局如图7.11所示 weight：该结点的权值； lchild：该结点的左孩子结点在数组中的下标； weight lchild rchild parent rchild：该结点的右孩子结点在数组中的下标； 图7.11 哈夫曼树的结点布局 parent：该结点的双亲结点在数组中的下标 将数组元素的结点类型定义为： struct element { double weight; //字符展现的概率为实数 int lchild, rchild, parent; }; 5 — 6 —。