362，汉诺塔

算法题尽量做到难易结合，在我们看一些难题的时候偶尔也可以看一些非常简单又非常容易看懂的题，要不然算法题一直看不懂，容易打击大家的兴趣，今天来看一道非常简单又非常常见的算法题，就是汉诺塔问题，这道题我想只要是学过编程的同学都应该知道的。

关于汉诺塔的传说

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔还有另外一个版本

汉诺塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（ Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc） ，并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损， 而也就是世界末日来临之时

我们这里不去追本溯源，追究他哪个版本是正确的，我们知道有这样一道题就行，直接文字叙述可能不太直观，我们画个图来分析一下

1，当只有一个的时候

2，当只有2个的时候

3，当只有3个的时候

当n等于3的时候移动的步数就比较多了，我们就不再画图了，我们来看一个动画

4，当只有4个的时候

5，当有n个的时候

这里主要还是考察对递归的理解，其实递归我们没必要把每一步都推出来，我们只需要找到他的规律和边界条件就行了，就像前面我们讲356，青蛙跳台阶相关问题的时候，我们提到了斐波那契数列，我们只需要找到斐波那契的规律f(n)=f(n-1)+f(n-2)，和他的边界条件f(0)=f(1)=1我们就可以写出代码了，其他的我们就不用管了。

故事篇

这里我来给大家讲个故事吧，很久很久以前有一个人，名叫“孤独求败”，他和家人住在山下过着与世无争的生活，就这样每天日出而作日落而息。有一天他从山上砍柴回来，突然看到家人遇害，他悲痛欲绝，于是决定给家人报仇，但他武艺不行，而仇人的功夫很高，如果硬拼不但报不了仇，而且还会白白丢了性命，所以他决定先去习武。

那天他来到一座山上，看到一个老和尚，向他说明了缘由，老和尚听闻之后怒火中烧，一脚把门前的一个千斤石狮踢开，想帮孤独求败报仇，但又怕得罪他的仇人导致引火烧身，所以他就对孤独求败说：“此仇只有你自己能报”。

孤独求败：“可我功夫不行，根本报不了仇”。

老和尚；“别急，请跟我来”。

于是老和尚带他来到了一间很破旧的房子里，指着里面的一个满是灰尘的破柜子说；“武功秘籍就锁在这里面，你拿到钥匙打开它，把它拿回去自己修炼，等你功夫达到十级之后就可以找你的仇人报仇了”。

然后找来了他的大徒弟对孤独求败说，这是你的大师兄，钥匙你找他要，我要回去睡觉了。然后大师兄说钥匙锁在我自己的小盒子里了，我小盒子的钥匙在二师兄拿着，你先去找二师兄把我这小盒子的钥匙拿到，我把这个小盒子打开，就可以把锁柜子的钥匙给你了。

于是孤独求败又去找到了二师兄，然后二师兄说，大师兄的钥匙被我锁在了我自己的小盒子里了，我自己的小盒子的钥匙在三师兄拿着……

就这样，孤独求败一直找下去，直到找到最小的100师兄拿到钥匙，然后交给第99师兄，打开第99师兄的小盒子，拿到第98师兄的钥匙，又交给第98师兄……一直到大师兄，然后大师兄拿到钥匙打开自己的小盒子，把藏有武功秘籍的柜子钥匙交给孤独求败，这样孤独求败就拿到了武功秘籍，回家修炼去了……

孤独求败从大师兄开始到拿到武功秘籍的过程其实就是递归。

读懂了上面的故事，再来看汉诺塔问题就容易多了，我们来看下代码。

 1//表示的是把n个圆盘成功的从A移动到C
 2public static void hanoi(int n, char A, char B, char C) {
 3    if (n == 1) {
 4        //如果只有一个，直接从A移动到C即可
 5        System.out.println("从" + A + "移动到" + C);
 6    } else {
 7        //表示先把n-1个圆盘成功从A移动到B
 8        hanoi(n - 1, A, C, B);
 9        //把第n个圆盘从A移动到C
10        System.out.println("从" + A + "移动到" + C);
11        //表示把n-1个圆盘再成功从B移动到C
12        hanoi(n - 1, B, A, C);
13    }
14}

我们还可以把每个柱子看作是一个栈，大的在下面，小的在上面，所以我们也可以使用栈来实现

 1//stackA 源柱  stackB 借助柱  stackC目的柱
 2public static void move(Stack stackA, Stack stackB, Stack stackC, int n) {
 3    if (n == 1) {
 4        stackC.push(stackA.pop());
 5    } else {
 6        move(stackA, stackC, stackB, n - 1);
 7        stackC.push(stackA.pop());
 8        move(stackB, stackA, stackC, n - 1);
 9    }
10}

如果想要统计总共移了多少次，可以使用公式(2^n)-1，代码如下

1public static long hanoiCount(int n) {
2    return (1L << n) - 1;
3}

当n=63的时候，我们得到9223372036854775807，当n=64的时候就已经出现了数字溢出。