自动搬运

查看原文

来自洛谷，原作者为

	Terrific_Year AFOed on 2023.11.18

搬运于2025-08-24 21:28:47，当前版本为作者最后更新于2019-08-07 13:22:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

既然有人发了 Pascal 的高精度，怎能少得了 C++ 的呢 qwq。

题目大意：

经典汉诺塔问题，有 A，B，C 三根柱子，开始时 A 柱有 $n$ 个圆盘，圆盘大的必须放在下面（移动过程中也一样），每一步移动能且只能移动一个圆盘，求把所有圆盘移到 C 处最少步数。（据说移动 64 个圆盘到 C，世界就会毁灭。）

公式推导：

1. 当只有一个圆盘时，显然直接将圆盘移到 C 处，此时得到 $T(1)=1$ 。

2. 我们考虑 $n=k$ 是已经得到 $T(k)$，则当 $n=k+1$ 时，我们要让大盘移到 C 处，必须先用 $T(k)$ 步把 $k$ 个小盘移到 B 处（这样才能让大盘的移动没有多余步骤），然后还要再用 $T(n)$ 步将 $k$ 个小盘移到 C 处，得到 $T(k+1)=T(k)\times 2+1$。

3. $T(k+1)+1=2\times (T(k)+1)$ 可以得到 $\{T(n)+1\}$ 为公比为 $2$ 的等比数列。

4. 最终求得的公式就是广为人知的 $T(n)=2^n-1$。

这道题由于 $n$ 比较大，要使用高精度才能将结果精确计算出来。

虽然大佬们都不用手写高精度，本蒟蒻还是个大家展示一下手写的吧：

#include<bits/stdc++.h>
using namespace std;

int n,l,i,a[10000];//a倒序放每位

void mul(){//高精乘2
	for(int i=1;i<=l;i++)a[i]*=2;//每位乘2
    
	for(int i=1;i<=l;i++)//满十进一(不会出现进2的情况)
		if(a[i]>9){
			a[i+1]++;
			a[i]-=10; 
		}
        
	if(a[l+1]>0)l++;//如高位进位，长度加1
	
	return;
}

int main(){
	cin>>n;
	a[1]=1;
	l=1;//答案初始长度为1
    
	for(i=0;i<n;i++)mul();//求2^n
    
	for(i=l;i>1;i--)cout<<a[i];//打印高位
	cout<<a[1]-1;//由于不可能出现末位为0的情况，输出末位减1即可
    
	return 0;
} 

再也不见。

upd:2023/07/19 更新了题目大意及公式推导部分。