[2168] Csimby | 2007-07-28 00:08:50 |
Szia! Köszi az ábrákat! Az én algoritmusom most veszem észre, hogy mégsem jó, mert noha megfelelő számú szakaszból áll, az egyiket 2 részletben húzom be az pedig csalás (1 behúzással nem lehet mert van benne egy 3-fokú csúcs így muszáj abból indulni). Amúgy azt akartam, hogy az n=5-re talált "nem kilépő" megoldásomat (amit még nem akarok lerajzolni) L-alakban két szakasszal kibővítem és egy régi szakaszt meghosszabítok, ekkor n=6 egy megoldását kapom és ez folytatható is lenne, csak hát mégsem jó.
|
Előzmény: [2167] epsilon, 2007-07-27 18:13:42 |
|
[2167] epsilon | 2007-07-27 18:13:42 |
A 328-as feladat kapcsán a következő biztos: n×n pont összeköthető 2n-2 szakaszból álló töröttvonallal, a kért feltétellel. Szemléltetés és algoritmus kialakítása végett itt egy "kép" egy pár esettel:
|
|
Előzmény: [2156] Csimby, 2007-07-26 23:20:32 |
|
[2166] Hajba Károly | 2007-07-27 12:47:46 |
A spirál alatt azt értem, hogy a mátrixot kivülröl körkörösen, majd mindig befelé haladva folyamatosan felfűztem. Ehhez, amint jól látod 1-gyel több vonal kell. Anno így határoztam meg a szükséges lépésszámot, azaz a spirálban található vonalak számából elvettem egyet. Persze később a képletet is meghatároztam. :o)
---
Az n=5 nemkilépő és visszazárón akkor elkezdek gondolkodni.
|
Előzmény: [2164] Csimby, 2007-07-27 09:52:47 |
|
|
[2164] Csimby | 2007-07-27 09:52:47 |
Most látom csak hogy ez a feladat egyszer mennyire ki lett már vesézve (pl. 39.feladat), Spirálozás alatt amúgy azt érted hogy mindig az egyel kisebb oldalhosszú négyzet megoldásából állítjuk elő a következőt? Vagy mire gondolsz? Mert ugye ha csak úgy felspirálozzuk a pontokat, akkor az 1-gyel több szakasz.
|
Előzmény: [2162] Hajba Károly, 2007-07-27 08:33:24 |
|
|
[2162] Hajba Károly | 2007-07-27 08:33:24 |
A "spirálozást" még anno eljátszottam, mikor a 7*7-es megoldását kerestem. E témakörben az lehet még érdekes, hogy melyik legkisebb n-nél lehet már megoldást találni, (1)hogy vissza lehessen zárni, (2)hogy ne lépjen ki a törtvonal a külső pontokon ill. (1) és (2) egyszerre. n=4-re már lehet zárt görgét találni, n=5-re pedig nem kilépőt. A kettő együtt eddig még az ismert n=7.
|
Előzmény: [2161] Csimby, 2007-07-27 01:31:34 |
|
|
|
[2159] Hajba Károly | 2007-07-27 00:54:05 |
Szerintem az általánosító képlet 2(n-1), azaz a mátrix pontjait spirálisan 2(n-1)+1 szakaszból álló törtvonal segítségével tudjuk felfűzni.
S így ezen feltételekkel szerintem már megoldhatóak. Lásd n=7 esetében már két szigorításal is. (nincs kilépés és visszazár)
|
Előzmény: [2148] Csimby, 2007-07-25 18:03:01 |
|