[V.....d]

#zagadkivorlanda #kiciochpyta #matematyka #logika #lamiglowki

JAJKA

Przypuśćmy, ze chcesz wiedzieć, z których pięter 36-piętrowego budynku można bezpiecznie zrzucać jajka (w jakimś specjalnym pojemniku), a z których już nie, bo rozbijają się podczas upadku. Aby wyeliminować element przypadkowości i ewentualne różnice między poszczególnymi jajkami poczynimy kilka (sensownych!) założeń:

•Jajko, które przetrwa upadek, może być użyte ponownie (jajko nie uszkadza się podczas upadku i nie jest słabsze).

• Rozbite jajko nie może być ponownie użyte do dalszych eksperymentów.

• Efekt upadku jest taki sam dla wszystkich jajek.

• Jeśli jajko rozbije się zrzucone z pewnego piętra, rozbije się też zrzucone z wyższego piętra.

• Jeśli jajko przetrwa upadek z pewnego piętra, przetrwa też zrzucone z niższego piętra.

Przypuśćmy, że mamy dwa jajka.

Pytanie: jaka jest najmniejsza liczba kroków (zrzuceń) prowadzących do ustalenia najniższego piętra, po zrzuceniu z którego jajko się rozbija?

[valdo]

@Vorland: Trzeba wykonać 4 rzuty

[V.....d]

@valdo: Wyjaśnij dlaczego. Ja Ci powiem, że się nie zgodzę ;)

[valdo]

@Vorland: Zakładałem dzielenie na pół. Czyli najpierw z 18. piętra, potem z 9 lub 27, potem z 4, 13, 23 lub 31, no i potem znowu na pół każdy zakres.

[V.....d]

@valdo: No ale nie określisz piętra i potrzebujesz kilku kroków więcej niż 4.

Zobacz. Wybieram, że jajko się stłucze do 36 piętrze. Na Twoim przykładzie, na 18 nie pęka a jedyną drogą, by takie piętro znaleźć jest zrzucanie po koleju z 19, 20... az do 36, co daje nam 18 kroków a nie 4 ;) Trzeba uwzględnić najgorsze przypadki :)

[valdo]

@Vorland: źle rozumujesz, ja też popełniłem błąd bo 5 kroków w moim sposobie trzeba;)

Rzucam z 18 - przeżyło.

Rzucam z 28 - przeżyło

Rzucam z 32 - przeżyło

Rzucam z 34 - przeżyło

Rzucam z 35 lub 36 i wiem.

[Pitzonik]

@Vorland: czy to dobra odpowiedz? Ja wybieram rozbicie jajka po rzucie z 2. pietra. I co teraz?

Proponuje pierwszy rzut z 1/3 wysokosci, nastepny z 1/3 pozostalego zakresu, gdy cale jajko (czyli do 12 cale, rzut z 12+(36-12)*1/3 itd az do rozbicia). gdy rozbite, rzut co 1 pietro od dolnego zakresu.

@valdo:

[valdo]

@Pitzonik: Jak z drugiego to wtedy:

18 piętro - rozbite

8 piętro - rozbite

4 piętro - rozbite

2 piętro - rozbite

Czyli wiesz, że tylko z 1. piętra przeżyje

[V.....d]

@valdo: To odwróćmy - zbije się z 1.

1szy rzut - 18pietro zbite - zostaje jeden rzut

2 rzut i nie jesteś w stanie tego ustalić, o ile nie zaczniesz od 1szego piętra. Przyjmujemy najgorszy możliwy scenariusz. Pamiętaj, że masz tylko dwa jajka.

[Pitzonik]

@valdo: "przypuscmy, ze mamy dwa jajka".To optymalizacyjne zadanie, a nie zwykly binsearch.

[Vanr_]

@valdo:

Jak z drugiego to wtedy:

18 piętro - rozbite

8 piętro - rozbite

4 piętro - rozbite

2 piętro - rozbite

Przypuśćmy, że mamy dwa jajka.

Tylko ja tu widze problem? Pierwsze dwie proby pozbawiaja cie mozliwosci wykonywania nastepnych, bo nie masz wiecej jajek.

[V.....d]

@Pitzonik: dobrze prawisz, binary search jest w tym przypadku intuicyjne :) Nalezy znalezc inna droge do rozwiazania. Twoje rozumowanie jest poprawne, jednak chcę, by mi ktoś podał konkretną liczbę i drogę dojścia do tej minimalnej liczby kroków ;)

hint:

[Vanr_]

Moja propozycja:

Jajka oznaczone jako J1 i J2.

Zrzucam J1 z 18 pietra.

Jesli J1-18 sie zbija, zrzucamy J2 po jednym pietrze zaczynajac od pietra 1 do momentu, az sie rozbije. (czyli kiepska sytuacja, duzo krokow)

Jesli J1 sie nie zbija, zrzucamy je ponownie z pietra 27.

Jesli sie zbija, wykonujemy procedure ze zrzucaniem J2 po jednym pietrze 19-26.

Jesli J1-27 sie nie zbija, zrzucamy je ponownie z 32 pietra.

Jesli sie

[Vanr_]

@Vorland: Cisza oznacza, ze moja kosmicznie blyskotliwa odpowiedz wyczerpala temat czy ktos zapomnial ze wypadaloby potwierdzic poprawne rozwiazanie? ಠ‿ಠ

[V.....d]

@Vanr_: nie padła poprawna odpowiedź. Podam ja jutro

[LuGo_]

@Vorland: A ja nadal czekam... ( ͡° ʖ̯ ͡°)

[V.....d]

@LuGo_: Wydawało mi się że odpowiedziałem w tagu :>

[V.....d]

@LuGo_:

https://news.ycombinator.com/item?id=4274631

http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html