中北大学软件学院算法实验报告(附截图).doc

中北大学软件学院 实验报告 专 业：_________________________ 方 向：_________________________ ？ 课程名称：_________________________ 班 级：_________________________ 学 号：_________________________ 姓 名：_________________________ 辅导教师：_________________________ 2016年3月制 # 成绩： 实验时间 2016年4月7日8时至10时 学时数 2 1.实验名称 实验一 串匹配程序设计 2.实验目的 (1) 熟练掌握串匹配的含义 (2) 掌握BF算法匹配的过程并编程实现 - (3) 熟悉C++编译环境的基本操作 3.实验内容 给定两个字符串S和T，用BF算法，在主串S中查找字串T，输出结果，输出时要求有文字说明。请编写程序。 4.实验原理或流程图 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一个字符。设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较次数是： 最坏情况是O（n×m）。 或者写书上P39页的伪代码描述。 5.实验过程或源代码 ， #include int BF(char S[], char T[]){ int index = 0; 验结论及心得 通过本次实验我理解了使用蛮力法解决问题的特点，蛮力法的设计思想是直接基于问题本身的描述来设计算法，即不采用任何方法来精简计算过程、运算次数或者设法简化问题本身。所以蛮力法设计的算法虽然简单易懂，但是效率却往往不是很令人满意，比如串的模式匹配问题中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失败就会产生回溯，如果能利用已有的匹配结果来减少回溯就可以提高效率，如KMP算法。 成绩： 实验时间 2016年4月7日8时至10时 学时数 2 [ 1.实验名称 实验二 排序问题程序设计 2.实验目的 (1) 掌握选择排序和起泡排序的基本思想 (2) 掌握两种排序方法的具体实现过程 (3) 在掌握的基础上编程实现两种排序方法 3.实验内容 输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。请编写程序。 4.实验原理或流程图 书上P42页选择排序想法三点抄上去 书上P43页冒泡排序想法三点抄上去 ? $ 5.实验过程或源代码 验结论及心得 通过本次实验我理解了选择排序和起泡排序的基本思想。选择排序和起泡排序都是通过将待排序记录划分成有序区和无序区，然后通过交换扩大有序区，缩小无序区，最终达到排序的目的。两者又有区别，选择排序可以直接选出无序区的最小记录并一次插入到合适的位置上，之后不再调整，而冒泡排序则是通过两两交换实现移动的，由于很多移动无法将记录一次放置到合适的位置上，所以存在很多“无效”的移动操作，从实验结果可以看出，起泡排序的移动次数明显比选择排序要多就是因为这样的“无效”的移动操作浪费了时间。 ？ 成绩： 实验时间 2016年4月7日8时至10时 学时数 2 1.实验名称 实验三 数字旋转方阵程序设计 2.实验目的 (1) 掌握分治法的设计思想 (2) 掌握数字旋转方阵的具体实现过程 (3) 熟练掌握二维数组的使用方法 … (4) 在掌握的基础上编程实现数字旋转方阵的实现过程 3.实验内容 给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。请编写程序。 4.实验原理或流程图 用二维数组data[N][N]表示N×N的方阵，观察方阵中