JavaScript 中的汉诺塔

• 下载源码 - 3.9 KB

引言

本文的目的是提出一个基于 JavaScript 的著名汉诺塔问题的解决方案。该问题要求将一组盘子从一个塔移动到另一个塔，限制条件是任何时候盘子都不能放在比它小的盘子上面。这个问题有一个著名的递归算法。

提出的解决方案（HTML 和 JavaScript 全部包含在一个 HTML 文件中）使用 JavaScript 的setInterval()函数展示了算法的一种可能的动画效果。

按照此处描述的方式为递归的汉诺塔算法制作动画的想法并非新颖。我大约在 15 年前用 Visual Basic 实现过。可以通过此链接观看视频。

汉诺塔的递归算法

汉诺塔问题的著名递归算法可以用以下 JavaScript 函数表示：

function Hanoi(n, from, to , via)
{
  if (n==0) return;

  Hanoi(n-1, from, via , to);

  moveDisk(from,to);

  // callStack.push([from,to]); // save parameters to callStack array
  
  Hanoi(n-1, via, to , from);
}

算法的输入是 4 个整数参数，如下所示：

1. n：盘子数量；作为递归的问题规模
2. from：“from”塔，即盘子放置的塔
3. to：“to”塔，即盘子最终必须放置的塔
4. via：“via”塔，在盘子在from塔和to塔之间移动时用作中间位置的塔。

通常（如果我们用 0, 1, 2 表示塔），对于 n 个盘子的初始调用将是 Hanoi(n,0,2,1)。

递归算法通常会尝试找到子问题（原始问题的实例，但问题规模更小）。然后用子问题的解来表达原始问题的解。汉诺塔的递归算法基于这样一个观察：“from”塔上最上面的 n-1 个盘子（连同其他两个塔）代表了原始问题的一个更小规模的实例，因此可以通过调用 Hanoi(n-1, 0,1,2) 来解决。这会将盘子移动到中间的塔（#1），并使用另一个塔（#2）作为中间。在此之后，我们可以将第 n 个盘子从塔 #0 移动到塔 #2，然后使用塔 #0 作为中间，通过调用 Hanoi(n-1, 1,2,0) 将 n-1 个盘子从中间的塔移动到最后一个塔。

上述算法编码了前面的描述，但塔的参数被保留为变量而不是特定值。

JavaScript 中的动画处理存在问题

通常动画代码可以利用 JavaScript 定时器函数：setInterval() 或 setTimer()。但是，事情并非如此简单。假设在上面的代码中，对 moveDisk() 函数的调用使用 setInterval() 进行动画处理。会发生一个问题，因为调用者中的代码将继续执行并干扰（混淆共享数据）动画。有人可能会建议调用者稍作等待以允许动画完成。然而，JavaScript 缺乏“真正的”延迟或睡眠机制。如果我们通过自旋循环来实现延迟，它将导致程序停滞，因为所有 JavaScript 代码都在单个线程上执行。

似乎 JavaScript 动画使用了以下模式：如果你开始动画，就不要做任何其他事情。

对于汉诺塔算法，我们希望为一次 moveDisk() 调用制作动画，然后返回调用者，直到遇到下一个 moveDisk() 调用，为其制作动画，依此类推。但是，使用 JavaScript 动画，我们必须以某种方式遵循此模式：为 moveDisk() 制作动画，为下一个 moveDisk() 制作动画，依此类推。换句话说，每次调用 moveDisk() 时，都应该（在完成后）发出下一个 moveDisk() 的调用。但是如何找到所有这些 moveDisk() 调用呢？经过一番思考，我问自己：为什么不使用栈（callStack）来保存 moveDisk() 的“from,to”调用参数呢？使用栈还将保留调用的顺序。这正是我所做的，也就是说，在上面的代码中注释掉 moveDisk(); 行，并取消注释 callStack.push([from,to]); 行。现在，修改后的 Hanoi() 函数是从下面给出的 executeHanoi() 函数调用的。

以下列表显示了我的脚本的完整源代码。

var callcallStack;   

function executeHanoi()
{ //  Some initialization code goes here
 
  callStack=[];  // callStack array is global

  Hanoi(diskCount, 0,2,1);
    
  moveDisk();  // moveDisk takes its parameters from callStack
}

function moveDisk()
{  if (callStack.length==0) return; 

   var param = callStack.shift(); // Get call parameters from callStack
   // Note: throughout the code, I use fromBar, toBar to refer to towers
   fromBar = param[0];
   toBar = param[1];
   // find top element in fromBar
   var elem = document.getElementById(barsInfo[fromBar].disks.pop());  
    
   moveInfo = { elem: elem,
                fromBar: fromBar,
                toBar: toBar,
                whichPos: "top", // element position property for movement
                dir: -1,  // 1 or -1
                state: "up", // move upward
                endPos:60    // end position (in pixels) for move upward
             } 

   myTimer = setInterval(animateMove,speed); // Start animation
}

调用 Hanoi() 后，callStack 将包含每个 moveDisk() 调用的一个条目。这些条目的处理由 moveDisk() 函数处理。moveDisk() 函数从 callStack 中检索一个条目，并为 animateMove() 函数设置一个 moveInfo 对象以传递数据。动画由 myTimer = setInterval(animateMove,speed) 行启动。

以下代码列表显示了 animateMove() 函数的代码。

function animateMove()
{  var elem = moveInfo.elem;
   var dir = moveInfo.dir;
   var styleInfo = window.getComputedStyle(elem);
   var pos = parseInt(styleInfo[moveInfo.whichPos]);
   
   if (((dir==1) && (pos >= moveInfo.endPos)) || 
             ((dir==-1) && (pos <= moveInfo.endPos)))
   {  // alert(moveInfo.state); 
     if (moveInfo.state == "up")
     {  moveInfo.state = "hor";
        moveInfo.whichPos ="left";
        moveInfo.dir = 1;
        if ( moveInfo.fromBar >  moveInfo.toBar) moveInfo.dir = -1;
        //alert("toBar:" + moveInfo.toBar);
        var toBar = document.getElementById("bar"+ moveInfo.toBar);
        // alert(toBar.offsetLeft); 
 
        moveInfo.endPos = toBar.offsetLeft - 
               Math.floor(elem.offsetWidth/2)+15; // 15 is half of tower width
        return;
     }

     else if (moveInfo.state  == "hor" ) // move down
     {  // alert("here");
        moveInfo.state = "down";
        moveInfo.whichPos ="top";
        moveInfo.dir = 1; 
        //alert(elem.offsetHeight);
        moveInfo.endPos = document.getElementById("bottombar").offsetTop - 
               (barsInfo[moveInfo.toBar].disks.length+1)*elem.offsetHeight;
        return; 
     }

     else // end of current call to moveDisk, issue next call
     {  clearInterval(myTimer);  // cancel timer
        barsInfo[moveInfo.toBar].disks.push(elem.id);
        moveDisk();
        return; 
     }
   }

   pos = pos + dir*moveInc;
   elem.style[moveInfo.whichPos] = pos+ "px"; 
}

animateMove() 函数基本上会将一个盘子向上移动，然后向右或向左移动（如果 toBar < fromBar），然后向下移动，最后发出对 moveDisk() 的下一个调用。请注意，在进行对 moveDisk() 的下一次调用之前，会取消计时器（使用 clearInterval(myTimer) 调用）。这是为了防止 animateMove() 错误地使用 moveInfo 对象。

局限性，建议

所提供的代码已在最新版本的流行浏览器中进行了测试。它在 IE（版本 11）、Chrome（版本 30）和 Firefox（版本 24）中运行完美。我们解决方案中的动画受 JavaScript setInterval() 函数的计时器精度的限制，该精度不能小于一毫秒。使用 window.requestAnimationFrame() 函数可能可以实现更快的动画。最后，可以通过使用 3D 图像作为盘子，在盘子向上和向下移动时部分被塔覆盖，来增强图形效果。

历史

• 2013 年 11 月 7 日：初始版本。 
• 2013 年 11 月 15 日：更新了更好的图形。
• 2015 年 11 月 7 日：对程序代码进行了少量更新，以便在单击“开始”按钮时，所有盘子都移动到最左边的列。