请教一个汉诺塔算法问题

Mrsum
  • 609

js用递归实现一个汉诺塔的完成步骤,相信很多同学都会。
我自己业余的时候写了个汉诺塔的游戏,里面有一个提醒功能, 用户点提醒,程序利用递归实现一个完成步骤,然后操作页面元素根据这个步骤来实现。
局部代码如下:

var moves = [];  // 存放完成步骤
/**
 * @param disc      当前关卡 (实际上也就是圆盘数量)
 * @param discs1    第一根圆柱
 * @param discs2    第二根圆柱
 * @param discs3    第三根圆柱
 */
function hanoiArithmetic(disc, discs1, discs2, discs3) {
    if (disc > 0) {
        hanoiArithmetic(disc - 1, discs1, discs3, discs2);
        moves.push(discs1 + '>' + discs3);
        hanoiArithmetic(disc - 1, discs2, discs1, discs3);
    }
}
hanoiArithmetic(4, 'discs1', 'discs2', 'discs3');
console.log(moves); 
// 最后得到这样一个步骤列表
[ 'discs1>discs3',
  'discs1>discs2',
  'discs3>discs2',
  'discs1>discs3',
  'discs2>discs1',
  'discs2>discs3',
  'discs1>discs3' ] // 大概意思就是想从第一个圆柱取最上面那个圆盘放到第三个圆柱...

一切都没什么问题, 现在碰到的难题是, 这只能完全是一个新关卡,用户没有移动过任何圆盘的情况下,生成的一个步骤列表, 如果用户移动过圆盘, 比如现在第一根圆柱上面3个圆盘, 第二个上面2个圆盘,第三个上面1个圆盘, 用户被难住了,不知道下一步该怎么走了,这时候点提醒, 怎么根据当前的局势来生成后续的步骤算法呢?
说来比较惭愧, 这个游戏半年前写的, 到目前为止这个提醒功能还没完成, 我一点头绪都没有。

回复
阅读 1.6k
2 个回答

这个你可以看斐波拉契数列 汉诺塔就是斐波拉契算法

如果需要这样的提醒功能,比你现在的复杂一些,需要纪录状态。
比如你这个例子是6个圆盘,第一根柱子上3个圆盘,有可能是456,也有可能是135,你需要明确现在的状态,然后完成步骤再从上向下分解。

if 最大圆盘不在目标圆柱上 {
  if 最大圆盘不能直接移动到目标圆柱 {
    其他圆盘移动到“中间”圆柱(规模减一)  //非最大圆盘所在圆柱和目标圆柱
  } 
  移动最大圆盘到目标圆柱
}
移动其他圆盘到目标圆柱(规模减一)
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏