算法分析报告与设计-课程设计报告材料.doc

实用文档 文案大全 实用文档 文案大全 PAGE XXXX大学 算法设计与分析课程设计报告 院 （系）： 年 级： 姓 名： 专 业： 计算机科学与技术 研究方向： 互联网与网络技术 指导教师： X X X X 大 学 目 录 TOC \o 1-3 \h \z \u 题目1 电梯调度 1 1.1 题目描述 1 1.2 算法文字描述 1 1.3 算法程序流程 4 1.4 算法的程序实现代码 8 题目2 切割木材 10 2.1题目描述 10 2.2算法文字描述 10 2.3算法程序流程 11 2.4算法的程序实现代码 15 题目3 设计题 17 3.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 参考文献 24 题目1 电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如：此刻电梯停靠需求为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 f1 f2 … fn，其中n表示有n层楼需要停靠，n=0表示没有更多的测试用例，程序终止运行。f1 f2 … fn表示需要停靠的楼层（n=30，2=f1f2…fn=31），每一个数字都用一个空格隔开。 输出要求： 对于每一个测试用例，第1行输出最后一位乘客到达目的楼层所需时间，第2行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。 1.2 算法文字描述 程序实现的算法思想，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到远问题的解。与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常是多项式量级。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下： eq \o\ac(○,1)找出最优解的性质，并刻画其结构； eq \o\ac(○,2)递归地定义最优值； eq \o\ac(○,3)以自底向上的方式计算最优值； eq \o\ac(○,4)根据计算最优值时得到的信息，构造最优解。 例如：给定金额n以及1，2,5分硬币，求找n的最少硬币数。 对于大于1分的找零理所当然可以找零1分，大于2分和5分的找零与此类似，那么找零时就有三种选择，即找零后剩余金额为n-1，n-2，n-5，这三种选择总的找零数最少的方案即为所求解的方案。显然，最终的找零方案与执行当前选择后剩余的金额的找零相关，即金额n的最优找零方案包含了金额n-1，n-2，n-5的最优找零方案，于是可得如下状态转移方程： F 具体的求解过程： 初始化F(1)=1,F(2),F(5)=1 F(1) 1 F(2) 1 F(3) min{F(2)+1,F(1)+1}=2 F(4) min{F(2)