N个点中距离最短的两个点求解解决办法 - C++当前位置:& &&&N个点中距离最短的两个点求解解决办法N个点中距离最短的两个点求解解决办法&&网友分享于：&&浏览：81次N个点中距离最短的两个点求解问题描述：三维空间中，在边长为M（int）的立方体内有N个点，如点a（x,y,z），点b（p,l,g），点的坐标值均为int整型数据即x,y,z,p,l,g均为int数据类型，求N个点中距离最短的两个点值。
PS：说出算法思想即可，不必码代码，要求算法空间和时间复杂度。
路过的帮顶顶，多谢！------解决方案--------------------难，相当难。------解决方案--------------------最笨的方法是2层循环全部搜索
O(n^2)的时间复杂度------解决方案--------------------可以化简：
由广义不等式：
Sqrt&(&a^2&+&b^2&+&c^2&)&&=&a&+&b&+&c
这里，A、B、C&对应着&deltaX,&deltaY,&deltaZ
因此&a&+&b&+&c&=&deltaX&+&deltaY&+&deltaZ&=&Sum(P1)&-&Sum(P2)，就是两个点的坐标值和之差。比平方再开方简单多了……
外层，还是遍历。------解决方案--------------------楼上的莫非就是传说中的放缩大法^_^？------解决方案--------------------最近点对，分治法典型问题：
最接近点对
下面是内容：
这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。
&&&&这个问题显然满足分治法的第一个和第二个适用条件，我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:　
T(n)=2T(n/2)+O(n2)
&&&&它的解为T(n)=O(n2)，即与合并步骤的耗时同阶，显示不出比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。
&&&&为了使问题易于理解和分析，我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证明的，耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。
&&&&假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S------解决方案--------------------x≤m}；S2={x∈S------解决方案--------------------x&m}。这样一来，对于所有p∈S1和q∈S2有p&q。
&&&&递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设δ=min{------解决方案--------------------p1-p2------解决方案--------------------,------解决方案--------------------q1-q2------解决方案--------------------}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。如图1所示。
图1&一维情形的分治法
&&&&我们注意到，如果S的最接近点对是{p3,q3}，即------解决方案--------------------p3-q3------解决方案--------------------&δ，则p3和q3两者与m的距离不超过δ，即------解决方案--------------------p3-m------解决方案--------------------&δ，------解决方案--------------------q3-m------解决方案--------------------&δ，也就是说，p3∈(m-δ,m]，q3∈(m,m+δ]。由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S1和S2的分割点，因此(m-δ,m]中至多包含S中的一个点。同理，(m,m+δ]中也至多包含S中的一个点。由图1可以看出，如果(m-δ,m]中有S中的点，则此点就是S1中最大点。同理，如果(m,m+δ]中有S中的点，则此点就是S2中最小点。因此，我们用线性时间就能找到区间(m-δ,m]和(m,m+δ]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说，按这种分治策略，合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢？还有一个问题需要认真考虑，即分割点m的选取，及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割，即S=S1∪S2&，S1∩S2=Φ，且S1{x 共&4&页:
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有4022人阅读
/*（描述）无穷数列1，1，2，3，5，8，13，21，34，55...称为Fibonacci数列，它可以递归地定义为
F(n)=1 ...........(n=1或n=2)
F(n)=F(n-1)+F(n-2).....(n&2)
现要你来求第n个斐波纳奇数。（第1个、第二个都为1)
（输入）第一行是一个整数m(m&5)表示共有m组测试数据
每次测试数据只有一行，且只有一个整形数n(n&20)
（输出）对每组输入n，输出第n个Fibonacci数*/
#include &iostream&
int Fibonacci(int n)
if(1==n||2==n)
& &return 1;
return Fibonacci(n-1)+Fibonacci(n-2);&
int main()
cout&&&Fibonacci数列中的第n个数：&;
cout&&endl&&&请输入n（小于0退出程序）:&;
while(n&0) //当输入小于0的数就会制动退出程序&
cout&&&F(&&&n&&&)==&&&Fibonacci(n)&&endl&&
cout&&&请输入n（小于0退出程序）：&;
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：96561次
积分：1794
积分：1794
排名：千里之外
原创：83篇
转载：17篇
(3)(2)(2)(2)(2)(4)(2)(5)(17)(9)(4)(1)(2)(3)(10)(24)(5)(3)}