Question

10．如图，汉诺塔问题是指有3根杆子A，B，C，杆上有若干碟子，把所有的碟子从B杆移到A杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面，把B杆上的3个碟子全部移动到A杆上，则最少需要移动的次数是（　　）

• A． 12
• B． 9
• C． 6
• D． 7

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（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；
故选D．

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