Forum » Programiranje » Dovolj logično ?
Dovolj logično ?
StratOS ::
Imagine a chessboard made of dark glass and transparent glass and for which the squares have been randomly set as dark or transparent. How many possible boards are there given that two boards which can be rotated or turned over to give the same array of squares are only counted once ? In other words how many ways are there of colouring a chessboard in two colours, ignoring rotations and reflections of the same board ?
consider the 2*2 problem, there are the following possible boards:
oo
oo
xo
oo
xx
oo
xo
ox
xx
xo
xx
xx
and there are no more because all others can be turned into one of these by means of some kind of rotation or reflection (in fact rotations suffice here).
_______________________________
Če kdo ne ve angleščine :
Imamo Šahovnico (8x8), ki ima naključna bela in črna polja, koliko je vseh kombinacij polj ( izbranih šahovnic ), tako da uporabimo le tiste kombinacije, ki niso rotacije ali zrcalne slike že naštetih, primer prikazuje pa vse možne kombinacije 2x2 šahovnice.
Torej število vseh možnih kombinacij je ?
consider the 2*2 problem, there are the following possible boards:
oo
oo
xo
oo
xx
oo
xo
ox
xx
xo
xx
xx
and there are no more because all others can be turned into one of these by means of some kind of rotation or reflection (in fact rotations suffice here).
_______________________________
Če kdo ne ve angleščine :
Imamo Šahovnico (8x8), ki ima naključna bela in črna polja, koliko je vseh kombinacij polj ( izbranih šahovnic ), tako da uporabimo le tiste kombinacije, ki niso rotacije ali zrcalne slike že naštetih, primer prikazuje pa vse možne kombinacije 2x2 šahovnice.
Torej število vseh možnih kombinacij je ?
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
JerKoJ ::
heheh
moznosti je ogromno tako da sam koncni rezultat in postopek
torej stevilo : malenkost vec kot 2^61
bolj tocno: 2^61+2^34+2^30+2^29+2^14
Teorija k je uzadi je
ciklicni indeks grupe in substitucija Polye
Link
beri od strani 202 dalje.
Ko si prebral bi moralo biti jasno zakaj je izracunan
ciklicni indeks enak
1/8(X[1]^64+2*X[4]^16+X[2]^32+2*X[1]^8*X[2]^28+2*X[2]^32)
in substitucija Polyle : X[i]-> 1+1
moznosti je ogromno tako da sam koncni rezultat in postopek
torej stevilo : malenkost vec kot 2^61
bolj tocno: 2^61+2^34+2^30+2^29+2^14
Teorija k je uzadi je
ciklicni indeks grupe in substitucija Polye
Link
beri od strani 202 dalje.
Ko si prebral bi moralo biti jasno zakaj je izracunan
ciklicni indeks enak
1/8(X[1]^64+2*X[4]^16+X[2]^32+2*X[1]^8*X[2]^28+2*X[2]^32)
in substitucija Polyle : X[i]-> 1+1
StratOS ::
Hvala zelo, jaz sem za to naredu program, ki bi skalkuliral pravilno kje jutri ...
Hm, cool !!
Hm, cool !!
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."
JerKoJ ::
Sej stvar je v osnovi simpl
Vseh moznih farbanj 64 kvadratkov z dvema farbama je 2^64 Ker pa ne dopuscamo da z vrtenjem in zrcaljenjem
sahovnice pridemo do istih farbanj je treba te moznosti
odstet.
Tko zlo na hitr se da rezultat ocent ker je osem
moznih takih operacij, ki nam da isto sahovnico:
1. pustimo na miru
2. vrtimo za 90°
3. vrtimo za 180°
4. vrtimo za 270°
5. zrcalimo prek polja (1,1) in (8,8) - diagonala sahovnice
6. zrcalimo prek polja (1,8) in (8,1) - druga diagonala
7. zrcalimo prek navpicne sredine sahovnice
8. zrcalimo prek vodoravne sredine sahovnice
torej 2^64/8=2^61
Tukaj pa stvar ni vec tok simpl
Problem je da nekaj farbanj preveckrat odstejemo
npr. pri doloceni razporeditvi dobimo isto farbanje
z vrtenjem za 180°in z zrcaljenjem prek diagonale
ne pa pri ostalih operacijah
in zarad tega je treba se mal zraven pristet k smo na
zacetku prevec odstel (zmer mislmo da so vse
operacije mozne)
Najtezje je sevada ocenit kok je takih "prevec odstevanj"
Lahko seveda to naredis s programom brut-force
lahko pa malo pogledas link k sem ti ga dal in
tam lepo pise kako pa kaj
Vseh moznih farbanj 64 kvadratkov z dvema farbama je 2^64 Ker pa ne dopuscamo da z vrtenjem in zrcaljenjem
sahovnice pridemo do istih farbanj je treba te moznosti
odstet.
Tko zlo na hitr se da rezultat ocent ker je osem
moznih takih operacij, ki nam da isto sahovnico:
1. pustimo na miru
2. vrtimo za 90°
3. vrtimo za 180°
4. vrtimo za 270°
5. zrcalimo prek polja (1,1) in (8,8) - diagonala sahovnice
6. zrcalimo prek polja (1,8) in (8,1) - druga diagonala
7. zrcalimo prek navpicne sredine sahovnice
8. zrcalimo prek vodoravne sredine sahovnice
torej 2^64/8=2^61
Tukaj pa stvar ni vec tok simpl
Problem je da nekaj farbanj preveckrat odstejemo
npr. pri doloceni razporeditvi dobimo isto farbanje
z vrtenjem za 180°in z zrcaljenjem prek diagonale
ne pa pri ostalih operacijah
in zarad tega je treba se mal zraven pristet k smo na
zacetku prevec odstel (zmer mislmo da so vse
operacije mozne)
Najtezje je sevada ocenit kok je takih "prevec odstevanj"
Lahko seveda to naredis s programom brut-force
lahko pa malo pogledas link k sem ti ga dal in
tam lepo pise kako pa kaj
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | 100x100 šahovnicaOddelek: Programiranje | 7041 (5217) | techfreak :) |
| » | problem Permutacijske grupeOddelek: Šola | 1218 (900) | RO87 |
| » | [C++]Tezava s strukturoOddelek: Programiranje | 967 (967) | Keki |
| » | Šah [Pacsal]Oddelek: Programiranje | 2225 (1828) | NeOman |
| » | Bljiznjica do napredka?Oddelek: Loža | 1080 (960) | Thomas |