Question

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

A．12

B．15

C．17

D．19

Answer 1

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

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

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