资源描述：
《算法导论_士兵站队课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、课程设计报告课程名称算法导论课题名称士兵站队问题专业信息与计算科学班级信科1002班学号023202180222姓名阳丹简琵珍李志良指导教师阳卫锋2012年12月7日13湖南工程学院课程设计任务书课程名称算法导论课题士兵战队问题专业班级信科1002班学生姓名阳丹简琵珍李志良学号023202180222指导老师阳卫锋审批任务书下达日期2012年11月26日任务完成日期2012年12月7日13一、设计内容与设计要求1．设计内容：对课程《算法导论》中的常用算法进行综合设计或应用（具体课题题目见后面的供选题目）。2．设计要求：l课程设计报告正文内容(
2、一)问题的描述；(二)算法设计与分析，内容包括1，算法设计，对问题的分析和算法的设计2，算法描述，以伪代码形式的算法3，算法分析，主要是算法的正确性和运行时间的分析（三）算法实现所有程序的原代码，要求用C语言程序实现，并对程序写出必要的注释。l书写格式a．要求用A4纸打印成册b．正文格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。c．正文的内容:正文总字数要求在3000字左右（不含程序原代码）。d．封面格式如下页。l考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等
3、进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：a．平时出勤（占10%）b．系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）c．程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）d．设计报告（占30%）13e．独立完成情况（占10%）。注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。l课程验收要求a．判定算法设计的合理性，运行相关程序，获得正确的数值结果。b．回答有关问题。c．提交课程设计报告。d．提交软盘（源程序、设计报告
4、文档）。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分13目录一、任务书……………………………………………………1二、问题描述…………………………………………………5三、算法设计与分析…………………………………………6四、程序调试…………………………………………………7五、附件………
5、………………………………………………8六、评分表……………………………………………………1313三、问题描述在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一列。编程任务计算使所有士兵排成一行需要的最少移动步数。数据输入由文件sol*.in提供输入数据。文件的第1行是
6、士兵数n，1£n£10000。接下来n行是士兵的初始位置，每行2个整数x和y，-10000£x，y£10000。结果输出程序运行结束时，将计算结果输出到文件sol*.out中。文件的第1行中的数是士兵排成一行需要的最少移动步数。输入文件示例输出文件示例sol0.insol0.out51222133-233813四、算法设计与分析算法设计士兵站队问题是一个排序问题，问题描述为：网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成
7、(x,y),(x+1,y),…,(x+n-1,y)。求需要移动的最少步数。首先用两个一维数组a[n],b[n]分别表示n个士兵的x,y坐标,再把表示士兵的y轴坐标的数组用选择排序从小到大排序，找出中位数b[(n-1)/2],(这里减一是因为数组的下标是从0开始的)以此确定士兵的y轴坐标，然后再构造一个新的一维数组c[n],c[i]=a[i]-i,(这样就可以错开相同的x轴也可以减少士兵之间间距，找出合适的中位数。)再把数组c[n]用选择排序从小到大排序，找出中位数c[(n-1)/2]以此确定第一个士兵的x轴坐标，第二个士兵的x轴坐标为c[(n
8、-1)/2]+1,依次类推第n个士兵的x轴坐标为c[(n-1)/2]+(n-1)。最后再计算这些士兵移动的步数和得到移动的最少步数。算法描述选择排序for(inti
