《算法设计与分析》实验指导书.doc

《《算法设计与分析》实验指导书.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验指导书本书是为配合《算法分析与设计实践教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。目录实验一统计数字及字符编码（2学时

2、）1实验二蛮力法（2学时）3实验三递归与分治法（2学时）5实验四贪心算法（2学时）8实验五回溯算法（2学时）10实验六分支限界法（2学时）12实验七动态规划算法（3学时）15实验一统计数字及字符编码（2学时）一、实验目的与要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学表述。3、掌握用C++语言描述算法的方法。4实现具体的编程与上机实验验证算法的时间复杂性函数二、实验内容1、统计数字问题1）问题描述一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示而不是06或006等。数字计数

3、问题要求对给定书的总页码n计算出书的全部页码中分别用到多少次数字0、1、2、…、9。2）编程任务给定表示书的总页码的10进制整数n(1≤n≤109)。编程计算书的全部页码中分别用到多少次数字0、1、2、…、9。3）程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数。此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。2、字典序问题1）问题描述在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英

4、文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。12…262728…ab…zabac…对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。算法设计：对于给定的长度不超过6的升序字符串，计算出它在上述字典中的编码。~17~数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第一行是一个正整数k，表示接下来共有k行。接下

5、来的k行中，每行给出一个字符串。结果输出：将计算结果输出到文件output.txt中。文件共有k行，每行对应于一个字符串的编码。~17~实验二蛮力法（2学时）一、实验目的与要求1、掌握蛮力法的基本思想2、使用蛮力法解决具体问题（通常，问题规模比较小时，此方法才有意义）二、实验内容1、用C++/C编写程序实现BF算法，进行模式匹配。以下是该算法的伪代码，请进行调试。intBF(charS[],charT[]){i=0;j=0;while(i

6、(j>=strlen(T))return(i-j);elsereturn0;}2、用C++/C编写程序实现KMP算法，进行模式匹配。①求模式串T的Next数组voidGetNext(charT[],intnext[]){next[1]=0;j=1;k=0;while(j

7、

8、(T[j]==T[k])){j++;k++;next[j]=k;}elsek=next[k];}~17~①KMP算法伪代码1.在串S和串T中分别设比较的起始下标i和j；2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕2.1如果S[i]=T[j]，则继续比较S和T

9、的下一个字符；否则2.2将j向右滑动到next[j]位置，即j=next[j]；2.3如果j=0，则将ißi+1，j=1，准备下一趟比较；3.如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回03、以源串“ababcabccabccacbab”和模式串”abccac”w为例，编写程序，给出采用BF算法和KMP算法进行串匹配过程中的字符比较次数。~17~实验三递归与分治法（2学时）基本题一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实