中北大学软件学院算法分析与设计实验报告Word文件下载.docx
《中北大学软件学院算法分析与设计实验报告Word文件下载.docx》由会员分享，可在线阅读，更多相关《中北大学软件学院算法分析与设计实验报告Word文件下载.docx（34页珍藏版）》请在冰点文库上搜索。
若不相等，则从主串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<
stdio.h>
intBF（charS[],charT[]）{
intindex=0;
//主串从下标0开始第一趟匹配
inti=0,j=0;
//设置比较的起始下标
while（（S[i]!
='
\0'
）&
&
（T[j]!
））{//模式匹配没有结束
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]=='
）
returnindex+1;
//返回本趟匹配的开始位置（不是下标）
else
return0;
}
intmain（）{
charS[100],T[100];
printf（"
请输入主串S（不超过100个字符）:
"
）;
scanf（"
%s"
S）;
请输入子串T（不超过100个字符）:
T）;
intindex=BF（S,T）;
if（index==0）{
printf（"
模式匹配失败！
}
else{
模式匹配成功，子串%s在主串%s中首次匹配的位置是%d"
T,S,index）;
return0;
}
6.实验结论及心得
通过本次实验我理解了使用蛮力法解决问题的特点，蛮力法的设计思想是直接基于问题本身的描述来设计算法，即不采用任何方法来精简计算过程、运算次数或者设法简化问题本身。
所以蛮力法设计的算法虽然简单易懂，但是效率却往往不是很令人满意，比如串的模式匹配问题中采用BF算法效率低下的主要原因就在于BF算法一旦主串和子串匹配失败就会产生回溯，如果能利用已有的匹配结果来减少回溯就可以提高效率，如KMP算法。
实验二排序问题程序设计
（1）掌握选择排序和起泡排序的基本思想
（2）掌握两种排序方法的具体实现过程
（3）在掌握的基础上编程实现两种排序方法
输入一个待排序的序列，分别用选择排序和起泡排序两种排序方法将其变换成有序的序列，输出结果，输出时要求有文字说明。
书上P42页选择排序想法三点抄上去
书上P43页冒泡排序想法三点抄上去
//----------------------------选择排序----------------------------------
//对含有n个数的数组进行遍历
voidvisit（intr[],intn）{
for（inti=0;
i<
n;
i++）
%4d"
r[i]）;
\n"
//选择排序
voidSelectSort（intr[],intn）{
inti,j,index,temp;
intcompare=0,move=0;
for（i=0;
i<
n-1;
i++）{ //对n个记录进行n-1趟选择排序
index=i;
for（j=i+1;
j<
n;
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）;
在本次排序中共比较了%d次，移动了%d次。
compare,move）;
intr[10]={0};
请依次输入10个整数，用空格隔开：
10;
scanf（"
%d"
&
r[i]）;
排序之前的记录：
visit（r,10）;
进行选择排序：
（每趟排序后的结果如下所示）\n"
SelectSort（r,10）;
排序之后的记录：
#include<
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;
bound;
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;
//记载每一次记录交换的位置
}
//每趟排序输出一次，观察记录的变动情况
本次排序中的比较次数为%d,移动次数为%d。
count1,count2）;
进行冒泡排序：
BubbleSort（r,10）;
通过本次实验我理解了选择排序和起泡排序的基本思想。
选择排序和起泡排序都是通过将待排序记录划分成有序区和无序区，然后通过交换扩大有序区，缩小无序区，最终达到排序的目的。
两者又有区别，选择排序可以直接选出无序区的最小记录并一次插入到合适的位置上，之后不再调整，而冒泡排序则是通过两两交换实现移动的，由于很多移动无法将记录一次放置到合适的位置上，所以存在很多“无效”的移动操作，从实验结果可以看出，起泡排序的移动次数明显比选择排序要多就是因为这样的“无效”的移动操作浪费了时间。
实验三数字旋转方阵程序设计
（1）掌握分治法的设计思想
（2）掌握数字旋转方阵的具体实现过程
（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次，填写区域A
4.1data[i][j]=number;
number++;
4.2行下标i++;
列下标不变；
5.重复下述操作size–1次，填写区域B
5.1data[i][j]=number;
5.2行下标不变；
列下标j++;
6.重复下述操作size–1次，填写区域C
6.1data[i][j]=number;
6.2行下标i--;
7.重复下述操作size–1次，填写区域D
7.1data[i][j]=number;
7.2行下标不变，列下标j--;
8.调用函数Full在size-2阶方阵中左上角begin+1处从数字number开始填数；
intdata[100][100]={0};
intmaxsize=0;
voidprintData（intsize）{
size;
i++）{
for（intj=0;
j<
j++）
printf（"
data[i][j]）;
voidFull（intnumber,intbegin,intsize）{
//从number开始填写size阶方阵，左上角的下标为（begin,begin）
inti,j,k;
if（size==0）//递归的边界条件，如果size等于0，则无须填写
return;
if（size==1）{//递归的边界条件，如果size等于1
data[begin][begin]=number;
//则只须填写number
printData（maxsize）;
return;
}
i=begin;
j=begin;
//初始化左上角下标
for（k=0;
k<
size-1;
k++）{//填写区域A，共填写size-1个数
data[i][j]=number;
//在当前位置填写number
number++;
i++;
//行下标加1
k++）{//填写区域B，共填写size-1个数
//列下标加1
k++）{//填写区域C，共填写size-1个数
//在当前位置填写number
i--;
//行下标减1
k++）{//填写区域D，共填写size-1个数
j--;
//列下标减1
printData（maxsize）;
Full（number,begin+1,size-2）;
//递归求解，左上角下标为begin+1
intsize;
输入方阵的大小：
size）;
maxsize=size;
开始填充之前的数字旋转方阵：
printData（maxsize）;
填充过程：
Full（1,0,size）;
最终填充完成的结果是：
通过本次实验，我理解了分治法解决问题的基本思想和一般过程，分治法的基本思想是“分而治之”，将大的复杂的问题分解成结构同、规模小的子问题，分解子问题要足够小以至于可以直接得出子问题的解，然后对子问题的解进行合并，最终得到原问题的解。
由于程序中采用了递归技术，需要设置递归终止的条件，在数字旋转方阵问题中，递归结束的条件是size等于0或者1。
递归问题的解决分为回溯和递推两个阶段，通过这两个过程可以求解本次实验的问题。
2016年4月8日8时至10时
实验四排序中分治法的程序设计
（1）掌握归并排序和快速排序的划分方法
（2）掌握归并排序和快速排序的具体分治策略
（3）在掌握的基础上编程两种排序方法的实现过程
给出一个初始序列，分别用归并排序和快速排序两种分治法将所给序列变换为有序序列，输出结果，输出时要求有文字说明。
二路归并排序的分治策略是：
（1）划分：
将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；
（2）求解子问题：
分别对这两个子序列进行排序，得到两个有序子序列；
（3）合并：
将这两个有序子序列合并成一个有序序列。
快速排序的分治策略是：
选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1…ri-1和ri+1…rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值；
分别对划分后的每一个子序列递归处理；
由于对子序列r1…ri-1和ri+1…rn的排序是就地进行的，所以合并不需要执行任何操作。
【写不下就不写了】以第一个记录作为轴值，对待排序序列进行划分的过程为：
（1）初始化：
取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；
（2）右侧扫描过程：
将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。
重复右侧扫描过程，直到右侧的记录小（即反序），若i＜j，则将基准记录与j指向的记录进行交换；
（3）左侧扫描过程：
将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。
重复左侧扫描过程，直到左侧的记录大（即反序），若i＜j，则将基准记录与i指向的记录交换；
（4）重复
（2）（3）步，直到i与j指向同一位置，即基准记录最终的位置。
//-----------------------------归并排序---------------------------------
voidMerge（intr[],intr1[],ints,intm,intt）{//合并子序列
inti=s,j=m+1,k=s;
合并子序列r[%d]~r[%d],r[%d]~r[%d]：
s,m,m+1,t）;
r:
visit（r,10）;
while（i<
=m&
=t）{
if（r[i]<
=r[j]）//取r[i]和r[j]中较小者放入r1[k]
r1[k++]=r[i++];
else
r1[k++]=r[j++];
=m）{//若第一个子序列没处理完，则进行收尾处理
r1[k++]=r[i++];
while（j<
=t）{//若第二个子序列没处理完，则进行收尾处理
r1[k++]=r[j++];
r1:
visit（r1,10）;
voidMergeSort（intr[],ints,intt）{
intm;
intr1[1000]={0};
if（s==t）
return;
//递归的边界条件
else{
m=（s+t）/2;
//划分
将序列r[%d]~r[%d]划分成r[%d]~r[%d]、r[%d]~r[%d]两个子序列进行求解：
s,t,s,m,m+1,t）;
MergeSort（r,s,m）;
//求解子问题1，归并排序前半个子序列
MergeSort（r,m+1,t）;
//求解子问题2，归并排序后半个子序列
Merge（r,r1,s,m,t）;
//合并解，合并相邻有序子序列
for（inti=s;
=t;
i++）
r[i]=r1[i];
}
intr[10]={0};
for（inti=
升级会员 