Перебор чисел

From

Georgy Plechanov (2:5026/49.33)

To

Dmitriy Gerasimenko

Date

2002-07-22T11:30:56Z

Area

RU.ALGORITHMS

Прогламаранж, Dmitriy!

22 Июл 02 09:08, Dmitriy Gerasimenko -> Andrey Belyakov:

 AB>> Да нет. Обычная force-атака, т.е. перебором.

 DG> Слабо верится!
 DG> Подробнее о "force-атаках" можно ?. Приведи пример, если есть.

 DG> Дмитрий
обычных, Дмитpий, мы не деpжим, но если интеpесно вот тебе умный пеpебоp
(пpога находит кол-во ваpиантов pазбиения шашматной доски nXn на 2-е
идентичные части, пеpевоpоты и отpажения за повоpот не считать)

Да, слабонеpвным пpосьба нажать Дел


* ---===* Здесь будет _Windows Clipboard_ *===--- *

class cm3
{
public:
    bool *data;     //chess tble
    int **dtab;     //depend. tabl
    bool *idt;      //init-zation dep table
    int n;          //num of el
    int side;       //side len
    int count;
    int lna;
    int beg ;
    bool left;
    bool leftz;
    bool up;
    bool upz;
    int ret;
    int cmax;

    void init(int sd)
    {
        side=sd;
        n=sd*sd/2;
        count=0;
        lna =1;


        data = new bool [n+side+10];
        idt =data+n+5;
        dtab = new int* [n];


        for(int i=0;i<n;i++)
            dtab[i] = new int [side];

        acttabgen(0);

    }

    int go(int sd,int max)
    {
        cmax=max;


        init(sd);
        return count;
    }
    bool setbeg()
    {
    lna=1;
    for(int i=0;i<side;i++)
        dtab[side-1][i]=-1;

    int c=0;
    for(int z=0;z<side;z++)
    {
    if(dtab[side-1][z]!=-1)
        continue;
    inittable(z);
    if(z==side-1)
        lna=0;
    for(int i=0;i<side;i++)
    {

        if(idt[i])
            dtab[side-1][i]=z;
    }

    }


    lna=side;
    return 1;


    }
    bool inittable(int n)
    {
        for(int i=0;i<side;i++)
            idt[i]=0;
        idt[n]=1;

        while(itabact());
        return 1;
    }
    bool itabact()
    {
        bool ret=0;
        for(int i=0;i<side;i++)
        {
            if(idt[i])
            {
            if(data[i]!=data[side-i-1]&&!idt[side-i-1])
            {
                idt[side-i-1]=1;
                ret=1;
            }
            else if(i&&data[i]==data[i-1]&&!idt[i-1])
            {idt[i-1]=1;
            ret=1;
            }
            else if(i!=side-1&&data[i]==data[i+1]&&!idt[i+1])
            {idt[i+1]=1;
            ret=1;
            }
            //if(ret)
            //  return 1;
            }

        }

        return ret;
    }

    void gettab(int num)
    {
                printf("\nvarint -","%ld",q);

                printf("\n");
                for(int y=0;y<side/2;y++)
                {
                    for(int x=0;x<side;x++)
                    {
                        if(!data[(side-x-1)+(side/2-y-1)*side])
                            printf("0");
                        else
                            printf(" ");
                    }
                    printf("\n");
                }

                for(y=0;y<side/2;y++)
                {
                    for(int x=0;x<side;x++)
                    {
                        if(data[x+y*side])
                            printf("0");
                        else
                            printf(" ");

                    }
                        printf("\n");
                }

    }

    void acttabgen(int gen)
    {
        if(gen==side)
        {
            ntab();
            return;
        }
        data[gen]=0;
        acttabgen(gen+1);


        if(gen==side/2-1||gen==side/2||gen==0)
            return;
        data[gen]=1;
        acttabgen(gen+1);

    }
    void ntab()
    {

    setbeg();
    act(side);

    }

    void act(int gen)
    {
    if(lna<0&&lna+1000>0)
        lna=2;
    if(count==cmax)
    return;
        if(gen>side&&!abrute(gen-1))
            return;
        if(gen==n||ntest(gen-1))
        {

            if(ltest())
            {
            count++;
            gettab(count);

            }
            return;
        }


        data[gen]=1;
        act(gen+1);


        data[gen]=0;
        act(gen+1);

    }
    bool ntest(int gen)
    {
        if(gen<side)return 0;
        bool z = data[gen-1]
        for(int i=gen-side;i<gen;i++)
        {
            if(data[i]!=z)return 0;
        }

        for(int i=gen-1;i<n;i++)
        {
            data[i]=z;
        }
        return 1;
    }
    void copytab(int gen)
    {
        for(int i=0;i<side;i++)
        {
            dtab[gen][i]=dtab[gen-1][i];
        }
    }
    bool abrute(int gen)
    {



            copytab(gen);
         beg = (gen)%side;
         left=0;
         leftz=0;
         up=0;
         upz=0;

         setfl(gen);

         if(!chfl(gen))//||!qutest(gen))
         {

             return 0;
         }

         dtab[gen][beg]=ret;
         if(!qutest(gen))
         {

             return 0;
         }

         return 1;
    }
    bool qutest(int gen)
    {
        bool i1=0;
        bool i0=0;
        bool c1=0;
        bool c0=0;
        for(int i=0;i<side;i++)
        {
            if(dtab[gen][i]==0)
            {
                if(data[gen+i-side]==0)
                    c0=1;
                else
                    c1=1;
            }
            else
            {
                if(data[gen+i-side]==0)
                    i0=1;
                else
                    i1=1;
            }
            if(c1&&c0)
                return 1;

        }
        if((i1&&!c1)||(i0&&!c0))
            return 0;
        return 1;
    }
    void setfl(int gen)
    {
        if(beg&&data[gen]==data[gen-1])
        {
            left=1;
            if(dtab[gen][beg-1]==0)
                leftz=1;
        }
        if(data[gen]==data[gen-side])
        {
            if(dtab[gen][beg]==0)
                upz=1;
            up=1;
        }
    }
    bool chfl(int gen)
    {
        if(up&&left)
        {
            if(leftz&&upz)
            {
                ret=0;
            }
            else if(leftz+upz)
            {
                repl(dtab[gen][beg-upz],0,gen);
                ret =0;
            }
            else
            {
                repl(dtab[gen][beg-1],dtab[gen][beg],gen);
                ret =dtab[gen][beg];
            }

        }
        else if(left)
        {   ret=dtab[gen][beg];
            dtab[gen][beg]=dtab[gen][beg-1];
            if(!isin(ret,gen))
                return 0;

            ret=dtab[gen][beg];
        }
        else if(up)
            ret=dtab[gen][beg];
        else
        {
            ret=dtab[gen][beg];
            dtab[gen][beg]=lna;
            lna++;
            if(!isin(ret,gen))
                return 0;
            ret=lna-1;
        }
        return 1;
    }
    void repl(int what,int to,int gen)
    {
        for(int i=0 ;i<side;i++)
        {
            if(dtab[gen][i]==what)
                dtab[gen][i]=to;
        }
    }
    bool isin(int what,int gen)
    {
        for(int i=0 ;i<side;i++)
        {
            if(dtab[gen][i]==what)
                break;
        }
        if(i==side)
            return 0;
        return 1;
    }
    bool ltest()
    {
        for(int i=0;i<side;i++)
        {
            if(dtab[n-1][i]!=0)
                return 0;
        }
        return 1;
    }

};
int main()
{
    cm3 c;
    c.go(8,-1);
};
* ---===*  Здесь был _Windows Clipboard_  *===--- *



-- 
 Зю?
... В подарок каждому сотому читателю мылом ушел своп!
--- написанное выше содержит ошибки
 * Origin: np: Era - Divano (Star Profile) (2:5026/49.33)