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

精心整理XXXX大学算法设计与分析课程设计报告院（系）：年级：姓名：专业：计算机科学与技术研究方向：互联网与网络技术指导教师：XXXX大学精心整理目录1.1题目描述..............................................1.2算法文字描述..........................................1.3算法程序流程..........................................1.4算法的程序实现代码....................................题目2切割木材2.1题目描述..............................................2.2算法文字描述..........................................2.3算法程序流程..........................................2.4算法的程序实现代码....................................题目3设计题3.1题目描述..............................................3.2输入要求..............................................3.3输出要求..............................................3.4样例输入..............................................3.5样例输出..............................................3.6测试样例输入..........................................3.7测试样例输出..........................................3.8算法实现的文字描述....................................3.9算法程序流程..........................................3.10算法的程序实现代码...................................精心整理算法分析与设计课程总结参考文献题目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行为整数nf1f2…fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1f2…fn表示需要停靠的楼层（n=30，2=f1f2…fn=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的最优找零方案，于是可得如下状态转移方程：(){()()()具体的求解过程：初始化F(1)=1,F(2),F(5)=1F(1)1F(2)1F(3)min{F(2)+1,F(1)+1}=2F(4)min{F(2)+1,F(3)+1}=2F(5)1F(6)min{F(1)+1,F(4)+1,F(1)+1}=2…F(n)min{F(n-1)+1,F(n-2)+1,F(n-5)+1}算法设计思路及求解过程思路：题目所描述的整个过程是“并行的”，而且所有人到达各自楼层的用时只与最晚到达的人有关。由于去各个楼层的具体数目对结果没有影响，所以可以将“电梯还剩i个人”表述成“电梯里面的乘客还要去i个楼层”。电梯从第1层开始向上运行，任意时刻的状态都可以由“电梯当前所处楼层”和“电梯里面都有哪些乘客确定”，初始状态为“电梯在1楼”和“所有乘客都在电梯上”。在电梯运行的每一个阶段都需要作出相应的决策，哪些乘客乘坐电梯到目的层，哪些乘客选择爬楼梯到达目的地。决策后，电梯里面的乘客被分成两部分：乘客留在电梯里面继续上升；乘客离开电梯走楼梯到达。求当前状态下电梯里面的乘客所有人到达目的所需要的最短时间，只需要找到一个最优决策，使得下电梯的乘客和留在电梯中的乘客最晚到达时间越短越好，这个最短时间就是当前状态下的最优解。如果假设决策后留在电梯里面的乘客到达各自楼层所需要的时间为T1，离开电梯的各自到达目的地所需时间为T2，则min{max(T1,T2)}就是当前状态的最优解，其中T1可以由“当前层数+1”和“决策后剩下的人”确定的状态得到；T2则为下电梯走楼梯到达目的走楼梯最多的那一位乘客所花时间。如果去第k层的乘客选择在当前楼层下电梯，那么第1，2…k-1层的乘客也应该选择在此时下电梯（如所示），这样就可以得到当前决策下的一个最优解。为了进一步处理停靠请求，对楼层按从高到低进行排序，并以此进行编号，如此可以避免在求解过层中处理不连续的请求，如：4，5，10。使用i,j两个参数表示电梯当前的状态，即电梯在第i层，电梯中有j位乘客。综上所述，可得如下状态转移方程：{(){()}(){|[]|}f(i,j)表示电梯在第i层楼时，电梯中j个人都到达目的地所需要的最短时间。具体求解过程：第一步：计算初始状态f(topFloor,1),f(topFloor,2),…,f(topFloor,n);第二步：根据状态转移方程计算f(i,j);1无论电梯当前位于何处2nk…3…第k楼的乘客选择在此下电梯k-1k层以下的乘客此刻都应离开电梯图解题结论第三步：根据计算最优值时记录的信息求解最优解。1.3算法程序流程开始输入n声明布尔变量flag，初始值为真0==nYflag=falseNi=ni=1将当前停靠请求保存到f[i]Y返回flag值函数执行结束i=i-1N图Input函数流程图主函数开始调用input函数Input函数返回结果为真？调用solve函数求解Y主函数结束N图main函数流程图solve函数开始执行初始化dp数组元素值为0和nextJ数组元素为0调用calculate函数调用rebuildSolution函数solve函数结束图solve函数流程图calculate函数开始执行topFloor=f[1]j=1j=n调用tLeave(topFloor,1,j)函数并将计算结果保存至dp[topFloor][j]j++Yi=topFloor-1i=1j=1j=n将dp[i][j]置为整型数最大值jj=0jj=j调用函数tStay(I,j,jj)计算留在电梯中的乘客到达目的地所需时间t1调用tLeave(I,jj+1,j)计算离开电梯的乘客到达目的地所需时间t2tmp=max(t1,t2)dp[i][j]tmpdp[i][j]=tmpnextJ[i][j]=jjjj=jj+1YNYYj=j+1NNi=i-1NYcalculate函数执行结束N输出dp[1][n]图calculate函数流程图tLeave函数开始执行lrres=0res=max(abs(currF-f[l]),abs(currF-f[r]))*vwNtLeave函数执行结束YtStay函数开始执行res=0j==jj1==ires=dp[i+1][jj]+veYYN0==jjNres=0res=dp[I+1][jj]+ve+stYN返回res值函数执行结束图tLeave函数流程图图tStay函数流程图1.4算法的程序实现代码#includeiostream#includecstring#includealgorithm#includecmath#includelimits#includevectorusingnamespacestd;constintmaxN=30,maxF=31;//电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间constintve=4,st=10,vw=20;intn,f[maxN+1];//数据读取boolinput(){cinn;if(n==0)returnfalse;//注意：f[1...n]中楼层数从高到低排列for(inti=n;i=1;i--)cinf[i];returntrue;}intdp[maxF+1][maxN+1],nextJ[maxF+1][maxN+1];//目前电梯在第currF层,第L层到第R层乘客离开电梯//函数返回这些离开电梯的乘客中最晚到达目的层所需时间inttLeave(intcurrF,intl,intr){if(lr)return0;//仅需考虑两端,无论此刻电梯在何处,第l-r层花时间最多的//一定是离电梯当前所在楼层最远的乘客returnmax(abs(currF-f[l]),abs(currF-f[r]))*vw;}//现在电梯在第i层,电梯里面本来有j位乘客,离开电梯的乘客剩下jj位inttStay(inti,intj,intjj){//没有乘客离开,电梯不停if(j==jj||i==1)returndp[i+1][jj]+ve;//所有人都离开电梯elseif(jj==0)return0;//一般情况，电梯在第i层停靠elsereturndp[i+1][jj]+ve+st;}//voidcalculate(){//边界：电梯在顶楼时所有人都必须下电梯inttopFloor=f[1];for(intj=1;j=n;j++){//1,j表示停靠请求的编号,编号越小表示编号停靠楼层越高dp[topFloor][j]=tLeave(topFloor,1,j);}for(inti=topFloor-1;i=1;i--){//i表示电梯此刻所在位置for(intj=1;j=n;j++){dp[i][j]=numeric_limitsint::max();for(intjj=0;jj=j