网格点上放棋子

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

账号		自动登录	找回密码
密码			欢迎注册

[提问] 网格点上放棋子

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。