Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Találjunk jobb megoldást!

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]  

Szeretnél hozzászólni? Jelentkezz be.
[27] Hajba Károly2005-01-11 21:17:21

Kedves lgdt!

Szurkolok Nektek, de azért nézzetek utána, hogy a kömalos cikk óta mit fejlődött a téma.

HK

Előzmény: [26] lgdt, 2005-01-11 16:29:27
[26] lgdt2005-01-11 16:29:27

jonas! miért nem döntjük meg a 32-es rekordot? :D

[25] lgdt2005-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ároly2005-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] jonas2005-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ároly2005-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] jonas2005-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] jonas2005-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] lgdt2005-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] jonas2005-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
[17] Hajba Károly2005-01-06 23:27:26

Köszi. Remélem a Coccolino maci mögötted volt, nem törted össze magad? :o)

Előzmény: [16] Sirpi, 2005-01-06 18:50:57
[16] Sirpi2005-01-06 18:50:57

Hú, dobtam egy hátast az ábrától. Nem semmi, csak gratulálni tudok hozzá!

Előzmény: [14] Hajba Károly, 2005-01-06 16:59:38
[15] Hajba Károly2005-01-06 17:04:47

A mondat helyesen :o)

A zöld szaggatott vonal a P pont helyét magyarázza, míg a kék vonal a szimmetriatengely.

Előzmény: [14] Hajba Károly, 2005-01-06 16:59:38
[14] Hajba Károly2005-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ároly2005-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] lgdt2005-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ároly2005-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] Sirpi2005-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ároly2005-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
[8] lgdt2005-01-05 19:11:56

a múltkor nem is láttam. ez most vicc? :-D

Előzmény: [7] jonas, 2004-12-31 12:48:06
[7] jonas2004-12-31 12:48:06

Ha meg tudod csinálni 11×11-es táblára, akkor hajrá. Szerintem az túl nagy.

Előzmény: [6] lgdt, 2004-12-30 22:08:03
[6] lgdt2004-12-30 22:08:03

Kövezzetek meg, de szerintem erre való a számítógép.

[5] Hajba Károly2004-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] jonas2004-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ároly2004-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

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]