引入

传说越南河内某间寺院有三根银棒

其中一根银棒上串 64 个金盘
金盘从上到下，由小至大。
一次只移动一片，不管在那根针上
但小片必须在大片上
从一根银棒按照同样的要求，全部移动到另外一根银棒上，任务完成

若传说属实，僧侣们需要 $2^{64}-1$步才能完成这个任务
若他们每秒可完成一个盘子的移动，就需要 5845 亿年才能完成。整个宇宙现在也不过 137 亿年。

汉诺塔玩具

玩具汉诺塔-图片来自于维基百科
(图片来自于维基百科)

在真实玩具中，一般 N=8；最少需移动 255 次。
如果 N=10，最少需移动 1023 次。
如果N=15，最少需移动32767次；
这就是说，如果一个人从 3 岁到 99 岁，每天移动一块圆盘，他最多仅能移动 15 块。
如果 N=20，最少需移动 1048575 次，即超过了一百万次。

如何用递归的算法求解汉诺塔呢？

这是一个经典的递归问题，我们可以这样考虑

ABC 三根柱子，A 上面从小到大排列着64个圆盘
我们把 A 上的63个圆盘移动到 B 上面
然后把A 最大的64号圆盘移动到 C 上面
然后再把 B 上的63个盘子逆向的移动到C上面

算法

#include <stdio.h>
void tower(int n, char a , char b , char c){
    if(n==1){
        printf("%c 移动到 %c\n",a,c);
    }else{
        tower(n-1,a,c,b);  
        printf("%c 移动到 %c\n",a,c);  
        tower(n-1,b,a,c);  
    }
}

int main(){
    int n;
    printf("请输入需要计算的层数：\n");
    scanf("%d",&n);
    printf("移动的步骤如下：\n");
    tower(n,'A','B','C');
    return 0;
}

解题思路，其实就是每次递归按照我们的要求移动一个碟子，你可以这么想

tower(n-1,a,c,b);，a 借助 c 移动到 b
printf("%c 移动到 %c\n",a,c); ，第 n 个盘子从 a 移动到 c
tower(n-1,b,a,c);，b 借助 a 移动到 c

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。