汉诺塔（河内塔）题解

· · 算法·理论

汉诺塔（河内塔）题解

我们定义 T_n 为根据规则将 n 个圆盘从一根柱子移动到另一根柱子的最少移动步数，按照这样的定义，本道题的答案实际上就是 T_n。

通过手动模拟，可得到 T_1=1,T_2=3。同时显然有 T_0=0,即表示 0 个圆盘根本无需做任何移动。

接着我们开始考虑大的情形：怎样才能移动一个大的塔呢？通过移动 3 个圆盘的试验发现，得先将前两个小的圆盘移动到第二根柱子上，再将最大的那个圆盘移到第三根柱子上，最后把那两个小圆盘移到最大的圆盘上面。

这给了我们启发：首先将 n-1 个小的圆盘移动到第二根柱子上（需要 T_{n-1} 次移动），再将最大的圆盘移动到第三根柱子上（需要 1 次移动），最后把 n-1 个圆盘移回最大的圆盘上面（再需要 T_{n-1} 次移动）。这样，就需要 2T_{n-1}+1 次移动就能移动 n （n＞0）个圆盘了，发现可以对子问题进行求解，故采用递推（递归）的形式。

用式子表示即：T_n=2T_{n-1}+1，这样可以O(n) 的时间复杂度通过。

#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
ull n,T[65];
int main(){cin>>n;
    for(int i=1;i<=n;i++)T[i]=2*T[i-1]+1;
    cout<<T[n];
}

我们会注意到 T_3=7,T_4=15,T_5=31,T_6=63。

发现 7=2^3-1,15=2^4-1,31=2^5-1,63=2^6-1。

所以我们假设 T_n=2^n-1，通过数学归纳法证明得出 T_n=2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1。

所以又有如下代码,时间复杂度同样是 O(n),但空间复杂度从 O(n) 优化到 O(1)：

#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
ull n,pw=1;
int main(){cin>>n;
    for(int i=1;i<=n;i++)pw*=2;
    cout<<pw-1;
}

空间是优化不了了，再考虑优化时间。我们发现我们推的式子里有 2^n ,考虑快速幂将时间复杂度优化成 O(logn)。

前置知识：x^k中，x为底数，k 为指数；x^{a+b}=x^a×x^b，

考虑将 n 表示成二进制的形式。 举个例子：假设我们要计算 2^{11}，实际转变为求 2^{(1011)_2}。考虑把这个二进制数拆开成每一位。得到 2^{(0001)_2}×2^{(0010)_2}×2^{(1000)_2}。再把它们的指数重新表示为十进制数。即 2^1×2^2×2^8。实际上只需要把底数不断平方就可以算出它们，具体的可以自己上网学习。

所以我们就可以用 O(logn) 的时间复杂度通过。

#include<bits/stdc++.h>             //此代码浅压 
#define ull unsigned long long 
using namespace std;
ull n;
ull ksm(ull x,ull k){ull sum=1;
    while(k){if(k&1)sum*=x;
        x*=x,k>>=1;
    }
    return sum;
}
int main(){
    cin>>n,cout<<ksm(2,n)-1;
}

对于这道题实际只需 O(n)，如果题目要求结果取模，则 n 可以开到 10^7；若 O(logn) ，则 n 至少可以开到 10^{18}。若 n 再开大一些，则考虑用字符串来保存 n，并使用高精除。

总结（引用于《具体数学》）：汉诺塔的递推（递归）式是在各种应用中出现的诸多问题的典范，在寻求像 T_n 这样有意义的量的封闭形式的表达式时，我们经过了如下三个阶段：

（1）研究小的情形，这有助于我们洞察该问题，且对第二第三阶段有所帮助。

（2）对有意义的量求出数学表达式（并证明）。

（3）对数学表达式求出封闭形式（并证明）。

感谢观看，求赞（qwq）。