|
|
Oldal: 1 / 1
|
[ 40 hozzászólás ] |
|
Szerző |
Üzenet |
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: A pontos kérdés az, hogy hány darab megoldás van, vagy kellenek a maguk a megoldások is? (Ha elég az, hogy hány darab megoldás van, az lehet egyszerûbben kiszámolható, mint az összes lehetõség végigpróbálgatása. Ráadásul egy 15x15-ös négyzetnél nem tudom, hová férne el egy ilyen hosszú lista)
szerintem nem számítható előre, hogy mennyi megoldás lesz. De ha mégis, akkor - természetesen - köszi azt is!
Megoldások kellenek, de nem az összes. Elég, ha csak néhány másodpercenként kidob egyet-egyet a gép.
|
pén. dec. 19, 2008 14:08 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
A pontos kérdés az, hogy hány darab megoldás van, vagy kellenek a maguk a megoldások is?
(Ha elég az, hogy hány darab megoldás van, az lehet egyszerűbben kiszámolható, mint az összes lehetőség végigpróbálgatása. Ráadásul egy 15x15-ös négyzetnél nem tudom, hová férne el egy ilyen hosszú lista)
|
pén. dec. 19, 2008 13:16 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Ok, köszi!
|
csüt. dec. 18, 2008 16:13 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Sajna már szabin vagyok, és csak január közepén megyek újra melózni.
Ha addig ráér a feladat, akkor majd megkérdezem az egyik kollégát, aki erős matekból. (Még a Szovjetunió idején az országos szovjet matematika versenyen 2. helyezést szokott elérni).
|
csüt. dec. 18, 2008 10:30 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
hát, én ehhez gyenge vagyok, azért köszi! Nekem egy algoritmus kéne, ami 15 rendű négyzet esetén is elfogadható sebességgel eredményeket produkál. Lehet, hogy ilyen nincs is?
Mindenesetre amit a fentiek szerint megírtam 4-ed rendűig nagyon gyors, másodpercek alatt megtalálja az összes megoldást, 5-öd és 6-od rendűnél pedig kb. másodpercenként szolgál egy-egy újabb megoldással. Ennél nagyobb tábla esetén magába fordul a gép és csak (feleslegesen) várhatok.
|
csüt. dec. 18, 2008 4:38 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
T68m írta: azt vettem észre, kartácsak, hogy pártalan számú négyzet esetén a középső szám (két átló találkozása) fix, számolható, páros számú négyzet esetén a középső négy szám összege fix, számolható. Az okát nem tudom. Meg tudná ezt valaki erősíteni, esetleg bizonyítani?
Mindenesetre a programot most átírom olyanra, hogy a közepőböl induljon.
Próbálom bizonyítani:
Azt tudjuk, hogy az összeg minden sorban, oszlopban és átlóban egyezik: mondjuk 3x, a középső elem legyen a z.
3x3-as négyzetben:
Kód: a 3x-a-b b z-a+b z z+a-b 3x-z-b -3x+2z+a+b 3x-a-z
A középső függőleges oszlopból: 3x = (3x-a-b) + (z) + (-3x+2z+a+b)
Egyszerűsítéseket elvégezve: 3x = 3z, vagyis x = z.
Remélem nem vétettem hibát ... ha ez jó, akkor egy hasonló módon be lehet bizonyítani, hogy a 4-es négyzetben a középső 4 elem összege állandó.
|
vas. dec. 14, 2008 20:59 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
azt vettem észre, kartácsak, hogy pártalan számú négyzet esetén a középső szám (két átló találkozása) fix, számolható, páros számú négyzet esetén a középső négy szám összege fix, számolható. Az okát nem tudom. Meg tudná ezt valaki erősíteni, esetleg bizonyítani?
Mindenesetre a programot most átírom olyanra, hogy a közepőböl induljon.
|
vas. dec. 14, 2008 16:50 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
vegyítettem a két módszer: legenerálom a sorozatokat, de azokból csak a két átlót állítom fel, majd az eredeti módszer szerint a maradék kockákba végigprobálgatom a maradék számokat. Így már 5-ös bűvös négyzetre is elfogadható sebességgel kezd megoldásokat adni. Viszont áttörő eredmény nem hozott a fejlesztés, hisz nem csak egy 15-ös kocka, hanem már egy 7-8-as kocka megoldásainak generálása ezen úton kivárhatatlan időt venne igénybe.
|
szomb. dec. 13, 2008 3:43 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
na, nekiálltam megírni! 8-as kockánál csak a segédtábla már milliós nagyságrendű...
hát, kartácsak csak szívok vele. Jóval bonyolultabb lett tőle a program és lényegesen lassult. Tehát a sorozatok elkészítése (bát 6-os kocka felett már sok időt vesz igénybe) de elég gyors, másodpercek alatt megvan. Azonban 4-es kocka esetén is 2064db van. Ezt 2064*2063*2062*2061 féleképp lehet felírni, ami 18ezermilliárd.
Elsőként úgy próbálkoztam (rögtön a legbonyolultabb, de leggyorsabbnak tűnő módon), hogy
1. felveszem az egyik átlót a sorozatból
2. felveszem a másik átlót (ami az előző(ek)nek megfelel) a sorozatból
3. felveszek egy sor (ami az előző(ek)nek megfelel) a sorozatból
4. felveszek egy oszlopot (ami az előző(ek)nek megfelel) a sorozatból
5. goto 3
|
hétf. dec. 08, 2008 23:34 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
oké, akkor átgondolom, megírom, aztán jelentkezek!
|
pén. okt. 17, 2008 0:19 |
|
|
MotoHacker
gyémánt tag
Csatlakozott: pén. jan. 28, 2005 20:39 Hozzászólások: 3683 Tartózkodási hely: Bp
|
Ezek azok a bizonyos "nemes sorozatok" amiket emlegettem, hogy előre le kell a halmazt szűkíteni rájuk, és azután beleírni őket a kockába.
|
csüt. okt. 16, 2008 20:58 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: Tehát pl. a 4x4-es négyzetben a sorok/oszlopok összege 34 tud csak lenni. Azokkal a kombinációkkal, ahol nem ennyi, nem is érdemes foglalkozni.
a, igen. Erre én is gondoltam halványan, de nem foglalkoztam vele érdemben. Tehát arra gondolsz, hogy előre gyártsam le mely számokból lehet kirakni egy sort(oszlopot) majd eleve ezekkel töltsem fel a kockát? Jó gondolatnak tűnik!
|
csüt. okt. 16, 2008 19:20 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
T68m írta: ... na, de mit akarsz ezzel a számmal? ...
Csak azt, hogy csak azokat a számkombinációkat kell próbálgatni a sorokba és oszlopokba, amiknek ennyi az összege.
(Lehet eredetileg is így csinálod?)
Fentebbi hozzászólásban írtam egy tól-ig tartományt, amibe kell esnie a sorokban/oszlopokban lévő számok összegének, mert ami kívül esik, az biztosan nem jó. Írtam is, hogy lehetbne tovább szűkíteni a "jó" tartományt. De azt nem gondoltam, hogy ez a tartomány igazából jóval keskenyebb: csak egyetlen szám.
Tehát pl. a 4x4-es négyzetben a sorok/oszlopok összege 34 tud csak lenni. Azokkal a kombinációkkal, ahol nem ennyi, nem is érdemes foglalkozni.
|
csüt. okt. 16, 2008 18:42 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: Új ötlet: Itt algoritmust írnak le: http://www.curiousmath.com/index.php?na ... cle&sid=64Ezen az oldalon írják: For any magic square, the sum is n*(n^2 + 1)/2.Itt lehet készíteni mágikus négyzetet: http://www.magic-squares.de/constructio ... /even.htmlPárat kipróbáltam, és mindegyiknek az összege egyezett az elõzõ lapon lévõ képlettel. Nem vagyok benne biztos, hogy az összes eredményre igaz ez. Nézd meg a programoddal a 3-as és a 4-es négyzetre, ami még emberi idõ alatt lefut, hogy az összegek minden esetben a fenti képletnek megfelelõek-e. Ha igen, akkor csak azok a számkombinációk jók soroknak/oszlopoknak, amikre ez igaz. Ez minden négyzet esetén egyetlen szám, így a fa nagy részét le lehet vágni. Szerk: az összes eredményre igaz! A Wikipedián is ezt írják: http://en.wikipedia.org/wiki/Magic_squareM(n) = (n^3 + n) / 2 (ua. mint a fenti képlet, csak n-et bevitték a zárójelbe)
én ezt sokkal egyszerűbben számoltam ki!
Először meghatározom a bűvös négyzet számainak összegét:
Osszesen:= Round(succ(Meret) * Meret / 2);
majd azt elosztom az oldal hosszával:
Osszeg:= Round(Osszesen / OldalHossz);
na, de mit akarsz ezzel a számmal?
Ezt a devedec algoritmus kellene áttanulmányozni...
|
csüt. okt. 16, 2008 10:12 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Új ötlet:
Itt algoritmust írnak le: http://www.curiousmath.com/index.php?na ... cle&sid=64
Ezen az oldalon írják: For any magic square, the sum is n*(n^2 + 1)/2.
Itt lehet készíteni mágikus négyzetet: http://www.magic-squares.de/constructio ... /even.html
Párat kipróbáltam, és mindegyiknek az összege egyezett az előző lapon lévő képlettel.
Nem vagyok benne biztos, hogy az összes eredményre igaz ez. Nézd meg a programoddal a 3-as és a 4-es négyzetre, ami még emberi idő alatt lefut, hogy az összegek minden esetben a fenti képletnek megfelelőek-e.
Ha igen, akkor csak azok a számkombinációk jók soroknak/oszlopoknak, amikre ez igaz. Ez minden négyzet esetén egyetlen szám, így a fa nagy részét le lehet vágni.
Szerk: az összes eredményre igaz!
A Wikipedián is ezt írják: http://en.wikipedia.org/wiki/Magic_square
M(n) = (n^3 + n) / 2 (ua. mint a fenti képlet, csak n-et bevitték a zárójelbe)
|
csüt. okt. 16, 2008 7:05 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: Tovább kell gondolkodni.
erről van szó! Csak nem jut épp eszembe semmi.
Amit te írtál, az pedig szerepel már, a következőképp
Result:= (Sorok[Sor] < Osszeg) and
itt azt vizsgálja, hogy nem léptük-e túl a maximumot, itt pedig azt
(Sorok[Sor] + (OldalHossz - Oszlop) * Meret >= Osszeg)
hogy elérhető-e az összeg.
|
csüt. okt. 16, 2008 2:20 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
T68m írta: ... Pl. hogy "1"-es mellé "2"-es nem kerülhet. Ez - ugye - lényegesen gyorsítana. ...
Ebben lehet valami!
Hiszen pl. 4x4-es négyzetben 1-től 16-ig vannak számok.
Tehát a legkisebb összeg egy sorban nem lehet 16-nál kisebb, hiszen egyik sorban benne lesz a 16 is. Sőt, ahol a 16-os van, ott még ha a 3 legkisebb szám is van mellette, akkor 16 + 1 + 2 + 3 = 22. Amelyik sorban, oszlopban a 16 van, ott nem lehet 22-nél kisebb az összeg.
Azok a számkombinációk, ahol az összeg 22-nél kisebb, azt egyből el is lehet dobni (4x4-es négyzet esetén).
Sőőt: van egy oszlopa is a 16-nak, ahol az 1, 2 és 3 már a sorban van, akkor a következő 3 szám legkisebb szám az oszlopra a 4, 5 és 6 lehet, így 31 a legkisebb összeg.
Ha átlóban is szerepel a 16, akkor a következő 3 legkisebb szám: 7, 8 és 9.
Bár ez így nem teljesen igaz, mert ha olyan kombináció van, hogy:
sorban: 1, 2, 4, 16 =23
oszlopban: 3, 5, 6, 16 = 30 (mégis sikerül 31 alá menni, és a 6 legkisebb számot használjuk, de biztosan van egy minimum, ami 22-nél nagyobb)
De a lényeg: 22-nél biztosan nem lehet kisebb összeg a 16-os szám sorában/oszlopában.
Esetleg lehetne tovább gondolni, biztos van még levágható rész a fában.
UI: ez csak most jutosst eszembe:
Ez a korlátozás szimmetrikus: ugyanígy felfelé is van "plafon":
ahol az 1-es van, abban a sorban nem lehet nagyobb összeg, mint:
1 + 16 + 15 + 14 = 46.
Tehát 4x4-es négyzetben csak olyan kombinációkat kell vizsgálni a sorkra/oszlopokra/átlókra, ahol a négy szám összege 22 és 46 között van.
És ez szűkíthető még picit, csak pontosan nem tudom mennyivel, mert az 1-esnek van oszlopa is (ugyanúgy, int fentebb a 16-nak).
De még így is túl nagy rész marad meg a fából, de a lehetséges variációk több, mint fele kiesik, és mivel az összes lehetséges kitöltések száma a lehetséges 4 számból álló variációk számával hatványozott arányban növekszik, ezért ez is nagy csökkenés.
Szóval, lehet, hogy az 5-ös és 6-os négyzet kiszámolható emberi idő alatt ezzel a módosítással, de a 8-as vagy 9-es, 10-es már biztosan nem.
Tovább kell gondolkodni.
|
szer. okt. 15, 2008 10:46 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Fijjúg!
Kicsit eltértünk az kérdésfeltevéstől! Tehát adva van egy program, egy algoritmus ami jónak tűnik, mert végigmegy minden lehetséges lépésen, csak túl lassú.
1. vagy gyorsítani kéne, tehát ehhez újabb szűkítési kritésium kellene. Ami felvetődött (hogy egy számot csak egyszer használjon fel, illetve, hogy soronként, oszloponként ellenőrizzen összeget, ne csak a legvégén), azt már beleépítettem. Olyan gyorsítás (szűkítési kritérium) kellene, ami lényegesen, sok nagyságrenddel gyorsít, hogy hatalmas részeket hagyhasson ki a gép a keresésből. Pl. hogy "1"-es mellé "2"-es nem kerülhet. Ez - ugye - lényegesen gyorsítana. Az assembler átírással - ahogy sp2 is mondta - legfeljebb két nagyságrendet nyerhetek, ami az 5x5-nél megoldás, de 6x6-nál már túl kevés.
2. vagy ha megtalálja valaki a leírását a már kitalált algoritmusnak, ami alapján az ötödrendűről kijelentették, hogy 600.000(-nél több) megoldása van, akkor átírom arra a programot és örülök.
Tehát a cél az hogy sokadrendű négyzetnél is aránylag gyorsan sok, különböző megoldást kapjak.
*************************
még régen megírtam a lólépésben végigmenni a sakktáblán problémát. Soha nem akart lefutni, mikor rájöttem a kulcsára. A szélek azok. Egy szélre csak két helyről lehet lépni, tehát ha ezen helyek egyikre ugrik a paci, akkor kötelező onnan a szélre lépni, különben a szélről sosem fog tudni kijönni a ló.
|
szer. okt. 15, 2008 10:34 |
|
|
MotoHacker
gyémánt tag
Csatlakozott: pén. jan. 28, 2005 20:39 Hozzászólások: 3683 Tartózkodási hely: Bp
|
A józan paraszti ész, az kevés, mert ha végig tudod gondolni, akkor végigmész egy logikai láncon, amit akár bizonyításnak is elfogadhatunk.
Ha arra gondolsz, hogy "úgy érzed" ez minden esetben jó, na ez az, ami viszont közel nem biztos, ez eddig egy un. sejtés.
|
szer. okt. 15, 2008 8:55 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
MotoHacker írta: Namost ez így lufihámozás. Keresünk "valami algoritmust" de akkor ehhez, ha lólépés, ha ufótánc, le kellene vezetni cáfolhatatlanul _miért BIZTOS minden esetben_, hogy az a stratégia kielégíti a feltételeket. Képes erre valaki?
Nem fontos, hogy én találjam ki az algoritmust és én bizonyítsam a helyességét. Elég csak megtalálnom, hiszen ezt már biztosan kitalálták és bizonyították is.
Másrészt a bizonyítás -- saját használatra, mint a fenti program-- nem fontos, ha az algoritmus olyan egyszerű, hogy azon "látszik", hogy jó.
Sok olyan egyszerű algoritmus létezik, amit józan paraszti ésszel végiggondolva látjuk, hogy helyes. Viszont a bizonyítása nehéz.
|
szer. okt. 15, 2008 8:39 |
|
|
MotoHacker
gyémánt tag
Csatlakozott: pén. jan. 28, 2005 20:39 Hozzászólások: 3683 Tartózkodási hely: Bp
|
Namost ez így lufihámozás.
Keresünk "valami algoritmust" de akkor ehhez, ha lólépés, ha ufótánc, le kellene vezetni cáfolhatatlanul _miért BIZTOS minden esetben_, hogy az a stratégia kielégíti a feltételeket.
Képes erre valaki?
Továbbá így visszafelé az összes olyan "lépkedést" megtalálni és levezetni, amivel minden variáció kimeríthető szintén érdekes feladat, mondhatni klasszikus P-beli probléma, mint megtervezni a lehető legideálisabb nyákot pl.(elnézést az elektrós hasonlatért)
|
szer. okt. 15, 2008 8:17 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Igen, az assembly-ben írás gyorsítana, de nem eleget. hiszen ha 10 óra helyett 5 (vagy 2, vagy 1 -- de 10-szeres gyorsítást úgysem lehet csinálni) óra alatt fut le, még az is sok.
És ez még kis négyzet, 5x5-ös. Egy 10x10-es sokkal-sokkal több variációból áll: több, mint 150 jegyű szám! Ez a 10 millió év helyett asm-ban megoldva 10-szer gyorsabban is 1 millió évig futna ...
Másik algoritmusra van szükség.
|
szer. okt. 15, 2008 7:40 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
MotoHacker írta: Ezt azért nem olyan nehéz assemblyben megírni, az eredeti program elképesztõ és kevéssé hatékony kódmennyisége helyett meglehetõsen optimalizált kódot lehet kiötleni.
Másfelõl én fordítva gondolkodnék. Az 5ös bûvös négyzet minden oszlopa és átlója egy olyan sorozat, aminek tagjait az 1..25 tartományból válogattuk.
Igen, és ez pont 25!, azaz 15.511.210.043.330.985.984.000.000.
(Ennek ellenőrzésére szolgál a "Foglalt" halmaz)
Az assemblerben való megoldás csak az 5x5-ön segítene, mivel a 6-osnál már 36!-t kell ellenőrizni.
|
kedd okt. 14, 2008 23:57 |
|
|
MotoHacker
gyémánt tag
Csatlakozott: pén. jan. 28, 2005 20:39 Hozzászólások: 3683 Tartózkodási hely: Bp
|
Ezt azért nem olyan nehéz assemblyben megírni, az eredeti program elképesztő és kevéssé hatékony kódmennyisége helyett meglehetősen optimalizált kódot lehet kiötleni.
Másfelől én fordítva gondolkodnék. Az 5ös bűvös négyzet minden oszlopa és átlója egy olyan sorozat, aminek tagjait az 1..25 tartományból válogattuk.
Ilyen sorozat összesen csak 6milliónál valamivel több létezik, szemben a teljes négyzet kitöltésének csillagászati variációjával.
Innen kellene következtetni azokra a "nemes" sorozatokra, amikből létezik olyan csoport, aminek az összege azonos, és beleírhatóak a négyzetbe.
|
kedd okt. 14, 2008 19:16 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
igen, a nyolcszoros az világos. Ezzel csak arra utaltam, hogy összhangban vannak az eredmények. Viszont a másik adat, hogy az ötödrendűnek 600.000 megoldás van, az azt suggalja, hogy ismert a megoldás algoritmusa. Mivel az én programom kb. óránként egyet talál az ötödrendűnél, ezért feltehetőleg 50-100évig futna.
|
kedd okt. 14, 2008 9:51 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Igen, ezt írták is a cikkben, hogy az egy megoldásnak számít.
Fentebb én is írtam, hogy egy megoldásból tükrözés és elforgatás transzformációkkal 8-at lehet csinálni.
|
kedd okt. 14, 2008 8:28 |
|
|
MotoHacker
gyémánt tag
Csatlakozott: pén. jan. 28, 2005 20:39 Hozzászólások: 3683 Tartózkodási hely: Bp
|
Azért a nyolcszorosa szerintem, mert a két tengely körüli tükröt, plusz a négyféle elforgatást ők nem számolják bele.
|
kedd okt. 14, 2008 7:50 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: Még két cikk a bûvös négyzetekrõl: http://www.sulinet.hu/tart/cikk/am/0/14873/1http://www.sulinet.hu/tart/cikk/ag/0/15625/1A felsõ cikkben egy 3x3-as négyzetet töltenek ki, de éppen fordítva, mint az elõzõekben írtuk: lentrõl indulnak, nem felülrõl, de a lényeg ugyanaz, csak pepitában. Azt írják, hogy a 3x3-as esetben csak egyetlen megoldás van (az összes megoldás egynek a tükrözése vagy elforgatása) Ugyanitt kitöltenek egy 4x4-es tömböt is, de nem világos számomra, hogy ezt lehet-e általánosítani az összes páros oldalhosszúságú négyzetre, vagy csak a 4x4-esre érvényes. Még egy cikk: itt 3x3-as négyzet, és egyenletrendszerekkel oldják meg. http://www.komal.hu/verseny/feladat.cgi ... f=S10&l=huNagyon nem volt idõm átolvasni, csak átfutottam ... azért remélem segít valamit.
jó a programom, hehe, ugyanis "negyedrendűek kitöltésére 880", én 7040-et találtam és ez - ugye - pont a nyolcszorosa. Viszont a cikkből kiderül, hogy az ötödrendű négyzeteknek 600.000-nél több lehetősége van - tehát ismert az algoritmus, hogyan lehet azt kitölteni!!!
|
kedd okt. 14, 2008 1:14 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Még két cikk a bűvös négyzetekről:
http://www.sulinet.hu/tart/cikk/am/0/14873/1
http://www.sulinet.hu/tart/cikk/ag/0/15625/1
A felső cikkben egy 3x3-as négyzetet töltenek ki, de éppen fordítva, mint az előzőekben írtuk: lentről indulnak, nem felülről, de a lényeg ugyanaz, csak pepitában. Azt írják, hogy a 3x3-as esetben csak egyetlen megoldás van (az összes megoldás egynek a tükrözése vagy elforgatása)
Ugyanitt kitöltenek egy 4x4-es tömböt is, de nem világos számomra, hogy ezt lehet-e általánosítani az összes páros oldalhosszúságú négyzetre, vagy csak a 4x4-esre érvényes.
Még egy cikk: itt 3x3-as négyzet, és egyenletrendszerekkel oldják meg.
http://www.komal.hu/verseny/feladat.cgi ... f=S10&l=hu
Nagyon nem volt időm átolvasni, csak átfutottam ... azért remélem segít valamit.
|
hétf. okt. 13, 2008 20:58 |
|
|
Hannibal
Moderátor
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 6486 Tartózkodási hely: Bonyhád - BP
|
A cím valami miatt összevissza krikszkraksz volt (nálam). Javítottam.
|
hétf. okt. 13, 2008 14:49 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Nem lóugrás, csak nem emlékeztem már: egyet balra és fel kell lépni. Ha ott már van szám, a mező nem üres, akkor a balra fel helyett egyenesen le kell menni.
Amelyik irányban kicsúszol a tábla szélén, ott a másik oldalon kell bejönni.
3-4: a 3-asnál jobbra kicsúszott, és bejön balról. A 4-esnél a felső sorban menne fel középre, de az már ki van töltve, ezért ilyenkor nem balra fel, hanem egyenesen le megy.
6-7:6. itt simán balra fel. 7.: itt kicsúszna és a bal alsóba menne, ahol már a 4-es szám van, ezért csak egyet le megy egyenesen.
Ez csak egy megoldást ad meg szerintem ...
Hacsak nem lehet másik számmal kezdeni, ezt ki kell próbálni. De akkor lenne annyiszor 8 (vagy több akár?) megoldás, ahány szám van a négyzetben.
|
hétf. okt. 13, 2008 14:21 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
a 3-4 és a 6-7 lépést nem értem, ott nincs lóugrás! Meg azt se értem, hogy ezzel a módszerrel minden megoldás elérhető???
|
hétf. okt. 13, 2008 13:40 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Ilyet találtam és csak páratlan egység méretű négyzethez jó:
http://www.iqjb.hu/iqinfo.php?command=2&cikk_id=14
Ezek szerint az első sor közepén kell kezdeni, és 1-gyel.
|
hétf. okt. 13, 2008 12:30 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Mindenestere: ha csak annyit változtatunk, hogy minden kockából csak lólépéssel járunk végig minden kockát, az is már óriási gyorsítás. De mekkora lólépés kell, hogy alakul az az oldalhossz-hoz?
|
hétf. okt. 13, 2008 11:44 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
igen, ezt a lólépésest hallottam, de szerint ez csak egy (vagy forgatva nyolc) megoldás a milliárdból. Persze lehet, hogyha különböző helyekről indítjuk a pacit, akkor minden megoldás megkapunk. ??? Tehát ez lenne a megoldás, a lólépés? Ha van link, küldj!
|
hétf. okt. 13, 2008 11:42 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Ha már 5 egység méretű négyzetre ilyen hatalmas lesz a fa, akkor nem így kell csinálni. Mert pl. 10 egység oldalú négyzetre már nem érne a végére a program az univerzum végéig sem.
(Kb. mint amikor a Galaxis útikalauzban kiszámolták, hogy 42 )
A pontos cél mi? Az összes lehetséges eredmény kiszámítása, vagy elég csak egyetlen? Vagy elég csak egy szám, hogy hány darab helyes megfejtés létezik?
A négyzet kitöltésére van algoritmus, valahogy lólépésben, vagy nemtom már hogyan kell tölteni, és ha egyik oldalon kiérsz a táblázatból, akkor a másik oldalon be kell menni, mintha a szélei összeérnének (henger- vagy inkább gömbszerűen). Neten biztos megtalálod.
Ez gyors, mert minden "kockába" csak egyszer kell értéket írni, és nem kell milliárdszor végigmenni az egészen.
De lehet, hogy ezt mindig 1-gyel kell kezdeni, és akkor csak egyetlen eredmény jön ki, már nem emlékszem. Ezért ha minden lehetséges megoldás kell, akkor ez nem biztos, hogy jó lesz.
És akkor persze az egy darab megoldás az rögtön 7 megoldás: mert az eredeti + elforgatva 90, 180, 270 fokkal, és tükrözve vízszintesen, függőlegesen, és tükrözve vízszintesen és függőlegesen is (ez utóbbi ugyanaz, mintha tükrözném függőlegesen és utána vízszintesen).
Valójában tehát 8 megoldás az egyetlen, de abból kettő ugyanaz.
Plusz még lehet, hogy az elforgatott megoldásokat is lehet tükrözni, és nem egy másikat adnak.
Ezt meg kell nézni.
|
hétf. okt. 13, 2008 11:14 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
na, most van 1 kis időm kommentelni. Természetesen köszi SP2 a hsz-ed, ilyen, elvi útmutatásra várok, mint amilyen a tied is, amivel nagyságrendeket lehet gyorsítani. (csak a tied már benne van, feltéve ha azt csinálja a program, amit akarok)
Tehát a program:
1. a Terminated kapcsoló a leállításra kell, algoritmus szempontjából lényegtelen
2. rekurziv algoritmus, ami kitölti egy számmal (pontosabban egytől maxszámig (oldalhossz*oldalhossz) egy olyan számmal, ami eddig még nem lett felhasználva) a bűvös négyzet egyik kockáját, majd a következő kockával meghívja önmagát.
Ezután eggyel nagyobb számmal tölti ki azt a kockát, majd ismét meghívja önmagát. Tehát így végigmegy (oldalméret*oldalméret)! kombináción. 1->1, 2->24, 3->362.880, 4->20.922.789.888.000, 5->15.511.210.043.330.985.984.000.000 mint látható "kicsit" gyorsan növekszik az összes lehetőség száma, ezért
3. ha befejezünk egy sort/oszlopot/átlót, akkor megvizsgáljuk, hogy az egyenlő-e az ÖSSZEGGEL, tehát ami egy oldal összege. Ha nem, akkor a fa alatta lévő részét eldobjuk.
mivel ez még kevés, ezért
4. minden egyes új számnál megvizsgáljuk, hogy így nem lesz-e nagyobb a sor/oszlop/átló összege az ÖSSZEGNÉL, mert ha igen, akkor ennek a kombinációi szintén mennek a levesbe
mivel ez még mindig kevés, ezért
5. minden egyes új számnál az is megvizsgáljuk, hogyha a fennmaradóba max összeget töltenénk-e, akkor elérhetjük-e az ÖSSZEGET, mert ha nem, akkor ennek a kombinációi szintén menne a levesbe
tehát eddig ennyit sikerült összehozni. Kéne még tipp!
A hozzászólást 1 alkalommal szerkesztették, utoljára T68m hétf. okt. 13, 2008 11:21-kor.
|
hétf. okt. 13, 2008 1:15 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Sparow2 írta: Lehet nem vagyok elég figyelmes, de nem látom az a részt, ahol ha nem egyezik a sorok/oszlopok/átlók összege, akkor eldobnád a fa az alatt lévõ részét.
Pl. ha az elsõ két sor összege nem egyezik, akkor semmi értelme tovább vizsgálni a többi sort, vagy az olyan kombinációkat, amikben az elsõ két sor ugyanez. Így a keresési fa nagy részét le lehet vágni.
ezt végzi a sorrendben, oszloprendben és átló1/2rendben funkció.
|
vas. okt. 12, 2008 18:44 |
|
|
Sparow2
gyémánt tag
Csatlakozott: hétf. jún. 26, 2006 11:21 Hozzászólások: 2544
|
Lehet nem vagyok elég figyelmes, de nem látom az a részt, ahol ha nem egyezik a sorok/oszlopok/átlók összege, akkor eldobnád a fa az alatt lévő részét.
Pl. ha az első két sor összege nem egyezik, akkor semmi értelme tovább vizsgálni a többi sort, vagy az olyan kombinációkat, amikben az első két sor ugyanez. Így a keresési fa nagy részét le lehet vágni.
|
vas. okt. 12, 2008 16:45 |
|
|
T68m
a fórum lelke
Csatlakozott: szer. márc. 24, 2004 13:43 Hozzászólások: 12729 Tartózkodási hely: FLF
|
Bûvös négyzet
Egy ismerõsöm kérte, hogy programozzam le. Megtettem: 1, 2, 3-ra jól mûködik. 4-re még elfogadható sebességgel lefut (7040 megoldás), 5-nél már órákat kell várni az elsõ eredményre és nem tudni meddig futna. Feljebb nem tudnia mikor születik eredmény.
(Bûvös négyzet: olyan négyzet, amiben 1x1, 2x2, 3x3, stb. amiben a sorok, oldalak és az átlók összege megegyezik)
Nincs további ötletem a gyorsításra, itt a lényeg
Kód: const MaxOldal = 99; var Negyzet: array[1..MaxOldal] of integer; OldalHossz, Meret, Osszesen, Osszeg, MeretHossz: integer;
OldalHossz:= StrToInt(OldalaEDT.Text); Meret:= OldalHossz * OldalHossz; Osszesen:= Round(succ(Meret) * Meret / 2); Osszeg:= Round(Osszesen / OldalHossz);
*************************
var I, Atlo1, Atlo2: integer; Foglalt: set of 1..MaxOldal; Sorok, Oszlopok: array[1..MaxOldal] of integer; procedure Rekurziv(const Melyseg: integer); var AtloRendben: boolean; I, Sor, Oszlop: integer; function SorRendben: boolean; begin if Oszlop = OldalHossz then Result:= (Sorok[Sor] = Osszeg) else Result:= (Sorok[Sor] < Osszeg) and (Sorok[Sor] + (OldalHossz - Oszlop) * Meret >= Osszeg) end; function OszlopRendben: boolean; begin if Sor = OldalHossz then Result:= (Oszlopok[Oszlop] = Osszeg) else Result:= (Oszlopok[Oszlop] < Osszeg) and (Oszlopok[Oszlop] + (OldalHossz - Sor) * Meret >= Osszeg) end; function Atlo1Rendben: boolean; begin if Melyseg < Meret then Result:= (Atlo1 < Osszeg) and (Atlo1 + (OldalHossz - Sor) * Meret >= Osszeg) else Result:= (Atlo1 = Osszeg) end; function Atlo2Rendben: boolean; begin if Sor < OldalHossz then Result:= (Atlo2 < Osszeg) and (Atlo2 + (OldalHossz - Sor) * Meret >= Osszeg) else Result:= (Atlo2 = Osszeg) end; begin if Melyseg > Meret then Synchronize(KockaAdd) else if not(Terminated) then begin for I:= 1 to Meret do begin if not(I in Foglalt) then begin AtloRendben:= true; include(Foglalt, I); Sor:= succ(pred(Melyseg) div OldalHossz); Oszlop:= succ(pred(Melyseg) mod OldalHossz); inc(Sorok[Sor], I); inc(Oszlopok[Oszlop], I); if Sor = Oszlop then begin inc(Atlo1, I); AtloRendben:= Atlo1Rendben end; if Sor = succ(OldalHossz) - Oszlop then begin inc(Atlo2, I); AtloRendben:= AtloRendben and Atlo2Rendben end;
if SorRendben and OszlopRendben and AtloRendben then begin Negyzet[Melyseg]:= I; Rekurziv(succ(Melyseg)) end;
if Sor = succ(OldalHossz) - Oszlop then dec(Atlo2, I); if Sor = Oszlop then dec(Atlo1, I); dec(Oszlopok[Oszlop], I); exclude(Foglalt, I); dec(Sorok[Sor], I) end end end end; begin for I:= 1 to MaxOldal do begin Oszlopok[I]:= 0; Sorok[I]:= 0 end; Atlo1:= 0; Atlo2:= 0; Foglalt:= []; Rekurziv(1) end;
1. a KockaAdd egy megoldást az eredmény táblába elhelyz
2. deklaráció és inicializáció az elején
3. gyorsítási ötletre lenne szükségem!
|
vas. okt. 12, 2008 14:23 |
|
|
|
Oldal: 1 / 1
|
[ 40 hozzászólás ] |
|
Ki van itt |
Jelenlévő fórumozók: nincs regisztrált felhasználó valamint 6 vendég |
|
Nem nyithatsz témákat ebben a fórumban. Nem válaszolhatsz egy témára ebben a fórumban. Nem szerkesztheted a hozzászólásaidat ebben a fórumban. Nem törölheted a hozzászólásaidat ebben a fórumban.
|
|
|