056254628 发表于 2011-1-13 17:18:38

网格点上放棋子

n*n的网格点上放棋子，要求任何3个棋子不共线，那么最多可以放多少个棋子？

hujunhua 发表于 2011-1-14 11:19:40

是个不錯的数学问题，也是一个不错的编程题目。
线怎么定义的，仅指纵、横和对角线方向的斜线，还是包括所有有理斜率的方向？
如果仅指纵横对角线三向，问题相对简单些，若要包括所有有理方向，预计不会有简明的结果。
这两种题设都可以考虑，分别讨论吧。

还有一种考虑，就是把这个n×n棋盘的对边邻接起来，即拓扑等价于轮胎面。这样一来所有斜率的线都是一样长的，结构反而比平面更单一，也许结果会更规则。

编程高手们，谁抛第一块砖（呵呵，应该是玉，我替人谦虚一哈）？

gxqcn 发表于 2011-1-14 13:52:04

hu版看问题总是比较深刻，
正应了那句俗话：站得高，看得远。

056254628 发表于 2011-1-14 16:50:00

最多肯定不会超过2*n个棋子，因为每一行最多放2个。
问题是2n个棋子能否摆得出来？对于一个具体的n值，只要能举出一个能摆成的例子，就可证明最多是2n。
比如n=2，f(n)=4
n=3,f(n)=6
         110
         101
         011      1表示棋子。
--------------------------------------
对于较小的n值，可以让电脑来暴力求解，但是n大的话，电脑可能吃不消了。
能不能构造出一种满足题目要求的摆法，使得2n个棋子的摆法成为可能，那么就不需要证明了。
或者暴力求解较小的n值，证明2n的答案是错误的。

medie2005 发表于 2011-1-14 18:24:55

本帖最后由 medie2005 于 2011-1-14 18:28 编辑

...........

G-Spider 发表于 2011-1-14 18:54:16

1    1    0    0   0
1    0   1   0   0
0   1    0   1   0
0   0    1   1   0
4或5的一种情形 ，每行每列最多出现两个，1是受限的，而0随着阶数在增多，2n个棋子能摆完吗？呵呵

056254628 发表于 2011-1-14 19:18:04

本帖最后由 056254628 于 2011-1-14 19:19 编辑

楼上是4*5的类型，
对于n*m，最多不会超过2*min(n,m)
楼上刚好放了8个棋子，恰好证明了上限值被取到了。
----------------------------
而实际上楼上的答案不对，斜线上3点共线了，不符合题目要求

G-Spider 发表于 2011-1-14 19:36:40

7# 056254628
如果斜线也考虑的话，4*5的一个例子
1 0 0 0 1
1 0 1 0 0
0 1 0 0 1
0 1 0 1 0

northwolves 发表于 2011-1-14 19:49:45

n=4
--------------
1010
0101
0101
1010

northwolves 发表于 2011-1-14 19:55:05

n=5
-----------
01010
11000
00101
10001
00110
页: [1] 2
查看完整版本: 网格点上放棋子