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个棋子呢？更多呢？

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

回溯法？呵呵，试试吧。
页: [1]
查看完整版本: 练习编程的题目