魔方吧·中文魔方俱乐部

标题: 练习编程的题目 [打印本页]

作者: aubell 时间: 2010-11-17 12:14:54 标题: 练习编程的题目

发现这样一个好题目，很适合练习编程：
大家有兴趣试试吗？手动求解很容易，但求到最短步数不一定很容易。
要求用计算机求最少步数。
题目描述：
棋盘是7个空格
棋子有6个，编号1-6，排一排，棋盘最右边留一个空格
走法：1.挪动一个棋子 2.跳动一个棋子，进入空格中
目标：把123456变成654321，仍放在最左边的6个格子里。

说明：由于只有一个空格，所以可以直接用数字表示走法。
例如一个解法是：6 4 2 1 3 5 6 4 2 1 3 5 6 4 2 1 3 5 6 4 2
共21着。

您能找到其它解法吗？换成9个格子，8个棋子呢？更多呢？

附件: 123456.JPG (2010-11-17 12:14:54, 90.89 KB) / 下载次数 70
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTE5NjQ4fDM1MmVlMzY1fDE3Mzk4MDQxNTd8MHww

作者: TanLaiChen 时间: 2010-11-17 12:41:07

什么东东来的？

作者: oyyq99999 时间: 2010-11-17 12:41:12

感觉属于经典的搜索题。。。

作者: 喝着牛奶数星星 时间: 2010-11-17 13:33:02

暂时没看明白再看一遍

作者: kattokid 时间: 2010-11-17 13:58:02

没看懂…待会还是上电脑看吧！

------------------
不会编程。。。草稿纸计算倒还是可以的

[ 本帖最后由 kattokid 于 2010-11-19 08:35 编辑 ]

作者: superacid 时间: 2010-11-17 15:13:47

果断先在草稿纸上算出来再写。。。

作者: ggglgq 时间: 2010-11-21 10:19:22

　　

支持一下！楼主的题目使我联想到

      推移魔方 Xdyne's Cube
      http://bbs.mf8-china.com/viewthread.php?tid=3075

它可以看做是一个三维空间的推移魔方。同样我们可以构造出二维空间的

推移魔方和一维空间的推移魔方。楼主的题目就可以看成是一维推移魔方。

但如果把楼主的题目看成是一维推移魔方，答案马上出来：

对于一维推移魔方 123...N 来说，实现“逆序”的最少步为 N 步：

         N , N-1 , ... , 3 , 2 , 1

为什么呢？大家稍作思考就明白了。


类似的又想到了一个五年前的一维空间的编程题目，感兴趣的魔友可以试试：

      一维二进制游戏
      http://bbs.mf8-china.com/viewthread.php?tid=1480
　　
　　

[ 本帖最后由 ggglgq 于 2010-11-21 10:59 编辑 ]

作者: 逸风 时间: 2011-3-13 21:36:12

回溯法？呵呵，试试吧。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)