汉诺塔问题的变形，给定初始局面和目标局面，问最少多少步可以把初始局面变成目标局面。
找到初始位置和目标位置不同的最大盘子X，那么比这个盘子还大的盘子就可以无视掉了。因为他们既不会被移动也不需要被移动。
我们设f(p[],x,final)为当前初始状态为p,要把比x小的盘子移动到柱子final的最少步数那么有f(p[],x,final)=f(p[],x-1,6-final-p[x])+2^(x-1)-1+1
意思就是先把比x-1小的都移动到柱子6-final-p[x]，然后把x-1移动到final，然后把比x-1小的盘子移动到final
有了这个式子之后，我们要求的答案可以分解成，从开始局面开始，把比X小的盘子全部移动到中转位置，然后移动X，然后在移动到目标局面即可。最后移动到目标局面可以看成是从目标局面移动到中转位置，那么答案就是
ans=f(start[],X,6 – start[X] – final[X]) + f(final[],X,6 – start[X] – final[X]) + 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 |
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using
namespace
std;typedef
long
long
LL;const
int
maxn = 70;int
start[maxn],finish[maxn];LL f(int
P[],int
i,int
fin) { if(i == 0) return
0; if(P[i] == fin) return
f(P,i - 1,fin); return
f(P,i - 1,6 - P[i] - fin) + 1 + (1LL << (i - 1)) - 1;}int
main() { int
n,kase = 1; while(scanf("%d",&n),n) { LL ans = 0LL; for(int
i = 1;i <= n;i++) { scanf("%d",&start[i]); } for(int
i = 1;i <= n;i++) { scanf("%d",&finish[i]); } for(int
i = n;i >= 1;i--) if(start[i] != finish[i]) { ans = f(start,i - 1,6 - start[i] - finish[i]) + f(finish,i - 1,6 - start[i] - finish[i]) + 1; break; } cout << "Case "
<< kase << ": "
<< ans << endl; kase++; } return
0;} |
总结：汉诺塔类问题关键就是要找到一个会重叠出现的状态，然后写出递归式求解，中间也可以利用一些数学结论和技巧，比如可逆性。
原文：http://www.cnblogs.com/rolight/p/3541396.html