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