汉诺塔问题

基础

一共有$n$个盘子，A B C 三个柱子，要把它从A柱移动到C柱，问最少需要多少步？

这个问题可以先把A柱上面的$n-1$个圆盘移动到B柱，然后把第$n$个圆盘移动到C柱，最后把$n-1$个圆盘从B柱移动到C柱。

而把$n-1$个圆盘从B柱移动到C柱其实就是把$n$个圆盘从A柱移动到C柱的一个子问题，

所以我们就可以分治递归处理。

当然，也可以递推处理，可以很轻松的拿出它的线性递推式：

用$a_i$代表把i个物品移动到另一个柱子最小转移的次数。

把A柱上面的$n-1$个圆盘移动到B柱： $ans_{n-1}$

把第$n$个圆盘移动到C柱： $1$

把B柱上的$n-1$个圆盘移动到C柱： $ans_{n-1}$

$\therefore ans_n=2\times{ans_{n-1}}+1$

$ans_1=1$

通过简单的计算和数学归纳法，我们便可以$O(1)$求解该问题：

$ans_n=2^n-1$

这里有一道例题，在c++里，你需要用到高精度（当然你也可以用python几行糊过），因为指数函数增长得实在是太快了！

P1760

#include<bits/stdc++.h>
using namespace std;
int n,cnt=1,a[1000000];//从个位开始倒着存
void p_2(int x[])
{
    for(int i=1;i<=cnt;i++) x[i]<<=1;
    for(int i=1;i<=cnt;i++)
    {
        if(x[i]>9)
        {
            x[i+1]++;
            x[i]-=10;
        }
    }
    if(x[cnt+1]>0) cnt++;//进位后长度变化
}
int main()
{
    cin>>n;
    a[1]=1;
    for(int i=1;i<=n;i++) p_2(a);
    for(int i=cnt;i>1;i--) cout<<a[i];
    cout<<a[1]-1;
    return 0;
}

---

进阶

P4285

该题中，每个操作有了一定的优先级。

三种操作，一共六种组合：AB AC BA BC CA CB

然后就可以分类讨论求解递推式了。

具体证明过过程见此。

然后运用简单的数学归纳法得出三种情况的递推式。

然后就做完了。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<math.h>
#define int long long
using namespace std;
string s;
int x[10],n;
int solve(int x)
{
    if(x==1) return 1ll*2*pow(3,n-1)-1;
    else if(x) return 1ll*pow(2,n)-1;//正常汉诺塔问题
    else return 1ll*pow(3,n-1);
}
signed main()
{
    // while(scanf("%lld",&n)!=EOF)
    // {
        cin>>n;
        int p=0;
        memset(x,0,sizeof(x));
        for(int i=6;i>=1;i--)
        {
            cin>>s;
            x[(s[0]-'A')*3+s[1]-'A']=i;
        }
        if(x[1]>x[2])//AB>AC
        {
            if(x[3]>x[5]) p=1;//BA>BC
            else if(x[6]>x[7]) p=2;//CA>CB
        }
        //AB<AC
        else if(x[7]<x[6]) p=1;//CB<CA
        else if(x[3]>x[5]) p=2;//BA>BC
        //没有更改就是0，为第三种情况
        cout<<solve(p)<<endl;
    // }
    return 0;
}

双倍经验

该题有一道重复：UVA1414

但不要觉得就是直接c v了。

本题翻译有误，看 pdf 源文件的话，可以发现在 UVA 本题是有多组数据的，把上面的代码注释的部分写上就行。