C++的课程作业，一个简单的最近点对程序，用dev就能直接运行，老师应该不会太仔细检查，糊弄一下肯定没事的，不过最好能自己看懂就是了
2022-04-24 13:51:49
1KB
1
不会吧！都2022年了，你还没有弄懂最接近点对问题？？？
相信我，就看这一篇就够啦！！！
1．问题描述
给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中该点对间的距离最小。
2．实验目的
1)掌握递归与分治法的基本思想及基本原理。
2)掌握使用分治法求解问题的一般特征及步骤。
3)掌握分治法的设计方法及复杂性分析方法。
掌握分治法解平面最接近点对算法设计思想、算法设计过程及程序编码实现。
采用分治法解最接近点对问题。请回答以下问题：
1)一维情形下如何用线性时间完成合并步骤？
2)二维情形下递归求解递归出口如何设置？
3)二维情形下证明该问题具有稀疏性质：什么是鸽舍原理？二维情形下为什么跨分割线点对能构成最接近点对候选者的最多只有6对？
4)在二维情形下如何能用线性时间完成左右最近点对与中间跨分割线点对的比较？
5)对算法做时间复杂性分析。
6)本题选做：二维情形设采用分治法解最接近点对问题，编程实现。
2022-04-07 09:08:00
164KB
问题：对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。
2022-04-06 01:22:14
11KB
《计算机算法设计与实现》，书上例题代码的实现，最接近点对问题的算法虽然简单，但是实现上却比较麻烦，尤其当作者套用N个形式不雅的函数后...
2022-03-19 21:11:29
1KB
1
利用动态分治思想解决一些如下问题：Strassen矩阵乘法Karatsuba快速乘法最近点对问题源代码(有C/C++程序)
2022-01-24 21:52:02
1006KB
1
二维空间的最接近点对问题
下面来考虑二维的情形。
选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。
递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2 ，如图2-9所示。
能否在线性时间内找到p,q？
考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图2-10所示。
由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。
图2-9距离直线l小于d的所有点
图2-10包含q的d×2d矩形R
2021-11-05 10:39:25
1.69MB
1