|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Georgy Plechanov 2:5026/49.33 22 Jul 2002 11:30:56
To : Dmitriy Gerasimenko
Subject : Перебор чисел
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
