下载文档原格式
算法设计与分析课程报告第一章算法问题求解基础1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。
2、算法的特性①有穷性：一个算法必须保证执行有限步之后结束；②确切性：算法的每一步骤必须有确切的定义；③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成3、算法与程序的关系：区别：程序可以不一定满足可终止性。
但算法必须在有限时间内结束；程序可以没有输出,而算法则必须有输出；算法是面向问题求解的过程描述，程序则是算法的实现。
联系：程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的有限性性质。
4、算法描述方式：自然语言，流程图，伪代码，高级语言。
第二章算法分析基础1、算法复杂性分析：算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。
算法复杂性度量：期望反映算法本身性能，与环境无关。
理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。
一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。
算法复杂性C依赖于问题规模N、算法输入I和算法本身A。
即C=F(N, I, A)。
第五章分治法1、递归算法：直接或间接地调用自身的算法。
用函数自身给出定义的函数称为递归函数。
注：边界条件与递归方程是递归函数的二个要素。
实例：①阶乘函数；②Fibonacci数列；③Ackerman函数；④排列问题；⑤整数划分问题；⑥Hanoi塔问题优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
算法与分析课程设计报告题目：专业：班级：学号：姓名：年月日一、算法问题描述独立钻石跳棋问题。
在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。
下棋的规则是任意棋子可以沿着水平或着垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。
试设计一个算法并找出一种下棋的方法，使得棋盘上最终只剩下一个棋子在棋盘的正中央。
二、算法问题形式化表示在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。
算法解决了在32个棋子摆放在有33格的盘上(只有中心格空着)在规定当一个棋子跳过邻近的一个棋子到空格时，就将这张邻近的棋子从盘上拿掉，使除了最后留在中心格一个棋子外其余的棋子均被拿掉的问题！三、期望输入与输出期望输入：显示一个棋盘，在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。
期望输出：使得棋盘上最终只剩下一个棋子在棋盘的正中央四、算法分析与步骤描述总体一个回溯的思想，如果两个子字间能跳，那么我们就跳了之后记录其新的位置，因为跳的前后都是一个问题，所以我们能用递归分治，跳了一次之后棋子数减1，并把被跳过的棋子和编号最后的棋子交换，这样就达到了把棋子去掉的目的。
并把最优解保存。
如果temp当前走的次数已经大于最优解，那么我们就不用算了。
五、问题实例及算法运算步骤此次问题主要用回溯算法，基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
六、算法运行截图开始时：结束后：七、附录代码（java）package sfdesign;import java.awt.Color;import java.awt.GridLayout;import java.awt.event.MouseEvent; import java.awt.event.MouseListener; import javax.swing.JButton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;public class DC extends JFrame {//-----move时候用的变量们public static int oldx = 0;public static int oldy = 0;public static int newx = 0;public static int newy = 0;public static boolean movingflag = false;//-----layeroutprivate GridLayout gamepanellayer = new GridLayout(1, 2); private GridLayout optionlayer = new GridLayout(2, 1); private GridLayout chessboardlayer = new GridLayout(9, 9); //-----左右布局的jpanelprivate JPanel leftpanel = new JPanel();private JPanel rightpanel = new JPanel();//-----public static int restcount = 32;public static int steps = 0;public static JLabel jl1 = new JLabel("剩余子数:" + restcount); public static JLabel jl2 = new JLabel("当前步数:0" + steps); //-----board点阵public static boolean[][] chessboard = {{false, false, false, false, false, false, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, true, true, true, true, true, true, true, false}, {false, true, true, true, true, true, true, true, false}, {false, true, true, true, true, true, true, true, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, false, false, false, false, false, false} };//-----chess点阵public static boolean[][] chessdot = {{false, false, false, false, false, false, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, true, true, true, true, true, true, true, false}, {false, true, true, true, false, true, true, true, false}, {false, true, true, true, true, true, true, true, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, true, true, true, false, false, false}, {false, false, false, false, false, false, false, false, false} };//-----chess引用点阵public static OneChess[][] chessArmy = new OneChess[9][9]; //-----初始化public DC(int w, int h) {this.setBounds(300, 300, 2 * w, h);this.setTitle("◇独立钻石◇eggno8");this.getContentPane().setLayout(gamepanellayer);this.getContentPane().add(this.leftpanel);this.leftpanel.setLayout(this.optionlayer);this.leftpanel.add(jl1);this.leftpanel.add(jl2);this.getContentPane().add(this.rightpanel);this.rightpanel.setLayout(chessboardlayer);for (int row = 0; row < 9; row++) {for (int col = 0; col < 9; col++) {boolean flag = chessdot[col][row];OneChess oc = new OneChess(flag, col, row);if (!chessboard[col][row]) {oc.setBoard();}this.chessArmy[col][row] = oc;this.rightpanel.add(oc);}}this.setVisible(true);}public static boolean canMove() {boolean f = false;if (oldx == newx && (oldy == newy + 2 || newy == oldy + 2)) { if (chessArmy[oldx][ (newy + oldy) / 2].getLife()) {f = true;} else {f = false;}}if (oldy == newy && (oldx == newx + 2 || newx == oldx + 2)) { if (chessArmy[ (newx + oldx) / 2][oldy].getLife()) {f = true;} else {f = false;}}return f;}public static void doMove() {if (oldx == newx) {chessArmy[oldx][ (newy + oldy) / 2].setLife(false);if (oldy == newy) {chessArmy[ (newx + oldx) / 2][oldy].setLife(false);}chessArmy[oldx][oldy].setLife(false);chessArmy[newx][newy].setLife(true);}public static void main(String[] _s) {DC dc = new DC(360, 360);}}class OneChess extends JButton implements MouseListener { private boolean life;private boolean isout;public int xp;public int yp;public OneChess(boolean sl, int x, int y) {setLife(sl);xp = x;yp = y;this.addMouseListener(this);}public void setLife(boolean l) {life = l;if (l) {setBackground(Color.YELLOW);} else {setBackground(Color.GRAY);}}public void setMoving() {this.setBackground(Color.orange);}public void setBoard() {isout = true;setBackground(Color.WHITE);}public boolean getLife() {return life;}public void mouseClicked(MouseEvent e) {}public void mousePressed(MouseEvent e) {if (isout) {return;//-----movingflag判断moving的两个边沿if (!DC.movingflag) { //选中单个子if (DC.chessboard[xp][yp] && getLife()) {DC.oldx = xp;DC.oldy = yp;DC.movingflag = true;setMoving();}} else { //成功移动1个子if (xp == DC.oldx && yp == DC.oldy) { //放弃1个子，计数1步setLife(true);DC.movingflag = false;DC.steps++;DC.jl2.setText("当前步数:0" + DC.steps);} else if (DC.chessboard[xp][yp] && getLife()) { //点到其他子身上，切换选中的子DC.chessArmy[DC.oldx][DC.oldy].setLife(true);DC.oldx = xp;DC.oldy = yp;DC.steps++;DC.jl2.setText("当前步数:0" + DC.steps);setMoving();}if (DC.chessboard[xp][yp] && !getLife()) {DC.newx = xp;DC.newy = yp;if (DC.canMove()) {DC.doMove();DC.restcount--;DC.jl1.setText("剩余子数" + DC.restcount);DC.oldx = xp;DC.oldy = yp;setMoving();}}}return;}public void mouseReleased(MouseEvent e) {}public void mouseEntered(MouseEvent e) {}public void mouseExited(MouseEvent e) {}//actionPerformed()}。
第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。
算法分析与设计实验报告算法分析与设计实验报告一、引言算法是计算机科学的核心，它们是解决问题的有效工具。
算法分析与设计是计算机科学中的重要课题，通过对算法的分析与设计，我们可以优化计算机程序的效率，提高计算机系统的性能。
本实验报告旨在介绍算法分析与设计的基本概念和方法，并通过实验验证这些方法的有效性。
二、算法分析算法分析是评估算法性能的过程。
在实际应用中，我们常常需要比较不同算法的效率和资源消耗，以选择最适合的算法。
常用的算法分析方法包括时间复杂度和空间复杂度。
1. 时间复杂度时间复杂度衡量了算法执行所需的时间。
通常用大O表示法表示时间复杂度，表示算法的最坏情况下的运行时间。
常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。
其中，O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，O(n log n)表示线性对数时间复杂度，O(n^2)表示平方时间复杂度。
2. 空间复杂度空间复杂度衡量了算法执行所需的存储空间。
通常用大O表示法表示空间复杂度，表示算法所需的额外存储空间。
常见的空间复杂度有O(1)、O(n)和O(n^2)等。
其中，O(1)表示常数空间复杂度，O(n)表示线性空间复杂度，O(n^2)表示平方空间复杂度。
三、算法设计算法设计是构思和实现算法的过程。
好的算法设计能够提高算法的效率和可靠性。
常用的算法设计方法包括贪心算法、动态规划、分治法和回溯法等。
1. 贪心算法贪心算法是一种简单而高效的算法设计方法。
它通过每一步选择局部最优解，最终得到全局最优解。
贪心算法的时间复杂度通常较低，但不能保证得到最优解。
2. 动态规划动态规划是一种将问题分解为子问题并以自底向上的方式求解的算法设计方法。
它通过保存子问题的解，避免重复计算，提高算法的效率。
动态规划适用于具有重叠子问题和最优子结构的问题。
3. 分治法分治法是一种将问题分解为更小规模的子问题并以递归的方式求解的算法设计方法。
《算法设计与分析》课程实验报告实验序号：07实验项目名称：实验8 贪心算法（一）一、实验题目1.删数问题问题描述：键盘输入一个高精度的正整数N（不超过250 位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。
编程对给定的N 和k，寻找一种方案使得剩下的数字组成的新数最小。
若输出前有0则舍去2.区间覆盖问题问题描述：设x1,x2,...xn是实轴上的n个点。
用固定长度为k的闭区间覆盖n个点，至少需要多少个这样的固定长度的闭区间？请你设计一个有效的算法解决此问题。
3.会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。
设计一个有效的贪心算法进行安排。
（这个问题实际上是著名的图着色问题。
若将每一个活动作为图的一个顶点，不相容活动间用边相连。
使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。
）4.导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
给定导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
二、实验目的（1）通过实现算法，进一步体会具体问题中的贪心选择性质，从而加强对贪心算法找最优解步骤的理解。
（2）掌握通过迭代求最优的程序实现技巧。
（3）体会将具体问题的原始数据预处理后（特别是以某种次序排序后），常能用贪心求最优解的解决问题方法。
三、实验要求（1）写出题1的最优子结构性质、贪心选择性质及相应的子问题。
（2）给出题1的贪心选择性质的证明。
（3）（选做题）：写出你的算法的贪心选择性质及相应的子问题，并描述算法思想。
XXXX大学算法设计与分析课程设计报告院 （系）：年 级：姓 名： 专 业： 计算机科学与技术研究方向： 互联网与网络技术 指导教师：X X X X 大 学目 录题目1 电梯调度 (1)11.1 题目描述 ..................................................................................11.2 算法文字描述 ..............................................................................1.3 算法程序流程 ..............................................................................481.4 算法的程序实现代码 ........................................................................题目2 切割木材 .. (10)2.1题目描述 ..................................................................................10102.2算法文字描述 ..............................................................................112.3算法程序流程 ..............................................................................2.4算法的程序实现代码 ........................................................................15题目3 设计题 (17)173.1题目描述 ..................................................................................173.2 输入要求 ..................................................................................173.3输出要求 ..................................................................................173.4样例输入 ..................................................................................173.5样例输出 ..................................................................................173.6测试样例输入 ..............................................................................183.7测试样例输出 ..............................................................................183.8算法实现的文字描述 ........................................................................193.9算法程序流程 ..............................................................................3.10算法的程序实现代码 .......................................................................20算法分析与设计课程总结 (23)参考文献 (24)题目1 电梯调度1.1 题目描述一栋高达31层的写字楼只有一部电梯，其中电梯每走一层需花费4秒，并且在每一层楼停靠的时间为10秒，乘客上下一楼需要20秒，在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。
实验二：分治法实验一、实验目的（1）掌握设计有效算法的分治策略。
（2）通过快速排序学习分治策略设计技巧二、实验要求（1）熟练掌握分治法的基本思想及其应用实现。
（2）理解所给出的算法，并对其加以改进。
三、分治法的介绍任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。
问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
而当n较大时，问题就不那么容易处理了。
要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法的适用条件：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)（1)分治法核心思想 (3)（2）MaxMin算法分析 (3)2、动态规划 (4)（1）动态规划核心思想 (4)（2）矩阵连乘算法分析 (5)3、贪心法 (5)(1）贪心法核心思想 (5)（2）背包问题算法分析 (6)（3）装载问题算法分析 (7)4、回溯法 (7)（1）回溯法核心思想 (7)（2)N皇后问题非递归算法分析 (7)(3）N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (10)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归） (11)6、N皇后问题(递归) (11)四、心得体会 (12)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (15)4、装载问题 (17)5、N皇后问题(非递归） (19)6、N皇后问题(递归） (20)一、课程内容1、分治法,求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。
二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。
如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。
那末，这类问题可以用分治法求解。
分治法的核心技术1)子问题的划分技术.2）递归技术。
反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。
3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。
课程设计报告课程设计名称: 算法设计与分析系: 三系学生姓名：吴阳班级：12软件（2)班学号：20120311232成绩：指导教师：秦川开课时间：2014 学年一学期一、问题描述1．普通背包问题给定n种物品和一个背包。
物品i的重量是Wi,其价值为Vi，背包的容量为C。
选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
2．0/1背包问题给定n种物品和一个背包。
物品i的重量是Wi，其价值为Vi,背包的容量为C。
选择装入的背包的物品，使得装入背包中的物品的总价值最大,在选择物品i 装入背包时，对于每种物品i只有两种选择，即装入背包或者不装入背包，不能将物品装入背包多次,也不能只装入部分的物品i。
3．棋盘覆盖问题在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌(每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
二、问题分析1．普通背包问题对于背包问题，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量Ｗ，剩余的将是n-1个原重物品1,2，······,j-1，j+1，·····，n以及重为Ｗi－Ｗ的物品j中可装入容量为C－Ｗ的背包且具有最大价值的物品。
2．0/1背包问题如果当前背包中的物品的总容量是cw，前面的k—1件物品都已经决定好是否要放入包中，那么第k件物品是否放入包中取决于不等式cw + wk 〈= M （其中，wk为第k件物品的容量，M为背包的容量)（此即约束条件）然后我们再寻找限界函数，这个问题比较麻烦，我们可以回忆一下背包问题的贪心算法，即物品按照 物品的价值/物品的体积 来从大到小排列，然后最优解为(1，1，1.。
算法分析与设计课程实验报告班级： 131213学号： 13121XXX姓名： XXX指导老师：邓凡目录算法分析与设计课程实验报告 (1)实验一排序 (1)1. 课本练习2.3-7 (1)2. 实现优先队列 (2)3.快速排序 (2)4. 第k大元素 (3)实验二动态规划 (4)1. 矩阵链乘 (4)2. 最长公共子序列 (5)3. 最长公共子串 (7)4. 最大和 (9)5. 最短路径 (10)实验三贪心策略 (11)1. 背包问题 (11)2. 任务调度 (14)3. 单源点最短路径 (15)4. 任意两点间最短路径 (16)实验四回溯法 (18)1. 0-1背包问题 (18)2. 8-Queen问题 (21)实验一排序1.课本练习2.3-7(1)问题描述描述一个运行时间为 (nlgn)的算法，给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好是x的元素。
(2)问题分析该问题首先要进行排序，然后用二分查找法判断S中是否存在两个其和刚好是x的元素，因为时间复杂度为(nlgn)，所以可以采用归并排序。
(3)算法分析归并排序的思想是将n个元素分成各含n/2个元素的子序列，然后对两个子序列递归地进行排序，最后合并两个已排序的子序列得到排序结果。
二分查找的思想是对于集合中的每一个数字，用二分法找到x-S[i]的位置，若存在且不为其本身，则输出S中存在有两个和等于x的元素；否则，不存在。
(4)实验结果2.实现优先队列(1)问题描述实现优先队列，维护一组元素构成的集合S。
(2)问题分析优先队列是基于堆排序的。
首先将集合S中的元素进行堆排序。
当进行操作时，要不断维护集合S的有序性，即要不断地调整堆。
(3)算法分析本程序中主要的函数有INSERT()：需要调用INCREASE_KEY()来维护堆，其时间复杂度为O（lgn），函数MAXIMUM()仅需要返回S[1]，时间复杂度为 (1)，函数EXTRACT_MAX()需要调用堆排序中的MAX_HEAPIFY，时间复杂度为O(lgn)，函数INCREASE_KEY()更新结点到根结点的路径长度为O(lgn)，时间复杂度为O(lgn)。
XXXX大学算法设计与分析课程设计报告院（系）：年级：姓名：专业：计算机科学与技术研究方向：互联网与网络技术指导教师：X X X X 大学目录题目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<=f1<f2…fn<=31），每一个数字都用一个空格隔开。
输出要求：对于每一个测试用例，第1行输出最后一位乘客到达目的楼层所需时间，第2行输出停靠次数和相应的停靠方案，每一个数字用一个空格隔开。
1.2 算法文字描述程序实现的算法思想，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到远问题的解。
与分治法不同的是，适合用动态规划发求解的子问题往往不是相互独立。
若用分治法求解这类问题，则分解的子问题数目太多，以至于最后解决原问题需要耗费指数时间。
然而，不同子问题的数目常常是多项式量级。
在分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时在找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
为了达到这个目的，可以采用一个表来记录所有已解决的子问题的答案。
不管子问题以后是否被使用，只要他被计算过，就将其结果填入表中。
动态规划算法适合求解最优化问题，设计动态规划算法的具体步骤如下：○1找出最优解的性质，并刻画其结构；○2递归地定义最优值；○3以自底向上的方式计算最优值；○4根据计算最优值时得到的信息，构造最优解。
例如：给定金额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层的乘客也应该选择在此时下电梯（如图 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.3 算法程序流程图 1 解题结论图 2 Input函数流程图图 4 main函数流程图图 3 solve函数流程图图 5 calculate函数流程图图7 tLeave函数流程图图 6 tStay函数流程图1.4 算法的程序实现代码# include<iostream># include<cstring># include<algorithm>#include<cmath># include<limits>#include<vector>using namespace std;const int maxN=30,maxF=31;// 电梯上一层楼所需时间，电梯每次停靠时长，人走一层楼所需时间const int ve=4,st=10,vw=20;int n,f[maxN+1];//数据读取bool input(){cin>>n;if(n==0) return false;// 注意：f[1...n]中楼层数从高到低排列for(int i=n;i>=1;i--)cin>>f[i];return true;}int dp[maxF+1][maxN+1],nextJ[maxF+1][maxN+1];// 目前电梯在第currF层, 第L层到第R层乘客离开电梯// 函数返回这些离开电梯的乘客中最晚到达目的层所需时间int tLeave(int currF,int l,int r){if(l>r) return 0;// 仅需考虑两端, 无论此刻电梯在何处, 第l-r层花时间最多的// 一定是离电梯当前所在楼层最远的乘客return max(abs(currF-f[l]),abs(currF-f[r]))*vw;}// 现在电梯在第i层, 电梯里面本来有j位乘客, 离开电梯的乘客剩下jj位int tStay(int i,int j,int jj){// 没有乘客离开,电梯不停if(j==jj || i==1)return dp[i+1][jj] +ve;// 所有人都离开电梯else if(jj==0)return 0;// 一般情况，电梯在第i层停靠elsereturn dp[i+1][jj]+ve+st;}//void calculate(){// 边界：电梯在顶楼时所有人都必须下电梯int topFloor=f[1];for(int j=1;j<=n;j++){// 1,j表示停靠请求的编号,编号越小表示编号停靠楼层越高dp[topFloor][j]=tLeave(topFloor,1,j);}for(int i=topFloor-1;i>=1;i--){// i表示电梯此刻所在位置for(int j=1;j<=n;j++){dp[i][j]=numeric_limits<int>::max();for(int jj=0;jj<=j;jj++){// 计算离开电梯的人和留在电梯里面的人中到达目的地最晚的int tmp=max(tStay(i,j,jj),tLeave(i,jj+1,j));// 在此求解花费时间最短的乘客if(dp[i][j]>tmp) {dp[i][j]=tmp;// jj以前的乘客均离开电梯nextJ[i][j]=jj;}}}}cout<<dp[1][n]<<endl;}// 重构最优解void rebuildSolution(){vector<int> stops;int j=nextJ[1][n],topFloor=f[1];for(int i=2;i<=topFloor;i++){if(nextJ[i][j]!=j){stops.push_back(i);j=nextJ[i][j];if(j==0) break;}}cout<<stops.size();for(int i=0;i<stops.size();i++){cout<<" "<<stops[i];}cout<<endl;}void solve(){memset(dp,0,sizeof(dp));memset(nextJ,0,sizeof(nextJ)); calculate();rebuildSolution();}题目2 切割木材2.1题目描述一个木匠从木材公司买了一批木材，每块木材的长度均相同，但由于制作家具时所需的木块长度各不相同，因此需要把这些木材切割成长度不同的木块。
