基于C语言实现的最近点对问题

Pubertyly

发布日期: 2019-03-12 14:28:39 浏览量: 303
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1、实验题目

最近点对问题:

已知平面上分布着点集P中的n个点p1,p2,…pn,点i的坐标记为(xi,yi),1≤i≤n。两点之间的距离取其欧式距离,记为:

问题:找出一对距离最近的点。

注:允许两个点位于同一个位置,此时两点之间的距离为0。

2、设计思路

2.1 基本思路

由于不要求控制算法的时间复杂度,所以采用最简单直观的暴力求解法。

对于所有的n个点,计算任意两个点之间的距离,一边计算一边比较,遇到距离更近的点对则保存下来,这样可以在所有的距离中,选出最小的值,即为算法需要的结果。

2.2 数据结构设计

需要两个数组分别存放点的横坐标和纵坐标,数组下标代表点的序号,这里假定点的坐标都是整数,所以用int型数组。此外还需要一个浮点型变量用于计算两点间的距离,4个int型变量用于存放当前最近点对的坐标。

2.3 时间复杂度

将所有的点排成一排,从第一个点开始,依次求其后面的点与它的距离,要计算n-1次,第二个点需要计算n-2次……倒数第二个点计算1次,所以一共计算的次数为:

  1. 1 + 2 + 3 + + n-2 + n-1 = nn-1)/2

因此算法时间复杂度为O(n)。

3、运行演示

测试用例以数组形式存放在代码中已经写好,不用手动输入,共8个点,坐标分别为:
(1,9)、(-8,-22)、(-9,16)、(101,68)、(6,13)、(233,100)、(12,-138)、(-35,591),这些点覆盖了各大象限,距离也有近有远,足够验证算法的正确性,运行结果如图1-1和图1-2。

遍历过程中每对点的距离都进行了输出,通过距离比较可以发现距离最近的两点是(1.9)和(-9,16),距离是约为6.4。

上传的附件 cloud_download 基于C语言实现的最近点对问题.7z ( 55.83kb, 1次下载 )
error_outline 下载需要5点积分

发送私信

走在一起是缘分,一起在走是幸福

17
文章数
16
评论数
最近文章
eject