c/c++语言开发共享C语言中使用递归解决汉诺塔问题

（一）汉诺塔介绍

汉诺塔（hanoi tower）问题是源于印度一个古老传说：

在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。

n=64时，假如每秒钟移动一次，共需多长时间呢？

2 ^ 64 – 1 = 18446744073709551615秒!

一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒。

这表明移完这些金片需要5845.54亿年以上。而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭！

（二）算法思想

将圆盘编号按从上到下的顺序表示为1，2，3……，n-1，n。

把所有的盘子分成两部分：上面的n-1个，第n个圆盘（即最下面的那个）。

（1）把上面的n-1个圆盘从柱子a移动到柱子b上，这一过程需要借助柱子c。

（2）把第n个圆盘从柱子a移动到柱子c上。这样第n个圆盘就放到了目标位置上。

（3）把上面的n-1个圆盘从柱子b移动到柱子c上，这一过程需要借助柱子a。

这里（1）用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。

同理（3）也用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。

（三）c语言实现

  #include     void hanoi(int n, char pillar1, char pillar2, char pillar3);    // 函数声明   void move(int n, char pillar_from, char pillar_to);     // 函数声明   int count;                                      // 全局变量     int main()  {      int n;        // 输入汉诺塔层数（即金片数量）       printf("please input the layer number of hanoi tower: ");      scanf("%d",&n);        // 目的：借助于b，把n个金片从a移动到c       hanoi(n, 'a', 'b', 'c');        return 0;  }    void hanoi(int n, char pillar1, char pillar2, char pillar3)  {      if (n == 1)      {          move(n, pillar1, pillar3);      }      else      {          // 借助于pillar3，把上面的n-1个金片从pillar1移动到pillar2           hanoi(n - 1, pillar1, pillar3, pillar2);            // 把最下面的第n个金片从pillar1移动到pillar3           move(n, pillar1, pillar3);            // 借助于pillar1，把上面的n-1个金片从pillar2移动到pillar3           hanoi(n - 1, pillar2, pillar1, pillar3);      }  }    void move(int n, char pillar_from, char pillar_to)  {      count++;    // 统计移动次数       printf("step %d: move layer %d, %c --> %cn", count, n, pillar_from, pillar_to);  }

运行结果：

  please input the layer number of hanoi tower: 1  step 1: move layer 1, a-->c    please input the layer number of hanoi tower: 2  step 1: move layer 1, a-->b  step 2: move layer 2, a-->c  step 3: move layer 1, b-->c    please input the layer number of hanoi tower: 3  step 1: move layer 1, a-->c  step 2: move layer 2, a-->b  step 3: move layer 1, c-->b  step 4: move layer 3, a-->c  step 5: move layer 1, b-->a  step 6: move layer 2, b-->c  step 7: move layer 1, a-->c