三柱汉诺塔相关扩展问题

设盘子编号为$1\sim N$,编号大的尺寸大,有三根柱子$1\sim 3$。

输出初始局面(所有盘子都在1号柱子)到终止局面(所有盘子都在3号柱子)的最优方案。
时间复杂度:$O(2^N)$
经典递归,略。

输出最优方案中某一局面之前经过的步骤数。
时间复杂度:$O(N)$

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
37
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int maxdisc, int src, int dst)
{
if (pos[maxdisc] == 6-src-dst)
{
fprintf(stderr, "error: this is not a midway of the best solution.\n");
exit(1);
}
if (pos[maxdisc] == src)
{
if (maxdisc > 1)
move(maxdisc-1, src, 6-src-dst);
pos[maxdisc] = dst;
}
else
{
nmoves += 1 << maxdisc-1;
if (maxdisc > 1)
move(maxdisc-1, 6-src-dst, dst);
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &pos[i]);
move(n, 1, 3);
printf("It is a midway of the best solution and there is/are %d move(s) before.\n", nmoves);
}

输出当前局面(不一定是最优解的中间步骤)到终止局面的最优方案。
时间复杂度:$Ο(2^N)$

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
#include <cstdio>
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int disc, int dst)
{
if (pos[disc] == dst) return;
for (int i = disc-1; i; --i)
move(i, 6-pos[disc]-dst);
printf("%d: %d -> %d\n", disc, pos[disc], dst);
pos[disc] = dst;
++nmoves;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &pos[i]);
//for (int i = n-1; i; --i)
// move(i, pos[n]);
for (int i = n; i; --i)
move(i, 3);
printf("total moves: %d\n", nmoves);
}

输出当前局面下,把所有盘子移动到任一根柱子的最优方案。
时间复杂度:Ο(2^N)

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
#include <cstdio>
using namespace std;
const int N = 1000;
int pos[N+1], nmoves = 0;
void move(int disc, int dst)
{
if (pos[disc] == dst) return;
for (int i = disc-1; i; --i)
move(i, 6-pos[disc]-dst);
printf("%d: %d -> %d\n", disc, pos[disc], dst);
pos[disc] = dst;
++nmoves;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &pos[i]);
for (int i = n-1; i; --i)
move(i, pos[n]);
printf("total moves: %d\n", nmoves);
}

输出当前局面下,把所有盘子移动到任一根柱子的最优方案所需步数。
时间复杂度:$Ο(N)$

易知,必定把$1\sim N-1$移动到$N$处
否则的话,需要至少$2^{N-1}$步,不会最优。
所以$N$所在位置就是 目标柱子

注意到如果$N,N-1,\ldots,k+1$初始时都在同一个根柱子上,那就不用再管它们了。
只需考虑$k,\ldots,1$

之所以要移动$i$,要么是为了给比它编号大的盘子让路,要么是因为要把它移动到目标柱子。
所以,如果要把$i$移动到某根柱子$X$,那么$i-1,i-2,\ldots,1$也应该移动到柱子$X$

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
#include <stdio.h>
const int N = 10000;
int cnt = 0, pos[N+1];
void move(int maxdisc, int dst)
{
if (!maxdisc) return;
int src = pos[maxdisc], aux = 6-src-dst;
if (src == dst)
move(maxdisc-1, dst);
else
{
move(maxdisc-1, aux);
cnt += 1 << maxdisc-1;
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &pos[i]);
move(n-1, pos[n]);
printf("%d\n", cnt);
}

总结一下,对于求方案的问题,因为最坏情况下步骤数可以达到$Ο(2^N)$,所以以上源码在渐进意义上达到最优复杂度。

对于求步骤数(无须输出方案),以上源码时间复杂度都是$Ο(N)$,由于输入时间已达到$Ο(N)$,所以在渐进意义上也达到了最优复杂度。