汉诺塔进阶 递归与高精度 上
今天遇到了一道汉诺塔进阶类型的问题，需要计算汉诺塔游戏圆盘移动的次数，正好来复习下函数的递归问题还有高精度数的存储问题，本次专栏分为两部分，上部先讲前者。
问题内容及分析
这道题是一个典型的递归问题，我们只要弄清An与An-1的关系就可以很快求解。
源代码如下：
为了更直观了解函数运行过程，我们以n=3为例：
计算机运行结果：
运行结果
手动模拟结果：
手动模拟结果
经过手工的模拟计算机的运行顺序，有助于更加了解递归的本质，建议大家也可以将递归程序进行模拟。
下面进入正题，我们来了解双层汉诺塔问题。
P1096 Hanoi 双塔问题题目描述
给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。
现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：
（1）每次只能移动一个圆盘；
（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。
输入输出样例
输入 #1输出 #1
12
输入 #2输出 #2
26
要求
1n200，时间1s;
分析
这道题只是让我们计算移动的最小次数，因此看上去反而比递归容易，而实际上注意n和时间的范围我们就会发现如果用递归运算显然会出现时间超时的问题。并且这道题无需求运算过程，因此应该采用更快的递推的方式进行。同时另外一个难点就是随着n的增大，结果会出现数据爆炸的情况（举个例子，当n为50时，最后的结果是2251799813685246），为了防止溢出，我们需要采用高精度存储。
下面是我写的两种有缺陷的程序：
1.复杂，时间可能超时，且数据溢出。
2.，递推算法，速度很快不超时，但数据溢出。
解释：
第1步：将n-2个圆盘移到B柱上。
第2步：将2个最大的圆盘移到C柱上。
第3步：将n-2个圆盘移到C柱上。
因为第3步的步数=第一步的步数且第2步需用2步。
所以，这一次的总步数=第1步的步数*2+2。
代码：
因此为了大数据的输出，我们需要采用高精度存储数据，我将会在下一个专栏，总结高精度数据存储的算法。
|汉诺塔进阶、递归与高精度、上
汉诺塔 汉诺塔进阶 递归 递归与高精度 递归算法