1、 计算机科学与技术系 课程设计报告 2009 2010 学年第 二 学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 最小套圈设计问题 学生姓名学生姓名 学号学号 专业班级专业班级 指导教师指导教师 2010 年 6 月 1 1、问题分析和任务定义、问题分析和任务定义 一）问题分析 本设计的要求是设计一个最小套圈，来进行一项游戏套圈游戏。 套圈游戏是游乐场中最常见的游戏之一，其规则为：游戏者将手中的圆环套圈投向场中 的玩具，被套中的玩具就作为奖品奖给游戏者。 次问题是给定一个套圈游戏场中的布局，固定每个玩具的位置。请你设计一个圆环套圈 的半径尺寸， 使得它每次最多只
2、能套中一个玩具， 但同时为了让游戏看起来更具吸引力这个 套圈的半径又需要尽可能大。 为使问题进一步简化，假设每个玩具都是平面上一个没有面积的点。套圈是简单的圆， 一个玩具被套住， 是指这个点到圆心的距离严格小于圆的半径。 如果有两个玩具被放在同一 个位置，那么输出的圆半径就是零。 模型说明（一） 模型说明（二） 二）任务定义 （1）定义一个点的结构体 Point 来存放点的横纵坐标，表示一个玩具的空间位置； 同时采用 Point 这种结构体数组来存放不同的玩具； （2）求最小套设计问题归结为先输入每个玩具的空间位置，然后求他们任意两点之 间的最小距离， 然后取最小距离的一半即为套圈半径； 判断
3、是否有两个或两个以上的玩具放 在同一点，若有两个或两个以上的玩具放在同一点，那么套圈的半径就为 0。 （3）求最小的距离的方法采用“分而治之” ，将所有的点按它的 X 坐标排序，从中间 将场地分为二， 然后递归的解决两边场地的子问题， 分别得到两个子问题的最小半径 d 左和 d 右，在横跨分界线的且距离分界线距离小于（d 左和 d 右中较小的那一个）的区域中找出 所有横跨分界线的点对中距离最近的点对，将其记为 d，然后看它和刚刚求的那个最小距离 求出哪个更小，最小的那个的一半即为最小套圈半径； （3）定义两个数组分别来存放玩具和最小距离，实现对多组测试数据的输入和测试 结果的存放和输出； 2
4、2、数据结构的选择和概要设计、数据结构的选择和概要设计 一）玩具的存储结构 将玩具抽象成空间一个没有面积的点，其数学模型如下图所示： a11 a12 a1n a21 a22 a2n Amn= (1Xm，1Yn) aij am1 am2 amn 因此可以用空间坐标 X 和 Y 来表示， 在本程序中我采用了数组这种存储结构， 包含横纵坐标 的结构体类型 Point; 数据类型描述如下： typedef struct float x; /点的横坐 标； float y; /点的纵坐 标； Point; 二）创建放置玩具思想的算法 （1）声明 Point 类型的结构体，根据提示信息输入玩具的个数，根据输入的玩具个数将每 个点的横纵坐标输入， 然后依次存放在数组之中； 如果输入的玩具个数大于程序刚开始自定 义的 MAX_POINTS 或小于 0 输出错误的提示信息； 当输入的玩具个数为 0 时结束输入测试 组； 三）将所有的点按 X 坐标排序； 为了提高求最
