算法分析与设计实验指导书.docx
- 文档编号:16268384
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:8
- 大小:25.27KB
算法分析与设计实验指导书.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(left inti=(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(p intq=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]; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 实验 指导书