Uva 算法入门经典（数据结构基础）线性表题目

r囧r小猫 2022-01-11 01:07 155阅读 0赞

这些题目都有一个共同点就是题目不容易看懂，对我们这些英语水的童鞋可是一个很大的挑战啊。。好了不废话，上题目：

[Uva101 - The Blocks Problem][] 此题最大的挑战就是难懂，这里综合一下别人的翻译。操作就是

*  move a onto b
    
     *  where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
     *  a和b都是积木的编号，先将a和b上面所有的积木都放回原处，再将a放在b上。
 *  move a over b
    
     *  where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
     *  a和b都是积木的编号，先将a上面所有的积木放回原处，再将a放在b上。（b上原有积木不动）
 *  pile a onto b
    
     *  where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
     *  a和b都是积木的编号，将a和其上面所有的积极组成的一摞整体移动到b上。在移动前要先将b上面所有的积极都放回原处。移动的一摞积木要保持原来的顺序不变。
 *  pile a over b
    
     *  where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
     *  a和b都是积木的编号，将a和其上面所有的积极组成的一摞整体移动到b所在一摞积木的最上面一个积木上。移动的一摞积木要保持原来的顺序不变。
 *  quit
    
     *  terminates manipulations in the block world.
     *  结束积木世界的操纵。

看了这些之后大概懂怎么移动了，但是就是不懂a，b分别是什么，开始以为是a和b分别有n个0 - n-1的积木，然后把a上的积木往b上的n个移动，但是分析了很久就是得不出答案给出的结果。于是继续百度，看到了这个。可以看成有n块板子，每块板子上面标记有0，1，……n - 1数字。对a板子和b板子的操作都是对板子的操作，。原来是条积木。操作就是对这些积木的编号a和b进行的操作。

分析了一下也不是很难，就动手写了。用了一个结构体保存每一个积木上面有的积木数量m和积木的编号。对其进行操作，结果吧移动想的简单了。后面看了别人写的，才搞懂。花了好长时间。这里贴代码：

#include <stdio.h>
    #include <string.h>
    struct node
    {
        int num,block[30];
    }a[30];
    int postion[30];
    
    void turnback(int x)
    {
        int i,j,pos,t=postion[x],T,s=0;
        for (i=1;i<=a[t].num;i++)
        if (a[t].block[i]==x)
            {pos=i;break;}
        for (i=pos+1;i<=a[t].num;i++)
        {
            T=a[t].block[i];
            ++a[T].num; ++s;
            for (j=a[T].num;j>=2;j--)
            a[T].block[j]=a[T].block[j-1];
            a[T].block[1]=T;
            postion[T]=T;
        }
        a[t].num=a[t].num-s;
    }
    
    void move1(int x,int y)
    {
        int i,pos,t=postion[x],T=postion[y];
        ++a[T].num;
        a[T].block[a[T].num]=x;
        for (i=1;i<=a[t].num;i++)
            if (a[t].block[i]==x)
            {pos=i;break;}
        for (i=pos;i<a[t].num;i++)
        a[t].block[i]=a[t].block[i+1];
        --a[t].num;
        postion[x]=postion[y];
    }
    void move2(int x,int y)
    {
        int i,pos,t=postion[x],T=postion[y],s=0;
        for (i=1;i<=a[t].num;i++)
            if (a[t].block[i]==x) 
            {pos=i;break;}
        for (i=pos;i<=a[t].num;i++)
        {
            ++a[T].num; ++s;
            a[T].block[a[T].num]=a[t].block[i];
            postion[a[t].block[i]]=T;
        }
        a[t].num=a[t].num-s;
    }
    int main()
    {
        char s[30],s1[30];
        int i,j,n,x,y;
        while (scanf("%d",&n)!=EOF)
        {
            for (i=0;i<n;i++)
            {a[i].num=1;
            a[i].block[1]=i;
            postion[i]=i;
            }
            while (scanf("%s",&s))
            {
                if (strcmp(s,"quit")==0) break;
                scanf("%d%s%d",&x,&s1,&y);
                if ((postion[x]!=postion[y])&&(x!=y))
                {
                    if ((strcmp(s,"move")==0)&&(strcmp(s1,"onto")==0))
                    {turnback(x); turnback(y); move1(x,y);}
                    if ((strcmp(s,"move")==0)&&(strcmp(s1,"over")==0))
                    {turnback(x); move1(x,y);}
                    if ((strcmp(s,"pile")==0)&&(strcmp(s1,"onto")==0))
                    {turnback(y); move2(x,y);}
                    if ((strcmp(s,"pile")==0)&&(strcmp(s1,"over")==0))
                    {move2(x,y);}
                }
            }
            for (i=0;i<n;i++)
            {
                printf("%d:",i);
                for (j=1;j<=a[i].num;j++)
                    printf(" %d",a[i].block[j]);
                printf("\n");
            }
        }
        return 0;
    }

[Uva101 - The Blocks Problem]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37