汉诺塔问题是源于印度一个古老传说的益智玩具。要求将圆盘从A柱移动到C柱规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
可以先通过3个盘子的hanoi游戏得出其算法步骤如下：
if
n=1 , 直接将圆盘移到c棒
if n>1
,
将A棒上的n-1个圆盘移到B棒上
将A棒上的1个圆盘移到C棒上
将B棒上的n-1个圆盘移到C棒上
（图：3个盘子时第一步和第二步如上图所示）
用Java的实现代码如下
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 |
package
cn.myseu.test.hanoi;public class Hanoi { public
static void main(String[] args) { hanoi(3,‘A‘,‘B‘,‘C‘); } /** * the implementation of hanoi, move all the plates from stick-src to stick-dest * @param n the amount of plates * @param src the first stick * @param assist the middle stick * @param dest the destination stick */ public
static void hanoi(int
n,char src,char
mid,char
dest){ if
(n==1){ move(src,dest); } else{ //move n-1 plates from stick-src to stick-mid ,assisted by stick-dest hanoi(n-1,src,dest,mid); //move the left 1 plate to the stick-dest directly move(src,dest); //move the left n-1 plates from stick-mid to sitck-dest hanoi(n-1,mid,src,dest); } } public
static void move(char
src,char
dest){ System.out.println("Move the plate from "
+ src +" to "+" dest "); }} |
算法分析：
n = 1 时，只需要移动一次即可完成任务
n > 1 时，需要 (2^n -1) 次，该算法的时间效率为O(2^n)
补充一句：
对时间效率为指数级的O(2^n)算法，以及数量级等同于O(2^n)的O(n!)算法，用现在的计算机处理无法得到结果
汉诺塔问题的算法分析与实现（Java）,布布扣,bubuko.com
原文：http://www.cnblogs.com/chenying99/p/3675843.html
