汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
提示：以下是本篇文章正文内容，下面案例可供参考
public void recursion(参数0) {
if (终止条件) {
return;
}
recursion(参数1);
}
总所周知斐波那契数列是从第三个起的数等于前面两数之和。
Fib（n）=Fib(n - 1) + Fib(n - 2);
int Fib(int n)
{
if(n==0)return 0;
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
//法二
//由于第一个代码在进行比较大的数据，会有大量重复计算，所以减少了计算
int fib(int n) {
int a = 1, b = 1, c = 1;
while (n > 2) {
c = a + b;
a = b;
b = c;
n--
}
return c;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
printf("%c-->%c\n", a, c);//把最底层的盘子移到c
}
else {
hanoi(n - 1, a, c, b);//将n-1个盘子进过c柱移到b柱
printf("%c-->%c\n", a, c);//把最底层的盘子移到c
hanoi(n - 1, b, a, c); //将n - 1个盘子进过b柱移到c柱
}
}
int main() {
int m;
scanf("%d", &m);
hanoi(m, 'A', 'B', 'C');
return 0;
}
首先来看看那运行结果
当有3个盘子的时候总共运行了7次
当有4个盘子的时候总共运行了15次
当有4个盘子的时候总共运行了21次
不难发现
2^n-1
也就说汉诺塔是有规律的，有规律就有机会使用递归。
在回顾汉诺塔的操作方式，总是先把n-1经过c柱到b柱(a->c->b)，然后让最后一个移动到c柱(a->c)，再把b柱的n-1盘子经过a柱到c柱（b->a->c）
当第一次进行调试进入函数，会进入hanoi(2, a, c, b)，然后进入函数hanoi(1, a, c, b)，再进入n=1时就会打印第一步先把a柱最上面一个直接移到c柱，结束后再回到n=2的函数继续执行移动把第二个先移到c柱。
hanoi(1, b, a, c)移动后再往下走就是移动第二个盘子，再把它移动b柱
回到hanoi(3, a, c, b)，往下走打印第三个将它从a移到b
之后进入hanoi(2, b, a, c)的递归，在进入hanoi(1, a, c, b)打印第一个移到a柱
调用函数完，回到hanoi(2, b, a, c)在把第二个移动到c柱，hanoi(1, b, a, c)会将第一个从a移动c
以上就是今天要讲的内容，本文仅仅简单介绍了汉诺塔的解题过程，本人小白来的，如果有错误可以指出来哦。