论坛 › 难题征解 › 格点正方形，可否发现一个新数列？

gxqcn 发表于 2012-5-31 14:27:47

26#想法从上图就否定了，上图中有红色正方形。
hujunhua 发表于 2012-5-31 14:12 http://bbs.emath.ac.cn/images/common/back.gif

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

wayne 发表于 2012-5-31 21:00:10

25# KeyTo9_Fans

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

wayne 发表于 2012-5-31 21:05:14

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

hujunhua 发表于 2012-5-31 21:53:19

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

hujunhua 发表于 2012-5-31 21:55:32

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

hujunhua 发表于 2012-5-31 22:04:38

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

hujunhua 发表于 2012-5-31 22:17:19

这样的算法可行么：
1、选择关联黑正方形最多的一个点
2、如果还有黑顶正方形，Goto 1, 否则结束。

我为此计算过点(x,y)所关联的正方形数，公式有点怪。

wayne 发表于 2012-5-31 22:18:07

36# hujunhua
:b:

额，我的不成熟的想法，老大都能猜得到，惭愧，惭愧。
我最初就是按这个思路构造的，可总是存在边长较小的斜正方形，于是索性打破规则，竟然成功了。
也就是说，在最后时刻，是拼凑出来的。
:loveliness:

我觉得fans一定有他的一套，他都能算到 n=5至少为15

wayne 发表于 2012-6-1 09:10:41

37# hujunhua
这就是贪心算法吧。
是可以的。
但局部最优好像不能保证 全局就是最优的(老大可否证明一下)。

程序最终结束的点数很可能不是最少的,即n=4的时候，算出来不是10个，而是11个，12个。

=============
我也计算过(x,y)每个点所关联的正方形个数。
还是蛮有意思的。

wayne 发表于 2012-6-1 10:49:24

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

查看完整版本: 格点正方形，可否发现一个新数列？