汉诺塔游戏

前天在一次面试中，面试官问到我汉诺塔(Towers of Hanoi)的问题，当时只知道是递归，知道手动玩游戏怎么玩，写程序还真的忘记了。大学我记得是有写过这样的作业，还有八皇后等等，不过真的都还给老师了，哈哈哈！

然后回家看了下，
http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html
http://www.python-course.eu/towers_of_hanoi.php

汉诺塔的介绍参见http://en.wikipedia.org/wiki/Tower_of_Hanoi等等

程序如下，

#include <stdio.h>

void move(char src, char dest)
{
	printf("\nMove the top plate of %c to %c", src, dest);
}

void hanoi(int n, char a, char b, char c)
{
	if (n == 1) { // 递归结束
		move(a, c); // 最小的那个盘子
	} else {
		hanoi(n - 1, a, c, b); // step 1，把所有小于最大的盘子移动到临时的柱子上(可以借助目的柱子)
		move(a, c); // step 2，把最大的盘子移动到目的柱子上
		hanoi(n - 1, b, a, c); // step 3，把临时的柱子上的盘子移动到目的柱子上(可以借助原始柱子)，和step 1的方式一模一样

							// step 1和3都会有递归产生
	}
}

int main()
{
	int n;
	printf("\nPlz input number of the plates:");
	scanf("%d", &n);
	printf("\nMoving %d plates from A to C:", n);

	hanoi(n, 'A', 'B', 'C');

	printf("\nDone!\n");
}

如果你能看懂上面的注释，很好。如果你看不懂，也没关系，现在我们来试着详细点解释这个问题。
我们先来玩这个游戏，如图(点击图片看正常大图)，

你会发现盘子的数量和最终要花费的步数是有关系的，为2^n – 1，也就是说只有1个盘子的时候需要1步，2个盘子的时候需要3步，3个盘子的时候需要7步，以此直到天荒地老。。。

所以这种思路我们是不是可以采用递归那完成呢？
比如3个盘子的时候，我们先移动上面的2个盘子(需要3步)，再移动最大的1个盘子(需要1步)，然后再移动那2个盘子到最大的盘子上面(需要3步)，加起来一共就是7步，刚刚好。
并且2个盘子也可以同理拆分，最终会变成1个盘子的情况，1个盘子的情况很好解决，就1步，别且这也就是边界情况。

看起来这样是可以，再回头来看看程序，
step 1 ~ 3是不是很清晰了，并且step 1和3自己又会有递归产生，继续拆分，直到最后都是1个盘子的时候，递归结束。

如果不关心内部细节是不是就这样完美结束了呢？确实，如果你不关心内部细节，这样已经让人很容易的理解这个问题。但是总归会有一部分人会继续深挖。
现在我们以3个盘子为例，以程序执行的角度来看，

hanoi(3, 'A', 'B', 'C')
{
	hanoi(2, 'A', 'C', 'B');
		hanoi(1, 'A', 'B', 'C')
			move('A', 'C')
		move('A', 'B')
		hanoi(1, 'C', 'A', 'B')
			move('C', 'B')
	move('A', 'C');
	hanoi(2, 'B', 'A', 'C');
		hanoi(1, 'B', 'C', 'A')
			move('B', 'A')
		move('B', 'C')
		hanoi(1, 'A', 'B', 'C')
			move('A', 'C')
}

好像也没什么好写的，有机会看看非递归的方式来实现。

P.S.
递归有风险，使用需谨慎！