《算法设计与分析》实验指导书.docx
- 文档编号:17544764
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:24
- 大小:24.73KB
《算法设计与分析》实验指导书.docx
《《算法设计与分析》实验指导书.docx》由会员分享,可在线阅读,更多相关《《算法设计与分析》实验指导书.docx(24页珍藏版)》请在冰点文库上搜索。
《算法设计与分析》实验指导书
《算法设计与分析》实验指导书
本书是为配合《算法分析与设计实践教学大纲》而编写的上机指导,其目的是使学生消化理论知识,加深对讲授容的理解,尤其是一些算法的实现及其应用,培养学生独立编程和调试程序的能力,使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤:
(1)、准备好上机所需的程序。
手编程序应书写整齐,并经人工检查无误后才能上机。
(2)、上机输入和调试自己所编的程序。
一人一组,独立上机调试,上机时出现的问题,最好独立解决。
(3)、上机结束后,整理出实验报告。
实验报告应包括:
题目、程序清单、运行结果、对运行情况所作的分析。
实验一统计数字及字符编码(2学时)
一、实验目的与要求
1、掌握算法的计算复杂性概念。
2、掌握算法渐近复杂性的数学表述。
3、掌握用C++语言描述算法的方法。
4实现具体的编程与上机实验验证算法的时间复杂性函数
二、实验容
1、统计数字问题
1)问题描述
一本书的页码从自然数1开始顺序编码直到自然数n。
书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。
例如,第6页用数字6表示而不是06或006等。
数字计数问题要求对给定书的总页码n计算出书的全部页码中分别用到多少次数字0、1、2、…、9。
2)编程任务
给定表示书的总页码的10进制整数n(1≤n≤109)。
编程计算书的全部页码中分别用到多少次数字0、1、2、…、9。
3)程序算法
将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1—9作为个位数,余数代表有1—余数本身这么多个数作为剩余的个位数。
此外,商还代表1—商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。
把这些结果统计起来即可。
2、字典序问题
1)问题描述
在数据加密和数据压缩中常需要对特殊的字符串进行编码。
给定的字母表A由26个小写英文字母组成A={a,b,…,z}。
该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同,且每个字符最多出现1次。
例如,a,b,ab,bc,xyz等字符串都是升序字符串。
现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。
1
2
…
26
27
28
…
a
b
…
z
ab
ac
…
对于任意长度不超过6的升序字符串,迅速计算出它在上述字典中的编码。
算法设计:
对于给定的长度不超过6的升序字符串,计算出它在上述字典中的编码。
数据输入:
输入数据由文件名为input.txt的文本文件提供。
文件的第一行是一个正整数k,表示接下来共有k行。
接下来的k行中,每行给出一个字符串。
结果输出:
将计算结果输出到文件output.txt中。
文件共有k行,每行对应于一个字符串的编码。
实验二蛮力法(2学时)
一、实验目的与要求
1、掌握蛮力法的基本思想
2、使用蛮力法解决具体问题(通常,问题规模比较小时,此方法才有意义)
二、实验容
1、用C++/C编写程序实现BF算法,进行模式匹配。
以下是该算法的伪代码,请进行调试。
intBF(charS[],charT[])
{
i=0;j=0;
while(i { if(S[i]==T[j]){i++;j++;} else{i=i-j+1;j=0;} } if(j>=strlen(T))return(i-j); elsereturn0; } 2、用C++/C编写程序实现KMP算法,进行模式匹配。 1求模式串T的Next数组 voidGetNext(charT[],intnext[]) { next[1]=0; j=1;k=0; while(j if((k==0)||(T[j]==T[k])){ j++; k++; next[j]=k; } elsek=next[k]; } 2KMP算法伪代码 1.在串S和串T中分别设比较的起始下标i和j; 2.循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕 2.1如果S[i]=T[j],则继续比较S和T的下一个字符;否则 2.2将j向右滑动到next[j]位置,即j=next[j]; 2.3如果j=0,则将i←i+1,j=1,准备下一趟比较; 3.如果T中所有字符均比较完毕,则返回匹配的起始下标;否则返回0 3、以源串“ababcabccabccacbab”和模式串”abccac”w为例,编写程序,给出采用BF算法和KMP算法进行串匹配过程中的字符比较次数。 实验三递归与分治法(2学时) 基本题一: 基本递归算法 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、通过本实验加深对递归过程的理解 二、实验容: 掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数,输出结果能够用递归方法实现整数的划分。 四、实验步骤 1.理解算法思想和问题要求; 2.编程实现题目要求; 3.上机输入和调试自己所编的程序; 4.验证分析实验结果; 5.整理出实验报告。 基本题二: 棋盘覆盖问题 一、实验目的与要求 1、掌握棋盘覆盖问题的算法; 2、初步掌握分治算法 二、实验题: 盘覆盖问题: 在一个2k×2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 三、实验提示 voidchessBoard(inttr,inttc,intdr,intdc,intsize) { if(size==1)return; intt=tile++, //L型骨牌号 s=size/2; //分割棋盘 //覆盖左上角子棋盘 if(dr //特殊方格在此棋盘中 chessBoard(tr,tc,dr,dc,s); else{//此棋盘中无特殊方格 //用t号L型骨牌覆盖右下角 board[tr+s-1][tc+s-1]=t; //覆盖其余方格 chessBoard(tr,tc,tr+s-1,tc+s-1,s);} //覆盖右上角子棋盘 if(dr //特殊方格在此棋盘中 chessBoard(tr,tc+s,dr,dc,s); else{//此棋盘中无特殊方格 //用t号L型骨牌覆盖左下角 board[tr+s-1][tc+s]=t; //覆盖其余方格 chessBoard(tr,tc+s,tr+s-1,tc+s,s);} //覆盖左下角子棋盘 if(dr>=tr+s&&dc //特殊方格在此棋盘中 chessBoard(tr+s,tc,dr,dc,s); else{//用t号L型骨牌覆盖右上角 board[tr+s][tc+s-1]=t; //覆盖其余方格 chessBoard(tr+s,tc,tr+s,tc+s-1,s);} //覆盖右下角子棋盘 if(dr>=tr+s&&dc>=tc+s) //特殊方格在此棋盘中 chessBoard(tr+s,tc+s,dr,dc,s); else{//用t号L型骨牌覆盖左上角 board[tr+s][tc+s]=t; //覆盖其余方格 chessBoard(tr+s,tc+s,tr+s,tc+s,s);} } 提高题一: 二分搜索 一、实验目的与要求 1、熟悉二分搜索算法; 2、初步掌握分治算法; 二、实验题 1、设a[0: n-1]是一个已排好序的数组。 请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最小元素位置j。 当搜索元素在数组中时,I和j相同,均为x在数组中的位置。 2、设有n个不同的整数排好序后存放于t[0: n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。 要求算法在最坏的情况下的计算时间为O(logn)。 三、实验提示 1、用I,j做参数,且采用传递引用或指针的形式带回值。 boolBinarySearch(inta[],intn,intx,int&i,int&j) { intleft=0; intright=n-1; while(left { intmid=(left+right)/2; if(x==a[mid]) { i=j=mid; returntrue; } if(x>a[mid]) left=mid+1; else right=mid-1; } i=right; j=left; returnfalse; } intSearchTag(inta[],intn,intx) { intleft=0; intright=n-1; while(left { intmid=(left+right)/2; if(x==a[mid])returnmid; if(x>a[mid]) right=mid-1; else left=mid+1; } return-1; } 提高题二: 用分治法实现元素选择 一、实验要求与目的 1、了解分治法的基本思想,掌握递归程序编写方法; 2、使用分治法编程,求解线形序列中第k小元素。 二、实验容 1、给定线形序列集中n个元素和一个整数k,1≤k≤n,输出这n个元素中第k小元素的值及其位置。 2、简述该算法的原理、步骤。 对该算法与直接排序查找进行比较。 3、编写并调试程序。 测试要求: 元素个数不少于100;分三种情况: k=1、k=n和k=中位数。 实验四贪心算法(2学时) 基本题一: 多机调度问题 一、实验目的与要求 1、熟悉多机调度问题的算法; 2、初步掌握贪心算法; 二、实验题 要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间由m台机器加工处理完成。 约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。 作业不能拆分成更小的子作业。 三、实验提示 1、把作业按加工所用的时间从大到小排序 2、如果作业数目比机器的数目少或相等,则直接把作业分配下去 3、 如果作业数目比机器的数目多,则每台机器上先分配一个作业,如下的作业分配时,是选那个表头上s最小的链表加入新作业。 typedefstructJob { intID;//作业号 inttime;//作业所花费的时间 }Job; typedefstructJobNode//作业链表的节点 { intID; inttime; JobNode*next; }JobNode,*pJobNode; typedefstructHeader //链表的表头 { ints; pJobNodenext; }Header,pHeader; intSelectMin(Header*M,intm) { intk=0; for(inti=1;i { if(M[i].s } returnk; 提高题一: 用贪心算法求解最小生成树 一、实验要求与目的 1、熟悉贪心算法的基本原理与适用围。 2、使用贪心算法编程,求解最小生成树问题。 二、实验容 1、任选一种贪心算法(Prim或Kruskal),求解最小生成树。 对算法进行描述和复杂性分析。 编程实现,并给出测试实例 提高题二: 汽车加油问题 一、实验目的与要求 1、掌握汽车加油问题的算法; 2、进一步掌握贪心算法; 二、实验题 一辆汽车加满油后可以行驶N千米。 旅途中有若干个加油站。 若要使沿途的加油次数最少,设计一个有效的算法,指出应在那些加油站停靠加油。 并证明你的算法能产生一个最优解。 三、实验提示 把两加油站的距离放在数组中,a[1..n]表示从起始位置开始跑,经过n个加油站,a[k]表示第k-1个加油站到第k个加油站的距离。 汽车在运行的过程中如果能跑到下一个站则不加油,否则要加油。 (算法略) 实验五回溯算法(2学时) 基本题一: 符号三角形问题 一、实验目的与要求 1、掌握符号三角形问题的算法; 2、初步掌握回溯算法; 二、实验题图 下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。 2个同号下面都是“+”,2个异号下面都是“-”。 + + - + - + + + - - - - + - + + + - - + + - - + - - - + 在一般情况下,符号三角形的第一行有n个符号。 符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。 三、实验提示 voidTriangle: : Backtrack(intt) { if((count>half)||(t*(t-1)/2-count>half))return; if(t>n)sum++; else for(inti=0;i<2;i++){ p[1][t]=i; count+=i; for(intj=2;j<=t;j++){ p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1]; } Backtrack(t+1); for(intj=2;j<=t;j++) count-=p[j][t-j+1]; count-=i; } } 基本题二: 0—1背包问题 一、实验目的与要求 1、掌握0—1背包问题的回溯算法; 2、进一步掌握回溯算法; 二、实验题: 给定n种物品和一背包。 物品i的重量是wi,其价值为vi,背包的容量为C。 问应如何选择装入背包的物品,使得装入背包中物品的总价值最大? 三、实验提示 template TypepKnap : Bound(inti) {//计算上界 Typewcleft=c-cw; //剩余容量 Typepb=cp; //以物品单位重量价值递减序装入物品 while(i<=n&&w[i]<=cleft){ cleft-=w[i]; b+=p[i]; i++; } //装满背包 if(i<=n)b+=p[i]/w[i]*cleft; returnb; } 提高题一: 用回溯法求解跳马问题 一、实验要求与目的 1、掌握回溯法的基本原理。 2、使用回溯法编程,求解跳马问题 二、实验容 1、问题描述: 在N*N棋盘上有N2个格子,马在初始位置(X0,Y0),按照象棋中马走“日”的规则,使马走遍全部格子且每个格子仅经过一次。 编程输出马的走法。 2、给出算法描述。 编程实现,给出N=5,(X0,Y0)=(1,1)时的运行结果。 实验六分支限界法(2学时) 基本题一: 旅行商售货员问题的分支限界算法 一、实验目的与要求 1、掌握旅行商售货员问题的分支限界算法; 2、区分分支限界算法与回溯算法的区别,加深对分支限界法的理解。 二、实验题: 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。 他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。 三、实验提示 旅行商问题的解空间是一个排列树。 有两种实现的方法。 第一种是只使用一个优先队列,队列中的每个元素中都包含到达根的路径。 另一种是保留一个部分解空间树和一个优先队列,优先队列中的元素并不包含到达根的路径。 以下为第一种方法。 由于我们要寻找的是最小耗费的旅行路径,因此可以使用最小耗费分枝定界法。 在实现过程中,使用一个最小优先队列来记录活节点,队列中每个节点的类型为MinHeapNode。 每个节点包括如下区域: x(从1到n的整数排列,其中x[0]=1),s(一个整数,使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0: s],而剩余待访问的节点是x[s+1: n-1]),cc(旅行路径前缀,即解空间树中从根节点到当前节点的耗费),lcost(该节点子树中任意叶节点中的最小耗费),rcost(从顶点x[s: n-1]出发的所有边的最小耗费之和)。 当类型为MinHeapNode(T)的数据被转换成为类型T时,其结果即为lcost的值。 分枝定界算法的代码见程序 程序首先生成一个容量为100的最小堆,用来表示活节点的最小优先队列。 活节点按lcost值从最小堆中取出。 接下来,计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut。 如果某些顶点没有出边,则有向图中没有旅行路径,搜索终止。 如果所有的顶点都有出边,则可以启动最小耗费分枝定界搜索。 根的孩子B作为第一个E-节点,在此节点上,所生成的旅行路径前缀只有一个顶点1,因此s=0,x[0]=1,x[1: n-1]是剩余的顶点(即顶点2,3,.,n)。 旅行路径前缀1的开销为0,即cc=0,并且,rcost=n&&i=1时MinOut。 在程序中,bestc给出了当前能找到的最少的耗费值。 初始时,由于没有找到任何旅行 路径,因此bestc的值被设为NoEdge。 旅行商问题的最小耗费分枝定界算法 template TAdjacencyWDigraph: : BBTSP(intv[]) {//旅行商问题的最小耗费分枝定界算法 //定义一个最多可容纳1000个活节点的最小堆 MinHeap>H(1000); T*MinOut=newT[n+1]; //计算MinOut=离开顶点i的最小耗费边的耗费 TMinSum=0;//离开顶点i的最小耗费边的数目 for(inti=1;i<=n;i++){ TMin=NoEdge; for(intj=1;j<=n;j++) if(a[j]! =NoEdge&&(a[j] Min=a[j]; if(Min==NoEdge)returnNoEdge;//此路不通 MinOut=Min; MinSum+=Min; } //把E-节点初始化为树根 MinHeapNodeE; E.x=newint[n]; for(i=0;i E.x=i+1; E.s=0;//局部旅行路径为x[1: 0] E.cc=0;//其耗费为0 E.rcost=MinSum; Tbestc=NoEdge;//目前没有找到旅行路径 //搜索排列树 while(E.s if(E.s==n-2){//叶子的父节点 //通过添加两条边来完成旅行 //检查新的旅行路径是不是更好 if(a[E.x[n-2]][E.x[n-1]]! =NoEdge&&a[E.x[n-1]][1]! =NoEdge&&(E.cc+ a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1] { //找到更优的旅行路径 bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]; E.cc=bestc; E.lcost=bestc; E.s++; H.Insert(E);} elsedelete[]E.x;} else{//产生孩子 for(inti=E.s+1;i if(a[E.x[E.s]][E.x]! =NoEdge) { //可行的孩子,限定了路径的耗费 Tcc=E.cc+a[E.x[E.s]][E.x]; Trcost=E.rcost-MinOut[E.x[E.s]]; Tb=cc+rcost;//下限 if(b //子树可能有更好的叶子 //把根保存到最大堆中 MinHeapNodeN; N.x=newi 如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。=tc+s)