题解 P1760 【通天之汉诺塔】

· · 题解

既然有人发了 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。

  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 更新了题目大意及公式推导部分。