|
[26] lgdt | 2005-01-11 16:29:27 |
jonas! miért nem döntjük meg a 32-es rekordot? :D
|
|
[25] lgdt | 2005-01-11 16:16:37 |
ha kiszűröm az azonosakat, rosszabb az algo. :?
3/4 óráig futtattad? én is hagytam az enyémet:
azóta kitaláltam kirakósra egy sokkal jobbnak ígérkezőt, majd lekódolom. most nincs időm. bye
|
Előzmény: [24] Hajba Károly, 2005-01-11 10:48:16 |
|
[24] Hajba Károly | 2005-01-11 10:48:16 |
Kedves lgdt!
Hogy számolod ki a szükséges és elégséges egyenesek számát és helyét? Van egy jó eljárásod vagy második menetben az azonosakat kiszűröd?
Mivel már N>3-ra több megoldás létezik, így gyanítom, hogy nehéz olyan eljárást alkotni, mely magasab N érték mellett 'visszalépés nélkül' kiadja az összes|valamely jó megoldást.
Az egyenesek átmetszésénél gondolom azokat számlálja, melyek rácsponton metszik egymás. (Ti. a leírásodból nem derült ez ki egyértelműen.)
HK
|
Előzmény: [12] lgdt, 2005-01-06 15:36:50 |
|
[23] jonas | 2005-01-10 13:44:50 |
Nos, 4-re valojaban negy megoldas van (az egybevagosag erejeig):
. |
O |
O |
. |
O |
. |
. |
O |
O |
. |
. |
O |
. |
O |
O |
. |
|
. |
O |
. |
O |
O |
O |
. |
. |
. |
. |
O |
O |
O |
. |
O |
. |
|
. |
O |
. |
O |
. |
O |
. |
O |
O |
. |
O |
. |
O |
. |
O |
. |
|
. |
O |
O |
. |
O |
. |
. |
O |
. |
O |
O |
. |
O |
. |
. |
O |
|
Az egybevagokat is szamolva a megoldasok szama (most nincs kedvem kiszurni az egybevagokat).
n |
2 |
3 |
4 |
5 |
6 |
7 |
megoldasok |
1 |
2 |
11 |
32 |
50 |
132 |
|
Ezt a sorozatot pedig mar meg lehet keresni a Sloane-ban: A000755. Szerintuk a folytatas 1,2,11,32,50,132,380,368,1135. Ez hivatkozik a A000769 sorozatra, amely szerint 1,1,4,5,11,22,57,51,156,158,566,499,1366,3978,5900 megoldas van az egybevagokat csak egyszer szamolva. Megemliti tovabba, hogy bizonyitott, hogy eleg nagy n-re nincs egy megoldas sem, de az a weboldal, amelyre hivatkozik, ezt csak sejtesken emliti.
|
Előzmény: [22] Hajba Károly, 2005-01-10 01:16:09 |
|
[22] Hajba Károly | 2005-01-10 01:16:09 |
Kedves jonas és lgdt!
Örülök, hogy ilyen szépen belemelegedtettek ebbe a témába. :o)
Nos dolgoztass(u|áto)k meg a CPU-t a fa teljes bejárásával. Azaz keresendő adott N-re az összes jó megoldás.
N=2-4-re én is jonas eredményeit kaptam, N=4-re a KöMaL számban (98/2 66-67) található még egy szimmetrikus változat.
N=5-re 3+1 db izomorf megoldást ismerek. (A +1 jonasé :o)
HK
|
Előzmény: [21] jonas, 2005-01-09 20:49:39 |
|
[21] jonas | 2005-01-09 20:49:39 |
Tizenkettore, kicsit javitott programmal:
. |
. |
. |
. |
O |
. |
. |
. |
. |
. |
. |
O |
. |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
O |
. |
. |
. |
. |
O |
. |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
. |
. |
O |
. |
. |
. |
O |
. |
. |
. |
. |
O |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
O |
. |
. |
. |
O |
. |
. |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
. |
O |
. |
. |
. |
. |
O |
. |
. |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
|
|
|
[20] jonas | 2005-01-09 17:34:41 |
Lefuttattam egy sima backtracket, ami nem elvesz, hanem felrak korongokat. Egyszeruen felulrol lefele, balrol jobbra probalkozik, annyi ellenorzest vegez, hogy kihuzva azokat a helyeket ahova mar nem mehet korong, minden sorban maradjon legalabb ket hely. Ez eleg lassu, lehet, hogy probalom gyorsitani.
Tizenegyre haromnegyed ora alatt (egy gyors gepen) megtalalta ezt a megoldast:
O |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
O |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
. |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
O |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
O |
. |
O |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
O |
O |
|
Felraktam a forrast es az eredmenyt
|
Előzmény: [19] lgdt, 2005-01-08 21:13:51 |
|
[19] lgdt | 2005-01-08 21:13:51 |
Sorry...
Sajnos kirakásra nem találtam jó heurisztikát, az alap backtrack pedig csak 9-es re futott le értelmes idő alatt.
Still workin' on it...
|
Előzmény: [18] jonas, 2005-01-08 16:11:40 |
|
[18] jonas | 2005-01-08 16:11:40 |
Ne erts felre, en nem azt gondoltam, hogy geppel nehezebb, mint kezzel, hanem azt, hogy meg geppel is nehez. Ezt most presze megcafoltad. Nekem mindenesetre eszembe nem jutott volna leszedegetni a pontokat felrakas helyett (persze lehet, hogy felrakassal is meg lehet oldani).
|
Előzmény: [12] lgdt, 2005-01-06 15:36:50 |
|
|
|
|
[14] Hajba Károly | 2005-01-06 16:59:38 |
Kedves Sirpi!
Adós maradtam a megoldásom bemutatásáaval, melyet most megteszek.
Ezzel egyben példát is mutatok a b) feladatra.
A zöld szaggatot vonal a P pont helyét magyarázza, míg a kék vonal a szimetriatengely. A (talán közel legjobb) megoldást sok-sok próbálkozás alapján találtam meg. A szám értelemszerűen a területet mutatja.
HK
|
|
Előzmény: [10] Sirpi, 2005-01-06 11:12:54 |
|
[13] Hajba Károly | 2005-01-06 16:42:11 |
Félreértettem.:o)
Nagyon tetszik az eljárásod. Hát ez az, mikor valaki benne van a dolgokban.
Az eljárás pontosításához nehéz hozzászólni, mivel a részleteket Te ismered. (S hát az ördög a részletekben rejtezik. :o)
Vizsgáltad-e, hogy az N egyesével történő növelésével, milyen mértékben nő a futásidő? A Cray-t én a magasabb (N>30) tartományra gondoltam, de erre a választ Te tudnád megadni, kipróbálás után.
HK
|
Előzmény: [12] lgdt, 2005-01-06 15:36:50 |
|
[12] lgdt | 2005-01-06 15:36:50 |
félreértetted: nem a feladat vicces, hanem hogy jonas szerint géppel nehezebb, mint gép nélkül. szerintem nem kell hozzá Cray. :-D nagyon gyanús, hogy lehet teljes mohó algot találni.
az eddigi progi backtrack+heurisztika. nem kirakja a pontokat, hanem leszedi. kezdetben minden helyen van pont. ekkor összeköti egyenessel mindegyiket mindegyikkel, és amelyiket átmetszi az egyenes, annak a counterjét növeli. első közelítésben a legnagyobb counterű pontot szedi le, (és a többi pont counterét megfelelően csökkenti). 6*6-ig így visszalépés nélkül megvan a megoldás, 11*11-esnél 20 pontos az első, amit talál, 2 mp múlva pedig kijön a 22-es.
nekem úgy tűnik, hogy csak kicsit kéne ezen a módszeren változtatni, hogy mindig pontosan lehessen tudni, hogy melyik pontot kell leszedni. mit gondoltok?
|
Előzmény: [9] Hajba Károly, 2005-01-06 01:08:18 |
|
[11] Hajba Károly | 2005-01-06 13:33:36 |
Kedves Sirpi!
Nem értetted félre. Az trivi, hogy a valamely szimetriával rendelkezőket szépen meg lehet oldani. A többire szép megoldásokat adtál. Gyanítom, hogy ezeken már nem lehet javítani. Gratula.
Én találtam az első sor végén szereplőre is jó megoldást.
A feladatot két irányba is lehet nehezíteni:
a, a két idom egymásnak valódi (el nem tolt) tükörképei legyenek;
b, három idomot helyezzünk el.
HK
|
Előzmény: [10] Sirpi, 2005-01-06 11:12:54 |
|
[10] Sirpi | 2005-01-06 11:12:54 |
Remélem, nem értettem félre a feladatot. 12 pentonimo létezik, ebből 7-nél szimmetria miatt trivi a felosztás, és 3-nál még tudtam javítani a 2-n, 2-nél passzolok. Eddig jutottam:
|
|
Előzmény: [9] Hajba Károly, 2005-01-06 01:08:18 |
|
[9] Hajba Károly | 2005-01-06 01:08:18 |
Kedves lgdt!
A feladat eredetije azon messzi időkből vala, mikoron még sem Te, sem PC paripád tervben sem volt.:o)
Szóval nem viccnek készült! Tekintsd úgy, mintha pl. a "Logika" újság egy feladata lenne. Azok egy részére is lehet rutinokat írni, de nem azért születtek.
De gyanítom, hogyha folyamatosan növeled a rácspontok számát előbb-utóbb a Cray (remélem a nevére jól emlékszem :o) se lenne elég a megoldáshoz. Továbbá ne felejtsd el, hogy nem mindenki van benne a programozásban. Valaha én is sok Basic ill. Pascal programocskát írtam, az egyetemen még megtapasztaltam a lyukkártyás Fortran programozásának mazohizmusát, de a munkám nem igényli a programozást, így a C++ ill. OOP és az utána jövő világról lemaradtam. (Talán egy jó, magyar leírással rendelkező Prologot még kipróbálnék.)
Félre ne értsd! Irigyellek a programozási gyakorlatodért, de így én az ilyen feladatokat már csak kockás papíron oldogatom, majd a CADilekkel lerajzolom.:o)
--------------------
No de itt a következő javítandó feladat csokor, mely megoldásában talán már segíthet egy jó grafikus program:
Tekintsük az 5 db egységnyi négyzetből összeállítható pentomínókat. Ezek mindegyikébe lehet 2 db 2 területegységű, egybefüggő és egybevágó síkidomot elhelyezni. (Lásd az ábrát!)
Létezik-e ezek közül olyan pentominó, melybe 2 egységnél nagyobb területű idomokat lehet elhelyezni?
HK
|
|
Előzmény: [8] lgdt, 2005-01-05 19:11:56 |
|
|
|
[6] lgdt | 2004-12-30 22:08:03 |
Kövezzetek meg, de szerintem erre való a számítógép.
|
|
[5] Hajba Károly | 2004-11-26 14:50:54 |
Kedves Laci és más érdeklődő!
Mintának felteszem az n=8 és n=10 esetekre egy-egy megoldást. Az előzőre én leltem, de gondolom nem elsőként, míg az utóbbit a matlap említett számából vettem át.
N=8-ig mindenre találtam már megoldást n=9-et még nem vizsgáltam. n=10 adott volt, míg n=11-re 20 korongot tudok beilleszteni a szabályok betartásával.
Üdv: HK
|
|
Előzmény: [2] sziklac, 2004-11-25 15:57:46 |
|
[4] jonas | 2004-11-26 13:48:35 |
Nem jó.
Van még négy másik olyan egyenes is, amin négy pont van. Kettő a jobb felső sarokból indul, kettő a bal alsóból. Van továbbá még négy, amin három-három egyenes van, ezek a másik két sarokból.
|
|
Előzmény: [2] sziklac, 2004-11-25 15:57:46 |
|
[3] Hajba Károly | 2004-11-26 00:27:07 |
Kedves Laci!
Nagyon örülök, hogy foglalkoztál a feltett feladattal.
De sajnos ez ennél egy kicsit nehezebb, nemcsak vízszintesen, függőlegesen és átlósan nem lehetnek egy egyenesben, hanem egyéb szög alatt sem. Megoldás létezik, hiszen n=32-ig már találtak mindre megoldást. N=10-ig elég hamar megoldható a feladat, azaz aránylag kevés próbálkozással található jó megoldás. Innen kezd érdekessé válni, mely kereséséhez sok sikert és kitartást kívánok.
Üdv: HK
|
Előzmény: [2] sziklac, 2004-11-25 15:57:46 |
|