Question

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

A．12
B．15
C．17
D．19

Answer 1

【答案】分析：設(shè)h（n）是把n個(gè)碟子從B柱移到C柱過程中移動(dòng)碟子之最少次數(shù)．當(dāng)n=1時(shí)，從B桿移到C桿上有一種方法B→C，即h（n1）=1；當(dāng)n=2時(shí)，從B桿移到C桿上分3步，即B→A，B→C，A→C，有三種方法，即h（2）=3，當(dāng)n=3時(shí)，從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個(gè)碟子從B柱移到C柱過程中移動(dòng)碟子之最少次數(shù)．
當(dāng)n=1時(shí)，h（1）=1；
n=2時(shí)，當(dāng)n=2時(shí)，從B桿移到C桿上分3步，即B→A，B→C，A→C，有三種方法，即h（2）=3，
當(dāng)n=3時(shí)，從B桿移到C桿上分七步，即B→C，B→A，C→A，B→C，A→B，A→C，B→C，有七種方法，即h（3）=7；
數(shù)列{h（n）}的通項(xiàng)公式為h（n）=2ⁿ-1，得h（4）=15．
故選B．
點(diǎn)評(píng)：本題以實(shí)際問題為載體，考查了進(jìn)行簡單的合情推理，屬于基礎(chǔ)題．