UVa 10795 - A Different Task

#思维 #汉诺塔问题 #递归

Published on 2016-01-16

描述

汉诺塔问题，现有 $n(n\le60)$ 个盘子，给定初始局面和目标局面，求从初始局面移动到目标局面所需要的最小步数？

样例输入

样例输出

Case 1: 7
Case 2: 3
Case 3: 0

分析

思维复杂度很高的一道题，我这里直接简要说刘汝佳的方法，代码里有对他的方法的详细注释。
首先如果第 $n$ 个盘子，也就是最大的盘子在正确的位置，它显然不需要移动也不会碍事。同理，如果在第 $n$ 个盘子正确的情况下第 $n - 1$ 个盘子也在正确的位置，它显然不需要移动也不会碍事。我们首先找到一个最小的 $k$ ，满足 $(k, n]$ 这个范围内的盘子都在正确位置，它们不碍事，所以可以看做只有 $k$ 个盘子。
我们现在想把第 $k$ 个盘子移动到正确的位置（显然最大的应该先考虑），那么我们就必须把 $[1, k)$ 这个范围内的盘子全部转移到一个中转盘子（不同于 $k$ 的起点终点），然后我们才能把第 $k$ 个盘子移动到正确的位置。我们把 $[k, n]$ 范围内的盘子在正确位置（还记得大于 $k$ 的盘子都不碍事吗）， $[1, k)$ 范围内的盘子都在中转盘子这一局面称之为参考局面。
接着我们下一步就是要从参考局面移动到目标局面，因为移动是可逆的，所以这需要的步数等价于从目标局面移动到参考局面到的步数。
定义函数 $f(\mathrm{pos}, k, \mathrm{target})$ 为盘子 $i$ 的初始位置为 $\mathrm{pos}[i]$ ，将 $[1, k]$ 的盘子全部移动到 $\mathrm{target}$ 盘子的最小步数，那么答案为

f(\mathrm{start}, k - 1, \mathrm{other}) + 1 + f(\mathrm{final}, k - 1, \mathrm{other})

其中 $\mathrm{other}$ 即刚刚的中转盘子，因为盘子只有 $1, 2, 3$ ，所以很方便计算： $\mathrm{other} = 6 - \mathrm{start}[k] - \mathrm{final}[k]$ 。而多出来的 $1$ 是要把 $k$ 移动到正确位置，以让初始局面变成参考局面。
考虑如何计算 $f(p, m, \mathrm{target})$ 。如果 $m$ 已经在正确位置 $f(p, m, \mathrm{target}) = f(p, m - 1, \mathrm{target})$ 。否则必须将 $[1, m - 1]$ 都移动到中转盘子，再将 $m$ 移动到目标，再将 $[1, m - 1]$ 也移动到目标，根据汉诺塔经典问题，最后一步所需的最小步数为 $2^{m - 1}$ 。
所以可以得到方程：

好了，题目分析完成，细节参见代码。

代码

//  Created by Sengxian on 1/16/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10795 递归思想，思维复杂度高！
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
inline int ReadInt() {
    int n = 0, ch = getchar();
    while((ch < '0' || ch > '9') && ch != EOF) ch = getchar();
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return n;
}
const int maxn = 60 + 3;
int start[maxn], final[maxn], n;

//每个牌的初始位置为 p, 要把 0 - k 移动到 target 需要的最小步数
ll f(int *p, int k, int target) {
    if(k == 0) return 0; //不需要移动了
    if(p[k] == target) return f(p, k - 1, target); //如果 k 已经在正确位置，转移为将 0 - (k - 1) 移动到 target
    return f(p, k - 1, 6 - p[k] - target) + (1LL << (k - 1)); //否则先将 0 - (k - 1) 移动到中转塔，再将 k 移动到 target，再将 0 - (k - 1) 移动到 target。
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), n) {
        for(int i = 1; i <= n; ++i) start[i] = ReadInt();
        for(int i = 1; i <= n; ++i) final[i] = ReadInt();
        int k = n;
        while(k >= 1 && start[k] == final[k]) k--; //从大到小，本来就在正确位置的不管
        ll ans = 0;
        if(k >= 1) {
            int other = 6 - start[k] - final[k];
            ans = f(start, k - 1, other) + 1 + f(final, k - 1, other);
            //参考局面: 把 k - (n - 1) 移动到正确位置，0 - (k - 1) 均在 other 位置
            //答案为从起始位置到参考位置需要的步数 (f(start, k - 1, other) + 1 多出来的1是要把 k 移动到正确位置) + 加上终极位置到参考局面需要的步数(f(final, k - 1, other))
        }
        printf("Case %d: %lld\n", ++caseNum, ans);
    }
    return 0;
}

UVa 1508 - Equipment UVa 261 - The Window Property

Sengxian's Blog