jx215 发表于 2015-1-24 14:16:56

一笔画的问题

下图有16个点，如一笔画通过所有的点，无论横线竖线或者斜线，每条线至少须通过一点，且不得超出方格范围。需要画几笔（也就是至少多少条线段）？能证明吗？
若改成5×5或6×6，甚至n×n呢？

               。    。    。    。
            
               。    。    。    。

               。    。    。    。

               。    。    。    。


sheng_jianguo 发表于 2015-1-26 08:00:09

至少需要画1笔，2n-1条线段。

jx215 发表于 2015-1-26 20:56:17

sheng_jianguo 发表于 2015-1-26 08:00
至少需要画1笔，2n-1条线段。

怎么得到的？

毒酒滴冻鸭 发表于 2015-1-28 11:21:39

据我所知，4x4一笔划最少为6线段，但那超出方格范围，如不超出最少应需要7线段。

毒酒滴冻鸭 发表于 2015-1-29 08:14:06

sheng_jianguo 发表于 2015-1-26 08:00
至少需要画1笔，2n-1条线段。

当n>4的时候，发现一个通解，可以用2n-2条线段成功一笔画！
页: [1]
查看完整版本: 一笔画的问题