导言

汉诺塔问题，最早接触到它是小时候的益智玩具，后来在学习C语言的函数递归知识时，又一次接触到了，那我想着就趁着有时间，把它实现出来，再写一篇博客分享出来。

简介

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。

操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

文字分析

三步

设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：

(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；

(2)将A杆中剩下的第n号盘移至C杆；

(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。

提示：

可以看出，第一步和第三步实现过程是一样的，所以在构造函数时，构造一个即可

然后求步数的数学表达式，我在网上学习了其他博主的文章：

设移动n个盘子所需步数为

hanoi（n）

求步数表达式为：

hanoi(n-1) + 1 + hanoi(n-1) = 2 * hanoi(n - 1) + 1

对棋子个数n的分类

n==1

那直接从A移动到C就完成了

n>1

每递推一次，n—，直到n==1

代码分析：

1.构造main函数主体

这道题中main函数只要实现输入棋子个数、以及把参数n传入hanoi函数两个功能即可

n为棋子个数

‘A’，‘B’，’C’三个字母代表三个柱子

int main()
{
  int n = 0;
  scanf("%d",&n);
  int ret = hanoi(n);
  printf("%d\n",ret);
  return 0;
}

2.创建hanoi函数实现递归

构造hanoi函数可以看文字分析部分

具体代码如下：

#include<stdio.h>
int hanoi(int n)
{
  if(n<=1)
    return 1;
  else
    return 2*hanoi(n-1)+1;
}

简易版本的代码实现：

#include<stdio.h>
int hanoi(int n)
{
  if(n<=1)
    return 1;
  else
    return 2*hanoi(n-1)+1;
}
int main()
{
  int n = 0;
  scanf("%d",&n);
  int ret = hanoi(n);
  printf("%d\n",ret);
  return 0;
}

优化版本的导入

问题：

对于玩家来说，只知道移动所需步数是不够的，玩家并不知道怎么移动，所以怎么能把每一步表示出来呢

可以再创建一个函数，表示出步骤

void move(int x, int y)
{
  printf("%c->%c\n", x, y);
}

但这就有一个问题没有解决，在回归的时候，无法把A，C两个参数传进去，这个问题由于我现在能力不足，就留到以后去解决吧。

当然，如果大家有想法或者有疑问的话，也欢迎大家可以和我沟通，共同进步，^_