《算法分析与设计-课程设计报告》由会员分享，可在线阅读，更多相关《算法分析与设计-课程设计报告（26页珍藏版）》请在金锄头文库上搜索。
1、XXXXXXXX 大学大学 算法设计与分析课程设计报告算法设计与分析课程设计报告院院 （系）：（系）： 年年 级：级： 姓姓 名：名： 专专 业：业： 计算机科学与技术计算机科学与技术 研究方向：研究方向： 互联网与网络技术互联网与网络技术 指导教师：指导教师： X X X X X X X X 大大 学学II目目 录录题目 1 电梯调度 .11.1 题目描述.1 1.2 算法文字描述.1 1.3 算法程序流程.4 1.4 算法的程序实现代码.8 题目 2 切割木材 .102.1 题目描述.10 2.2 算法文字描述.10 2.3 算法程序流程.11 2.4 算法的程序实现代码.15 题目 3
2、设计题 .173.1 题目描述.17 3.2 输入要求.17 3.3 输出要求.17 3.4 样例输入.17 3.5 样例输出.17 3.6 测试样例输入.17 3.7 测试样例输出.18 3.8 算法实现的文字描述.18 3.9 算法程序流程.19 3.10 算法的程序实现代码.20 算法分析与设计课程总结.23参考文献.241题目题目 1 1 电梯调度电梯调度1.11.1 题目描述题目描述一栋高达 31 层的写字楼只有一部电梯，其中电梯每走一层需花费 4 秒，并且在每一层楼停靠的时间为 10 秒，乘客上下一楼需要 20 秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如
3、：此刻电梯停靠需求为 4 5 10（有三位乘客，他们分别想去 4 楼、5 楼和 10 楼） ，如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为 3*4=12 秒、4*4+10=26 秒、4*9+2*10=56 秒，则最后一位乘客到达办公室的时间为 56 秒，相应的停靠计划为 4 5 10 均停靠。对于此测试用例电梯停靠计划方案：4 10，这样到第 4 楼的乘客所需时间为 3*4=12 秒，到第 5 楼的乘客所需时间为 3*4+20=32 秒，到第10 楼的乘客所需时间为 9*4+10=46 秒，即最后到达目的楼层的顾客所需时间为46 秒。输入要求：输入要求：输入的第 1 行为整数 n f
4、1 f2 fn，其中 n 表示有 n 层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 fn 表示需要停靠的楼层（n=1将当前停靠请求保 存到fiY返回flag值函数执 行结束i=i-1N图 2 Input 函数流程图67主函数开始调用input函数Input函数返回 结果为真？调用solve函数求解Y主函数结束N图 4 main 函数流程图solve函数开始执行初始化dp数组元素 值为0和nextJ数组 元素为0调用calculate函数调用rebuildSolution 函数solve函数结束图 3 solve 函数流程图8calculate函数开始 执行topFloo
5、r=f1j=1j=1j=1jtmpdpij=tmp nextJij=jjjj=jj+1YNYYj=j+1NNi=i-1NYcalculate函数执行 结束N输出dp1n图 5 calculate 函数流程图9tLeave函数开始执行lrres=0res=max(abs(currF-fl), abs(currF-fr) * vwNtLeave函数执行结束YtStay函数开始执行res=0j=jj1=ires=dpi+1jj+veYYN0=jjNres=0res=dpI+1jj+ve+stYN返回res值函数执行 结束图 7 tLeave 函数流程图图 6 tStay 函数流程图101.41.4
6、算法的程序实现代码算法的程序实现代码# include # include # include #include # include #include using namespace std;const int maxN=30,maxF=31; / 电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间 const int ve=4,st=10,vw=20;int n,fmaxN+1;/数据读取 bool input()cinn;if(n=0) return false;/ 注意：f1.n中楼层数从高到低排列for(int i=n;i=1;i-)cinfi;return true; int
7、 dpmaxF+1maxN+1,nextJmaxF+1maxN+1;/ 目前电梯在第currF层, 第L层到第R层乘客离开电梯 / 函数返回这些离开电梯的乘客中最晚到达目的层所需时间 int tLeave(int currF,int l,int r)if(lr) return 0;/ 仅需考虑两端, 无论此刻电梯在何处, 第l-r层花时间最多的/ 一定是离电梯当前所在楼层最远的乘客return max(abs(currF-fl),abs(currF-fr)*vw; / 现在电梯在第i层, 电梯里面本来有j位乘客, 离开电梯的乘客剩下jj位 int tStay(int i,int j,int jj)/ 没有乘客离开,电梯不停if(j=jj | i=1)return dpi+1jj +ve;/ 所有人都离开电梯else if(jj=0)return 0;/ 一般情况，电梯在第i层停靠elsereturn dpi+1jj+ve+st; / void calculate()/ 边界：电梯在顶楼时所有人都必须下电梯int topFloor=f
