三柱汉诺塔相关扩展问题

10th Jan 2010
3 min read
Tags:
algorithm,
hanoi

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

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

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

#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)\)

#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)

#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\)

#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)\)，所以在渐进意义上也达到了最优复杂度。