Question

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具｡大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘｡大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘.如下图所示，从左到右有A､B､C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则:一次只能移动一个盘子且大盘子不能在小盘子上面，则移动的次数为_______(用表示)

ABC

Answer

【解析】

设n个圆盘移动次数为，，得到递推公式，计算得到答案.

设n个圆盘移动次数为，当时，易知.

当有个圆盘时，需要把上面的个圆盘移出来，把最下面的圆盘放在最下面，再把上面的个圆盘移上去，故.

即，数列是首项为，公比为的等比数列，故，.

故答案为：.