Question

【題目】如圖所示，在著名的漢諾塔問題中，有三根高度相同的柱子和一些大小及顏色各不相同的圓盤，三根柱子分別為起始柱、輔助柱及目標柱.已知起始柱上套有個圓盤，較大的圓盤都在較小的圓盤下面.現(xiàn)把圓盤從起始柱全部移到目標柱上，規(guī)則如下：每次只能移動一個圓盤，且每次移動后，每根柱上較大的圓盤不能放在較小的圓盤上面，規(guī)定一個圓盤從任一根柱上移動到另一根柱上為一次移動.若將個圓盤從起始柱移動到目標柱上最少需要移動的次數(shù)記為，則（ ）

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

Answer 1

【答案】D

【解析】

由簡單的合情推理得：是以P（1）+1＝2為首項，2為公比的等比數(shù)列，由等比數(shù)列通項公式可得：P（n）+1＝2n，所以P（n）＝2n﹣1，得解．

設(shè)把圓盤從起始柱全部移到目標柱上最少需要移動的次數(shù)記為p（n），則把起始柱上的（除最底下的）圓盤從起始柱移動到輔助柱最少需要移動的次數(shù)記為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為公比的等比數(shù)列，

由等比數(shù)列通項公式可得：P（n）+1＝2n，所以P（n）＝2n﹣1，

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

故選：D．