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．

点评：本题以实际问题为载体，考查了进行简单的合情推理，属于基础题．