字幕君

题解 Hanoi双塔问题 - 题解

题解

/ 注册

Hanoi双塔问题 - 题解

1339 浏览 0 回复 2019-11-08

字幕君

+关注

Hanoi双塔问题题目题解_牛客竞赛OJ

https://ac.nowcoder.com/acm/problem/blogs/16642

线性递推

首先我们来看一下基本的Hanoi塔问题
图片说明
有 $n$ 个盘子，我们的目标是将起点柱 $A$ 上的盘子，借助过渡柱 $C$ 移到目标柱 $B$ 上去。其中大盘子不能压在小盘子上，一次只能移动 $1$ 个盘子。

我们来一步一步思考：

如果只有 $1$ 个盘子，那么我们只需要将这个盘子移到 $B$ 上去
如果有 $2$ 个盘子，那么就将小盘字移到 $C$ 上，再把大盘子移到 $B$ 上，再把小盘子移到大盘子上
如果移动的盘子数为 $i(i>2)$ ，那么像上图那样考虑：
我们想要移蓝色盘子，就需要把它上面的盘子全部移到过渡柱（这里不一定是 $C$ ，下同）上去

然后再把前 $n-1$ 个盘子移到目标上
所以，我们得出结论，对于移动第 $i$ 个盘子的步数，只与移动第 $i-1$ 个盘子所需步数有关
这里设 $f(i)$ 为移动 $i$ 个盘子所需的步数。
那么将前i-1个盘子移动到过渡柱上所需的步数是等同于移动到目标柱上的步数的，都为 $f(i-1)$ ;
然后需要一步操作将第 $i$ 个盘子移动到目标柱上，所需步数为 $1$
从过渡柱移 $i-1$ 个盘子到目标柱上需要步数仍为 $f(i-1)$ 不在做赘余的解释。
那么总操作数就是 $f(i)=f(i-1)+1+f(i-1)=2f(i-1)+1$
边界条件为 $f(0)=0$

通项公式

线性推是 $O(n)$ 的，虽说复杂度已经够了，但是有时还满足不了要求，因此我们需要推通项公式。
看这个递推式 $f(i)=2f(i-1)+1$
我们不妨把这个等式两边同时 $+1$
可以得到： $f(i)+1=2f(i-1)+2$
即 $f(i)+1=2(f(i-1)+1)$
这里设 $f(i)+1$ 为 $f'(i)$
那么 $f'(i)=2f'(i-1)$
所以这个通项公式就好想了吧 $f'(i)=2^{n}$
现在把这个 $+1$ 减回去，就得到了 $f(i)=2^n-1$

Hanoi双塔

其实就是把我们刚刚得到的 $f(i)$ 乘 $2$ ，为什么呢?
不妨把题意中每两个一样大小的盘子看成一块
那就变成了一个一般的Hanoi塔问题
只不过每一次移动都需要移两次而已
通项公式 $f(i)=2 \times (2^n-1)=2^{n+1}-2$
计算复杂度 $O(\log n)$ ，因为要用快速幂
但是由于要用高精，算法复杂度会比较玄学

这题坑点在于高精。因为要写高精，通项公式就更有必要了
可以考虑用python水过
代码就不挂了

通项公式有推导过程递推数学数论

举报

收藏 1

赞

评论加载中...