汉诺塔

问题描述：

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。假定圆盘从小到大编号为1, 2, ...

解题思路：

其实汉诺塔问题只是一个简单的数学问题，由分析易知：

如果考虑把64片金片，由一根柱子上移到另一根柱子上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里可以先进行枚举，找到对应的数学规律。假设有n片，移动次数是f(n）。则有：

由上述分析可以得到两个函数关系:   (1) f(n)=2^n-1  (2) f(n)=2*f(n-1)+1

而由我们之前在C语言中学到的函数递归知识可知，可以将数学函数关系式利用在代码中，形成一个求移动步数的函数递归式。相关代码如下：