算法导论士兵站队课程设计.docVIP

课 程 设 计 报 告课程名称 算法导论 课题名称 士兵站队问题 专 业 信息与计算科学 班 级 信科1002班 学 号 0232 0218 0222 姓 名 阳丹 简琵珍 李志良 指导教师 阳卫锋 2012年 12 月 7 日湖 南 工 程 学 院课 程 设 计 任 务 书课程名称 算法导论 课 题 士兵战队问题 专业班级 信科1002班 学生姓名 阳丹 简琵珍 李志良 学 号 0232 0218 0222 指导老师 阳卫锋 审 批 任务书下达日期 2012 年 11 月 26 日任务完成日期 2012 年 12 月 7日 一、设计内容与设计要求1设计内容： 对课程算法导论中的常用算法进行综合设计或应用（具体课题题目见后面的供选题目）。2设计要求：l 课程设计报告正文内容(一)问题的描述；(二)算法设计与分析，内容包括1， 算法设计，对问题的分析和算法的设计2，算法描述，以伪代码形式的算法3，算法分析，主要是算法的正确性和运行时间的分析（三）算法实现所有程序的原代码，要求用C语言程序实现，并对程序写出必要的注释。l 书写格式a要求用A4纸打印成册b正文格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。c正文的内容:正文总字数要求在3000字左右（不含程序原代码）。d封面格式如下页。l 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：a平时出勤 （占10%）b系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）c程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）d设计报告（占30%）e独立完成情况（占10%）。注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。l 课程验收要求a判定算法设计的合理性，运行相关程序，获得正确的数值结果。b回答有关问题。c提交课程设计报告。d提交软盘（源程序、设计报告文档）。e依内容的创新程度，完善程序情况及对程序讲解情况打分。3、进度安排1、 班级： 信息与计算科学：1001,1002,1003，2、 主讲教师：阳卫锋3、 时间安排：第 16 周 星期一 8时：30分11时：30分 星期二 8时：30分11时：30分 星期四 8时：30分11时：30分 星期五 8时：30分11时：30分 目录一、任务书1二、问题描述5三、算法设计与分析6四、程序调试7五、附件8六、评分表13三、问题描述 在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。编程任务 计算使所有士兵排成一行需要的最少移动步数。数据输入 由文件sol*.in提供输入数据。文件的第1行是士兵数n，1n10000。接下来n行是士兵的初始位置，每行2个整数x和y，-10000x，y10000。结果输出程序运行结束时，将计算结果输出到文件sol*.out中。文件的第1行中的数是士兵排成一行需要的最少移动步数。输入文件示例输出文件示例sol0.insol0.out51 22 21 33 -23 38四、算法设计与分析算法设计 士兵站队问题是一个排序问题，问题描述为：网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),(x+n-1,y)。求需要移动的最少步数。 首先用两个一维数组an,bn分别表示n个士兵的x,y坐标,再把表示士兵的y轴坐标的数组用选择排序从小到大排序，找出中位数b(n-1)/2,(这里减一是因为数组的下标是从0开始的)以此确定士兵的y轴坐标，然后再构造一个新的一维数组cn,ci=ai-i,(这样就可以错开相同的x轴也可以减少士兵之间间距，找出合适的中位数。)再把数组cn用选择排序从小到大排序，找出中位数c(n-1)/2以此确定第一个士兵的x轴坐标，第二个士兵的x轴坐标为c(n-1)/2+1,依次类推第n个士兵的x轴坐标为c(n-1)/2+(n-1)。最后再计算这些士兵移动的步数和得到移动的最少步数。算法描述 选择排序 for(int i=0;ia.length;i+) for(int j=i+1;j=aj) int temp = 0; temp = ai; ai = aj; aj = temp; 找中位数 for(int i=0;ia.length;i+) ci = ai-i; selectSort(c); if(n%2=0) mid_a = c(n-1)/2; mid_b = b(n-1)/2; else mid_a = cn/2; mid_b = bn/2; for(int i = 0;in;i+) sum = Math.abs( bi - mid_b ) +Math.abs( ai - mid_a -i) + sum; System.out.println(需要移动的最少步数是+sum+步);算法分析时间复杂度分析：首先使用选择排序对一维数组a,b,c排序，由于选择排序是一个嵌套循环主循环for i= 0.n-1子循环for j=1.n-1所以选择排序的时间复杂度为O(n2-n)因为要遍历三个数组并对其排大小所以时间复杂度变为O(3n2-3n)，数组c是遍历数组a得到的所以此时时间复杂又变为O(3n2-2n)最后我们要同时遍历数组a和数组b以求出士兵移动后的坐标和士兵需要移动的最少步数。所以最后得到的时间复杂度为O（3n2-n）。五、程序调试 初始化窗口 运行后窗口六、附件源程序 import java.awt.Button;import java.awt.Frame;import java.awt.TextArea;import java.awt.TextField;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.Box;import javax.swing.JFrame;public class TheSoldierCorps extends JFramepublic static void main(String args) launchFrame();public static void launchFrame()Frame f = new JFrame(士兵站队);f.setBounds(350, 150, 450, 300);Box vertical = Box.createVerticalBox();final TextField tf1 = new TextField(50);final TextField tf2 = new TextField(50);final TextField tf3 = new TextField(50);/设置输入的文本长度 这里 int 指列数Button button = new Button(排序);/设置一个按钮final TextArea ta = new TextArea(); /构造一个新字符串作为新文本的文本区/水平布局添加一个文本区 和一个按钮vertical.add(tf1);vertical.add(tf2);vertical.add(tf3);vertical.add(button);vertical.add(ta);/窗口添加一个水平文本区和一个按钮f.add(vertical);/在窗口上添加一个垂直文本区tf1.setText(请输入一个整数表示士兵的个数);tf2.setText(请输入输入士兵的X轴坐标，以空格隔开);tf3.setText(请输入士兵的Y轴坐标，以空格隔开);button.addActionListener(new ActionListener() public void actionPerformed(ActionEvent e) int n = 0; String sum ; String str1 = tf1.getText(); String str2 = tf2.getText(); String str3 = tf3.getText(); int m = new TheSoldierCorps().getArr(str1); int a = new TheSoldierCorps().getArr(str2); int b = new TheSoldierCorps().getArr(str3); if(m.length!=1 | m0!=a.length | a.length!=b.length) tf1.setText(输入有误，请重新输入); tf2.setText(请输入输入士兵的X轴坐标数与士兵数不符，请重新输入，以空格隔开); tf3.setText(请输入士兵的Y轴坐标数与士兵数不符，请重新输入，以空格隔开); try Thread.sleep(10000); catch (InterruptedException e1) e1.printStackTrace();System.exit(-1); else n = m0; int c = new inta.length; Crops crops = new Crops(); crops.selectSort(a); crops.selectSort(b); String str = 需要移动的最少步数是 +crops.standInLine(a, b, c, n); ta.setText(str);); f.setVisible(true);public int getArr(String str)String strArr = str.split( );int a = new intstrArr.length;for(int i = 0;ia.length;i+)ai = Integer.valueOf(strArri);return a;class Cropsprivate int a;private int b;private int c;private int n;int sum = 0; String str2;/将数组排序 public int selectSort(int a) for(int i=0;ia.length;i+) for(int j=i+1;j=aj) int temp = 0; temp = ai; ai = aj; aj = temp; return a; /士兵战队，先找出中位数 public String standInLine(int a,int b,int c,int n) int mid_a = 0; int mid_b = 0; for(int i=0;ia.length;i+) ci = ai-i; selectSort(c); if(n%2=0) mid_a = c(n-1)/2; mid_b = b(n-1)/2; else mid_a = cn/2; mid_b = bn/2; StringBuilder sb = new StringBuilder(); for(int i = 0;in;i+