最小套圈分治法数据结构课程设计_66727.doc

目 录 1 简介 1 2 算法说明 1 3测试结果 3 3.1 测试输入 3 3.2 测试目的 4 3.3 正确输出 5 3.4 实际输出 5 4 分析与探讨 6 4.1 测试结果分析 6 4.2 探讨与改进 6 附录：源代码 8 1 简介 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般的算法设计模式如下： divide-and-conquer(P) { if(|P|=n0) adhoc(P); divide P into smaller subinstances P1,P2,...,Pk; for(i=1;i=k;i++) yi=divide-and-conquer(Pi); return merge(y1,...,yk); } 其中，|P|表示问题P的规模。n0为一阀值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接算法adhoc(P)求解。算法merge(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的解y1,y2,...,yk合并为P的解。 根据分治法的分割原则，应把原问题分为多少个子问题才比较适宜？每个子问题是否规模相同或怎样才为适当？这些问题很难给予肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(banlancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 从分治法的一般设计模式可以看出，用它设计出的算法一般是递归算法。因此，分治法的计算效率通常可以用递归方程来进行分析。一个分治法将规模为n的问题分成m个规模为n/m的子问题，其中k(k=m)个子问题需要求解。为方便起见，设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。另外再设将原问题分解为k个问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法divide-and-conquer(P)解规模为|P|=n的问题所需的计算时间，则有： 下面来讨论如何解这个与分治法有密切关系的递归方程。通常可以用展开递归式的方法来解这类递归方程，反复代入求解得： 注意，递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果T(n)足够平滑，由n等于m的方幂时T(n)的值估计T(n)的增长速度。通常，可以假定T(n)单调上升。 另一个需要注意的问题是，在分析分治法的计算效率是，通常得到的是递归不等式：在讨论最坏情况下的计算时间复杂度，用等号(=)还是用小于等于号(=)是没有本质区别递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 套圈游戏是游乐场最常见的游戏之一，规则是：套圈者将手中的圆环套圈投向场中的奖品或者礼物，如果运气好的话，套中的奖品和礼物奖励给游戏者。 分治法的套圈设计的一系列思路来源于套圈游戏中。在给定玩具固定的情况下，怎样设计套圈的半径才会让游戏更吸引人。顾名思义圆环的半径在等概率的情况下半径越大套中的礼物或者礼品的概率较大，相对而言圆环半径越小，套中的礼物或奖品的在等概率的情况下套中是几率较小。因此使游戏的吸引力与半径的大小成正比。游戏的本身就是以营利为目的，因此为了吸引跟多的游玩者需要不赔本的情况下，吸引更多的游客达到最大营利的目的。 怎么设计圆环套圈半径恰大好处的既吸引游客又让自己的盈利最大化？从而引入了套圈半径的设计。 本实验的目的是设计一个程序，比较不同的算法在时间、空间中效率。  2 算法说明 套圈半径的设计有很多的方法。通过一系列算法的比较得出，最小套圈的算法采用“分而治之”法。既精确又提高了运行效率精确，将所有的点按照x y坐标有序的排列，从中间的场地一分为二，用递归的方法解决场地两边的子问题，求出两个坐标点之间的距和左右子集中的极小距离。 float dist(Point a, Point b) /*求两个坐标点之间的距离*/ { /*求两个坐标点之间的距离*/ return sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } float Nearest(Point* po