Question

如图所示，在著名的汉诺塔问题中，有三根高度相同的柱子和一些大小及颜色各不相同的圆盘，三根柱子分别为起始柱、辅助柱及目标柱.已知起始柱上套有个圆盘，较大的圆盘都在较小的圆盘下面.现把圆盘从起始柱全部移到目标柱上，规则如下：每次只能移动一个圆盘，且每次移动后，每根柱上较大的圆盘不能放在较小的圆盘上面，规定一个圆盘从任一根柱上移动到另一根柱上为一次移动.若将个圆盘从起始柱移动到目标柱上最少需要移动的次数记为，则（   ）

A. 33 B. 31 C. 17 D. 15

Answer

D

【解析】

由简单的合情推理得：是以P（1）+1＝2为首项，2为公比的等比数列，由等比数列通项公式可得：P（n）+1＝2n，所以P（n）＝2n﹣1，得解．

设把圆盘从起始柱全部移到目标柱上最少需要移动的次数记为p（n），则把起始柱上的（除最底下的）圆盘从起始柱移动到辅助柱最少需要移动的次数记为p（n﹣1），

则有P（n）＝2P（n﹣1）+1，

则有P（n）+1＝2[P（n﹣1）+1]，又P（1）＝1，

即是以P（1）+1＝2为首项，2为公比的等比数列，

由等比数列通项公式可得：P（n）+1＝2n，所以P（n）＝2n﹣1，

即P（4）＝24﹣1＝15，

故选：D．