汉诺塔

要把n个盘子从开始的柱子移动到最后的柱子:

(1)如果实际上只有一个盘子,那就直接移动

(2)否则用这个方法把除了盘子n(最大的盘子)之外的所有盘子从开始的柱子移动到辅助柱子

(3)把盘子n从开始柱子移动到最后的柱子

(4)用这个方法把辅助柱子上的所有盘子移动到最后的柱子上

即:

sub hanoi {

my ($n, $start, $end, $extra) = @_;

if ($n == 1) {

print “Move disk 1 from $start to $end.\n”;

} else {

hanoi($n – 1, $start, $extra, $end);

print “Move disk $n from $start to $end.\n”;

hanoi($n – 1, $extra, $end, $start);

}

}

假设一共6个盘子,调用函数:

hanoi(6, ‘A’, ‘C’, ‘B’);

 

运行结果:

Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 3 from A to B.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.
Move disk 4 from A to C.
Move disk 1 from B to C.
Move disk 2 from B to A.
Move disk 1 from C to A.
Move disk 3 from B to C.
Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 5 from A to B.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.
Move disk 3 from C to A.
Move disk 1 from B to C.
Move disk 2 from B to A.
Move disk 1 from C to A.
Move disk 4 from C to B.
Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 3 from A to B.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.
Move disk 6 from A to C.
Move disk 1 from B to C.
Move disk 2 from B to A.
Move disk 1 from C to A.
Move disk 3 from B to C.
Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 4 from B to A.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.
Move disk 3 from C to A.
Move disk 1 from B to C.
Move disk 2 from B to A.
Move disk 1 from C to A.
Move disk 5 from B to C.
Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 3 from A to B.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.
Move disk 4 from A to C.
Move disk 1 from B to C.
Move disk 2 from B to A.
Move disk 1 from C to A.
Move disk 3 from B to C.
Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.

发表回复