算法分析与设计-课件教育设计报告.docx

精选优质文档-倾情为你奉上XXXX大学算法设计与分析课程设计报告院（系）：年级：姓名：专业：计算机科学与技术研究方向：互联网与网络技术指导教师：XXXX大学目录题目1电梯调度11.1题目描述11.2算法文字描述11.3算法程序流程41.4算法的程序实现代码8题目2切割木材102.1题目描述102.2算法文字描述102.3算法程序流程112.4算法的程序实现代码15题目3设计题173.1题目描述173.2输入要求173.3输出要求173.4样例输入173.5样例输出173.6测试样例输入173.7测试样例输出183.8算法实现的文字描述183.9算法程序流程193.10算法的程序实现代码20算法分析与设计课程总结23参考文献24专心-专注-专业题目1电梯调度1.1题目描述一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为4510（有三位乘客，他们分别想去4楼、5楼和10楼），如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒，则最后一位乘客到达办公室的时间为56秒，相应的停靠计划为4510均停靠。对于此测试用例电梯停靠计划方案：410，这样到第4楼的乘客所需时间为3*4=12秒，到第5楼的乘客所需时间为3*4+20=32秒，到第10楼的乘客所需时间为9*4+10=46秒，即最后到达目的楼层的顾客所需时间为46秒。输入要求：输入的第1行为整数nf1f2fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1f2fn表示需要停靠的楼层（n<=30，2<=f1<f2fn<=31），每一个数字都用一个空格隔开。输出要求：对于每一个测试用例，第1行输出最后一位乘客到达目的楼层所需时间，第2行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。1.2算法文字描述程序实现的算法思想，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到远问题的解。与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常是多项式量级。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下：找出最优解的性质，并刻画其结构；递归地定义最优值；以自底向上的方式计算最优值；根据计算最优值时得到的信息，构造最优解。例如：给定金额n以及1，2,5分硬币，求找n的最少硬币数。对于大于1分的找零理所当然可以找零1分，大于2分和5分的找零与此类似，那么找零时就有三种选择，即找零后剩余金额为n-1，n-2，n-5，这三种选择总的找零数最少的方案即为所求解的方案。显然，最终的找零方案与执行当前选择后剩余的金额的找零相关，即金额n的最优找零方案包含了金额n-1，n-2，n-5的最优找零方案，于是可得如下状态转移方程：Fn=minFn-1+1Fn-2+1Fn-5+1具体的求解过程：初始化F(1)=1,F(2),F(5)=1F(1)1F(2)1F(3)minF(2)+1,F(1)+1=2F(4)minF(2)+1,F(3)+1=2F(5)1F(6)minF(1)+1,F(4)+1,F(1)+1=2F(n)minF(n-1)+1,F(n-2)+1,F(n-5)+1算法设计思路及求解过程思路：题目所描述的整个过程是“并行的”，而且所有人到达各自楼层的用时只与最晚到达的人有关。由于去各个楼层的具体数目对结果没有影响，所以可以将“电梯还剩i个人”表述成“电梯里面的乘客还要去i个楼层”。电梯从第1层开始向上运行，任意时刻的状态都可以由“电梯当前所处楼层”和“电梯里面都有哪些乘客确定”，初始状态为“电梯在1楼”和“所有乘客都在电梯上”。在电梯运行的每一个阶段都需要作出相应的决策，哪些乘客乘坐电梯到目的层，哪些乘客选择爬楼梯到达目的地。决策后，电梯里面的乘客被分成两部分：乘客留在电梯里面继续上升；乘客离开电梯走楼梯到达。求当前状态下电梯里面的乘客所有人到达目的所需要的最短时间，只需要找到一个最优决策，使得下电梯的乘客和留在电梯中的乘客最晚到达时间越短越好，这个最短时间就是当前状态下的最优解。如果假设决策后留在电梯里面的乘客到达各自楼层所需要的时间为T1，离开电梯的各自到达目的地所需时间为T2，则minmax(T1,T2)就是当前状态的最优解，其中T1可以由“当前层数+1”和“决策后剩下的人”确定的状态得到；T2则为下电梯走楼梯到达目的走楼梯最多的那一位乘客所花时间。如果去第k层的乘客选择在当前楼层下电梯，那么第1，2k-1层的乘客也应该选择在此时下电梯（如图1所示），这样就可以得到当前决策下的一个最优解。为了进一步处理停靠请求，对楼层按从高到低进行排序，并以此进行编号，如此可以避免在求解过层中处理不连续的请求，如：图1解题结论1无论电梯当前位于何处2nk3第k楼的乘客选择在此下电梯k-1k层以下的乘客此刻都应离开电梯4，5，10。使用i,j两个参数表示电梯当前的状态，即电梯在第i层，电梯中有j位乘客。综上所述，可得如下状态转移方程：fi,j=minmaxt1,t2t1=fi+1,k+tEle+tStop 0kjt2=maxfl-i*tPeo k+1ljf(i,j)表示电梯在第i层楼时，电梯中j个人都到达目的地所需要的最短时间。具体求解过程：第一步：计算初始状态f(topFloor,1),f(topFloor,2),f(topFloor,n);第二步：根据状态转移方程计算f(i,j);第三步：根据计算最优值时记录的信息求解最优解。1.3算法程序流程图2Input函数流程图图3solve函数流程图图4main函数流程图图5calculate函数流程图图6tStay函数流程图图7tLeave函数流程图1.4算法的程序实现代码#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<limits>#include<vector>usingnamespacestd;constintmaxN=30,maxF=31;/电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间constintve=4,st=10,vw=20;intn,fmaxN+1;/数据读取boolinput()cin>>n;if(n=0)returnfalse;/注意：f1.n中楼层数从高到低排列for(inti=n;i>=1;i-)cin>>fi;returntrue;intdpmaxF+1maxN+1,nextJmaxF+1maxN+1;/目前电梯在第currF层,第L层到第R层乘客离开电梯/函数返回这些离开电梯的乘客中最晚到达目的层所需时间inttLeave(intcurrF,intl,intr)if(l>r)return0;/仅需考虑两端,无论此刻电梯在何处,第l-r层花时间最多的/一定是离电梯当前所在楼层最远的乘客returnmax(abs(currF-fl),abs(currF-fr)*vw;/现在电梯在第i层,电梯里面本来有j位乘客,离开电梯的乘客剩下jj位inttStay(inti,intj,intjj)/没有乘客离开,电梯不停if(j=jj|i=1)returndpi+1jj+ve;/所有人都离开电梯elseif(jj=0)return0;/一般情况，电梯在第i层停靠elsereturndpi+1jj+ve+st;/voidcalculate()/边界：电梯在顶楼时所有人都必须下电梯inttopFloor=f1;for(intj=1;j<=n;j+)/1,j表示停靠请求的编号,编号越小表示编号停靠楼层越高dptopFloorj=tLeave(topFloor,1,j);for(inti=topFloor-1;i>=1;i-)/i表示电梯此刻所在位置for(intj=1;j<=n;j+)dpij=numeric_limits<int>:max();for(intjj=0;jj<=j;jj+)/计算离开电梯的人和留在电梯里面的人中到达目的地最晚的inttmp=max(tStay(i,j,jj),tLeave(i,jj+1,j);/在此求解花费时间最短的乘客if(dpij>tmp)dpij=tmp;/jj以前的乘客均离开电梯nextJij=jj;cout<<dp1n<<endl;/重构最优解voidrebuildSolution()vector<int>stops;intj=nextJ1n,topFloor=f1;for(inti=2;i<=topFloor;i+)if(nextJij!=j)stops.push_back(i);j=nextJij;if(j=0)break;cout<<stops.size();for(inti=0;i<stops.size();i+)cout<<""<<stopsi;cout<<endl;voidsolve()memset(dp,0,sizeof(dp);memset(nextJ,0,sizeof(nextJ);calculate();rebuildSolution();题目2切割木材2.1题目描述一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。同时每次切割时由于锯子本身有一定的宽度，因此每切割一次就会浪费掉一些木料。请设计一个程序使木匠能够用最少的木材切割出所需的木块。输入描述：输入有若干个测试样例，每个测试样例占一行。每行由若干个整数构成，第一个整数为所购买的木块的长度L（0<L<=30000）,第二个整数为锯子的宽度W（0<W<=1000）,其后的若干个整数分别表示制作家具时需要的木块的长度。输出描述：每个测试样例输出一行，为一个整数N，表示制作家具时需要购买的木块的数量。样例输入：070样例输出：342.2算法文字描述此题目是装载问题的一个变种，与装载问题不同的是此问题没有给出“船”数量，但是给出了船的载重量，因此仍旧可以借鉴解装载问题的思路，即让每一根原材料可以切出更多符合要求的木料，类似于装载问题中“将第一艘轮船尽可能地装满”，即保证切割以后剩余的原材料是最少的。算法具体描述如下：Step1：声明求解结果变量res=0，剩余未切割木料数量count=n，当前已切割木料长度和cw=0，目前最大切割长度bestW=0，求解标记数组visitedn，当前最优求解数组nVisitedn，问题求解状态记录数组res_arrn，锯口宽度sw；Step2：当剩余未切割木料数量count大于0时，利用回溯法进行最大子集和求解。当i<n-1时，搜索左子树的条件：当前节点未被访问且cw+datai<=w+sw，访问左子树时第i层相应节点时将相应访问标记visitedi置为true，递归搜索该节点的左子树；递归搜索右子树时，将当前节点访问标记visitedi置为false；Step3：当i>n-1时，获得一种切割方案，若此次求解结果优于已得求解结果，即bestW<cw，使用nVisited数组记录当前求解状态，同时更新bestW的值；Step4：利用回溯法完成1次木料切割后，更当前问题求解状态res_arr数组，根据最新的求解状态更新未切割木料数量count，同时res+，若count=0则求解结束，否则重复2,3,4直至count=0。2.3算法程序流程图8main函数流程图图9input函数流程图图10solve函数流程图图11backtrack函数流程图2.4算法的程序实现代码#include<stdio.h>#include<malloc.h>#include<cstring>#defineMAX_SAMPLE_LENGTH50/*回溯法求解*/int*in=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int);int*data=(int*)malloc(MAX_SAMPLE_LENGTH*sizeof(int);bool*visited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);bool*nVisited=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);bool*res_arr=(bool*)malloc(MAX_SAMPLE_LENGTH*sizeof(bool);intw;/原材料长度intn;/数据元素个数intsw;/锯口宽度intcw;/当前已锯木头长度和intres;/求解结果intbestW;/当前求解最大值boolinput()boolflag=true;/初始化数据保存数组memset(in,0,MAX_SAMPLE_LENGTH*sizeof(int);memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool);memset(res_arr,false,MAX_SAMPLE_LENGTH*sizeof(bool);memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool);/记录输入数据个数n=0;/读取数据-原材料(木头)长度scanf("%d",&w);if(0=w)flag=false;/锯口宽度scanf("%d",&sw);while(flag)scanf("%d",data+n);n+;charch=getchar();if(ch='n')break;returnflag;voidbacktrack(inti,intk)if(i>n-1)if(bestW<cw)/记录最优值bestW=cw;/记录当前最优解for(inti=0;i<n;i+)nVisitedi=visitedi;return;/进入右子树条件if(!res_arri&&cw+datai+k*sw<=w)/记录当前已锯木头数量k+;/进入右子树实际操作cw+=datai;/访问标记visitedi=true;backtrack(i+1,k);cw-=datai;k-;visitedi=false;backtrack(i+1,k);intsolve(int*data,intn)res=0;/求解结果初始化intcount=n;while(count>0)/初始化,cw当前已锯木头长度和,/count剩余未锯木头数量,bestW本次求解最大长度和cw=0,count=0,bestW=0;backtrack(0,0);for(inti=0;i<n;i+)/更新待解决问题状态if(!res_arri)res_arri=nVisitedi;/剩余未求解元素个数if(!res_arri)count+;/记录求解结果res+;returnres;intmain()while(input()solve(data,n);printf("n%dn",res);题目3设计题3.1题目描述给定一个数塔，如图12所示。在此数塔中，从顶部出发，在每一节点可以选择向左走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。图12数塔3.2输入要求第一行输入一个整数n，n表示数塔的层数，第2，n+1行为数塔对应节点的数值。3.3输出要求第一行输出路径数值和，第二行输出具体路径。3.4样例输入5131112407163.5样例输出91(1,1)->(2,1)->(3,1)->(4,2)->(5,3)3.6测试样例输入711981210773.7测试样例输出113(1,1)->(2,1)->(3,2)->(4,3)->(5,3)->(6,4)->(7,5)3.8算法实现的文字描述动态规划采用自底向上逐层分阶段决策1)第1次决策，针对第4层如果最优路径经过6，则从第4层到第5层应该经过12，则第4+第5层的最大路径为6+12=18如果最优路径经过14，则从第4层到第5层应该经过13，则第4+第5层的最大路径为13+14=27这样实际上将5阶数塔变为4阶数塔问题了。2)逐层向上递推，最后得到问题的最优解根据题意，待处理的数据规模同数塔的层数有关，同时数据节点的个数与层数相同，所以可以使用二维数组data存储待处理节点数值，只有一半的节点有数值，实际上是一个下三角矩阵。可以较为容易地得到问题状态转移方程：di,j=datai,j i=ndi,j=maxdi+1,j,di+1,j+1+datai,j 1i<nStep1：声明变量数塔层数n，待处理数据节点数值数组datann,结果（状态）数组dnn;Step2：输入数塔层数n，维数组data和d分配内存空间；Step3：初始化第n层结果（状态）数组值；Step4：根据状态转移方程求解d(i,j)，其中i从n-1到1，j从1到i；Step5：输出d(1,1)；Step6：根据数组d求解具体路径并输出。3.9算法程序流程图13main函数流程图图14tower_walk函数流程图3.10算法的程序实现代码#include<stdio.h>#include<cstring>#include<malloc.h>#include<math.h>usingnamespacestd;int*data=NULL;/存储数塔原始数据int*dp=NULL;/状态值记录intn;/塔的层数/*动态规划实现数塔求解*/voidtower_walk()intindex1=0,index2=0;/dp初始化for(inti=0;i<n;+i)index1=(n-1)*n+i;dpindex1=dataindex1;inttemp_max;for(inti=n-2;i>=0;-i)for(intj=0;j<=i;+j)/使用递推公式计算dp的值index1=(i+1)*n+j;index2=i*n+j;temp_max=(dpindex1>dpindex1+1)?dpindex1:dpindex1+1;dpindex2=temp_max+dataindex2;/*打印最终结果*/voidprint_result()intindex=0;printf("%dn",dpindex);intnode_value;/首先输出塔顶元素intj=0,i=0;printf("(%d,%d)",i+1,j+1);for(i=1;i<n;+i)index=(i-1)*n+j;node_value=dpindex-dataindex;/如果node_value=dpij则说明下一步应该是dataij;/如果node_value=dpij+1则说明下一步应该是dataij+1.index=i*n+j+1;if(node_value=dpindex)+j;printf("->(%d,%d)",i+1,j+1);printf("n");intmain()scanf("%d",&n);data=(int*)malloc(n*n*sizeof(int);memset(data,0,n*n*sizeof(int);dp=(int*)malloc(n*n*sizeof(int);memset(dp,0,n*n*sizeof(int);intindex=0;for(inti=0;i<n;+i)for(intj=0;j<=i;+j)index=i*n+j;scanf("%d",data+index);charch=getchar();tower_walk();print_result();算法分析与设计课程总结通过本课程各个专题模块的学习，回顾和巩固了曾经学习过的知识，并且有了新的感受和收获。老师的教学具有很强的启发性，在整个学习过程中，通过具体的示例详细地讲解了穷举法、动态规划、贪心算法、回溯法和分支限界法等不同类型的算法，是我对学习算法充满了热情。学习算法对逻辑思维能力、推理能力和表达能力都有一定的要求，同时学习过程也有助于提高个人的逻辑思维能力，有助于培养分析问题和解决问题的习惯。最后感谢黄海于老师的悉心指导。参考文献1 王晓东.算法设计与分析.清华大学出版社.2014.2 ThomasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein.算法导论.机械工业出版社.2011.