C语言——汉诺塔游戏（递归典型问题）-一一网

【摘要】笔者在高三时遇到过一道以汉诺塔游戏为原型的数学填空题，印象特别深刻，记得当时用小纸片代替圆盘在桌子上反复实验。（诶，就是玩儿）
汉诺塔游戏?
汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新…

笔者在高三时遇到过一道以汉诺塔游戏为原型的数学填空题，印象特别深刻，记得当时用小纸片代替圆盘在桌子上反复实验。（诶，就是玩儿）

汉诺塔游戏?

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

稍微想一想?️

现令盘子都在最左边的A柱子上，我们要把他们移动到最右边的B柱子上，中间的柱子为B。
先考虑最简单的情况，即只有一个圆盘放在最左边的柱子上。那么要完成大梵天（笔者不知道这么引用妥不妥，哈哈哈哈）的命令就只需要A–>C（这个符号表达是笔者“自创”的，意思是将A柱上的盘子移动到C柱上）。
读者可以自行尝试一下A柱上有3个盘子的情况。

仔细想一想??

设现在有n个盘子放在A柱上，我们将移动这n个盘子的任务分为3个部分。

将n-1个盘子从A移动到B
将剩下的1个盘子，即最大的那个盘子从A移动到C
最后将B上的n-1个盘子移动到C

以上，n个盘子已经移动完毕。
读者肯定会想：？？？那么你告诉我那n-1个盘子该怎么移？？？
那我告诉你：

将n-2个盘子从A移动到B
将剩下的1个盘子，即最大的那个盘子从A移动到C
最后将B上的n-2个盘子移动到C

诶，是不是来感觉来！！！一直进行上述步骤（思考解决办法）直至我们需要解决只有1个盘子该怎么办

以上就构成了一个递归系统

递归

程序调用自身的编程技巧称为递归(recursion)。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

建立一个（简单的）数学模型

完成一个n层的汉诺塔需要的操作次数为：
$2^{n}-1$
我们可以将上式子理解为：
$2^{n}-1=2\times (2^{n-1}-1)+1$
到这里就很清晰的展示了完成n-1层的汉诺塔与完成一个n层的汉诺塔的关系。其中
$2^{n-1}-1$
就是完成n-1层汉诺塔所需要的步骤。

具体代码

//通过递归列出汉诺塔游戏的单步步骤
#include <stdio.h>
#include <time.h>
int i=0;//步数记录器，这是一个全局变量哦
int n;//盘子个数，没错，这也是一个全局变量
clock_t start, stop; //clock_t为clock()函数返回的变量类型
double duration;

int main()//这只是一个可爱的计时函数，把主要函数套在这里面对不起了?
{ void g(void);//声明函数 printf("输入总共的盘子数:"); scanf("%d",&n); printf("移动%d个盘子需要以下步骤：\n",n); start=clock(); g();//来了来了，这就是真正的主程序 stop=clock(); duration=(double)(stop-start)/CLOCKS_PER_SEC; //CLOCKS_PER_SEC为clock函数的时间单位，即时钟打点 printf("所花费的时间为%f sec\n",duration); return 0;
}

void g(void)//汉诺塔游戏中如果需要在两个杆之间调动多个盘子则必须要借助第三个盘子
{ void f(int n,char a,char b,char c);//声明函数 f(n, 'A', 'B', 'C');//给各个杆子命名从左到右依次是A，B，C，顺便传递一下参数 :-)
}

void f(int n,char a,char b,char c)//从a借助b移动到c
{ void m(char x,char y);//声明函数 if(n==1) {m(a,c);}//只有个盘子的太简单了！直接移动到c上就完事了啊！ //（这一步还有一个重要‼️作用，那就是告诉这个递归体系原点的定义） else {f(n-1,a,c,b);//先把a上的n-1个借助c移动到b上 m(a,c);//把a上剩下的一个盘子移动到c上 f(n-1,b,a,c);//把放在b上的n-1个盘子借助a移动到c上 }
}

void m(char x,char y)//这是最基本的移动函数即将某一个盘子从☝️杆子移动到另☝️杆子上
{ i++;//移动一次就要记录一次步数别忘了！！！ printf("第%d步：%c-->%c\n",i,x,y);
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46