On 19 Oct 01, at 15:13,  wrote:
> Hi Coders!
Szevasz,
> Mikent lehet bejarni algoritmikusan egy
> NxN (N>=2) matrixot (gyki. 8x8 ill. 16x16).
>
> A lenyeg, hogy minden kockara
> csak egyszer lephetunk.
....
> Lehetoleg jo trukkosok
Csinalhatsz mondjuk olyat, hogy veszel egy N-nel nagyobb 2
hatvanyt, ez legyen 2^X. Eztan novelsz egy szamot egyesevel 0-tol
(2^(2*X)-1)-ig. Ez tehat egy 2*X hosszu bitsorozat lesz, es a szam
minden ilyen erteket felvesz. Minden lepesben a szambol eloallitod
a ket indexet ugy, hogy akarmilyen modon kiveszel X darab bitet
az egyik szamhoz, a maradek X darab bitet a masik szamhoz. A
szamot a bitekbol akarmilyen sorrendben osszeallithatod, xor-
olhatod egy masik X hosszu bitsorozattal, stb. Vegulis igy lesz ket
X bites szamod, amik teljesen osszevissza sorrendben kovetik
egymast ahogy egyesevel noveled a szulojuket. Azokat az index
parokat persze kihagyod, amikben legalabb az egyik kialakult
szam erteke nagyobb, mint N.
Pl. egy egyszerubbik fajta kutyulas: (N<=32 eseten 5+5 bit
elegendo a ket indexhez, szoval a szamolas 1023-ig megy)
int bit(int b, int x)
{
if (x & (1<<b)) return 1; // az x szam b bitje 1-es
else return 0;
}
int otbit(int b4, int b3, int b2, int b1, int b0)
{
return b0+2*(b1+2*(b2+2*(b3+2*b4)));
}
for (int i=0; i<1024; i++) {
int x = otbit(bit(0,i), bit(2,i), bit(4,i), bit(6,i), bit(8,i));
int y = otbit(bit(1,i), bit(3,i), bit(5,i), bit(7,i), bit(9,i));
x ^= 23; // invertalunk nehany bitet: 10111
y ^= 17; // mas biteket invertalunk: 10001
if (x>=N || y >=N)
continue;
printf("tomb[%d,%d] = %d\n", x, y, tomb[x][y]);
}
> p.s.: a ZigZag Marosi Istvan jovoltabol megvan :)
Szerintem ez attol sokkal rondabb :))
István
|
