作者：bake

6-3古老的河內塔演算法

法國數學家Lucas在1883年介紹了一個十分經典的河內塔Tower of Hanoli智力遊戲，是典型使用遞迴式與堆疊觀念來解決問題的範例，內容是說在古印度神廟，廟中有三根木樁，天神希望和尚們把某些數量大小不同的圓盤，由第一個木樁全部移動到第三個木樁。

更精確來說，河內塔問題可以這樣形容：假設有A、B、C三個木樁和n個大小均不同的套環Disc，由小到大編號為1,2,3,…n，編號越大直徑越大。開始的時候，n個套環套進A木樁上，現在希望找到將A木樁上的套環藉著B木樁當中間橋樑，全部移到C木樁上最少次數的方法。不過在搬動時還必須遵守下列規則：

1.直徑較小的套環永遠置於直徑較大的套環上。
2.套還可任意弟由一個木樁移到其他的木樁上。
3.每一次僅能移動一個套環，而且只能從最上面的套環開始移動。

現在我們考慮n=1~3的狀況，以圖示方式為大家示範處理河內塔問題的步驟：

結論：移動了2@2-1=3次，盤子移動的次序為1,2,1(此處為盤子次序)
步驟：1->2，1->3，2->3(此處為木樁次序)

結論：移動了2@3-1=7次，盤子移動的次序為1,2,1,3,1,2,1(盤子次序)。
步驟為1->3，1->2，3->2，1->3，2->1，2->3，1->3(木樁次序)

當有4個盤子時，我們實際操作後(在此不作圖說明)，盤子移動的次序為121312141214121，而移動木樁的順序為1->2，1->3，2->3，1->2，3->1，3->2，1->2，1->3，2->3，2->1，3->1，2->3，1->2，1->3，2->3，而移動次數為2@4-1=15。
當n不大時，各位可以逐步用圖示解決，但n的值較大時，那就十分傷腦筋了。

事實上，我們可以得到一個結論，例如當有n個盤子時，可將河內塔問題歸納成三個步驟：歸納成三個步驟：

1.將n-1個盤子，從木樁移動到木樁2。
2.將第n個最大盤子，從木樁1移動到木樁3。
3.將n-1個盤子，從木樁2移動到木樁3。

由上圖中，應該發現河內塔問題是非常適合以遞迴式與堆疊來解決。因為它滿足了遞迴的兩大特性1.有反覆執行的過程、2.有停止的出口。以下則以遞迴式來表示河內塔遞迴函數的演算法。

var hanoi=(n, p1, p2, p3)=>{
         if (n==1) //遞迴出口
                         process.stdout.write(‘套環從 ‘+p1+ ‘移到 ‘+p3+’\n’);
         else {
                         hanoi(n-1, p1, p3, p2);
                         process.stdout.write(‘套環從 ‘+p1+’ 移到 ‘+p3+’\n’);
                         hanoi(n-1, p2, p1, p3);
             }
}

JS          haoni.js

var hanoi=(n, p1, p2, p3)=> {
	if (n==1) //遞迴出口
		process.stdout.write('套環從'+p1+'移到 '+p3+'\n');
	else {
		hanoi(n-1, p1, p3, p2);
		process.stdout.write('套環從 '+p1+'移到' +p3+'\n');
		hanoi(n-1, p2, p1, p3);
	}
}
const prompt = require('prompt-sync')();
const j= parseInt(prompt('請輸入所移動套環數量：'));
hanoi(j,1,2,3);

PHP          haoni.php

$n=3;
echo "您所輸入的N是{$n}<br>";
haoni($n,1,2,3);

function haoni ($j, $p1, $p2, $p3){

	switch ($j){
		case 1;
		  	echo "套環從{$p1}移到{$p3}<br>";
		    break;
		default:
			haoni($j-1,$p1, $p3, $p2);
		  	echo "套環從{$p1}移到{$p3}<br>";
		  haoni($j-1,$p2, $p1, $p3);
	}

}