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 --> %c\n", 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