汉诺塔问题

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

把题目抽象出来就是：已知有A、B、C三个柱子，A柱子上有从小到大叠放的n个圆盘，现要求我们将A柱子上的圆盘移到C柱子上去，但移动的过程中，不得将大圆盘放到小圆盘上面且每次只能移动一个圆盘，问应该如何移动。

先来分析一下题目：
如果A柱子上只有一个圆盘，我们就只需要将这一个圆盘从A移到C。
如果A柱子上有两个圆盘，那么我们需要分为三部来移动：首先我们需要将最上面的圆盘从A移到B，再将最大的圆盘从A移到C，最后将B上的圆盘移到C。
如果A柱子上有四个圆盘，同样也可分成三部分走：首先将上面的三个圆盘借助C从A移到B上，再将最大的圆盘从A移到C，最后将B上的圆盘借助A移到C。

通过上面的分析，可以把这个问题分成三个步骤：
设有n个圆盘在A柱子上。
1. 将A柱子上的n-1个圆盘借助C移动到B上；
2. 将A柱子上剩下的最大的一个圆盘移到C上；
3. 将B柱子上n-1个圆盘借助A移到C上。

显然需要通过递归的方法来求解。
代码如下：

#include <stdio.h>

void Move(int i, char start, char end){
    printf("move: %c --> %c\n",start, end);
}
void hanoi(int n, char A, char B, char C){
    if(n == 1){
        Move(1, A, C);//如果 n = 1；直接将这一个从 A 搬移至 C
    }
    else{
        hanoi(n-1, A, C, B);//将n-1个盘从 A 借助 C 移动到 B
        Move(n, A, C);//将最大的盘直接从 A 移动到 C
        hanoi(n-1, B, A, C);//将 B 上的 n-1 个盘借助 B 移到 C
    }
}

int main(){
    int n;
    printf("input n:");
    scanf("%d", &n);
    hanoi(n,'A','B','C');
    return 0;
}