必考题

考点

数据结构-栈、队列-栈

面5笔5

4个圆盘的Hanoi塔,总的移动次数为()

A.7

B.8

C.15

D.16

解答

正确答案是 C

答案为C。设f(n)为n个圆盘的hanoi塔总的移动次数，其递推方程为f(n)=f(n-1)+1+ f(n-1)=2*f(n-1)+1。理解就是先把上面n-1个圆盘移到第二个柱子上(共f(n-1)步），再把最后一个圆盘移到第三个柱子(共1步），再把第二柱子上的圆盘移动到第三个柱子上（共f(n-1)步）。而f（1）=1；于是f(2)=3,f(3)=7,f(4)=15。故答案为C。进一步，根据递推方程其实可以得出f(n) = 2^n - 1。

卡卡卡乐星

2024-04-02 23:00:00

学习学习学习

0 0

假期

2021-02-24 14:04:58

Ccccccc

0 0

ZZZ29

2021-02-24 13:48:58

正确答案应该是c

0 0

五分i

2021-02-24 11:12:23

正确答案是C

0 0

落地成盒

2018-10-13 14:44:30

tthhee

f(1) = 1;

f(2) = 3;

f(n) = 2*f(n-1)+1;

0 0

花将离

2018-10-13 14:44:19

设移动n个盘子的汉诺塔问题需要g(n)次移动操作来完成。由展示移动过程算法可知g(n)应是三部分之和。
(1) 将n个盘上面的n-1个盘子借助C桩从A桩移到B桩上，需g(n-1)次移动；
(2) 然后将A桩上第n个盘子移到C桩上（1次）；
(3) 最后，将B桩上的n-1个盘子借助A桩移到C桩上，需g(n-1)次。
因而有递归关系：
g(n)=2*g(n-1)+1
初始条件(递归出口)：
g(1)=1
即 1、3、7、15、31。。。即g(n) = 2^n -1

0 0