首页 《算法设计与分析》实验指导书

《算法设计与分析》实验指导书

举报
开通vip

《算法设计与分析》实验指导书《算法设计与分析》实验指导书本书是为配合《算法分析与设计实践教学大纲》而编写的上机指导,其目的是使学生消化理论知识,加深对讲授容的理解,尤其是一些算法的实现及其应用,培养学生独立编程和调试程序的能力,使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤:1)、准备好上机所需的程序。手编程序应书写整齐,并经人工检查无误后才能上机。2)、上机输入和调试自己所编的程序。一人一组,独立上机调试,上机时出现的问题,最好独立解决。3)、上机结束后,整理出实验报告。实验报告应包括:题目、程序清单、运行结果、对运...

《算法设计与分析》实验指导书
《算法设计与 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 》实验指导书本书是为配合《算法分析与设计实践教学大纲》而编写的上机指导,其目的是使学生消化理论知识,加深对讲授容的理解,尤其是一些算法的实现及其应用,培养学生独立编程和调试程序的能力,使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤:1)、准备好上机所需的程序。手编程序应书写整齐,并经人工检查无误后才能上机。2)、上机输入和调试自己所编的程序。一人一组,独立上机调试,上机时出现的问题,最好独立解决。3)、上机结束后,整理出实验报告。实验报告应包括:题目、程序清单、运行结果、对运行情况所作的分析。目录实验一统计数字及字符编码(2学时).................................................................1实验二蛮力法(2学时).........................................................................................3实验三递归与分治法(2学时).............................................................................5实验四贪心算法(2学时).....................................................................................8实验五回溯算法(2学时)...................................................................................10实验六分支限界法(2学时)...............................................................................12实验七动态规划算法(3学时)...........................................................................15实验一统计数字及字符编码(2学时)一、实验目的与要求1、掌握算法的计算复杂性概念。2、掌握算法渐近复杂性的数学 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述。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由写英文字母组成A={a,b,⋯,z}。该字母表产生的升序字符串是指字符串中字母按照从左到出现的次序与字母在字母表中出现的次序相同,且每个字符最多出现1次。例如,26个小右a,b,ab,bc,xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。12⋯262728⋯ab⋯zabac⋯对于任意长度不超过6的升序字符串,迅速计算出它在上述字典中的编码。算法设计:对于给定的长度不超过6的升序字符串,计算出它在上述字典中的编码。数据输入:输入数据由文件名为k,表示接下来共有k行。接下来的input.txt的文本文件提供。文件的第一行是一个正整数k行中,每行给出一个字符串。结果输出:将计算结果输出到文件output.txt中。文件共有k行,每行对应于一个字符串的编码。实验二蛮力法(2学时)一、实验目的与要求1、掌握蛮力法的基本思想2、使用蛮力法解决具体问题(通常,问题规模比较小时,此方法才有意义)二、实验容1、用C++/C编写程序实现BF算法,进行模式匹配。以下是该算法的伪代码,请进行调试。intBF(charS[],charT[]){i=0;j=0;while(i=strlen(T))return(i-j);elsereturn0;}2、用C++/C编写程序实现KMP算法,进行模式匹配。①求模式串T的Next数组voidGetNext(charT[],intnext[]){next[1]=0;j=1;k=0;while(j=tc+s)特殊方格在此棋盘中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=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的最大元素的位置I和大于x的最小元素位置和j相同,均为x在数组中的位置。使得当搜索元素x不在数组中j。当搜索元素在数组中时,I2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为三、实验提示O(logn)。1、用I,j做 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 ,且采用传递引用或指针的形式带回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){intleft=0;intright=n-1;while(lefta[mid])left=mid+1;elseright=mid-1;}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(lefta[mid])right=mid-1;elseleft=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、初步掌握贪心算法;二、实验题要求给出一种作业调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,使所给的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;ihalf)||(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(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。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?三、实验提示templateTypepKnap::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。旅行商问题的最小耗费分枝定界算法templateTAdjacencyWDigraph::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]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}基本题二:最大字段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法;2、进一步掌握动态规划算法;二、实验题若给定n个整数组成的序列值。三、实验提示a1,a2,a3,⋯⋯an,求该序列形如ai+ai+1+⋯⋯+an的最大intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(intK=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}提高题一:用动态规划法求解0/1背包问题一、实验要求与目的1、掌握动态规划算法求解问题的一般特征和步骤。2、使用动态规划法编程,求解0/1背包问题。二、实验容1、问题描述:给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?2、算法描述。程序实现;给出实例测试结果。
本文档为【《算法设计与分析》实验指导书】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
个人认证用户
EYhyppy
暂无简介~
格式:doc
大小:455KB
软件:Word
页数:0
分类:
上传时间:2021-09-26
浏览量:14