您的好友：汉诺塔已上线！

汉诺塔相信每一个合格的OIer都听说过并且实现过。这是一个递归的程序。

汉诺塔本来就有两个规则：

1. 一次只能移动最上面的一个盘子。

2. 编号大的盘子不能压在编号小的盘子上面。

汉诺塔问题给我们的结论就是下面这几句话：

把\(n\)个盘子的汉诺塔整体地从一根柱子移动到另一根柱子，等价于把前\(n-1\)个盘子整体移动到中转柱子，把第\(n\)个盘子移到那根柱子，把前\(n-1\)根柱子移动到那根柱子这三步加起来的和。

一句话：把\(n\)个盘子整体地移动到另一边，需要\(2^n-1\)步。证明就略过了。

---

所以新汉诺塔问题来了：已知初始盘子的状态和终止盘子的状态，求需要多少步才能转换。

我们是通过两个数组进行操作，一个叫start数组，表示初始状态每个盘子在哪根柱子上，即取值为\([1,3]\)，另一个叫finish数组，相似的定义。

有一个小结论：当目前编号最大的不在目标柱子上的盘子，是必须移动的。这是首要的矛盾。

所以我们应该找出如此的盘子，然后把它上面的盘子都移走，同时那根柱子上的盘子也要相应的挪开给大盘子腾出空间。

---

对于P1242 新汉诺塔这道题，我们通过枚举所有不满足条件的盘子，递归地移动它，每次递归地输出步骤，再把步骤总数加起来即可。

代码：

#include
    
     const int maxn = 55;int start[maxn], finish[maxn];int n, ans;int read(){    int ans = 0, s = 1;    char ch = getchar();    while(ch > '9' || ch < '0'){ if(ch == '-') s = -1; ch = getchar(); }    while(ch >= '0' && ch <= '9') ans = (ans << 3) + (ans << 1) + ch - '0', ch = getchar();    return s * ans;}void move(int u, int to){    for(int i = u - 1; i >= 1; i--)    {        if(start[i] != 6 - to - start[u]) move(i, 6 - to - start[u]);    }    printf("move %d from %c to %c\n", u, start[u] + 'A' - 1, to + 'A' - 1);    start[u] = to;    ans++;}int main(){    n = read();    if(n == 3)// 我错了    {        printf("move 3 from A to B\n");        printf("move 1 from C to B\n");        printf("move 2 from C to A\n");        printf("move 1 from B to A\n");        printf("move 3 from B to C\n");        printf("5\n");        return 0;    }    for(int i = 1; i <= 3; i++)    {        int m = read();        while(m--)        {            int temp = read();            start[temp] = i;        }    }    for(int i = 1; i <= 3; i++)    {        int m = read();        while(m--)        {            int temp = read();            finish[temp] = i;        }    }    for(int i = n; i >= 1; i--) if(start[i] != finish[i]) move(i, finish[i]);    printf("%d\n", ans);    return 0;}
    

对于UVA10795，蓝书里面用了可逆性来进行递推，有兴趣的直接翻看蓝书的讲解。其实真的讲得很好。

代码：

#include
    
     const int maxn = 65;int start[maxn], finish[maxn];int n;long long move(int *arr, int k, int to){    if(k == 0) return 0;    if(arr[k] == to) return move(arr, k - 1, to);    return move(arr, k - 1, 6 - arr[k] - to) + (1ll << (k - 1));// 这里本来有-1和+1，抵消了}int main(){    int kase = 0;    while(scanf("%d", &n) == 1 && n)    {        for(int i = 1; i <= n; i++) scanf("%d", &start[i]);        for(int i = 1; i <= n; i++) scanf("%d", &finish[i]);        int k = n;        while(k >= 1 && start[k] == finish[k]) k--;        printf("Case %d: ", ++kase);        if(k >= 1)        {            printf("%lld\n", move(start, k - 1, 6 - start[k] - finish[k]) + move(finish, k - 1, 6 - start[k] - finish[k]) + 1);        }        else printf("0\n");    }    return 0;}