|
|
 |
lxt
2014-04-16 20:42:26
|
9083
|
Maximum 5 kísérlet kell hozzá, de akkor már tényleg elmondhatod magadról, hogy tök balszerencsés vagy.:-)
Hogy vegyük komolyan egymást, leírom ide az egyik lehetséges megoldás 'első oszlopát' - bár tegyük hozzá, azért ennél van egy nagyságrendileg elegánsabb (egyszerűbb, viszont kevésbé szemléletes) megoldása is a problémának.:-)
34
---
32
---
27
---
18
---
9
---
4
---
2 |
|
 |
FASIRT
2014-04-08 11:29:36
|
9079
|
A megoldás azon alapul, hogy egy tojással csak az előző egy lépésenkénti eljárás ad megoldást n emelet esetén legfeljebb n lépésben. A második tojással úgy osztom ketté az n emeletes házat, hogy ledobom a k-adik emeletről. Ha eltörik, a másik tojással az alacsonyabb szinteken k-1 lépésben eldöntöm, hogy mi a megoldás, ha nem, a fölső n-k emeletre megint van két tojásom. Ha k-t úgy választom meg, hogy ennyi emeleten két tojással k-1 lépéssel eredményt kapjak, akkor k lépés kellett az n emelethez. 3 emelet esetén 2 kísérlet kell, ha a másodikról ledobott tojás eltörik, akkor a másikat az elsőről kell ledobni, ha nem akkor a harmadikról. Ha ez a legfelső 3 emelet, és ide úgy jutottál el, hogy az alatta levő emeletről még nem tört el a tojás, akkor még az alatt is lehet 2 emelet, amit a másik tojással próbálhatsz végig két kísérlettel,, ha az első mégis eltört volna. 3 kísérlettel tehát 6 emeletet lehet végigpróbálni. Ez alatt 1+3 emelet lehet a 4 kísérlethez, és így tovább, minden egyes plusz kísérlettel eggyel több plusz emelet adható hozzá. |
|
 |
Axióma
2014-04-08 11:16:42
|
9078
|
A kulcs ott van, hogy az elso tojas csak akkor torhet el, ha a masodikkal az utolso "nem torott el" es az eltores helye kozotti minden emeletet kiprobalhatunk (alulrol felfele), hiszen masodikra mar nem kockaztathatsz, ha atlepsz valamit es utana egybol torik, akkor nem tudsz biztos valaszt mondani.
A probalkozasokat meg ugy kell erteni, hogy TE megmondod elore azt a szamot, hogy legfeljebb hanyat fogsz probalkozni, amibol meg tudod mondani az eredmenyt. Azt nem tudod, hogy most eppen eros vagy gyenge tojasokat kaptal, csak azt hogy az egyik szint es alatta nem tornek el, felette barhol eltornek (az elobbi miatt tudsz a 36 lepesbol faragni). A lenyeg, hogy amit vallalsz, azt a legrosszabb esetben is teljesitened kell, nem lehet bizonytalan kimenetel.
Megfogalmazhato ugy is a kerdes, hogy melyik legkisebb szam eseten letezik algoritmus, amelyikre igaz, hogy ennyi lepesszamon belul minden esetben helyes valaszt ad.
Nem tudom, mennyivel sikerult megvilagositani a minmax problemat...
Ez egyebkent azt hiszem mas emeletszammal de idei Zrinyi feladat is volt (talan tobb evfolyamon, 5. osztalyosoknak biztosan). |
|
 |
FASIRT
2014-04-08 11:03:14
|
9077
|
Egy kísérlet kimenetele jó, ha el tudom dönteni, mit bír ki egy tojás, rossz, ha nem tudom eldönteni, mert további kísérletekre van szükség. Például egy megoldás, ha elkezdem az első emeleten. Ha eltörik, már meg is van a válasz, ha nem, megyek a másodikra. Ezzel az eljárással a legrosszabb esetben 36 kísérletre van szükség, ha olyan kemény tojásaim vannak, hogy csak a legfelső emeletről leejtve törnek el (vagy még akkor sem). Mivel ezt egy tojással is el tudnám játszani, viszont két tojásom van, feltehetően van olyan algoritmus is, amivel ennél kevesebb kísérlet is elég. |
|
A hozzászólás:
 |
Elm
2014-04-08 10:50:31
|
9076
|
sziasztok,
kicsit pihent a topik, feldobnám egy kérdéssel. Adott egy régi feladat, szerintem itt is szerepelt, még a megoldását is tudom (valszeg a jót), de nem értem. Le tudná valaki írni a megoldást magyarázattal együtt?
Ez az a feladat :
Van 2 tojásunk és egy 36 emeletes épület. Ha valamelyik emeleten kidobunk egy tojást, akkor az vagy összetörik vagy nem. Állapítsuk meg melyik a legmagasabb emelet, ahol még nem törik össze egy tojás, méghozzá úgy, hogy a lehető legkevesebb próbálkozást kelljen elvégezni a legrosszabb esetben is.
Esetleg egy kis segítséget a feladat átírásához is : "legkevesebb próbálkozást kelljen elvégezni a legrosszabb esetben is" eléggé hülyén hangzik szerintem. Vagy matematikailag helyes, csak nyelvtanilag fura? |
|
|
Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!
|