汉诺塔
有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，
要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小
盘子上方。
--如果朋友您想转载本文章请注明转载地址"http://www.cnblogs.com/XHJT/p/3878076.html "谢谢--
问题：
1.如何移动；
2.n个盘子移动多少次(count)？
解决问题1：
为了将第n个盘子从A移动到C，就得先将第n个盘子上面的第n-1盘子移动到B上；
同样的，要想将B上的第n-1个盘子移动到C上，就得先将第n-2个盘子移动到A上。
解决问题2：
当n = 1 时,count = 1;
当n = 2 时,count = 3;
当n = 3 时,count = 7;
当n = 4 时,count = 15;
…………
根据以上可得表达式：
count(1) = 1
count(n) = 2*count(n)+1 (n>1）
即n个盘子移动的次数表达式为：
count(n) = 2^n - 1 (n>0)
用代码实现为：
package com.xhj.data;
import java.util.Scanner;
/**
* 递归算法实现汉诺塔
*
* @author XIEHEJUN
*
*/
public class HanoiTower {
/**
* 定义移动次数
*/
private static int count;
/**
* 设置移动次数的起始值
* @param count
*/
public static void setCount() {
HanoiTower.count = 1;
}
/**
* 获取移动次数
*
* @return
*/
public static int getCount() {
return count-1;
}
/**
* 移动递归
*
* @param num
* 盘子数
* @param from
* 柱子A
* @param inner
* 柱子B
* @param to
* 柱子C
*/
public static void moveDish(int num, char from, char inner, char to) {
if (num == 1) {
System.out.println("\t\t**\t"+count++ + " " + num + "号盘子从" + from + "移动到" + to);
} else {
moveDish(num - 1, from, inner, to);
System.out.println("\t\t**\t"+count++ + " " + num + "号盘子从" + from + "移动到" + to);
moveDish(num - 1, inner, from, to);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
try {
for (;;) {
System.out.print("请输入盘子的个数：");
int n = sc.nextInt();
System.out.println("\t\t**********************************");
System.out.println("\t\t**\t移动步骤为：");
setCount();
moveDish(n, 'A', 'B', 'C');
System.out.println("\t\t**\t一共移动的步数为：" + getCount());
System.out.println("\t\t**********************************");
}
} catch (Exception e) {
System.out.println("输入数据不正确，请输入整数");
main(null);
}
}
}