算法分析与设计实验指导书.docx
《算法分析与设计实验指导书.docx》由会员分享，可在线阅读，更多相关《算法分析与设计实验指导书.docx（8页珍藏版）》请在冰点文库上搜索。
算法分析与设计实验指导书
电子科技大学成都学院计算机系
实验指导
（实验）课程名称《算法分析与设计》
电子科技大学成都学院计算机系制表
实验一
一、实验室名称：
二、实验项目名称：
最大公约数
三、实验学时：
2
四、实验原理：
利用欧几里德算法、连续检测整数方法求两个数的最大公约数。
五、实验目的：
1.复习数据结构课程的相关知识，实现课程间的平滑过渡；
2.理解不同算法能够解决相同的问题，思路不同，复杂度不同。
六、实验内容：
求两个自然数m和n的最大公约数。
七、实验提示
法一：
连续整数检测
1.t=min{m,n}
2.m除以t，如果余数为0，则执行步骤3，否则执行步骤4
3.n除以t，如果余数为0，返回t的值作为结果，否则执行步骤4
4.t=t-1，转第2步
方法二：
欧几里得算法
1.r=m%n
2.循环直到r=0
2.1m=n
2.2n=r
2.3r=m%n
3.输出n
实验二
一、实验室名称：
二、实验项目名称：
串匹配
三、实验学时：
2
四、实验原理：
穷举法是最直接的一种解决问题的方法，它的思想易于理解。
实质利用遍历的方式求解。
五、实验目的：
理解并掌握穷举法的设计思想；
六、实验内容：
1.实现BF算法及对其的改进算法BM算法
2.对BF、BM进行时间复杂度的分析并编程验证。
七、实验提示
法一：
BF算法见《数据结构》串模式一节
法二：
BM算法
BM基本思想：
假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中，若发现不匹配，则下次应从主串的i+dist（si）位置开始重新进行新一轮的匹配，其效果相当于把模式和主串均右滑过一段距离dist（si）,即跳过dist（si）个字符而无需进行比较。
假设字符表{a,b,c,……,z}，BM算法对给定的模式T=“t1t2…tm”,定义一个从字符到正整数的映射：
dist:
c—>{1,2,…，m},c属于字符表
滑动函数给出了正文中可能出现的任意字符在模式中的位置，定义如下：
m-jj=max{j|tj=c且1≤j≤m-1
dist（c）=
c若c不出现在模式中或tm=c
BM算法模块：
intBM（chars[],chart[],intn,intm）
{
i=m;//模式串长度
while（i<=n）//n主串的长度
{j=m;
while（j>0&&s[i]==t[j]）
{j--;
i--;
}
if（j==0）returni+1;
elsei=i+dist（s[i]）;//dist（s[i]）滑行函数，要求同学自己编写
}
return0;
}
实验三
一、实验室名称：
二、实验项目名称：
排序问题
三、实验学时：
2
四、实验原理：
合并排序：
将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
快速排序：
将整个排序的元素按第一个元素的值分成左右两部分，使得左边的数据小于划分点的数据，右边的数据大于划分点的数据，再分别对左右两部分继续前面的操作，直到整个数据序列有序为止。
五、实验目的：
1.进一步掌握递归算法的设计思想及递归程序的调用技术；
2.理解：
分治与递归经常同时应用在算法设计中。
六、实验内容：
用c/c++语言实现二分搜索算法。
要求：
用数组先存放从键盘输入的n个数据，再对n个数据采用二分搜索方法对从键盘上输入的数据分别进行合并排序、快速排序（从小到大排序）。
七、实验提示
法一：
合并排序
voidMergeSort（Typea[],intleft,intright）
{
if（leftinti=（left+right）/2;//取中点
mergeSort（a,left,i）;
mergeSort（a,i+1,right）;
merge（a,b,left,i,right）;//合并到数组b
copy（a,b,left,right）;//复制回数组a
}
}
法二：
快速排序
分三步完成：
第一步划分，第二步递归求解，第三步合并。
划分模块：
template
intPartition（Typea[],intp,intr）
{
inti=p,j=r+1;
Typex=a[p];
//将//将>x的元素交换到右边区域
while（true）{
while（a[++i]while（a[--j]>x）;
if（i>=j）break;
Swap（a[i],a[j]）;
}
a[p]=a[j];
a[j]=x;
returnj;
}
递归求解模块：
template
voidQuickSort（Typea[],intp,intr）
{
if（pintq=Partition（a,p,r）;
QuickSort（a,p,q-1）;//对左半段排序
QuickSort（a,q+1,r）;//对右半段排序
}
}
实验四
一、实验室名称：
二、实验项目名称：
贪心算法求背包问题
三、实验学时：
2
四、实验原理：
在贪婪或贪心算法（greedymethod）中采用逐步构造最优解的方法。
在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。
决策一旦作出，就不可再更改。
作出贪婪决策的依据称为贪婪准则
五、实验目的：
明确连续背包问题的概念；利用贪心算法解决连续背包问题；并通过本例熟悉贪心算法在程序设计中的应用方法。
六、实验内容：
已知n个物体和1个背包，其中物体i有重量wi和价值vi，背包承重量为W。
求一装载方案，要求在不超过背包负重的前提下，背包中装入的物品价值最大。
很明显，如果
，则最优解就是装入全部物体，因此下面假设
。
注：
连续背包问题中的物体可以任意分割，即部分装入背包。
分析：
连续背包问题可形式化为如下模型：
对于连续背包问题，可用贪心技术求得最优解。
贪心策略是单位重量价值高者优先。
七、实验提示
背包问题思路：
1.改变数组w,v的排列顺序,使其按单位重量价值V[i]/W[i]降序排列;
2.将数组x[n]初始化为0;//初始化解向量
3.i=1;
5.循环直到（W[i]>c）
x[i]=1;//将第i个物品放入背包
c=c-W[i];
i++;
5.X[i]=c/w[i];
函数模块
voidKnapsack（intn,floatM,floatv[],floatw[],floatx[]）
{
Sort（n,v,w）;
inti;
for（i=1;i<=n;i++）x[i]=0;
floatc=M;
for（i=1;i<=n;i++）{
if（w[i]>c）break;
x[i]=1;
c-=w[i];
}
if（i<=n）x[i]=c/w[i];
}
升级会员 