《数据结构与算法设计》课程设计任务书
数据结构与算法设计课程设计
专业班级学号
姓名（签名）完成日期指导教师（签名）
1、程序设计说明书
【设计题目】迷宫设计
【问题描述】
在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示，每个方块或者是通道或者是墙。“迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案，并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。
【软件功能】
1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。
2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上
下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc 键退出；
3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。
4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。
【算法思想】
1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组中的元素的值
表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。
2、在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类Node，
定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。
3、采用A*算法，找到起点到终点的最短路径；
4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。
5、用java编程语言，有简单、美观的图形界面。
【逻辑结构设计】
运行程序，进入设置迷宫大小界面，输入行和列的值点击生成迷宫按钮进入迷宫自定义界面，根据操作菜单中的帮助选项，用键盘上的按键进行自定义操作（设置迷宫的起点、终点和墙）按F9或者操作菜单中的A*算法寻找最短路径选项即可实现对应的通路。
【存储结构设计】
该程序主要采用数组对迷宫信息进行存储，数组的元素的值表示迷宫对应位置的内容，主要是利用栈对路径信息进行存储，类Node，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。
栈：
public class Stack {
private Node top;//节点为Node类型
private int size;//栈中节点数
public Stack(){//构造方法
public void push(Object o)//进栈
public void pop()//出栈
public boolean isEmpty()//判断栈是否为空
public Node(Object o,Node n){//Node类构造方法
Position类中;
public class Position
public int x, y;// x代表图形界面的横坐标, y代表图形界面的纵坐标
public Position(int x, int y)//构造方法
public boolean equals(Object o)// 判断当前位置的o对象是否和调用该方法的Position类对象的内容相等
MazeGUI类中
public class MazeGUI //迷宫GUI
final Object obj=new Object();//锁对象
int row=0,col=0;//设置值迷宫图形界面的大小
Image offScreen = null;// 双缓冲技术防止屏幕闪烁
Maze maze;//构建迷宫参数
Rollback rollback;// 求解迷宫，并绘制人物在迷宫图形界面中的位置。
Thread t1= new Thread(new SolveThread(),"SolveThread");//寻路进程，在初始化Thread类时，把目标对象传递给这个线程实例
Thread t2 = new Thread(new AThread(),"AThread");
public void paint(Graphics g){//调用绘制地图的draw()方法和绘制人物位置的draw()方法
public void update(Graphics g)//双缓冲防止屏幕闪烁
public MazeGUI(int row,int col)//初始化窗体
private class SolveThread implements Runnable{//提供一个实现借口Runnable接口的类的实例，作为一个线程的目标对象
private class AThread implements Runnable//展示用A*算法求解迷宫过程的线程
【基本操作设计】
1、运行程序，进入设置迷宫大小界面，输入行和列的值点击生成迷宫按钮
进入迷宫自定义界面，
2、根据操作菜单中的帮助选项，用键盘上的按键进行自定义操作（设置迷
宫的起点、终点和墙）按F9或者操作菜单中的A*算法寻找最短路径
选项即可实现对应的通路。
【模块流程图】
模块划分图:
用户设置迷宫参数：
【界面设计】
迷宫大小设置界面：
主界面：
【用户手册】
2、程序上机调试报告
【语法错误及其排除】
在展现迷宫求解过程中出错，通过MazeGUI内部定义的一个线程类（SolveThread）。该线程根据rollback.isOver()返回的值判断求解迷宫过程是否结束，若没有结束，则不断在求解过程中不断地使线程睡眠200毫秒，可使求解迷宫的过程能清楚地展现给用户，
【算法错误及其排除】
在用回溯法求的通路时出现错误，调用l back（）方法，当curPos周围没有通路时，调用此方法获取栈顶元素中info域，若不空，则将curPos标记为从栈中弹出的点，并弹出栈顶元素，把info域赋给curPos，实现回溯。若为空，则表示栈中没有元素，此时已经回溯到起点，迷宫不存在可通的路径，使求解迷宫线程等待。
3、程序测试结果
【输出结果】
设置迷宫大小：
自定义迷宫设置迷宫起点、终点和墙（人代表起点，门代表终点）
按F9找到通路：
选择菜单操作中的A*算法寻找最短路径找到起点到终点的最短路径：
【程序性能评价】
该程序较好的对自定义的迷宫寻找通路，并且即可实现普通通路又可以用A*算法实现最短路径。
【性能改进方面】
该程序还可以提高系统容错能力，另外还可以添加部分功能，如可随机设置障碍物，或者对走完路径的时间进行记时，增加游戏的趣味性。
【收获及体会】
在这次课程设计的中，从任务书、程序的编写、运行、调试到设计报告，整个过程自己收获了许多，编写程序运行遇到错误时，一次次的修改，使我体会到要坚持有耐心，有毅力，同时通过一些资料的查找和运用使自己的程序运行成功。通过这次实践让我更好的了解到java语言在生活领域中的应用，更多的体会到算法思维的重要性，提高了自己独立思考、动手实践操作的能力。同时也认识到自己在学习中不足的地方，这些都让自己在以后的学习和生活中能更有方向的去提高自己。
4、源程序代码
package maze;
/**
*A*算法点坐标类
*
*/
public class Aposition extends Position{//继承了Position类int f=0,g=0,h=0;
int flag;//标记是否开启
Aposition pre;
public Aposition(int x,int y,Aposition p,int flag){
super(x,y);
this.pre=p;//前驱节点
this.flag=flag;
}
}
package maze;
import java.util.*;
import javax.swing.JOptionPane;
/**
*A*算法实现
*
*/
public class Astar {
Maze maze;
Stack as = new Stack();
Aposition[][] aMap;
Aposition cur;// 当前点
Aposition begin;
Aposition end;
LinkedList
int[][] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//方向数组，右下左上
public Astar(Maze maze) {// 构造方法
this.maze = maze;
aMap = new Aposition[maze.row][maze.col];// 该二维数组的元素都为null
this.begin = new Aposition(maze.begin.x, maze.begin.y, null, 0);//1:close
// ,
//
0:open
this.end= new Aposition(maze.end.x, maze.end.y, null, -1);// -1 is end
aMap[this.begin.y][this.begin.x] = this.begin;
aMap[this.end.y][this.end.x] = this.end;
open.add(this.begin);// 将起点放入关闭列表
}
public void probe(Aposition cur) {// 试探方法
for (int i = 0; i < 4; i++) {
int tx = cur.x + direction[i][0];
int ty = cur.y + direction[i][1];
if (maze.mazeMap[ty][tx] == 0 && this.aMap[ty][tx] == null) {// 是通路，
// 并且还不存在
// ，
// 引用为null
aMap[ty][tx] = new Aposition(tx, ty, cur, 0);// 使引用明确,并开启
setH(aMap[ty][tx]);
setG(aMap[ty][tx]);
setF(aMap[ty][tx]);
open.add(aMap[ty][tx]);// 加入到开启列表中
} else if (aMap[ty][tx] != null) {// 已存在的
if (close.contains(aMap[ty][tx])) {
}// 已在关闭列表中则不处理
else if (aMap[ty][tx].equals(this.end)) {// 若找到终点，将终点加入到关闭列表中
this.end.pre = cur;
close.add(this.end);
} else {
if (aMap[ty][tx].g > cur.g + 1) {// 已在开启列表中，比较是否更优
aMap[ty][tx].pre = cur;
setG(aMap[ty][tx]);
setF(aMap[ty][tx]);
}
}
}
}
sort(); // 将开启列表排序
}
public void sort() {// 根据F值从小到大排序
Aposition temp;
for (int i = 0; i < open.size() - 1; i++) {
for (int j = i + 1; j < open.size(); j++) {
if (open.get(i).f > open.get(j).f) {
temp = open.get(i);
open.set(i, open.get(j));
open.set(j, temp);
}
}
}
}
public void solve() { // 求解
Aposition temp;// 设置回滚对象
while (open.size() != 0) {// 当开启列表不为空时，循环
this.cur = (Aposition) open.poll();// 取开启列表中F值最小的,并从开启列表中删除
close.add(this.cur);// 加入到关闭列表中
this.cur.flag = 1;// 标记为关闭
probe(this.cur);// 探索启发
if (close.contains(this.end)) {
temp = this.end;
while (temp != null) {
as.push(temp);
temp = temp.pre;
}
return;
}
}
JOptionPane.showMessageDialog(null, "Sorry,Path not found!");
return;
}
public void setH(Aposition p) {// 求H值
p.h= Math.abs(this.end.x- p.x) + Math.abs(this.begin.y- p.y);
}
public void setG(Aposition p) {// 求G值
p.g = p.pre.g + 1;
}
public void setF(Aposition p) {// 求F值
p.f = p.g + p.h;
}
}
package maze;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
@SuppressWarnings("serial")
public class Dialog extends JDialog {
private JTextField tf1 = new JTextField("10", 10);
private JTextField tf2 = new JTextField("10", 10);
private JButton b = new JButton("生成迷宫");
public static void main(String srgd[]) {
try {
Thread.sleep(300);
} catch (Exception e) {
e.printStackTrace();
}
new Dialog();
}
public Dialog() {
setTitle("课程设计--求解迷宫");
setLayout(new BorderLayout());
JPanel p = new JPanel(new GridLayout(4, 1));
FlowLayout flowLayout = new FlowLayout();
flowLayout.setAlignment(FlowLayout.LEFT);
flowLayout.setHgap(10);
FlowLayout flowLayout1 = new FlowLayout();
flowLayout1.setAlignment(FlowLayout.RIGHT);
JPanel p1 = new JPanel(flowLayout);
JPanel p2 = new JPanel(flowLayout);
JPanel p3 = new JPanel();
JPanel p4 = new JPanel();
JPanel p5 = new JPanel(flowLayout1);
p1.add(new JLabel(" 行数： "));
p1.add(tf1);
p2.add(new JLabel(" 列数： "));
p2.add(tf2);
p1.setBackground(new Color(226, 244, 255));
p2.setBackground(new Color(226, 244, 255));
p3.setBackground(new Color(226, 244, 255));
p4.setBackground(new Color(226, 244, 255));
p.add(p3);
p.add(p1);
p.add(p2);
p.add(p4);
p5.add(b);
p5.setBackground(new Color(196, 227, 248));
add(new JLabel(new ImageIcon("maze.jpg")), BorderLayout.NORTH);
add(p, BorderLayout.CENTER);
add(p5, BorderLayout.SOUTH);
setSize(345, 250);
setLocation(400, 100);
setVisible(true);
b.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
new MazeGUI(Integer.parseInt(tf1.getText()), Integer
.parseInt(tf2.getText()));
setVisible(false);
}
});
addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
}
}
package maze;
import java.awt.*;
import javax.swing.*;
/**
*迷宫参数
*
*/
public class Maze {
int[][] mazeMap;// 地图数据
Position begin;// 起始坐标
Position end;// 结束坐标
Position drawPos = new Position(1, 1);
Image wallPic = new ImageIcon("wall.jpg").getImage();
Image roadPic = new ImageIcon("road.jpg").getImage();
Image a = new ImageIcon("a.jpg").getImage();
Image goPic = new ImageIcon("go.jpg").getImage();
Image endPic = new ImageIcon("end.jpg").getImage();
Image beginPic = new ImageIcon("begin.jpg").getImage();
int row = 0, col = 0;
public Maze(int row, int col) {
this.row = row;
this.col = col;
mazeMap = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || j == 0 || j == col - 1 || i == row - 1) {// 迷宫最外层设为墙
this.mazeMap[i][j] = 1;
} else {
this.mazeMap[i][j] = 0;
}
}
}
}
public Maze() {
}
public void mark(Position p, int m) {// 标记位置已走过
this.mazeMap[p.y][p.x] = m;
}
public void draw(Graphics g) {// 绘制地图图片
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (begin != null && i == begin.y && j == begin.x) {// 起点
g.drawImage(beginPic, j * 50, 24 + i * 50, 50, 50, null);
} else if (end != null && i == end.y && j == end.x) {// 终点
g.drawImage(endPic, j * 50, 24 + i * 50, 50, 50, null);
} else if (this.mazeMap[i][j] == 1) {// 墙壁
g.drawImage(wallPic, j * 50, 24 + i * 50, 50, 50, null);
} else if (this.mazeMap[i][j] == 2) {// 已走过的路径
g.drawImage(goPic, j * 50, 24 + i * 50, 50, 50, null);
} else if (this.mazeMap[i][j] == 3) {// 已走过的路径，消除脚印
g.drawImage(roadPic, j * 50, 24 + i * 50, 50, 50, null);
} else if (this.mazeMap[i][j] == 5) {// A*方法路径
g.drawImage(a, j * 50, 24 + i * 50, 50, 50, null);
} else {// 通道
g.drawImage(roadPic, j * 50, 24 + i * 50, 50, 50, null);
}
}
}
g.drawRect(drawPos.x * 50, 24 + drawPos.y * 50, 50, 50);
}
public void resume() {// 恢复迷宫
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(this.mazeMap[i][j] == 2 || this.mazeMap[i][j] == 3) { this.mazeMap[i][j] = 0;
}
}
}
}
public void setEnd(int x, int y) {
end = new Position(x, y);
}
public void setBegin(int x, int y) {
begin = new Position(x, y);
}
}
package maze;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
/**
*迷宫图形界面
*
*/
@SuppressWarnings("serial")
public class MazeGUI extends Frame implements KeyListener, ActionListener {// 迷宫GUI
final Object obj = new Object();// 锁对象
int row = 0, col = 0;
Image offScreen = null;
Maze maze;// 构建迷宫参数
Rollback rollback;
Astar astar;
Thread t1 = new Thread(new SolveThread(), "SolveThread");//寻路进程，在初始化Thread类时
// ，
// 把目标对象传
递给这个线程实例
Thread t2 = new Thread(new AThread(), "AThread");
public void paint(Graphics g) {// 调用绘制地图的draw()方法和绘制人物位置的draw()方法
maze.draw(g);
rollback.draw(g);
}
public void update(Graphics g) {// 双缓冲防止屏幕闪烁
if (offScreen == null) {
offScreen = this.createImage(col * 50, row * 50);
}
Graphics offg = offScreen.getGraphics();
Color c = offg.getColor();
offg.setColor(Color.BLUE);
offg.fillRect(0, 0, col * 50, row * 50);
offg.setColor(c);
paint(offg);
g.drawImage(offScreen, 0, 0, null);
}
public MazeGUI() {
}
public MazeGUI(int row, int col) {// 初始化窗体
this.setTitle("算法课程设计-求解迷宫问题");
this.setSize(col * 50, row * 50);
this.setLocation(200, 80);
this.setResizable(false);
this.addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
this.row = row;
this.col = col;
maze = new Maze(row, col);// 构建迷宫参数
rollback = new Rollback(maze, this);
this.setVisible(true);
MenuBar menuBar = new MenuBar();
Menu fileMenu = new Menu("文件");
Menu settingMenu = new Menu("操作");
MenuItem exitItem = new MenuItem("退出");
MenuItem mapItem = new MenuItem("刷新地图");
MenuItem aItem = new MenuItem("A*算法寻找最短路径");
MenuItem helpItem = new MenuItem("帮助");
fileMenu.add(exitItem);
settingMenu.add(mapItem);
settingMenu.add(aItem);
settingMenu.add(helpItem);
menuBar.add(fileMenu);
menuBar.add(settingMenu);
setMenuBar(menuBar);
addKeyListener(this);
exitItem.addActionListener(this);
mapItem.addActionListener(this);
aItem.addActionListener(this);
helpItem.addActionListener(this);
}
private class SolveThread implements Runnable {// 提供一个实现借口Runnable接口的类的实例，
// 作为一个线程的目标对象public void run() {
while (!rollback.isOver()) {// 寻路结束后，线程结束
synchronized (obj) {
try {
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
if (!rollback.forward()) {
rollback.back();
}
repaint();
}
}
}
}
private class AThread implements Runnable {// 展示用A*算法求解迷宫过程的线程
public void run() {
while (!astar.as.isEmpty()) {
synchronized (obj) {
try {
Thread.sleep(200);
} catch (InterruptedException e) {
e.printStackTrace();
}
Aposition temp = (Aposition) astar.as.top();
astar.as.pop();
maze.mazeMap[temp.y][temp.x] = 5;
rollback.curPos.x = temp.x;
rollback.curPos.y = temp.y;
}
repaint();
if (astar.as.isEmpty())
JOptionPane.showMessageDialog(null, "找到最短路径最短路径！");
}
}
}
public void keyTyped(KeyEvent e) {
}
public void keyReleased(KeyEvent e) {
}
public void keyPressed(KeyEvent e) {
if (e.getKeyCode() == KeyEvent.VK_DELETE) {
maze.mark(maze.drawPos, 0);
} else if (e.getKeyCode() == KeyEvent.VK_ENTER) {
maze.mark(maze.drawPos, 1);
} else if (e.getKeyCode() == KeyEvent.VK_F9) {
if (maze.begin == null) {
JOptionPane.showMessageDialog(null, "起点没有设置");
} else if (maze.end == null) {
JOptionPane.showMessageDialog(null, "终点没有设置");
} else if (t1.getState().equals(Thread.State.NEW)) {// 当没有线程处于运行态时
t1.start();// 启动寻路线程
System.out.print("new");
} else if(t1.getState().equals(Thread.State.TERMINATED)) {// 当该线程处于终止态时
// ，
// 又点击了F9
// ，
// 即重新演示
t1 = new Thread(new SolveThread(), "SolveThread");// 新建线程
rollback.flush();// 刷新
maze.resume();// 恢复迷宫到初始状态
t1.start();
} else {// 在寻路过程中，如果点击了“F9”按键
System.out.print("repeat");
rollback.flush();// 清空栈，并把sprite中的curPos对象恢复到初试位置
maze.resume();// 恢复迷宫到初始状态
repaint();
}
} else if (e.getKeyCode() == KeyEvent.VK_DOWN) {
if (maze.drawPos.y + 1 > 0 && maze.drawPos.y + 1 < row - 1)// 禁止定位方框移动到最外围的
// “墙”上
maze.drawPos.y = maze.drawPos.y + 1;
} else if (e.getKeyCode() == KeyEvent.VK_UP) {
if (maze.drawPos.y - 1 > 0 && maze.drawPos.y - 1 < row - 1) maze.drawPos.y = maze.drawPos.y - 1;
} else if (e.getKeyCode() == KeyEvent.VK_RIGHT) {
if (maze.drawPos.x + 1 > 0 && maze.drawPos.x + 1 < col - 1) maze.drawPos.x = maze.drawPos.x + 1;
} else if (e.getKeyCode() == KeyEvent.VK_LEFT) {
if (maze.drawPos.x - 1 > 0 && maze.drawPos.x - 1 < col - 1) maze.drawPos.x = maze.drawPos.x - 1;
} else if (e.getKeyCode() == KeyEvent.VK_END) {
maze.setEnd(maze.drawPos.x, maze.drawPos.y);
} else if (e.getKeyCode() == KeyEvent.VK_HOME) {
maze.setBegin(maze.drawPos.x, maze.drawPos.y);// 起点坐标
rollback.setCurPos(maze.drawPos.x, maze.drawPos.y);// 设置回溯算法中的当前点
rollback.remember(rollback.curPos);
}
repaint();
}
《算法设计与分析》期中试卷 一、叙述分治算法的基本思想及一般算法设计模式； 二、叙述动态规划算法的基本步骤及动态规划算法的基本 要素； 三、改进课本P74的Lcs算法，使改进算法不用数组b亦 可在O（m+n）的时间内构造最长公共序列； 四、求下列函数的渐近表达式 (1). 3n2+10n (2).n2/10+2n (3)21+1/n (4)logn3 (5)10log3n 五、对于下列各组函数发f（n）和g（n），确定f（n）=O(（g(n)）) 或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由 (1). f（n）=logn2 , g(n)=logn+5; (2). f（n）=logn2 , g(n)= √n; (3), f（n）=n, g(n)= logn2; (4). f（n）=nlogn+n,g(n)=logn; (5). f（n）=10.g(n)=log10; (6). f（n）=log2n g(n)=logn (7). f（n）=2n g(n)= 3n; (8). f（n）=2n g(n)= 100n2;
六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当 搜索元素x不再数组中时，返回小于x的最大元素位置i和大于x 的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x 在数组中的位置 七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。 试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。 八、在一个由元素组成的表中出现次数最多的元素称为众数。试写 一个寻找众数的算法，并分析其计算复杂性。 九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长 单调递增子序列。 十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价 值为v i ，背包的容量为C，容积为D。问：应该如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i。 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。
第一章算法概述 1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。 2.算法的性质： 1)输入：有零个或多个输入 2)输出：有至少一个输出 3)确定性：每条指令是清晰的、无歧义的 4)有限性：每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复 杂性，需要空间资源的量称为空间复杂性 2)三种时间复杂性：最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念：直接或间接调用自身的算法 2.递归函数：用函数自身给出定义的函数 3.递归要素：边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout< HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 1.设计模式的原理? (C) C. 面向接口编程 2. 以下对"开-闭"原则的一些描述错误的是?(A) A. "开-闭"原则与"对可变性的封装原则"没有相似性. 3.以下属于创建型模式是? (A) B.BUILDER（生成器） C. PROTOTYPE（原型） D.SINGLETON（单件） 4.以下属于结构型模式是? (D) COMPOSITE（组合） B. ADAPTER（适配器） B.FLYWEIGHT（享元） 5.以下属于行为型模式是? (D ) 6. COMMAND（命令） 7. STRATEGY(策略) 8. MEMENTO（备忘录） /*23模式意图*/ 6.以下意图那个是用来描述ABSTRACT FACTORY（抽象工厂)?(A) A.提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。 7.以下意图那个是用来描述BUILDER（生成器）?(B) 将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。 8.以下意图那个是用来描述FACTORY METHOD（工厂方法）?(C) C.定义一个用于创建对象的接口，让子类决定实例化哪一个类。该模式使一个类的实例化延迟到其子类。 9.以下意图那个是用来描述PROTOTYPE（原型）?(D) D.用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象。 10.以下意图那个是用来描述SINGLETON（单件）?(B) B.保证一个类仅有一个实例，并提供一个访问它的全局访问点。 11.以下意图那个是用来描述ADAPTER（适配器）?(A) A.将一个类的接口转换成客户希望的另外一个接口。本模式使得原本由于接口不兼容 而不能一起工作的那些类可以一起工作。 12.以下意图那个是用来描述BRIDGE（桥接）?(B) B.将抽象部分与它的实现部分分离，使它们都可以独立地变化。 13.以下意图那个是用来描述COMPOSITE（组合）?(C) C.将对象组合成树形结构以表示“部分-整体”的层次结构。 14.以下意图那个是用来描述DECORATOR（装饰）?(D) 动态地给一个对象添加一些额外的职责。 15.以下意图那个是用来描述FACADE（外观）?(A) A.为子系统中的一组接口提供一个一致的界面，本模式定义了一个高层接口，这个接 口使得这一子系统更加容易使用。 16.以下意图那个是用来描述FLYWEIGHT（享元）?(B) B.运用共享技术有效地支持大量细粒度的对象。 17.以下意图那个是用来描述PROXY（代理）?(C) C.为其他对象提供一种代理以控制对这个对象的访问。 18.以下意图那个是用来描述CHAIN OF RESPONSIBILITY(职责链)?(D) D.使多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合关系。 19.以下意图那个是用来描述COMMAND（命令）?(A) A.将一个请求封装为一个对象，从而使你可用不同的请求对客户进行参数化；对请求排队或记录请求日志，以及支持可撤消的操作 20.以下意图那个是用来描述INTERPRETER(解释器)?(B) B.给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。 21.以下意图那个是用来描述ITERATOR(迭代器)?(C) 。 C.提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。 1.1.采用的方法和技术路线1.1.1.项目技术路线描述 “开发设计平台”使整个项目技术架构上更加合理，更容易获得长期的进步和发展。 本项目的主要技术路线如下： 采用Java语言开发，符合J2EE规范； 应用服务器支持各种主流应用服务器，包括BEA Weblogic、IBM Webphere、Tomcat 等； 数据交换和配置采用XML技术； 数据库支持各种主流数据库，包括Oracle、SqlServer、Sybase、MySql等； 由于采用Java技术，服务器操作系统支持各种主流操作系统平台，如Windows、Linux、Unix等； 客户端支持Windows操作系统的IE6以上浏览器； 开发工具主要采用Eclipse。 1.1. 2.采用B/S多层结构 该项目基于J2EE技术平台，采用XML数据总线技术、MVC设计模式和SOA框架，将各种服务包装为松散耦合的模块，通过在XML数据包中加入标签数据（元数据）的方法实现了调用接口的弹性，从而面向最终用户和开发商提供了一个随需应变的企业级应用和开发设计平台。 在技术路线上，采用组件化技术和基于BROWER/APPSERVER/DBSERVER的三层应用架构模型，以B/S方式实现。数据外部数据交换通过数据共享与交换平台，实现数据的可靠、稳定、及时的交换，各个应用终端采用客户端浏览器的方式根据不同权限进行数据的查询、增加等操作。 整个系统采用B/S多层体系结构，在体系结构中，客户（请求信息）、程序（处理请 求）和数据（被操作）被隔离。多层结构是个更灵活的体系结构，它把显示逻辑从业务逻辑中分离出来，这就意味着业务代码是独立的，可以不关心怎样显示和在哪里显示。业务逻辑层处于中间层，不需要关心由哪种类型的客户来显示数据，也可以与后端系统保持相对独立性，有利于系统扩展。多层结构中安全性也更易于实现，因为应用程序已经同客户隔离。 在一个多层次系统中，每一级都支持应用程序的一个独立部分。应用客户机完成描述逻辑，应用服务器完成业务处理逻辑。在一个事务处理过程中，每一个客户机只向应用服务器发出一个请求，这就大大减少了网络通讯和竞争。每个应用程序的业务逻辑是由该应用程序的所有用户共享的，这样就能更好地控制业务处理，同时当修订业务处理而产生变化时，能极大地简化变化的实现。数据服务器负责管理和优化同时并发的数据存取。 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 专业： 班级： 学号： 姓名： 日期： 2014年 11月 10日 48476Λn n 111+++=。 2、q(n ，m)=q(n ，n)，m>=n 。 最大加数n1实际上不能大于n ，因此，q(1，m)=1。 3、q(n ，n)=1+q(n ，n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ，m)= q(n ，m-1)+q(n-m ，m)，n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 （2）、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日 题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 Ex.1(p20)若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？ 解：若将y ←uniform(0, 1) 改为 y ←x，此时有 ，则k++，即 ，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。 Ex.2(p23) 在机器上用 估计π值，给出不同的n值及精度。 解：由ppt上p21可知，的大小 ，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← uniform(0, 1)，y ← uniform(0, 1)。 计算的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为： 结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道= k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。 代码的主要部分为： 运行结果为： 结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则 。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则 。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。 解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下： 公路路线设计方法与设计内容 一、有关资料 （一）设计资料 1．某地区1：2000或1：1000地形图一张； 2．交通量； 3．该地区地质、水文、气候、植被情况； 4．路线起终点位置。 （二）设计依据 1．《公路工程技术标准》（JTJ001—97）。 2．《公路路线设计规范》（JTJ011—94）。 3．《公路路基设计规范》（JTJ013—95）。 二、设计方法与设计内容 （一）公路技术等级的确定 根据所给资料，参照《公路工程技术标准》（以下简称《标准》）、《公路路线设计规范》（以下简称《路线规范》）确定路线的等级。 （二）公路技术标准的确定 根据已确定的公路技术等级，按《标准》、《规范》规定，确定公路的技术标准，及各项指标。 （三）公路的平面设计 1．纸上定线 1）路线布局 根据已确定的公路等级及技术标准，由课程设计指导教师，指导学生在地形图上确定出路线的各转角点，从而确定出路线导线的位置。 2）线形设计 按照地形图上已确定的转角点 （1）用正切法求出各转角点处的转角值，并确定出左偏或右偏。 （2）按地形图比例测量计算出交点间的距离。 （3）根据技术标准和交点间距，初步确定布线类型，如单曲线、同向曲线或同向复曲线、反向曲线或反向复曲线等。 ①同向曲线间尽量避免插入短直线，插入时，其最小长度不小于6V（V≧60km/h）。 ②反向曲线间最小直线长度不小于2V（V≧60km/h）。 ③V≦40km/h时，可参照①和②执行。 （4）据转角а、交点间距离，并结合交点处地形情况，确定合适的曲线半径R和曲线长 度，计算曲线要素。切线长T h、曲线长L h外距E h和超距J h，并推算主点桩号。 （5）沿着已经布好的公路中线，从路线起点开始，按整桩号法排桩，将起点桩号 （K0+000）、百米桩、公里桩、曲线主点桩、终点桩及各相应整桩号桩布设，标定在公路中线上。 3)计算超高与加宽 参照《标准》与《规范》以及教材中的公式列表计算加宽值，确定旋转轴，列表计算超高值。 2．填写“直线、曲线及转角一览表” 第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题（有确定的输入数据）依次执行一个正确的算法中的各操作步骤，最终将得到该问题的解（正确的输出数据）。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上：数值型算法:算法中的基本运算为算术运算；非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上：串行算法:串行计算机上执行的算法；并行算法:并行计算机上执行的算法 算法的五个重要的特性 （1） 有穷性：在有穷步之后结束。 （2） 确定性：无二义性。 （3） 可行性：可通过基本运算有限次执行来实现。 （4） 有输入 表示存在数据处理 （5） 有输出 伪代码 程序设计语言（PDL ），也称为结构化英语或者伪代码，它是一种混合语言，它采用一种语言（例如英语）的词汇同时采用类似另外一种语言（例如，结构化程序语言）的语法。 特点：1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征； 2)以自然语言的自由语法描述了处理过程；3)数据声明应该既包括简单的也包括复杂的数据结构；4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下，分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==）)O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值，比较，算术运算，逻辑运算，读写单个变量（常量）只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；...； am: sm 需要的时间为 max （TS1,TS2 ,..., TSm ）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句：对非递归调用，根据调用层次由里向外用规则1-7进行分析； 对递归调用，可建立关于T(n)的递归方程,求解该方程得到T(n). 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 高二信息技术选修模块〈算法与程序设计〉 学分认定考试试题 班级学号姓名 一、单选题（每题3分，共42分） 1.一位爱好程序设计的同学想编写程序解决“鸡兔同笼”问题，他制定的如下工作过程中，更恰当的是（） A、设计算法，编写程序，分析问题，调试运行程序，检测结果。 B、分析问题，编写程序，设计算法，调试运行程序，检测结果。 C、分析问题，设计算法，编写程序，调试运行程序，检测结果。 D、设计算法，分析问题，编写程序，调试运行程序，检测结果。 2.在编制计算机程序解决问题的过程中，对算法描述正确的是（） A、算法是用计算机求解某一问题的方法，是解决问题的有序步骤。 B、算法必须在计算机上用某种语言实现。 C、一个问题对应的算法都只有一种。 D、常见的算法描述方法有自然语言法、流程图法、程序法。 3、要使循环体至少执行一次，应使用循环。 A、Do While条件 B、Do Until 条件 循环体循环体 Loop Loop C、For 初值to条件 D、do 循环体循环体 Next Loop Until 条件 4.小明对《算法与程序设计》情有独钟，下面是他编写的一段程序，请问他是采用了哪种程序语言设计和编写的？（） private sub command1_click( ) I=1 Do If I mod 3 then print I I=I+1 Loop while I<=100 End sub A、机器语言 B、Visual Basic语言 C、Basic语言 D、汇编语言 5.结构化程序设计由三种基本结构组成，下面哪个不属于这三种基本结构？（） A、顺序结构 B、输入、输出结构 C、选择结构 D、循环结构 五大常用算法之一：分治算法 分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 二、基本思想及策略 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1 XXXX大学 算法设计与分析课程设计报告 院（系）： 年级： 姓名： 专业：计算机科学与技术 研究方向：互联网与网络技术 指导教师： XXXX 大学 目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27) 题目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 二十三种设计模式的通俗理解 1、FACTORY 追MM少不了请吃饭了，麦当劳的鸡翅和肯德基的鸡翅都是MM爱吃的东西，虽然口味有所不同，但不管你带MM去麦当劳或肯德基，只管向服务员说“来四个鸡翅”就行了。麦当劳和肯德基就是生产鸡翅的Factory 工厂模式：客户类和工厂类分开。消费者任何时候需要某种产品，只需向工厂请求即可。消费者无须修改就可以接纳新产品。缺点是当产品修改时，工厂类也要做相应的修改。如：如何创建及如何向客户端提供。 2、BUILDER MM最爱听的就是“我爱你”这句话了，见到不同地方的MM,要能够用她们的方言跟她说这句话哦，我有一个多种语言翻译机，上面每种语言都有一个按键，见到MM我只要按对应的键，它就能够用相应的语言说出“我爱你”这句话了，国外的MM也可以轻松搞掂，这就是我的“我爱你”builder。（这一定比美军在伊拉克用的翻译机好卖）建造模式：将产品的内部表象和产品的生成过程分割开来，从而使一个建造过程生成具有不同的内部表象的产品对象。建造模式使得产品内部表象可以独立的变化，客户不必知道产品内部组成的细节。建造模式可以强制实行一种分步骤进行的建造过程。 3、FACTORY METHOD 请MM去麦当劳吃汉堡，不同的MM有不同的口味，要每个都记住是一件烦人的事情，我一般采用Factory Method模式，带着MM到服务员那儿，说“要一个汉堡”，具体要什么样的汉堡呢，让MM直接跟服务员说就行了。工厂方法模式：核心工厂类不再负责所有产品的创建，而是将具体创建的工作交给子类去做，成为一个抽象工厂角色，仅负责给出具体工厂类必须实现的接口，而不接触哪一个产品类应当被实例化这种细节。 4、PROTOTYPE 跟MM用QQ聊天，一定要说些深情的话语了，我搜集了好多肉麻的情话，需要时只要copy出来放到QQ里面就行了，这就是我的情话prototype了。（100块钱一份，你要不要）原始模型模式：通过给出一个原型对象来指明所要创建的对象的类型，然后用复制这个原型对象的方法创建出更多同类型的对象。原始模型模式允许动态的增加或减少产品类，产品类不需要非得有任何事先确定的等级结构，原始模型模式适用于任何的等级结构。缺点是每一个类都必须配备一个克隆方法。 5、SINGLETON 俺有6个漂亮的老婆，她们的老公都是我，我就是我们家里的老公Sigleton，她们只要说道“老公”， 《算法分析与设计》2020年03月考试考前练习题 一、简答题 附：参考答案 1. 何谓P、NP、NPC问题。 解答: P（Polynomial问题）：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 NPC（NP Complete）问题，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。 2. 动态规划算法的基本思想是什么？它和分治法有什么区别和联系？ 解答: 动态规划算法的基本思想为：该方法的思路也是将待求解的大问题分成规模较小的子问题，但所得的各子问题之间有重复子问题，为了避免子问题的重复计算，可依自底向上的方式计算最优值，并根据子问题的最优值合并得到更大问题的最优值，进而可构造出所求问题的最优解。 分治法也是将待求解的大问题分成若干个规模较小的相同子问题，即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；利用该问题分解出的子问题的解可以合并为该问题的解。 3. 贪心算法和动态规划算法都要求问题具有共同的性质是？ 解答: 最优子结构性质。 4. 为什么用分治法设计的算法一般有递归调用？ 解答: 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 5. 简述分治法所能解决的问题一般应具有的特征。 解答: 1）该问题的规模缩小到一定的程度就可以容易地解决； 2）该问题具有最优子结构性质； 3）利用该问题分解出的子问题的解可以合并为该问题的解； 4）该问题所分解出的各个子问题是相互独立的。 6. 在回溯法中，为了避免无效的搜索，通常采用哪两种剪枝策略？ 解答: 约束剪枝，限界剪枝。 7. 给定如下二分搜索算法，请分析算法的复杂性。 int BinarySearch(Type a[], const Type& x, int l, int r){ while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } 算法设计技术 常用技术 分治法（Divide and Conquer） 贪心法（Greedy） 动态规划法（Dynamic programming） 回溯法（Backtracking） 分枝界限法（Branch and Bound） 局部搜索法 (Local search algorithms） 一、分治法 定义：对于一个输入大小为n的函数或问题，用某种方法把输入分划成k个子集。（１< k ≤ n）。从而产生L个子问题，解出这L个子问题后再用某种方法把它们组合成原来的解。如子问题相当的大，则递归使用分治法。 时间复杂度 T(n) g(n) n足够小 T(n)= 2T(n/2)+f(n). 其它 g(n) n很小时，直接计算时间。 f(n) 分成二个子问题解后的整合时间。 例1.1 求一个集合中的最大元素和最小元素。 Procedure maxmin(s); 1.if |s|=2 2.then begin 设|s|={c,d}; 3. (a,b)←(MAX（c,d),MIN(c,d)). end else begin 4.把S分成二个子集S1，S2，各存一半元素； 5. (maxl, minl) ←maxmin(S1 ); 6. (max2, min2) ←maxmin(S2 ); 7.（a,b）← (MAX(max1,max2), MIN(min1,min2)) end 例：1.2 找第k个最小元素。 一般先分类为递减序列，得到第k个最小元素，要O (nlogn). 分治法可以O (n)内得到第k个最小元素。当k=[n/2]时，成为在线性时间内找一个序列的中值问题。 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)；算法设计与分析课程设计(完整版)
设计模式题库(修改后)
采用的方法和技术路线
算法设计与分析学习总结
算法分析与设计
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
算法设计与分析
公路路线设计方法与详细步骤
算法分析与设计
算法分析与设计习题集整理
算法设计试题
五大常用算法
算法分析与设计-课程设计报告
二十三种设计模式的通俗理解
算法分析与设计
算法设计技术
算法设计与分析(详细解析(含源代码)
相关主题
文本预览