1、 课 程 设 计 报 告 课程名称课程名称 算法导论算法导论 课题名称课题名称 士兵站队问题士兵站队问题 专专 业业 信息与计算科学信息与计算科学 班班 级级 学学 号号 姓姓 名名 指导教师指导教师 2012 年年 12 月月 7 日日 1 一 、 设计 内容与设计要 求一 、 设计 内容与设计要 求 1 1设计内容：设计内容： 对课程算法导论中的常用算法进行综合设计或应用（具体课题 题目见后面的供选题目） 。 2 2设计要求：设计要求： 课程设计报告正文内容课程设计报告正文内容 (一)问题的描述； (二)算法设计与分析，内容包括 1， 算法设计，对问题的分析和算法的设计 2，算法描述，以伪
2、代码形式的算法 3，算法分析，主要是算法的正确性和运行时间的分析 （三）算法实现 所有程序的原代码，要求用 C 语言程序实现，并对程序写出必要的注释。 书写格式书写格式 a要求用 A4 纸打印成册 b正文格式：一级标题用 3 号黑体,二级标题用四号宋体加粗,正文 用小四号宋体;行距为 22。 c正文的内容:正文总字数要求在 3000 字左右（不含程序原代码） 。 d封面格式如下页。 考核方式考核方式 指导老师负责验收程序的运行结果， 并结合学生的工作态度、 实际动手能力、 创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五 个等级给出每位同学的课程设计成绩。具体考核标准包含
3、以下几个部分： a平时出勤 （占 10%） b系统需求分析、功能设计、数据结构设计及程序总体结构合理与 否（占 10%） c程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%） d设计报告（占 30%） 2 e独立完成情况（占 10%） 。 注意：不得抄袭他人的报告（或给他人抄袭） ，一旦发现，成绩为零分。 课程验收要求课程验收要求 a判定算法设计的合理性，运行相关程序，获得正确的数值结果。 b回答有关问题。 c提交课程设计报告。 d提交软盘（源程序、设计报告文档） 。 e依内容的创新程度，完善程序情况及对程序讲解情况打分。 3 3、进度安排、进度安排 1 1、 班级： 信息与
4、计算科学：1001,1002,1003， 2 2、 主讲教师 3 3、 时间安排： 第 16 周 星期一 8 时：30 分11 时：30 分 星期二 8 时：30 分11 时：30 分 星期四 8 时：30 分11 时：30 分 星期五 8 时：30 分11 时：30 分 3 目录目录 一、任务书1 二、问题描述5 三、算法设计与分析6 四、程序调试7 五、附件8 六、评分表13 4 三三、问题描述、问题描述 在一个划分成网格的操场上，n 个士兵散乱地站在网格点上。网格点由整数 坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻 任一网格点上只能有一名士兵。按照军官的命
5、令，士兵们要整齐地列成一个水平 队列，即排列成(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.in sol0.out 5 1 2 2 2 1 3 3 -2 3 3 8 5 四、算法四、算法设计设计与分析与分析 算法设计算法设计 士兵站队问题是一个排序问题，问题描述为：网格点由整数坐标(x,y)表 示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上 只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列 成(x,y),(x+1,y),(x+n-1,y)。求需要移动的最少步数。 首先用两个一维数组 an,bn分
