Keresés

Részletes keresés

vurugya Creative Commons License 2014.04.24 0 0 9104

Versenyfeladatként tűztem ki az idei 12-eseknek...

vurugya Creative Commons License 2014.04.24 0 0 9103

Helyes a válasz, de az a) részre is párosítással lehet válaszolni. Ha minden cédulához a komplementerét rendeljük párként, akkor az összes számot tartalmazónak nem lesz párja. Egy cédulának és a párjának mindig 5 végű az összege (azaz pl. a 2-es és a 3-a vagy a 6-os és 9-es kalapokban ugyanannyi cédula lesz). (Ez azért van, mert az összes számjegy összege 45.) Az 5 feliratú kalapban levő cédulák párjai a 0 feliratú kalapba kerülnek, de az az összes számot tartalmazó is itt van, ennek nincs párja, ezért van az 5-ben eggyel több cédula, mint a 0-ban.

sz_laci Creative Commons License 2014.04.24 0 0 9102

ez szép

 

Előzmény: Törölt nick (9101)
Törölt nick Creative Commons License 2014.04.24 0 0 9101

"utolag konnyu okosnak lenni" alapon egy onallo megfejtes a b) kerdeshez (paros-paratlan)

 

- rendezzuk parokba a cedulakat ugy, hogy minden cedula melle odatesszuk azt, amin ugyanazok a szamok vannak, plusz a 0

- minden cedulanak lesz parja, kiveve annak, amin eleve csak egy 0 van

- a cedulaparokon ugyanannyi a szamjegyek osszege

- tehat minden kalapban paros szamu cedula lesz, kiveve a nullasban, ahova meg beesik az extra nullas cedula

Előzmény: Törölt nick (9100)
Törölt nick Creative Commons License 2014.04.24 0 0 9100

csak SilkTest Classic volt keznel, ezert kisse ocsmany a kod, de ez van, viragokat az oltozombe kerem

 

[-] testcase logi ()
 [ ] INTEGER i = 0
 [ ] INTEGER j = 0
 [ ] list of integer kalapok = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
 [ ]
 [-] for i = 1 to 1023
  [ ] string cetli = ""
  [ ] integer szamjegyekosszesen = 0
  [ ] integer kalap = 0
  [ ]
  [-] for j = 0 to 9
   [-] if i / (2 ** j ) % 2 == 1
    [ ] cetli += "{j}"
    [ ] szamjegyekosszesen += j
   [ ]
  [ ] kalap = szamjegyekosszesen %10
  [ ] // print ("cetli: {cetli}, szamjegyek osszesen {szamjegyekosszesen}, kalap {kalap}")
  [ ] kalapok[kalap+1] ++
  [ ]
 [-] for i = 0 to 9
  [ ] print ("{i}-s kalap: {kalapok[i+1]}  db")
  [ ]
 [ ]

 

eredmeny

 

[-] Testcase logi - Passed
 [ ] 0-s kalap: 103  db
 [ ] 1-s kalap: 102  db
 [ ] 2-s kalap: 102  db
 [ ] 3-s kalap: 102  db
 [ ] 4-s kalap: 102  db
 [ ] 5-s kalap: 104  db
 [ ] 6-s kalap: 102  db
 [ ] 7-s kalap: 102  db
 [ ] 8-s kalap: 102  db
 [ ] 9-s kalap: 102  db

 

Előzmény: Törölt nick (9099)
Törölt nick Creative Commons License 2014.04.24 0 0 9099

valaki irja meg pls, hogy jo-e, kulonben kenytelen leszek leprogramozni az ellenorzest :-)

Előzmény: Törölt nick (9098)
Törölt nick Creative Commons License 2014.04.23 0 0 9098

az előbb elszállt, baszki :-( akkor most rövidítek

 

tippem: az 5-ösben eggyel több van, mint a nullásban (104 ill. 103), valamint mindegyikben páros számú, kivéve a nullásban (0 és 5 ld előbb, a többiben 102)

 

a gondolatmenet lényege, hogy a számok mérnöki intuícióm alapján "eléggé egyenletesen" vannak elosztva, az összes 1023 db. cédulából 10x102 egyenletesen, a 3 kakukktojás meg "valahogy"

 

hogy hány számjegyű cédulából hány darab van, azt a Pascal-háromszög tízes sora mondja meg, ez a Wikipédiából kopizva 1 10 45 120 210 252 210 120 45 10 (1 - ez nincs) , ránézésre látszik, hogy az 1-et és a 252-t kell alaposabban megnézni

 

az egy szem tízjegyű cédulán a számok összege 45, tehát az 5-ös kalapba megy

az ötjegyűekből 25x10 egyenletesen elosztva, plusz egy-egy az 5-ös és a 0-s kalapba (szimmetria, mérnöki megérzés :-) )

 

 

 

 

Előzmény: vurugya (9095)
Vad Creative Commons License 2014.04.22 0 0 9097

vagy kombinatórika. vagy bürokrácia :)

 

Előzmény: Vad (9096)
Vad Creative Commons License 2014.04.22 0 0 9096

"E feltételnek eleget téve a lehető legtöbb cédulát készítjük el."

 

Tehát az összeset?

Akkor ez statisztikai analízis

Előzmény: vurugya (9095)
vurugya Creative Commons License 2014.04.19 0 0 9095

Van rengeteg cédulánk, egy tollunk, valamint tíz kalapunk, melyeken rendre a 0; 1; 2; 3; 4; 5, 6; 7; 8, 9 számok vannak felírva. Minden cédulára ráírunk valahányat (legalább egyet) a 0, 1; 2; 3; 4; 5; 6; 7; 8; 9 számok közül, hogy bármely két cédula esetén legyen olyan szám, mely az egyiken rajta van, a másikon nincs. E feltételnek eleget téve a lehető legtöbb cédulát készítjük el.

Adjuk össze mindegyik ilyen cédulán a ráírt számokat, figyeljük meg a kapott összeg utolsó számjegyét, és ennek megfelelő jelzésű kalapba dobjuk be a cédulát! Így mindegyik cédula bekerül valamelyik kalapba.

a) A 0 és az 5 feliratú kalapok közül melyikben van több cédula és mennyivel?

b) Melyik kalapokban lesz páros és melyekben páratlan a cédulák száma?

 

treff2 Creative Commons License 2014.04.19 0 0 9094

A feladványnak van értelme (egy jó megoldásnak pláne, de még gyakorlati haszna is

 

Kollégám mesélte, hogy az öccse gyereküléseket gyártó cégnél dolgozik, ütközési tesztek, sebesség-határ, csecsemő-bábuk, ilyesmi.  Nyilván előadtam a lenti fejtörőt.  Kolléga első reakciója: tök jó, ez hasznos lesz az öcsémnek, lévén hogy két gyereke van.

 

Előzmény: lxt (9091)
lxt Creative Commons License 2014.04.19 0 0 9093

Értem.:-)

 

Ez esetben gratulálok neki az alsó csoportosok számára kreált feladványhoz, mindazonáltal - ha volna egyáltalán értelme -, ajánlanám figyelmébe az előle rejtőzködő, ámde tőle függetlenül is, kétségtelenül létező, magasabb szintű összefüggéseket. De ha így, akkor az más, a problémát megoldottnak tekintheti.:-)

Előzmény: Oszi (9092)
Oszi Creative Commons License 2014.04.19 0 0 9092

... hacsak nem a következőkkel állna elő a feladvány kiagyalója:

- egy tojást akárhányszor ledobhatunk, de az csak egyszer tud összetörni

De bizony, ez pontosan így értendö.

Előzmény: lxt (9091)
lxt Creative Commons License 2014.04.19 0 0 9091

Önmagában, a feladvány logikai ellentmondás, mert 2 lépésben nem lehet eldönteni a kérdést – hacsak nem a következőkkel állna elő a feladvány kiagyalója:

- egy tojást akárhányszor ledobhatunk, de az csak egyszer tud összetörni

- hát persze hogy egyetlen tojást se kell felhasználni, hiszen ha 3 métert számolunk egy emelet magasságának, az még akkor is összetörik, ha szivacsra vagy habra ejtjük…

- de én arra gondoltam, hogy…

- akkor most mondjuk azt, hogy…

 

Nem. A feladványnak van értelme (egy jó megoldásnak pláne, de még gyakorlati haszna is:-)), de nem abban a formában, ahogyan azt elénk tárták.

Továbbá:

- ha nincs olyan emelet, ahonnan leejtve egy (ugyanazt a) tojást, az ne törne össze

- illetve, ha bármelyik emeletről is ejtünk le egy tojást, azok mindig összetörnek

akkor egyváltozós (amihez 6 lépésre (tojásra) volna szükség, de pl. egy algoritmus esetében, ennek eldöntése a 0. egyben utolsó lépés is volna:-)), és akkor azért nincs értelme a feladványnak.

 

Én tehát arra az esetre vázoltam fel az egyik lehetséges megoldást leíró (magyarázó) folyamat első oszlopát, amikor:

1. van az az egy/több emelet, ahonnan leejtve egy tojást, az minden egyéb körülménytől függetlenül összetörik

2. van az az egy/több emelet, ahonnan leejtve egy tojást, a tojás nem törik össze

 

Ugyanakkor szeretnélek arról biztosítani: a fentebb leírtak szerint, 5 lépésből lehet megoldani a problémát; vagyis, megtalálni azt az (földszinttől számolt) 'első' emeletet, ahonnan leejtve egy tojást, az nem törik össze.

 

A korábban felírt oszlop, gyakorlatilag a megoldás kulcsa - már csak a zárat kell megtalálni.:-)

Általában a fától nem látjuk az erdőt…

Előzmény: Oszi (9086)
Elm Creative Commons License 2014.04.17 0 0 9090

Nem, nem, dehogy, mondom, csak átfutottam, az értő olvasáshoz még nem volt elég időm. Vagy tényleg funkcionális analfabéta vagyok...

 

Amúgy kezdem kapisgálni. Különben az volt eddig a bajom, hogy nem értettem, hogy ha az első dobás a 8.-ról indul, akkor miért nem a 16,24,32 a további. Hiszen "szimmetrikusnak" kellene lennie. De most már kezdem sejteni, hogy az első dobásnál, ha nem törik el, akkor a következő szakaszra már csak eggyel kevesebb kell maradjon, "elpazaroltuk" az első dobást, és így tovább...

 

Most már annyi hozzászólás van, hogy ebből tényleg megértem, ha lesz egy kis időm.

Előzmény: Axióma (9085)
DrRetro Creative Commons License 2014.04.17 0 0 9089

Egy rekurzív típusú algoritmus megközelítés:

 

Az első tojást úgy dobjuk, hogy ha eltörik, akkor az elsőtől elindulva az ezt megelőző szintig összesen X dobás legyen, ha nem törik el, akkor pedig a "maradék" épület legyen megoldható X-1 dobásból. Innen kiindulva visszafelé. Egy szintes ház 1 dobás. Minden lépésben az épület a korábbi épületszint dobásainak száma+1-gyel növelhető és az első dobás is erről az emeletről történik.

max emelet - legkevesebb dobás sorrendben:

1 - 1

3 - 2

6 - 3

10 - 4

15 - 5

21 - 6

28 - 7

36 - 8

 

Tehát első dobás 8. emeletről, ha eltört akkor elsőtől elindulva legrosszabb esetben a 7-en törik el a második tojás (8 dobás összesen), ha pedig az első dobás nem tört el, akkor a maradék 28 emeletnyi épületet tudjuk ugyanígy 2 tojással 7 dobásból megmondani (a részletesség kedvéért 15. emeletről ha eltört akkor 9-től a 14-ig max 7 dobás, ha nem akkor 21-ről dobok ami maradék emeletek 6 dobásból lesznek meg ... stb.)

 

Oszi Creative Commons License 2014.04.17 0 0 9088

Kombinatórikai megközelítés:

 

Van egyrészt egy eljárás, miszerint először honnan dobod le a tojást, majd innen hogyan lépsz tovább, ha eltört; illetve hova, ha nem tört el. Ezt követően megint van egy terv arra, hogy az egyes kimenetek után hogyan lépsz tovább.

A terv elágazó, de előre rögzített, konstans.

 

Van másrészt a mérési eredmény, a dobások eredménye. Ha eltört a tojás, írjunk 1-t, ha nem tört el, írjunk 0-t.

Ha mindkettő eltört, onnantól írjunk a megmaradó helyekre 0-t.

 

Így ha n dobásunk van, akkor van egy n számjegyből álló sorozatunk, amiből legfeljebb kettő lehet 1-es, a többi 0-s.

A lehetséges sorozatok száma felső határt ad arra, hogy n dobásból hány kimentet tudunk megkülönböztetni.

Nyolc dobás esetén van 1 olyan sorozat, ami nem tartalmaz egyest, 8 olyan, ami pontosan egy darab egyest, 28 olyan, ami két darab egyest tartalmaz. Ez 37.

Hét dobásra 29 lenne a végeredmény, annyi tehát nem elegendő egy 36 emeletes házhoz.

 

A nyolc dobás tehát szükséges.

A megfelelő dobási rendszerd megalkotásával pedig igazolható, hogy elégséges is.

Axióma Creative Commons License 2014.04.17 0 0 9087

OK, jatsszunk itt, a forumon! Te bemondod, hogy i. dobas k. emelet, mi meg bemondjuk, hogy osszetort vagy sem, es mondhatod a kovetkezot. Meglatjuk, menni fog-e max. ket tojas max. 5 dobasbol.

(Az elso oszlopodban eleve nem 5 dobas van...)

Előzmény: lxt (9083)
Oszi Creative Commons License 2014.04.17 0 0 9086

Nem hiszem, hogy ez jó lehet. 

Öt dobással még korlátlan számú (ez esetben: öt) tojás birtokában is csak

25=32

lehetséges kimenetet tudunk megkülönböztetni. 

Nekünk meg csak két tojásunk van. 

Nekem kombinatorikai alapon az jött ki, hogy nyolcnál kevesebb dobás nem elég, nyolcra pedig van megoldásom. 

 

Persze, lehet, hogy valamit elnéztem...

Előzmény: lxt (9083)
Axióma Creative Commons License 2014.04.16 0 0 9085

Ebbol is latszik, hogy nemhiaba nincs meg a tanar szakom:)

Előzmény: Elm (9084)
Elm Creative Commons License 2014.04.16 0 0 9084

Nem, nem jobb. Az elvet nagyjából értem, de ehhez is le kellene üljek egy papírral, és lerajzolni, hogy megértsem... :o)

De azért köszönöm az igyekezetet. Meg fogom tenni. :o)

Előzmény: Axióma (9082)
lxt Creative Commons License 2014.04.16 0 0 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

Előzmény: Elm (9076)
Axióma Creative Commons License 2014.04.16 0 0 9082

Ez forditva sokkal egyszerubb feladat!

Hany emeletes maximum az a haz, amibol N dobassal el tudod donteni a leirt feltetelekkel, hogy pont hol torne el?

[N=1 es N=2 konnyen atgondolhatoak (1,3)].

Legyen (N-1)-re ez a szam K, es keressuk N-re a maximumot.

Dobd ki az elsot az N. emeletrol. Ha eltorik, a masodik tojassal az also N-1 emelet lentrol kezdve egyszeruen vegigprobalhato a maradek N-1 probalkozasodbol (es mas megoldas nincs is a pontos valaszhoz); ha nem torik el, akkor az N+1 ... N+K emeletek kozott a ket ep tojassal a rekurzio miatt meg tudod mondani, hogy pontosan meddig nem torik (sot, ennel tobbrol biztos nem).

Az biztos, hogy ha az elsot magasabbrol dobod, es torik, akkor az alsok kozul nem tudsz biztosat mondani. Az is, hogy lentebbrol meg nem erdemes kezdeni, ha egyszer N-rol is lehet, es maxot keresunk.

Adodik, hogy N-re 1+...+N a legmagasabb epulet, amire meg tudod mondani. Sot, az algoritmus is adodik: az N, N+(N-1), N+(N-1)+(N-2), ... ,N+...+2, N+...+1 emeletekrol kell kidobni addig a tojast, amig el nem torik, es a ket utolso dobas kozott pont annyi kulonbseg lesz, amennyi dobasod me'g visszamaradt, hiszen igy csinaltuk a sorozatot, alulrol haladva az utolsotol felfele egyesevel kiprobalod a masodik toresig.

Forditva mar csak az a kerdes, hogy mi a legkisebb N, aminek a szumma 1..N-je mar eppen eleri a kivant magassagot.

 

Igy jobb? Csak elsore nem akartam leloni a konkret megoldast, ravezetes akart lenni amit irtam.

 

Előzmény: Elm (9081)
Elm Creative Commons License 2014.04.16 0 0 9081

Köszi a válaszokat, párszor elolvastam, még nem teljesen értem, legalábbis nem tudom elég jól vizualizálni, az "n-k" formulák néha még gondot okoznak... :o)

Lesz egy kis időm elemzem, jó lesz, köszi még1x.

Oszi Creative Commons License 2014.04.14 0 0 9080

Köszönöm!

Megvan!

Az optimális stratégiával legfeljebb nyolc dobásra van szükség.

Előzmény: FASIRT (9079)
FASIRT Creative Commons License 2014.04.08 0 0 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á.

Előzmény: Elm (9076)
Axióma Creative Commons License 2014.04.08 0 0 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).

Előzmény: Elm (9076)
FASIRT Creative Commons License 2014.04.08 0 0 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.

Előzmény: Elm (9076)
Elm Creative Commons License 2014.04.08 0 0 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?

attoparsec Creative Commons License 2013.10.12 0 0 9075

:: Megnéztem a Wiki-n a moho-t, de én semmi hasonlóságot nem látok a moho és az itt leírt logika között

 

a moho algoritmus lenyege, hogy reszfeladatokra osztja az eredeti problemat es ezek kozul azt oldja meg, amelyik a legnagyobb haszonnal jar. a feladat "maradekat" ugyanebben a stilusban oldja meg, amig a feladat "el nem fogy".

 

ebben a feladatban ez ugy nyilvanult meg, hogy a bemeneti karaktersorbol addig pakolt egy dobozba, ameddig az egyaltalan lehetseges.

egy nem moho algoritmus hamarabb valtana dobozt mint a moho, abban a remenyben, hogy a maradek karaktersor joval kevesebb dobozvaltasbol megoldhato. jelen feladatnal ez nem lehetseges, ezert optimalis itt a moho algoritmus.

Előzmény: PikkPukk (9074)

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!