| 作者 |
 智力题 90 puzzle。求一般性解法。一般性解法中有可能得出一种新算法，新集合 |
 |
| 所跟贴 |
智力题 90 puzzle。求一般性解法。一般性解法中有可能得出一种新算法，新集合 -- 秀才 - (1171 Byte) 2008-6-20 周五, 00:53 (1431 reads) |
勤劳
[博客]
头衔: 海归元勋
声望: 大师
加入时间: 2008/01/26
文章: 9711
海归分: 2805340
|
|
|
作者：勤劳 在 海归招聘 发贴, 来自【海归网】 http://www.haiguinet.com
看到这个题目，第一感觉是，找三个不相等的数字，然后在格子里标出来xy，xz,，yz。
x < y < z , 所以你把这三个格子找出来，就会发现是一个直角三角形，直角在左上角。
于是题目就成了，找30个这样的三角形，把顶点所在的90个格子刚好涂满。
由于90个格子是有规矩的，因此不是随便的直角在左上角的直角三角形都可以，你任意找到两点，第三点实际上就固定住了，因为两点的坐标里，就有了这三个数字。
把(4,4), (5,5), (6,6),(7,7), (8, , (9,9),(A,A), (B,B), (C,C)这九个格子涂红，你会发现每个符合要求直角三角形都和这条线有关系，如果你把直角三角形再补上右下方的一半形成一个矩形的时候，右下角必然落在这九个红格子上。
问题就变成：从这九个红格子里的某一个开始，向左上方发展出一个矩形，一共发展出30个矩形，使得矩形的另外三个端点（共90个），刚好覆盖满90个格子。
从(4,4)这个红格子开始考虑。
从(4,4)向上发展，有三个选择，就是发展到 (1,4), (2.4), (3,4)。向左发展呢？最少也要到(4,7)，因此(5,5), (6,6) 都需要自己来向上发展到上面的三个格子以找到矩形的右上角。
这就是说，从(4,4), (5,5), (6,6)的每个红格子可以发展出3个矩形。同理，(A,A), (B,B), (C,C)也是。这样就一定会发展出18个矩形。其他的12个矩形是从(7,7), (8,, (9,9)向左上方发展的。
因为整个图形是以(1,F), (8,的连接线为对称的，因此如果本题有解，一定不是唯一解，对称的那个解法也是解。
由于xyz三个数字一定有大小顺序，不能相等，所以(8,那个地方会比较特别。
我给一个空白的图，再给一个填写的样子，每次想好一个矩阵，就把xyz三个数字填写四次，三次在格子里，一次在记录里。记录的右边可以做星号以表示这里有很多选择的，此路不通的话下次再试别的。
接下来的工作就是多撞几次南墙，如果有解，一定可以找到解。（如果有电脑高手帮忙，写个程序，就更好了，应该很快可以找到答案。）
等我晚上有空就去撞墙。
作者：勤劳 在 海归招聘 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
|
| |
|
|
|
您不能在本论坛发表新主题, 不能回复主题, 不能编辑自己的文章, 不能删除自己的文章, 不能发表投票, 您 不可以 发表活动帖子在本论坛, 不能添加附件可以下载文件, |
|
|
