算法分析与设计-课程设计报告

XXXX大学

算法设计与分析课程设计报告

院 （系）： 年 级： 姓 名： 专 业： 计算机科学与技术

研究方向： 互联网与网络技术

指导教师：

X X X X 大 学

目 录

题目1 电梯调度 .......................... 错误!未定义书签。

题目描述 .................................................错误!未定义书签。

算法文字描述 .............................................错误!未定义书签。 算法程序流程 .............................................错误!未定义书签。 算法的程序实现代码 .......................................错误!未定义书签。

题目2 切割木材 .......................... 错误!未定义书签。

题目描述 ..................................................错误!未定义书签。 算法文字描述 ..............................................错误!未定义书签。 算法程序流程 ..............................................错误!未定义书签。 算法的程序实现代码 ........................................错误!未定义书签。

题目3 设计题 ............................ 错误!未定义书签。

题目描述 ..................................................错误!未定义书签。 输入要求 .................................................错误!未定义书签。 输出要求 ..................................................错误!未定义书签。 样例输入 ..................................................错误!未定义书签。 样例输出 ..................................................错误!未定义书签。 测试样例输入 ..............................................错误!未定义书签。 测试样例输出 ..............................................错误!未定义书签。 算法实现的文字描述 ........................................错误!未定义书签。 算法程序流程 ..............................................错误!未定义书签。 算法的程序实现代码 ........................................错误!未定义书签。

算法分析与设计课程总结 ................... 错误!未定义书签。 参考文献 ................................. 错误!未定义书签。

题目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<=f1

对于每一个测试用例，第1行输出最后一位乘客到达目的楼层所需时间，第2行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。

算法文字描述

程序实现的算法思想，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到远问题的解。与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常是多项式量级。在分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下：○1找出最优解的性质，并刻画其结构；○2递归地定义最优值；3以自底向上的方式计算最优值；○4根据计算最优值时得到的信息，构造最优○解。