格点正方形，可否发现一个新数列？

gxqcn

26#想法从上图就否定了，上图中有红色正方形。 hujunhua 发表于 2012-5-31 14:12

再仔细看了会，还真有红色顶点正方形呢（早上回帖时没过细看啊），边长为$sqrt5$

wayne

25# KeyTo9_Fans fans可否透漏一下程序的原理？

wayne

其实随机生成也挺方便的。

hujunhua

图没必要搞这么大呀，照顾一下1024×768的屏哟。

hujunhua

都有红顶正方形呢，有的还有2个。

hujunhua

33#第2图打消了我的一个疑虑。我曾猜测27#wayne所说的猜想可能是什么。 我猜测wayne的猜想是: 除了原点，存在x轴和 y轴上不含其它红点的涂抹方案。 这样一来，17#的证明就充分了。 我以为wayne在27说的在n=4时推翻了这种猜想，看来不是啊。

hujunhua

这样的算法可行么： 1、选择关联黑正方形最多的一个点 2、如果还有黑顶正方形，Goto 1, 否则结束。 我为此计算过点(x,y)所关联的正方形数，公式有点怪。

wayne

36# hujunhua 额，我的不成熟的想法，老大都能猜得到，惭愧，惭愧。 我最初就是按这个思路构造的，可总是存在边长较小的斜正方形，于是索性打破规则，竟然成功了。 也就是说，在最后时刻，是拼凑出来的。 我觉得fans一定有他的一套，他都能算到 n=5至少为15

wayne

37# hujunhua 这就是贪心算法吧。 是可以的。 但局部最优好像不能保证 全局就是最优的(老大可否证明一下)。 程序最终结束的点数很可能不是最少的,即n=4的时候，算出来不是10个，而是11个，12个。 ============= 我也计算过(x,y)每个点所关联的正方形个数。 还是蛮有意思的。

wayne

34# hujunhua 俺是粗人， 还好，有郭老大帮忙。