汉诺塔（河内塔）题解

汉诺塔（河内塔）题解

我们定义 \(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）。