zadatak za one koji vole da razmisljaju

[shimmy]

Pozzz,

evo jednog problema, razbijam glavu vec duze vreme, na putu sam resenja, ali ne bi bas rekao da je opsteg tipa

ovo pitanje su postavili mom drugaru pri razgovoru za posao(neznam i nije ni bitno koja je firma)…

dakle, zgrada ima 100 spratova, na raspolaganju su vam 2 jaja napravljena od nekog nepoznatog vam materijala(dakle nisu kokosija), vas zadatak je da experimentalno pomocu ta 2 jaja, dodjete do zakljucka koliko su izdrzljiva ta jaja, tj KOJI JE NAJVISI SPRAT SA KOG MOZETE BACITI/PUSTITI JAJE A DA SE ONO NE RAZBIJE? ???

zadatak je nadam se jasan, NAPOMENA: resenje/algoritam mora biti sto tacniji i efikasniji(da se ubode tacni sprat, sa sto manjim brojem bacanja jaja. i naravno ta 2 jaja imate pravo bacati neogranicen broj puta(pod uslovom da ukoliko bacite jaje i ono se razbije, onda vise nemate pravo da ga koristite)

nakon sto im je izneo svoje resenje, i prokomentarisao ga. oni su mu rekli kakav su odgovor ocekivali…

njihovo resenje(komisije) je totalno debilno, oni su ocekivali odgovor tipa binarnog pogadjanja, ili sta vec, tj…

baciti jedno jaje sa 50 sprata, pa ukoliko se razbije, znaci da je izdrzljivost jajeta negde izmedju 0tog i 49 sprata, pa sa tim drugim jajetom sad pokusati negde izmedju 0 i 50, a ukoliko se ne razbije, onda pokusavati negde izmedju 50 i 100, sa preostala 2 jajeta, sto je napominjem debilana od resenja, jer NEMA VEZE SA TACNOSCU, jer se moze desiti da razbijemo oba jajeta, i ni ne dodjemo do preciznog podatka o izdrzljivosti jajeta, vec samo orijentacionog tipa…a nije ni efikasno

ajmo da vas cujem tj vidim??

resenje do kog sam dosao je super, ali gubi na efikasnosti ukoliko zgrada naprimer ima 1000 spratova, ili ukoliko imamo na raspolaganju 3 ili vise jaja

 

[dvajedan]

Pretpostavimo da je resenje X. Bacimo jaje sa sprata X, ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa spratova 1, 2, …, X – 1 ako se ne razbije bacimo jaje sa X + (X – 1), ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa spratova X + 1, X + 2, …, X + (X – 1) – 1 . Ako se ne razbije bacimo jaje sa X + (X – 1) + … + (X – X + 2), ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa sprata X + (X – 1) + … + (X – X + 3) + 1 najmanje X za koje se ovo moze uraditi je X = 14, pa je to ujedno i resenje
View attachment 299

To ako tako saopštiš komisiji, reći će ti: Dečko ti si mnogo pametan, bolje traži drugi posao :connie_pumpkinsmile: .

 

[system]

Ovako, rešenje je vrlo jednostavno. Baca jedno jaje sa svakog drugog (parnog npr. 4.) sprata. Ako mu se slomi na 100. (a na prethodnim parnim nije) onda on baca na 99. i ako mu se razbije tu onda je sve jasno. Ako mu se ne razbije, onda može da preživi i sa 100.

 

[shimmy]

Ovako, rešenje je vrlo jednostavno. Baca jedno jaje sa svakog drugog (parnog npr. 4.) sprata. Ako mu se slomi na 100. (a na prethodnim parnim nije) onda on baca na 99. i ako mu se razbije tu onda je sve jasno. Ako mu se ne razbije, onda može da preživi i sa 100.

ok za pocetak ovo resenje radi, ali se postavlja pitanje efikasnosti, ovakav algoritam ce raditi jako dobro ukoliko su svojstva materijala losa tj ukoliko jaje moze da izdrzi recimo pad sa npr 9 sprata(trebalo bi ti 6 bacanja), ali ukoliko je jaje recimo jako izdrzljivo, i recimo da moze da izdrzi pad sa 99 sprata, onda ovakvim putem treba 51 bacanje, sto bas i nije efikasno u odnosu na onih 6 bacanja…kombinacija ovakvog algoritma sa mojim resenjem bi bilo ultra efikasno kada bi recimo imali 3 jaja…

Pretpostavimo da je resenje X. Bacimo jaje sa sprata X, ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa spratova 1, 2, …, X – 1

ok, ovo je osnova za moje resenje, s time sto sam ja krenuo od varijante da je X=10, znaci bacam jedno jaje sa 10, 20, 30 itd sprata, sve dok se ne razbije, i onog trenutka kad se razbije, onda sa X-10 krecem da bacam sa svakog sprata dok ne dodjem do sprata pucanja jaja.

znaci ukoliko jaje izdrzava pad sa 9 sprata, dolazimo do resenja: bacimo sa 10, razbilo se, pa drugo jaje bacamo sa 1,2,3,4,5,6,7,8,9, znaci sve ukupno je trebalo 10 bacanja, sto je losije od Zdroidovog resenja, ali zato ukoliko jaje moze da prezivi pad sa 99 sprata, dok se recimo na stotom lomi, onda treba samo 19 bacanja a ne 51. ovakav algoritam bi naravno bio jos bolji ukoliko bi imao recimo 3 jaja na raspolaganju, jer bi isao prvo po 10 spratova, a onda bi mogao da predjem na po 2 sprata, tj na parno kao droid, i to bi dodalo na efikasnosti…

ako se ne razbije bacimo jaje sa X + (X – 1), ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa spratova X + 1, X + 2, …, X + (X – 1) – 1 . Ako se ne razbije bacimo jaje sa X + (X – 1) + … + (X – X + 2), ako se razbije drugim jajetom nadjimo gde je trazeni sprat bacajuci 2. jaje sa sprata X + (X – 1) + … + (X – X + 3) + 1 najmanje X za koje se ovo moze uraditi je X = 14, pa je to ujedno i resenje
View attachment 299

ovde samo ne razumem zasto ukolko se jaje ne razbije sa X, ti bacas sa X+(X-1) ?? ukoliko se jaje razbije, nema dvoumice, mora se krenuti od prethodnog poznatog stanja da je jaje izdrzalo i gurati po 1, kako bi sigurno dosli do resenja…

i nije mi jasno kako si dosao do broja 14?? ukoliko sam dobro razumeo bacili bi recimo sa 14 sprata, ukoliko se razbilo prelazimo na standar trazenje od 0tog sprata do 13, da vidimo gde je tacka pucanja, ukoliko se nije razbilo dalje bacamo sa 27 sprata?(14+(14-1))??
i zasto je to efikasniji nacin nego da se ide po 10 spratova? probao sam recimo da idem po 20 spratova i to je vec manje efikasno…

razmisljao sam i o algoritmu gde bi krenuo prvo po jedan sprat znaci bacam sa prvog, sa drugog, itd, i onda nakon uspesnih N(treba smisliti koji broj izabrati da bi bilo efikasno) bacanja, povecamo prag bacanja, znaci bacili bi recimo sa prvog, sa drugog, sa treceg, pa onda ne povecavamo za po 1 sprat, vec recimo za 5, pa za 10 itd…ali ni tome nisam isterao do kraja…

 

[system]

ok za pocetak ovo resenje radi, ali se postavlja pitanje efikasnosti, ovakav algoritam ce raditi jako dobro ukoliko su svojstva materijala losa tj ukoliko jaje moze da izdrzi recimo pad sa npr 9 sprata(trebalo bi ti 6 bacanja), ali ukoliko je jaje recimo jako izdrzljivo, i recimo da moze da izdrzi pad sa 99 sprata, onda ovakvim putem treba 51 bacanje, sto bas i nije efikasno u odnosu na onih 6 bacanja…kombinacija ovakvog algoritma sa mojim resenjem bi bilo ultra efikasno kada bi recimo imali 3 jaja…

ok, ovo je osnova za moje resenje, s time sto sam ja krenuo od varijante da je X=10, znaci bacam jedno jaje sa 10, 20, 30 itd sprata, sve dok se ne razbije, i onog trenutka kad se razbije, onda sa X-10 krecem da bacam sa svakog sprata dok ne dodjem do sprata pucanja jaja.

znaci ukoliko jaje izdrzava pad sa 9 sprata, dolazimo do resenja: bacimo sa 10, razbilo se, pa drugo jaje bacamo sa 1,2,3,4,5,6,7,8,9, znaci sve ukupno je trebalo 10 bacanja, sto je losije od Zdroidovog resenja, ali zato ukoliko jaje moze da prezivi pad sa 99 sprata, dok se recimo na stotom lomi, onda treba samo 19 bacanja a ne 51. ovakav algoritam bi naravno bio jos bolji ukoliko bi imao recimo 3 jaja na raspolaganju, jer bi isao prvo po 10 spratova, a onda bi mogao da predjem na po 2 sprata, tj na parno kao droid, i to bi dodalo na efikasnosti…

ovde samo ne razumem zasto ukolko se jaje ne razbije sa X, ti bacas sa X+(X-1) ?? ukoliko se jaje razbije, nema dvoumice, mora se krenuti od prethodnog poznatog stanja da je jaje izdrzalo i gurati po 1, kako bi sigurno dosli do resenja…

i nije mi jasno kako si dosao do broja 14?? ukoliko sam dobro razumeo bacili bi recimo sa 14 sprata, ukoliko se razbilo prelazimo na standar trazenje od 0tog sprata do 13, da vidimo gde je tacka pucanja, ukoliko se nije razbilo dalje bacamo sa 27 sprata?(14+(14-1))??
i zasto je to efikasniji nacin nego da se ide po 10 spratova? probao sam recimo da idem po 20 spratova i to je vec manje efikasno…

razmisljao sam i o algoritmu gde bi krenuo prvo po jedan sprat znaci bacam sa prvog, sa drugog, itd, i onda nakon uspesnih N(treba smisliti koji broj izabrati da bi bilo efikasno) bacanja, povecamo prag bacanja, znaci bacili bi recimo sa prvog, sa drugog, sa treceg, pa onda ne povecavamo za po 1 sprat, vec recimo za 5, pa za 10 itd…ali ni tome nisam isterao do kraja…

Ček, ček. Razmisli malo. Dao sam primer za 100. sprat, nisam mislio da je to baš taj, može i da bude negi drugi npr. 54.

 

[shimmy]

Ček, ček. Razmisli malo. Dao sam primer za 100. sprat, nisam mislio da je to baš taj, može i da bude negi drugi npr. 54.

da da, o tome se i radi, tvoje resenje radi, ali sto je veci sprat u pitanju, treba ti vec broj bacanja. znaci resenje ti je tacno, ali nije dovoljno efikasno…

nadam se da smo se dovoljno razumeli. znaci tvoj medot je nesto efikasniji ukoliko se desi situacija da je jaje poprilicno lomljivo(treba ti manji broj bacanja od ostalih algoritama u nizim spratovima), ali zato svu tu efikasnost izgubis na visim spratovima npr. koliko puta treba da bacis jaje da bi dosao do rezultata da se npr lomi na 97 a izdrzi na 96 spratu?

 

[1112]

Може са укупно 15 бацања.

Ако имам само једно јаје, онда морам да идем од најнижег могућег спрата ка највишем по један корак, јер ако нешто прескочим, па баш тад ми пукне, не могу знати да ли би пукло на спрату који сма прескочио.

Када ми прво јаје прође m-ти спрат, а разбије се на n-том, онда преостало јаје морам да бацам са (m+1)-вог итд, па највише до (n-1)-ог, што значи да ми у том случају треба још у најгорем случају n-m-1 бацања.

Да бих све завршио са 15 бацања, прво јаје не смем на почетку да бацим са вишег спрата од 15-тог. Дакле, бацам га са 15-тог. Ако се разбије, у највише 14 бацања другог јајета долазим до резултата. Ако прво јаје прође пробу, онда морам имати на уму да сам једно бацање већ потрошио, па да ми је преостало 14. Ако знам да је прво јаје прошло 15-ти спрат, онда други пут не смем да га бацим са вишег спрата од 29-тог, јер ако се разбије, за бацање другог јајета имам још 13 покушаја. Дакле, алгоритам бацања првог јајета са спратова је

15,29,42,54,65,75,84,92,97,100.

Затим се друго јаје баца почев од спрата изнад последњег спрата које је прво јаје прошло (или са првог ако се друго одмах разбило).

Е, сад ја имам питање за вас: Шта да смо имали три јајета?

 

[dvajedan]

http://sr.wikipedia…аскалов_троугао
http://sr.wikipedia…мни_коефицијент

14ti sprat x+1 nad 2 >= 100 iliti recimo (15×14)÷(2x1) >=100

Tako da… sa 3 jajeta, sprat bi bio 10 nad 3 znači 9ti.

 

[shimmy]

da smo imali 3 jajeta to je prosta prica…

ja ne kontam samo ne kontam da li je to vase efikasnije od varijante po 10 spratova, pa kad pukne onda po 1…

i ne kontam jel bolje 15, 29 ili 14, 27…

a 3 jajeta nam daju opciju, da nakon tih skokova 10, 20, 30…(po mom), ili 15, 29…po nedeljkovom, ili 14,27, po dvajedan algoritmu, onda umesto da idemo po jedan sprat, mozemo ici svaki drugi sprat, jer kad dodje do razbijanja jajeta ostaje nam jedno da proverimo i medju sprat…bar ja tako gledam na to

 

[1112]

Да, јесте 14 бацања, мало сам се забројао:

14,27,39,50,60,69,78,84,90,95,99,100.

Добро, колико би било потребно бацања, ако имамо на располагању 10 јаја?