C语言递归小游戏—汉诺塔（hanoi）

前言：

汉诺塔大家都不陌生吧，在猩球崛起这个电影里，人们通过凯撒玩汉诺塔知道了它的智商增高了，这个益智小游戏的规则就是：

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

动画演示就是这样：

对于这个小游戏，其实用到了递归的思想。

移动两层汉诺塔的步骤：

这样的话，我们推算n层汉诺塔的实现。

我们需要做的步骤便是：

用代码来演示一下：

设计函数hanoi：

hanoi(unsigned int n,char a,char b,char c);

其中n代表汉诺塔层数，用a,b,c来演示三个柱子间盘子的移动。

代码：

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

void move(char a, char b)
{
    printf("%c -> %c
", a,b);           //打印盘子需要移动的方向
}

void hanoti(unsigned int n,char a,char b,char c)
{
    if (n == 1)
        move(a, c);
    else
    {
        hanoti(n - 1, a, c, b);
        move(a, c);
        hanoti(n - 1, b, a, c);
    }
}


int main()
{
    unsigned int n = 0;
    scanf("%d", &n);                    //输入几层汉诺塔
    hanoti(n,A,B,C);
    return 0;
}

那演示一下3个盘子的移动验证函数正确性：

结果正确。

总结：

递归是函数解决问题的一种重要方式，掌握和熟练应用递归函数可以解决复杂问题。