《最小套圈设计问题》由会员分享，可在线阅读，更多相关《最小套圈设计问题（13页珍藏版）》请在金锄头文库上搜索。
1、合肥学院计算机科学与技术系课程设计报告2009 2010学年第 二 学期课程数据结构与算法课程设计名称最小套圈设计问题学生姓名查文芳学号0804012034专业班级08计科(2)指导教师王昆仑张贯虹2010 年 6 月1、问题分析和任务定义一）问题分析本设计的要求是设计一个最小套圈，来进行一项游戏套圈游戏。 套圈游戏是游乐场中最常见的游戏之一，其规则为：游戏者将手中的圆环套圈投向场中 的玩具，被套中的玩具就作为奖品奖给游戏者。次问题是给定一个套圈游戏场中的布局，固定每个玩具的位置。请你设计一个圆环套圈 的半径尺寸，使得它每次最多只能套中一个玩具，但同时为了让游戏看起来更具吸引力这个 套圈的半径
2、又需要尽可能大。为使问题进一步简化，假设每个玩具都是平面上一个没有面积的点。套圈是简单的圆 一个玩具被套住，是指这个点到圆心的距离严格小于圆的半径。如果有两个玩具被放在同一 个位置，那么输出的圆半径就是零。模型说明（一）套圈的最大H径模型说明（二）任务定义1)定义一个点的结构体 Point 来存放点的横纵坐标，表示一个玩具的空间位置；同时采用 Point 这种结构体数组来存放不同的玩具；(2) 求最小套设计问题归结为先输入每个玩具的空间位置，然后求他们任意两点之 间的最小距离，然后取最小距离的一半即为套圈半径；判断是否有两个或两个以上的玩具放 在同一点，若有两个或两个以上的玩具放在同一点，那么
3、套圈的半径就为 0。(3) 求最小的距离的方法采用“分而治之”，将所有的点按它的X坐标排序，从中间 将场地分为二，然后递归的解决两边场地的子问题，分别得到两个子问题的最小半径 d 左和 d右，在横跨分界线的且距离分界线距离小于(d左和d右中较小的那一个)的区域中找出 所有横跨分界线的点对中距离最近的点对，将其记为d,然后看它和刚刚求的那个最小距离 求出哪个更小，最小的那个的一半即为最小套圈半径；(3)定义两个数组分别来存放玩具和最小距离，实现对多组测试数据的输入和测试 结果的存放和输出；2、数据结构的选择和概要设计 一)玩具的存储结构 将玩具抽象成空间一个没有面积的点，其数学模型如下图所示：a
4、 a a11 12 1na a a21 22 2nA =(lWXWm, lWYWn)m X niii:a :ija a am1m2mn因此可以用空间坐标X和Y来表示，在本程序中我采用了数组这种存储结构，包含横纵坐标 的结构体类型 Point;数据类型描述如下：typedef struct float x;/点的横坐标；float y;/点的纵坐标；Point;二) 创建放置玩具思想的算法(1) 声明 Point 类型的结构体，根据提示信息输入玩具的个数，根据输入的玩具个数将每 个点的横纵坐标输入，然后依次存放在数组之中；如果输入的玩具个数大于程序刚开始自定 义的MAX_POINTS或小于0输出
5、错误的提示信息；当输入的玩具个数为0时结束输入测试 组；三) 将所有的点按 X 坐标排序；为了提高求最短距离的效率，将所有的点先按X坐标排序，本程序中排序采用的是系 统的库函数qsort,采用该算法能够提高算法的效率；算法思想：在compx ()函数为将两个 点的横坐标减横坐标，如果大于0，返回1 则发生交换，如果等于0或小于0则不发生交换， 在 qsort 函数中第一个参数为数组名，第二个为数组中元素的个数，第三个为每个数组元素 所占的字节大小，最后一个为调用的表式比较的交换函数 compx；int compx(const void *a, const void *b) /实现按 x 排序r
6、eturn (Point*)a)-x-(Point*)b)-x;/实现按 y 排序int compy(const void* a, const void* b) return (Point*)a)-y-(Point*)b)-y;/ 将数组按 X 排序 / 将数组按 Y 排序； sizeof(Point), compy);qsort(points, numPoints, sizeof(Point), compx); qsort(points, numPoints/2, sizeof(Point), compy); qsort(points+numPoints/2, numPoints-numPo
7、ints/2,四) 计算套圈的半径的算法思想(1) 定义子函数float dist(Point a,Point b)求空间任意两点间的距离，调用系统的库函数 sqrt 求两点间的距离 算法描述如下：float dist(Point a, Point b) return(float)sqrt(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);(2) 定义一个子函数float Nearest(Point* points, int n)求空间中点之间哪两 点距离最短，求出它们间的距离；其中n表示玩具的个数；points表示数组名；如果n等 于1,返回0； n等于2,调用d
8、ist函数求它们之间的距离；n等于3,调用dist函数求出 第一个点与第二个点之间的距离；调用 dist 函数求出第二个点与第三个点之间的距离；调 用 dist 函数求出第一个点与第三个点之间的距离；利用双目运算？：求出三点间距离最短 的两点间的距离；当n大于3,利用递归将场地分成左右两半，然后对左右两部分分别调用 Nearest函数；比较刚刚求出的左右两边的最短距离，将其中较小的那个赋值给变量d,同 时将d赋值给nearest.综合中间地带，通过扫描左右子集中与其距离在d之内的所有点， 已完成合并求最短距离。然后取中间地带的距离temp与nearest中较小的距离，并将它最 为参数返回；算法
9、描述如下：float Nearest(Point* points, int n) float temp1,temp2,temp3,temp,nearest; float left,right,d;int i,j;/一个点情形/两个点情形/三个点情形if(n=1)return 0;if(n=2)return dist(points0,points1);if(n=3)temp1=dist(points0, points1);temp2=dist(points0, points2 );temp3=dist(points1, points2);return temp3(temp1temp2)?temp
10、1:temp2)?temp3:(temp1temp2)?temp1:temp2);/多于 3 点的情形，用分治法 left=Nearest(points,n/2);/递归求解right=Nearest(&pointsn/2,n-n/2);d=leftright?left:right; /综合中间带求得最小距离nearest=d;for（i=0;in/2;i+） for（j=n/2;jn&（fabs（pointsj.y-pointsi.y）d）;j+） temp=dist（pointsi,pointsj）; nearest=nearesttemp?nearest:temp;return near
11、est;五）如何输出多组测试数据的套圈的最小半径定义一个数组result来存放最小半径，并且赋初始值为T （因为套圈半径不可能为 负数），将求的最小套圈半径存在result中，当resulti ! =T时，输出所有的测试结 果；六）结构图Main（）Compx(const void a ,const void b)Nearest(Point *points,int n)dist(Point a,Point b)Qsort(points, numPoints, sizeof(Point), compx)3、详细设计和编码一）算法思想首先创建一个放置玩具的平面（每个玩具都是平面上一个没有面积的点）
12、，其次判断是否有 放在同一位置的玩具，再次计算套圈的半径。（1） 创建放置玩具平面的算法思想该算法的实现是定义一个含有横纵坐标X和Y的结构体，其次定义一个含有X和Y的结 构体数组Poi nt,具体操作于下：（I）当程序提示，输入玩具数目时，就读入玩具的个数t （正整数），若输入小于0 或大于自定义最大的那个MAX_POINTS，输出输入错误的提示信息。(II) 输入正确则依次输入各个点的横纵坐标。接下来又出现“输入玩具个数”的提示 信息，当还想输入一组测试数组，按上述继续输入，当输入为0,则结束输入了。(2) 计算套圈的半径的算法思想(I) 定义子函数float dist(Point a,Po
13、int b)求空间任意两点间的距离，调用系统 的库函数sqrt求两点间的距离；(II) 为了提高求最短距离的效率，将所有的点先按X坐标排序，本程序中排序采用的 是系统的库函数qsort,采用该算法能够提高算法的效率；算法思想：在compx()函数为将 两个点的横坐标减横坐标，如果大于0，返回1则发生交换，如果等于0或小于0 则不发生 交换，在 qsort 函数中第一个参数为数组名，第二个为数组中元素的个数，第三个为每个数 组元素所占的字节大小，最后一个为调用的表式比较的交换函数 compx；(III) 定义一个子函数floa t Neares t(Poin t* poin ts, int n)
14、求空间中点之间哪 两点距离最短，求出它们间的距离；其中n表示玩具的个数；points表示数组名；如果n 等于1,返回0； n等于2,调用dist函数求它们之间的距离；n等于3,调用dist函数求 出第一个点与第二个点之间的距离；调用 dist 函数求出第二个点与第三个点之间的距离； 调用 dist 函数求出第一个点与第三个点之间的距离；利用双目运算？：求出三点间距离最 短的两点间的距离；当n大于3,利用递归将场地分成左右两半，然后对左右两部分分别调 用 Nearest 函数；比较刚刚求出的左右两边的最短距离，将其中较小的那个赋值给变量 d， 同时将d赋值给nearest.综合中间地带，通过扫描
15、左右子集中与其距离在d之内的所有点， 已完成合并求最短距离。然后取中间地带的距离temp与nearest中较小的距离，并将它最 为参数返回；(3) 如何输出多组测试数据的套圈的最小半径定义一个数组result来存放最小半径，并且赋初始值为-1 (因为套圈半径不可能为 负数)，将求的最小套圈半径存在result中，当resulti ! =-1时，输出所有的测试结 果；二)主要算法描述(1)创建放置玩具平面的算法思想typedef struct float x;/点的横坐标；float y;/点的纵坐标；Point;printf (ttt 请输入数据n);while(1) loop:printf(请输入玩具个数：)；scanf(%d, &numPoints);if(!numPoints) break;/当玩具个数为 0 时，结
