汉诺塔公式

1. 汉诺塔公式

2n次减一！！！！！！！！！！！！

2. 如何推导汉诺塔的公式

汉诺塔通项公式

汉诺塔问题家传户晓，其问题背景不做详述，此处重点讲解在有3根柱子的情况下，汉诺塔问题求解的通项公式的推导。

问题背景：有A，B和C三根柱子，开始时n个大小互异的圆盘从小到大叠放在A柱上，现要将所有圆盘从A移到C，在移动过程中始终保持小盘在大盘之上。求移动盘子次数的最小值。
变量设置：n为圆盘个数，H（k）为n=k时移动盘子次数的最小值。
递推公式： H（k）=2H（k-1）+1。
通项公式：H（k）=2^k-1。
证明：
（1）证明递推公式：首先被移动到C盘的必定是最大的盘子，否则必定违反“在移动过程中始终保持小盘在大盘之上”的规定。既然要将最大盘移动到C，此时最大盘之上必定没有任何盘子，亦即它独自在一根柱子上，要做到这点最优做法当然是先把较小的n-1个盘子由A移动到B，剩下最大盘独自在A。将n-1个盘由A移动到B花费的最少次数为H（n-1）。此时再将最大盘由A移动到C，此时移动总次数为H（n-1）+1。接着把剩下的n-1个盘由B移动到C，花费的最少次数当然也是H（n-1）。于是得到总移动次数2H（n-1）+1.证得H（k）=2H（k-1）+1。

（2）推导通项公式。由H（k）=2H（k-1）+1得H(k)+1=2(H(k-1)+1)，于是{H(k)+1}是首项为H(1)=1，公比为2的等比数列，求得H(k)+1 = 2^k，所以H(k) = 2^k-1

3. 汉诺塔问题通项公式

通项公式：H（k）=2^k-1。
汉诺塔游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。
操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
分析：对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，但可以利用下面的方法来解决。设移动盘子数为n，为了将这n个盘子从A杆移动到C杆，可以做以下三步：
(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；
(2)将A杆中剩下的第n号盘移至C杆；
(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。
事实上，上述方法设盘子数为n, n可为任意数，该法同样适用于移动n-1个盘。因此，依据上法，可解决n -1个盘子从A杆移到B杆(第一步)或从B杆移到C杆(第三步)问题。现在，问题由移动n个盘子的操作转化为移动n-2个盘子的操作。
依据该原理，层层递推，即可将原问题转化为解决移动n -2、n -3? ? 3、2，直到移动1个盘的操作，而移动一个盘的操作是可以直接完成的。

扩展资料：
目前关于汉诺塔问题解决的一个最主要的观点认为，完成汉诺塔任务时要对圆盘的移动顺序进行预先计划和回顾性计划活动。
当问题呈现后，在开始第一步的移动之前，大多数被试都会根据设定好的目标状态，对圆盘的移动顺序进行预先计划。以决定圆盘的移动顺序，但是这种计划能力的作用可能会受到问题难度的影响。
也有研究者认为，不是计划能力而是抑制能力参与汉诺塔问题的解决过程。为了把更大的圆盘先放置于指定位置，必须让较小的圆盘暂时偏离其最终应该放置的位置，但被试的自然反应总是“尽快”将圆盘移动到最终的目的地，如此反而导致错误，使移动步数更多，完成时间更长。