关于点的分布问题
本帖最后由 aimisiyou 于 2020-3-25 01:50 编辑在n×n的方格网上最多可以选取多少个网点，使得任意四个点(x1, y1), (x2, y2), (x3, y3) 和 (x4, y4) 均不满足{x1+x2=x3+x4 and y1+y2=y3+y4}.
n=32时，点数m=? 本帖最后由 aimisiyou 于 2020-3-25 13:49 编辑
感觉有些类似筛法。 在n×n的方格网上最多可以选取多少个网点，使得其中任意四点都不是一个平行四边形（包括四点共线的退化情形）的顶点。 本帖最后由 aimisiyou 于 2020-3-26 11:20 编辑
hujunhua 发表于 2020-3-25 23:09
在n×n的方格网上最多可以选取多少个网点，使得其中任意四点都不是一个平行四边形（包括四点共线的退化情形 ...
恩，是的。有没有好的算法。另外我不确定是否从第一个选取，判断后续是否可选的结果是最优的（比如不选第一个，从选第二个开始，再判断后续是否可选的结果可能更好）。若按皇后问题思路，运算量又太大了。 是否包括四点共线？ 1#2#的图有四点共线。 本帖最后由 aimisiyou 于 2020-3-26 12:32 编辑
zeroieme 发表于 2020-3-26 12:14
是否包括四点共线？ 1#2#的图有四点共线。
只要不满足广义平行四边形，四个点可以共线。每点可以看成一个复数，即要求任意两个复数之和都不相等。
页:
[1]