1 问题描述
有A，B，C三个柱子，A柱子上从上到下，从小到大排列着n个圆盘。现要求将A柱子上的n个圆盘全部移动到C柱子上，依然按照从上到下，从小到大的顺序排列。且对移动过程要求如下：
a）一次只能移动一个盘子。
b）移动过程中大盘子不允许出现在小盘子上方。
问：总共需要移动的步数是多少？
2 化繁为简，分析题目
从宏观角度来分析，将移动步骤分为三步：
a）将最上面的n-1个盘子移动到B柱子上
b）将最大的盘子移动到C柱子上
c）再将B柱子上的n-1个盘子移动到C柱子上
完成以上三步，即可达到目标。因此，问题转化为如何移动n-1个盘子？同样的思路解决n-1个盘子移动的问题，可以发现其中规律。假设移动n个盘子需要的步数为f(n)，则移动n-1个判断需要f(n-1)步。
因此，得到递推公式：f(n) = 2 * f(n - 1) + 1
3 求解递推公式
将上一步的递推式进行变形：f(n) + 1 = 2(f(n - 1) + 1)，设q(n) = f(n) + 1， 则q(n) = 2q(n-1)， q(n) / q(n-1) = 2，可见q(n) 是一个等比序列，q(1) = 2，因此q(n) = 2^n(n >= 1)， f(n) = 2^n - 1。
4 java编程实现递归算法
public class TowerOfHanoi { // 统计移动次数 static int count = 0; public static void main(String[] args) { char a = 'A'; char b = 'B'; char c = 'C'; int n = 3; TowerOfHanoi test = new TowerOfHanoi(); test.recurse(n, a, b, c); System.out.println(count); } // 移动一次 private void move(int n, char from, char to){ count = count + 1; System.out.println("将圆盘" + n + "号, 从" + from + "移动到" + to); } // 递归 private void recurse(int n, char a, char b, char c){ // 递归结束条件：n == 1，只一个盘子时 if (n == 1){ move(1, a, c); } else { recurse(n - 1, a, c, b); move(n, a, c); recurse(n - 1, b, a, c); } } }