汉诺塔问题php解法

汉诺塔是一个有趣的智力游戏,在程序的观点中,它的解题方法是一个典形的递归:

 

假设有n个塔,要从A柱移到B柱,移的过程中,每次只能移动一个塔,大塔不能在小塔上,可以借助C柱,递归过程序如下:

1)把n-1个塔从A移到C

2)把剩下一个由A移到B

3)把n-1个由C移到B,完成

 

这其中,每一步操作都是递归,php的解法如下:

 

function hanoi($n,$x,$y,$z){
    if($n == 1) printf("从 %s 移到 %s 
",$x, $y);
    else{
        hanoi($n-1,$x,$z,$y);
        hanoi(1,$x,$y,$z);
        hanoi($n-1,$z,$y,$x);
    }
}

 

例如:hanoi(4,'A','B','C')表示有四个塔,要从A柱移到B柱,结果是:

 

从 A 移到 C
从 A 移到 B
从 C 移到 B
从 A 移到 C
从 B 移到 A
从 B 移到 C
从 A 移到 C
从 A 移到 B
从 C 移到 B
从 C 移到 A
从 B 移到 A
从 C 移到 B
从 A 移到 C
从 A 移到 B
从 C 移到 B