Question

【題目】如圖所示，在著名的漢諾塔問題中有三根針和套在一根針上的若干金屬片，按下列規(guī)則，把金屬片從一根針上全部移到另一根針上：①每次只能移動一個金屬片；②在每次移動過程中，每根針上較大的金屬片不能放在較小的金屬片上面．將n個金屬片從1號針移到3號針最少需要移動的次數記為f（n），則f（6）=（ ）
A.31
B.33
C.63
D.65

Answer 1

【答案】C
【解析】解：設f（n）是把n個盤子從1柱移到3柱過程中移動盤子之最少次數 n=1時，f（1）=1；
n=2時，小盤→2柱，大盤→3柱，小柱從2柱→3柱，完成，即h（2）=3=22﹣1；
n=3時，小盤→3柱，中盤→2柱，小柱從3柱→2柱，
[用h（2）種方法把中、小兩盤移到2柱，大盤3柱；再用h（2）種方法把中、小兩盤從2柱3柱，完成]，
f（3）=f（2）×f（2）+1=3×2+1=7=23﹣1，
f（4）=f（3）×f（3）+1=7×2+1=15=24﹣1，
…
以此類推，h（n）=h（n﹣1）×h（n﹣1）+1=2n﹣1，
∴f（6）=26﹣1=63．
故選：C．