三柱汉诺塔相关扩展问题

设盘子编号为，编号大的尺寸大，有三根柱子。

输出初始局面（所有盘子都在1号柱子）到终止局面（所有盘子都在3号柱子）的最优方案。 时间复杂度： 经典递归，略。

输出最优方案中某一局面之前经过的步骤数。 时间复杂度：

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);
}

输出当前局面（不一定是最优解的中间步骤）到终止局面的最优方案。 时间复杂度：

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);
}

输出当前局面下，把所有盘子移动到任一根柱子的最优方案所需步数。 时间复杂度：

易知，必定把移动到处 否则的话，需要至少步，不会最优。 所以所在位置就是 目标柱子

注意到如果初始时都在同一个根柱子上，那就不用再管它们了。 只需考虑

之所以要移动，要么是为了给比它编号大的盘子让路，要么是因为要把它移动到目标柱子。 所以，如果要把移动到某根柱子，那么也应该移动到柱子

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);
}

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

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