搜索
中北大学软件学院实验报告专业：_______软件工程_________方向：软件测试与开发（偏开发）课程名称：____算法设计与分析_______班级：_____13140A03______学号：_________________________姓名：________xxx____________辅导教师：_______马巧梅____________2016年3月制成绩：实验时间2016年4月7日8时至10时学时数21.实验名称实验一串匹配程序设计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次，因此平均比较次数是：11112)2()(11)(mnimniimnmmimnmip最坏情况是O（n×m）。或者写书上P39页的伪代码描述。5.实验过程或源代码#includestdio.hintBF(charS[],charT[]){intindex=0;//主串从下标0开始第一趟匹配inti=0,j=0;//设置比较的起始下标while((S[i]!='\0')&&(T[j]!='\0')){//模式匹配没有结束printf(-从主串的第%d个位置开始与模式串进行匹配:（只输出回溯信息）\n,i);if(S[i]==T[j]){//相同位置字符相同i++;j++;//向后匹配}else{//相同位置字符不同printf(由于主串下标i为%d的字符%c和模式串下标j为%d的字符%c失配,i,S[i],j,T[j]);index++;i=index;j=0;//i和j分别回溯printf(所以i和j分别回溯到%d,%d重新开始匹配\n,i,j);}}if(T[j]=='\0')returnindex+1;//返回本趟匹配的开始位置（不是下标）elsereturn0;}intmain(){charS[100],T[100];printf(请输入主串S(不超过100个字符):);scanf(%s,S);printf(请输入子串T(不超过100个字符):);scanf(%s,T);intindex=BF(S,T);if(index==0){printf(模式匹配失败！);}else{printf(模式匹配成功，子串%s在主串%s中首次匹配的位置是%d,T,S,index);}return0;}6.实验结论及心得通过本次实验我理解了使用蛮力法解决问题的特点，蛮力法的设计思想是直接基于问题本身的描述来设计算法，即不采用任何方法来精简计算过程、运算次数或者设法简化问题本身。所以蛮力法设计的算法虽然简单易懂，但是效率却往往不是很令人满意，比如串的模式匹配问题中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失败就会产生回溯，如果能利用已有的匹配结果来减少回溯就可以提高效率，如KMP算法。成绩：实验时间2016年4月7日8时至10时学时数21.实验名称实验二排序问题程序设计2.实验目的(1)掌握选择排序和起泡排序的基本思想(2)掌握两种排序方法的具体实现过程(3)在掌握的基础上编程实现两种排序方法3.实验内容输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图书上P42页选择排序想法三点抄上去书上P43页冒泡排序想法三点抄上去5.实验过程或源代码//----------------------------选择排序----------------------------------#includestdio.h//对含有n个数的数组进行遍历voidvisit(intr[],intn){for(inti=0;in;i++)printf(%4d,r[i]);printf(\n);}//选择排序voidSelectSort(intr[],intn){inti,j,index,temp;intcompare=0,move=0;for(i=0;in-1;i++){//对n个记录进行n-1趟选择排序index=i;for(j=i+1;jn;j++){//在无序区中查找最小记录if(r[j]r[index])index=j;compare++;//比较次数增加1}if(index!=i){//交换记录temp=r[i];r[i]=r[index];r[index]=temp;move+=3;//交换一次移动3次}visit(r,10);}printf(在本次排序中共比较了%d次，移动了%d次。\n,compare,move);}intmain(){intr[10]={0};printf(请依次输入10个整数，用空格隔开：\n);for(inti=0;i10;i++)scanf(%d,&r[i]);printf(排序之前的记录：\n);visit(r,10);printf(进行选择排序：(每趟排序后的结果如下所示)\n);SelectSort(r,10);printf(排序之后的记录：\n);visit(r,10);return0;}//----------------------------选择排序----------------------------------#includestdio.h//对含有n个数的数组进行遍历voidvisit(intr[],intn){for(inti=0;in;i++)printf(%4d,r[i]);printf(\n);}voidBubbleSort(intr[],intn){intcount1=0,count2=0;//count1和count2记载比较次数和移动次数intbound,exchange=n-1;//第一趟起泡排序的区间是[0,n-1]while(exchange!=0){//当上一趟排序有记录交换时bound=exchange;exchange=0;for(intj=0;jbound;j++)//一趟起泡排序区间是[0,bound]if(++count1&&r[j]r[j+1]){//注意不能写作count1++inttemp=r[j];r[j]=r[j+1];r[j+1]=temp;count2=count2+3;//1次交换是3次移动操作exchange=j;//记载每一次记录交换的位置}visit(r,10);//每趟排序输出一次，观察记录的变动情况}printf(本次排序中的比较次数为%d,移动次数为%d。\n,count1,count2);}intmain(){intr[10]={0};printf(请依次输入10个整数，用空格隔开：\n);for(inti=0;i10;i++)scanf(%d,&r[i]);printf(排序之前的记录：\n);visit(r,10);printf(进行冒泡排序：(每趟排序后的结果如下所示)\n);BubbleSort(r,10);printf(排序之后的记录：\n);visit(r,10);return0;}6.实验结论及心得通过本次实验我理解了选择排序和起泡排序的基本思想。选择排序和起泡排序都是通过将待排序记录划分成有序区和无序区，然后通过交换扩大有序区，缩小无序区，最终达到排序的目的。两者又有区别，选择排序可以直接选出无序区的最小记录并一次插入到合适的位置上，之后不再调整，而冒泡排序则是通过两两交换实现移动的，由于很多移动无法将记录一次放置到合适的位置上，所以存在很多“无效”的移动操作，从实验结果可以看出，起泡排序的移动次数明显比选择排序要多就是因为这样的“无效”的移动操作浪费了时间。成绩：实验时间2016年4月7日8时至10时学时数21.实验名称实验三数字旋转方阵程序设计2.实验目的(1)掌握分治法的设计思想(2)掌握数字旋转方阵的具体实现过程(3)熟练掌握二维数组的使用方法(4)在掌握的基础上编程实现数字旋转方阵的实现过程3.实验内容给出一个初始数据，在此数据的基础上由外层向里层填写数据，完成一个数字旋转方阵，输出结果，输出时要求有文字说明。请编写程序。4.实验原理或流程图用二维数组data[N][N]表示N×N的方阵，观察方阵中数字的规律，可以从外层向里层填数。设变量size表示方阵的大小，则初始时size=N，填完一层则size=size-2；设变量begin表示每一层的起始位置，变量i和j分别表示行号和列号，则每一层初始时i=begin，j=begin。将每一层的填数过程分为A、B、C、D四个区域，则每个区域需要填写size–1个数字，填写区域A时列号不变行号加1，填写区域B时行号不变列号加1，填写区域C时列号不变行号减1，填写区域D时行号不变列号减1。显然，递归的结束条件是size等于0或size等于1。【写不下就算了】数字旋转方阵算法描述：输入：当前层左上角要填的数字number，左上角的坐标begin，方阵的阶数size输出：数字旋转方阵1.如果size等于0，则算法结束；2.如果size等于1，则data[begin][begin]=number，算法结束；3.初始化行、列下标i=begin,j=begin；4.重复下述操作size–1次，填写区域A4.1data[i][j]=number;number++;4.2行下标i++;列下标不变；5.重复下述操作size–1次，填写区域B5.1data[i][j]=number;number++;5.2行下标不变；列下标j++;6.重复下述操作size–1次，填写区域C6.1data[i][j]=number;number++;6.2行下标i--;列下标不变；7.重复下述操作size–1次，填写区域D7.1data[i][j]=number;number++;7.2行下标不变，列下标j--;8.调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数；5.实验过程或源代码#includestdio.hintdata[100][100]={0};intmaxsize=0;voidprintData(intsize){for(inti=0;isize;i++){for(intj=0;jsize;j++)printf(%4d,data[i][j]);printf(\n);}printf(\n);}voidFull(intnumber,intbegin,intsize){//从number开始填写size阶方阵，左上角的下标为(begin,begin)inti,j,k;if(size==0)//递归的边界条件，如果size等于0，则无须填写return;if(size==1){//递归的边界条件，如果size等于1data[begin][begin]=number;//则只须填写numberprintData(maxsize);return;}i=begin;j=begin;//初始化左上角下标for(k=0;ksize-1;k++){//填写区域A，共填写size-1个数data[i][j]=number