汉诺塔原理详解+变式例题

一.汉诺塔详解

1.详解

汉诺塔
汉诺塔
在汉诺塔游戏中，有三个分别命名为A、B、C得塔座，几个大小各不相同，从小到大一次编号得圆盘，每个原盘中间有一个小孔。最初，所有得圆盘都在A塔座上，其中最大得圆盘在最下面，然后是第二大，以此类推.

　　　　游戏的目的是将所有的圆盘从塔座A移动到塔座B;塔座C用来防止临时圆盘,游戏的规则如下:
　　　　1、一次只能移动一个圆盘
　　　　2、任何时候都不能将一个较大的圆盘压在较小的圆盘上面.
　　　　3、除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.
　　汉诺塔问题解决思想:
　　　　在解决汉诺塔问题时,事实上,我们不是关心圆盘1开始应该挪到哪个塔座上,而是关心最下面的圆盘4.当然,我们不能直接移动圆盘4,但是圆盘4最终将从塔座A移动到塔座B.按照游戏规则,在移动圆盘4之前的情况一定如下图

　　 我们仍将分析,如何将前三个圆盘从A移动到C,然后圆盘4从A移动到B,前三个圆盘从C再移动到B.
　　但是上面的步骤可以重复利用!例如将三个圆盘从A移动到C,那么应该先将前两个圆盘从A移动到B,然后将圆盘3从A移动到C,最后将前两个圆盘从B移动到C.
　　持续简化这个问题,最终我们将只需要处理一个圆盘从一个塔座移动到另一个塔座的问题.
我们先来想一下我们人类应该怎样操作吧。

我们每次操作都会这样问自己：我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢？

我们必须也只能用这么几个参数：

需要移动的盘子的总数，3个柱子。

所以函数头为：

void hanoi(int n, char x, char y, char z)

其中，n代表盘子总数，x，y，z代表柱子

hanoi(n, x, y, z)的意思就是：将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。

那不就完了！

hanoi(n, ‘A’, ‘B’, ‘C’)就是这道问题的答案！

那么这一步的前一步是什么？

记住了，在求解f(n, other variables)的时候，我们直接默认f(n - 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。

我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想

那么，前一步也就是f(n - 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上

2.完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=1e9+7;
ll cnt,n;
void move(ll id,char from,char to)
{
    printf ("step %lld: move %lld from %c->%c\n", ++cnt, id, from, to);
}
void hanoi(ll n,char x,char y,char z)
{
    if(n==0)
        return;
    hanoi(n-1,x,z,y);//把n-1个盘子全部从X经过z移动到y柱上
    move(n,x,z);//偷偷把第n个盘子从x移动到z上
    hanoi(n-1,y,x,z);//把n-1个盘子从y经过x移动到z柱上，结束
}

int main()
{
    cin>>n;
    hanoi(n,'A','B','C');
    return 0;
}

二.汉诺塔公式：ans=2ⁿ-1

1.例题：P1760 通天之汉诺塔

P1760 通天之汉诺塔
输入表示一共就n个圆盘，输出s，表示需要s步（n<15000）
思路：
数据非常大，需要打高精，人生苦短，我选python

n=int(input())# 必须转成int哦，python用input输入的是字符串
print(pow(2,n)-1)

三.变式1：牛牛的汉诺塔

牛牛的汉诺塔

输入：
3

就是按照经典汉诺塔的写法写递归函数，然后再写一个结构体，巧妙地用数组把六种情况存起来即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=1e9+7;
ll cnt,n;
struct node
{
    ll date[6];
    node()
    {
        memset(date,0,sizeof date);
    }
    //a->b 0
    //a->c 1
    //b->a 2
    //b->c 3
    //c->a 4
    //c->b 5
};
node dp[3][3][3][105];
bool vis[3][3][3][105];
node operator+(const node &a,const node &b)
{
    node c;
    for(ll i=0;i<=5;++i)
    {
        c.date[i]=a.date[i]+b.date[i];
    }
    return c;
}
void moveto(ll x,ll y,node &temp)
{
    if(x==0&&y==1)++temp.date[0];
    if(x==0&&y==2)++temp.date[1];
    if(x==1&&y==0)++temp.date[2];
    if(x==1&&y==2)++temp.date[3];
    if(x==2&&y==0)++temp.date[4];
    if(x==2&&y==1)++temp.date[5];
    return;
}
node hanoi(ll a,ll b,ll c,ll n)//把a经过b移动到c柱上（第n个）
{
    if(vis[a][b][c][n])return dp[a][b][c][n];
    if(n==1)
    {
        moveto(a,c,dp[a][b][c][n]);
        vis[a][b][c][n]=true;//标记一下
        return dp[a][b][c][n];
    }
    node temp;//普通的hanoi塔
    temp=temp+hanoi(a,c,b,n-1);//先把n-1个从a经过c移动到b
    moveto(a,c,temp);//把第n个直接从a移动到c
    temp=temp+hanoi(b,a,c,n-1);//再把刚刚那n-1个从b经过a移动到c
    vis[a][b][c][n]=true;//完成！
    return dp[a][b][c][n]=temp;
}
int main()
{
    cin>>n;
    node ans=hanoi(0,1,2,n);
    printf("A->B:%lld\n",ans.date[0]);
    printf("A->C:%lld\n",ans.date[1]);
    printf("B->A:%lld\n",ans.date[2]);
    printf("B->C:%lld\n",ans.date[3]);
    printf("C->A:%lld\n",ans.date[4]);
    printf("C->B:%lld\n",ans.date[5]);
    printf("SUM:%lld\n",(ll(1)<<n)-1);//公式ans=2^n-1
}

四.变式2：P4285 [SHOI2008]汉诺塔

P4285 [SHOI2008]汉诺塔
题目描述
汉诺塔由三根柱子（分别用A、B、C表示）和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上，大的在下面，小的在上面，形成了一个塔状的锥形体。 对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。我们可以用两个字母来描述一次操作：第一个字母代表起始柱子，第二个字母代表目标柱子。例如，AB就是把柱子A最上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子A移动到柱子B或柱子C上面。 有一种非常简洁而经典的策略可以帮助我们完成这个游戏。首先，在任何操作执行之前，我们以任意的次序为六种操作（AB、AC、BA、BC、CA和CB）赋予不同的优先级，然后，我们总是选择符合以下两个条件的操作来移动盘子，直到所有的盘子都从柱子A移动到另一根柱子： （1）这种操作是所有合法操作中优先级最高的； （2）这种操作所要移动的盘子不是上一次操作所移动的那个盘子。 可以证明，上述策略一定能完成汉诺塔游戏。现在你的任务就是假设给定了每种操作的优先级，计算按照上述策略操作汉诺塔移动所需要的步骤数。

输入格式
输入有两行。第一行为一个整数n（1≤n≤30），代表盘子的个数。第二行是一串大写的ABC字符，代表六种操作的优先级，靠前的操作具有较高的优先级。每种操作都由一个空格隔开。

输出格式
只需输出一个数，这个数表示移动的次数。我们保证答案不会超过10的18次方。
输入输出样例
输入

3
AB BC CA BA CB AC

输出

7

输入

2
AB BA CA BC CB AC

输出

5

说明/提示
对于20%的数据，n ≤ 10。 对于100%的数据，n ≤ 30。