多柱汉诺塔问题。
引用自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 ;
}