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

题目

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。

C 6条回复评论

卡卡卡乐星

学习学习学习

发表于 2024-04-02 23:00:00

0 0

假期

Ccccccc

发表于 2021-02-24 14:04:58

0 0

ZZZ29

正确答案应该是c

发表于 2021-02-24 13:48:58

0 0

五分i

正确答案是C

发表于 2021-02-24 11:12:23

0 0

落地成盒

tthhee

f(1) = 1;

f(2) = 3;

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

发表于 2018-10-13 14:44:30

0 0

花将离

设移动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

发表于 2018-10-13 14:44:19

0 0

问题信息

分类：数据结构 - 栈

难度:

最新校招难题刷题，快来进刷题群吧