nyoj89 汉诺塔（二）

题目网址：http://acm.nyist.net/JudgeOnline/problem.php?pid=89

汉诺塔问题的经典结论：

把i个盘子从一个柱子整体移到另一个柱子最少需要步数是 2的i次方减一。那我们这个给定一个初始局面，求他到目标局面（全部移到第三个柱子上）需要的最少步数。怎么办呢！！分析：

1、总的来说一定是先把最大的盘子移到第三个柱子上，然后再把第二大的移到柱子3上，然后再把第三大的盘子移到柱子3上.........直到把最小的盘子（1号盘子）移到柱子3上，才算结束。

2、现在设想一下，在移动第k个盘子动作前，柱子上的整体情况，假设盘子k在柱子1上，要移到柱子3上，由于那些比k大的盘子都已经移动完了，就不需要考虑了。那么此时那些所有比k小的盘子都应该在柱子2上，因为他们不能在柱子1、3上，并且此时柱子2上的盘子从上到下盘子编号依次为1，2, 3.......k-1。

3、找出最大的盘子，先从最大的盘子开始移动，如果最大的盘子已经在柱子3（目标柱子）上那就不用移动了。所以我们应该找出不在柱子3上的最大盘子。

4、我们在这里先说一下这个函数ac（i, x）表示前i个盘子全部移到地x个柱子上所需的最少步数。那k个盘子（在柱子1上）举例：把盘子k移到柱子3上前一瞬间柱子上的情况是：1到k-1个盘子都在柱子2上， k在1上。ac（k-1, 2）就是移动到之一状态所需的步数。此时k移到柱子3需要1步。要想把所有盘子移到3上，还需将2上 1~k-1 个盘子全部移到柱子3上。又已知经典汉诺塔结论移动k-1个盘子需要2的k-1次幂减一。那么也就得出总共需要步数为：ac(k-1, 2) + 1 + pow(2, k-1) - 1 = ac(k-1, 2) + pow(2, k-1);

#include<iostream>

#include<cstdio>

#include<string.h>

#include<math.h>

using namespace std;

long long ans, a[][];

int t, n, mx, star[];

long long ac(int x, int t)

{

    if(x == )

    {

        if(star[x] == t)

            return ;

        else

            return ;

    }

    if(a[x][t] != -) return a[x][t];

    if(star[x] == t)//如果第x个盘子已经在目标柱子上了那就不移动了， 直接考虑移动下一个

        a[x][t] = ac(x-, t);

    else

        a[x][t] = ac(x-, -t-star[x]) + pow(, x-);

    //三个盘子编号总和6， 不能在目标柱t子上， 又不能和要移动的盘子x在一个柱子， 只能在6-t-satr[x]上

    return a[x][t];

}

int main()

{

    cin >> t;

    while(t--)

    {

        memset(a, -, sizeof(a));

        scanf("%d", &n);

        mx = ;

        for(int i = ; i <= n; i++)

        {

            scanf("%d", &star[i]);

            if(i > mx && star[i] != )

                mx = i;

        }

        if(mx == )

            printf("0\n");

        else if(mx == )

            printf("1\n");

        else if(mx > )

        {

            ans = ac(mx-, -star[mx]);

            ans += pow(, mx-);

            printf("%ld\n", ans);

        }

    }

    return ;

}

巴特西

nyoj89 汉诺塔（二）

最新文章

热门文章