Question

如圖，漢諾塔問題是指有3根桿子A．B．C，B桿上有若干碟子，把所有碟子從B桿移到C桿上，每次只能移動一個碟子，大的碟子不能疊在小的碟子上面．把B桿上的4個碟子全部移到C桿上，最少需要移動（　�。┐危�

A．12

B．15

C．17

D．19

Answer 1

分析：設(shè)h（n）是把n個碟子從B柱移到C柱過程中移動碟子之最少次數(shù)．當(dāng)n=1時，從B桿移到C桿上有一種方法B→C，即h（n1）=1；當(dāng)n=2時，從B桿移到C桿上分3步，即B→A，B→C，A→C，有三種方法，即h（2）=3，當(dāng)n=3時，從B桿移到C桿上分七步，即B→C，B→A，C→A，B→C，A→B，A→C，B→C，有七種方法，即h（3）=7；同理，得h（4）=15．

解答：解：設(shè)h（n）是把n個碟子從B柱移到C柱過程中移動碟子之最少次數(shù)．
當(dāng)n=1時，h（1）=1；
n=2時，當(dāng)n=2時，從B桿移到C桿上分3步，即B→A，B→C，A→C，有三種方法，即h（2）=3，
當(dāng)n=3時，從B桿移到C桿上分七步，即B→C，B→A，C→A，B→C，A→B，A→C，B→C，有七種方法，即h（3）=7；
數(shù)列{h（n）}的通項公式為h（n）=2ⁿ-1，得h（4）=15．
故選B．

點評：本題以實際問題為載體，考查了進(jìn)行簡單的合情推理，屬于基礎(chǔ)題．