SGU 202. The Towers of Hanoi Revisited

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

多柱汉诺塔问题。

引用自wiki百科

多塔汉诺塔问题

在有3个柱子时，所需步数的公式较简单，但对于4个以上柱子的汉诺塔尚未得到通用公式，但有一递归公式（ 未得到证明，但目前为止没有找到反例 ）：

令为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：

对于任何移动方法，必定会先将个圆盘移动到一个中间柱子上，再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上，最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为。

进行最优化，易得: 。

 #include <bits/stdc++.h>

 #define rep(_i, _n) for(int _i = 1; _i <= _n; ++_i)

 typedef long long LL;

 typedef double    DB;

 const int inf = (INT_MAX / ) - ;

 using namespace std;

 const int maxn =  + ;

 int n, m;

 int f[maxn][maxn], pos[maxn][maxn];

 void dfs(int a, int b) {

     if(f[a][b] != -) return ;

     f[a][b] = inf;

     if(b < ) return ;

     rep(r, a - ) {

         dfs(r, b);

         dfs(a - r, b - );

         int tmp = f[r][b] *  + f[a - r][b - ];

         if(tmp < f[a][b]) {

             f[a][b] = tmp;

             pos[a][b] = r;

         }

     }

 }

 int tower[maxn][maxn], num[maxn];

 void print(int s, int t, int a, int b) {

     if(a == ) {

         printf("move %d from %d to %d ", tower[s][num[s]], s, t);

         if(num[t] != ) printf("atop %d", tower[t][num[t]]);

         puts("");

         tower[t][++num[t]] = tower[s][num[s]--];

         return ;

     }

     rep(i, m) if(i != s && i != t) {

         if(tower[i][num[i]] > tower[s][num[s] - pos[a][b] + ]) {

             print(s, i, pos[a][b], b);

             print(s, t, a - pos[a][b], b - );

             print(i, t, pos[a][b], b);

             return ;

         }

     }

 }

 int main() {

 #ifndef ONLINE_JUDGE

     freopen("data.in", "r", stdin), freopen("data.out", "w", stdout);

 #endif

     cin >> n >> m;

     memset(f, -, sizeof f);

     rep(i, m) f[][i] = ;

     dfs(n, m);

     cout << f[n][m] << '\n';

     for(int i = n;  < i; --i) tower[][++num[]] = i;

     rep(i, m) tower[i][] = inf;

     print(, m, n, m);

     return ;

 }