最小套圈设计问题课程设计报告.doc

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