Zadanie z rozmowy o pracę. Czy umiesz mysleć nieszablonowo.

pytanie zadane 11 stycznia 2016 w Algorytmy przez Zero Dyskutant (8,210 p.)

Masz drabine 100 szczeblową i dwie żarówki. Musisz znaleźć najniższy szczebel z którego jak zrzucisz żarówke to się ona rozbije. Zaproponuj optymalny algorytm. Oczywiście jesli żarówka upadnie i się nie rozbije możesz użyc jej kolejny raz.

10 odpowiedzi

odpowiedź 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

Po takim stereotypowo googlowym pytaniu to by mnie korciło wyjść.

(...ale w sumie skuteczne, patrząc na odpowiedzi innych)

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Nie widziałem tego zadania w google.

Na sześćdziesięciu kandydatów rozwizało je trzech.

komentarz 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

Strzał:

pierwszą skaczę co 10: szczebel 10, 20... 100. Jeśli rozbiła się na np. 40 to pozostaje drugą sprawdzić po kolei szczeble 31..39. Maksymalna liczba testów: bodajże 20. Na oko dla N szczebli, jeśli pierwszą żarówką będę skakał sqrt(N) razy, to maksymalnie będę potrzebował 2N testów.

Co do "googlowego pytania" nie miałem na myśli "znalezione w googlu", tylko brzmi jak stereotypowe pytanie zadawane w Googlu. Myliłem się, te stereotypowe są znacznie gorsze.

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Jaki przypadek jest najgorszy?

Dobrze myślisz ale nie rozumiem sprawdzania drugą od 11 do 39.

Jeśli skaczesz o 10 to 20 i 30 juz sprawdziłeś.

komentarz 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

oczywiście literówka, miałem na myśli 31..39.

Najgorszy to pewnie gdy rozbija się na 100, bo dojeżdżam do 100 i muszę jeszcze sprawdzić 91..99.

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Przy przypadku 100 jadąc po 10 trafiasz po 10 ruchach.

Najgorszy to chyba 99.

komentarz 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

Przypadek 100 rozumiem jako "rozbija się na szczeblu 100". Jeśli dla Ciebie przypadek 100 to "nie rozbija się na szczeblu 100", to tak, wtedy wystarczy 10.

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Przepraszam, rozpędziłem się. Masz rację.

komentarz 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

Poeksperymentowałem z małym skrytem Pythona, skacząc po kolei o 14, 13, 12... poprawiłem minimum do 14 testów. Nie jestem jeszcze pewnie skąd to 14, znalazłem metodą prób i błędów. W każdym razie działa. Idę spać.

odpowiedź 12 stycznia 2016 przez Porcupine Nałogowiec (31,560 p.)

odpowiedź 12 stycznia 2016 przez Benek Szeryf (91,070 p.)
edycja 12 stycznia 2016 przez Benek

Widzę, że się męczycie, ja bym to zrobił w ten sposób. Mamy dwie żarówki, więc najpierw trzeba zrzucić pierwszą żarówkę z N-tego szczebla, czyli 1 rzut, jak się rozbije, to zostaje nam N-1 opcji, by sprawdzić z którego niższego szczebla zbije się druga żarówka. Czyli 1+N-1 daje nam dokładnie N. Jeśli pierwsza żarówka się nie rozbije, to zrzucamy ją następnie z N+N-1-tego szczebla. Ktoś zapyta dlaczego nie z 2N-tego. Dzieje się tak dlatego, że "straciliśmy" już jeden rzut zrzucając żarówkę z N-tego szczebla. Jeśli pierwsza żarówka rozbije się z N+N-1-tego szczebla, to mamy drugą żarówkę i N-2 prób. -2 dlatego że w pierwszym kroku pierwsza żarówka się nie rozbiła i rozbiliśmy ją w drugim kroku, zrzucając ją z N+N-1-tego szczebla, stąd właśnie -2.

Matematycznie wyglądałoby to tak: N + (N -1) + (N - 2) + (N - 3) ... <= 100. Zwróćcie uwagę, że kolejne wartości w nawiasie są pomniejszane, dlatego że wcześniej musieliśmy wykonać rzuty z niższych szczebli. Sumę N kolejnych liczb naturalnych możemy znaleźć za pomocą wzoru: sum = N (N + 1) / 2

Czyli mamy: N (N + 1) / 2 <= 100 --> N^2 + N - 200 <= 0, rozwiązanie to: N1 = -14.66; N2 = 13.65. N1 odpada, bo rozważamy liczby dodatnie. Ponieważ parabola ma ramiona skierowane w górę (współczynnik a jest dodatni), to aby nierówność była spełniona musimy rozważyć wszystkie liczby naturalne poniżej 14. W praktyce 14 (13.65) będzie najbliższą liczbą spełniającą równanie (nie nierówność).

Pokaż 8 poprzednich komentarzy

komentarz 12 stycznia 2016 przez Benek Szeryf (91,070 p.)

Maksymalnie w 14 krokach. Ale możesz znaleźć szybciej, jak np. będzie to pierwszy szczebel, to wystarczą 2 rzuty: z 14. szczebla (pierwsza żarówka) a potem z 1. (druga żarówka).

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Chapeau bas :) Dzieki.

komentarz 12 stycznia 2016 przez Wojciech Trojanek Obywatel (1,230 p.)
edycja 13 stycznia 2016 przez Wojciech Trojanek

Również oddaje honory :) ta opcja jest lepsza jeśli chodzi o ilość skoków :D pytanie tylko co z tą optymalnością i jak do tego się odnieść. Zakładając że myślimy dosłownie o pełnowymiarowej drabinie i o faktycznej wytrzymałości żarówki uwzględniając fizykę to szybciej rozwiązanie znajdziemy skacząc o 10 bo strzeli zapewne w pierwszych szczeblach tzn jest bardziej realistyczne - większe prawdopodobieństwo że żarówka strzeli w pierwszej 20tce niż pozostałej 80tce szczebli. Jeśli natomiast weźmiemy pod uwagę algorytm który ma w założeniu najszybsze odnalezienie liczby z zakresu od 1 do 100 mając na to dwie próby władowania się "na minę" to jeśli losowana liczba będzie jedną z 15 liczb (59,68,69,77,78,79,86,87,88,89,95,96,97,98,99) to algorytm skoku o 10 przegra z kretesem. Dla tych wartości liczy od 15 do 19 kroków. Wszystko zależy od punktu odniesienia. :) lubię takie zagadki można z kimś mądrym pogłówkować :D

komentarz 13 stycznia 2016 przez Benek Szeryf (91,070 p.)

To jest najbardziej optymalny algorytm, ponieważ milcząco zakładamy że żarówka może się rozbić zrzucona z dowolnego szczebla z takim samym prawdopodobieństwem. Jeśliby założyć inaczej, tzn. prawdopodobieństwo zbicia żarówki z kolejnego i-tego szczebla by rosło (bo rzucamy przedmiot z coraz większej wysokości), to należałoby zmodyfikować wzór, np. wprowadzając wagi dla poszczególnych kroków. W ten sposób bardziej rozciągnęlibyśmy odległości pomiędzy punktami z których rzucamy żarówkę z niższych partii drabiny, a zagęścilibyśmy punkty z których rzucamy żarówkę z dużych wysokości.

komentarz 13 stycznia 2016 przez Wojciech Trojanek Obywatel (1,230 p.)

Jeśli tak stawiamy sprawę to skok o 14 jak najbardziej lepszy

odpowiedź 12 stycznia 2016 przez Wojciech Trojanek Obywatel (1,230 p.)
edycja 12 stycznia 2016 przez Wojciech Trojanek

Moim zdaniem należy wziąć pod uwagę najgorszą możliwą opcję czyli że rozbija się na szczeblu 99 i pod niego dobrać najkrótszą możliwą drogę moim zdaniem będzie to krok od dołu najpierw o 10 czyli 10, 20, 30, 40, 50, 60, 70, 80, 90, 100-na tym pierwsza żarówka się rozbija (10 krok) potem pozostaje tylko od 90 szczebla pojedynczo w górę opuszczać żarówkę 91, 92, 93, 94, 95, 96, 97, 98, 99- tu rozbija się druga żarówka (19 krok) wszystkie wcześniejsze kombinację zajmą mniej kroków np dla liczy 36 będzie to: 10, 20, 30, 40 (1 pękła) 31, 32, 33, 34, 35, 36 (2 pękła) = 10 kroków. Nie możemy drugą żarówką skakać co 2 ponieważ powiedzmy na 34 nie pęknie a pęknie na 36 to nie mamy możliwości już sprawdzenia szczebla 35. Skok natomiast co 3 od dołu da nam 33 kroki do szczebla 99 co już pokazuje że dłużej algorytm będzie pracował. To samo w przypadku skoku o 5 i drugim liczonym od dołu: pierwsza żarówka 5, 10, 15, 20....100-pierwsza pęka (20 kroków), 96, 97, 98, 99 - druga pęka (4 kroki) razem 24 kroki - jest gorzej. Moim zdaniem pierwsza żarówka co 10 szczebli a druga co 1 od największej 10tki która nie pękła. To da nam 19 kroków w najgorszym możliwym stanie czyli 99 szczebel. W najlepszym (pęka na 1 szczeblu) sprawdzamy 10tkę - 1 pęka i więc jedziemy od dołu (zgodnie z algorytmem) druga żarówka pęka na 1 szczeblu = 2 kroki.

Pokaż 9 poprzednich komentarzy

komentarz 12 stycznia 2016 przez Czort Nałogowiec (32,500 p.)

16 było tylko przykładem nie sprawdzałem tego. Dokładnie tak jak kolega z Pythona napisał 14 jest najmniejszą liczbą którą można osiągnąć. Statystycznie też wygląda lepiej niż skakanie co 10. https://docs.google.com/spreadsheets/d/1e997J3qO_GyDoV0D-olrbmqUqqaFsHfKWw5fcIpxfOs/pubhtml?gid=0&single=true

komentarz 12 stycznia 2016 przez Benek Szeryf (91,070 p.)

Zero, mylisz się, to zadanie jest ogólne, nie wiesz z góry jakie jest jego rozwiązanie. Nie możesz tak zakładać, że przy szczeblu 67 krok co 14 jest lepszy niż ten co 10.

komentarz 12 stycznia 2016 przez Czort Nałogowiec (32,500 p.)

Poza tym przy 67 skacząc co 10 potrzeba 14 kroków a nie 13.

komentarz 12 stycznia 2016 przez adrian17 Ekspert (344,860 p.)

Wojtek i Adrian nie znaleźli rozwiązania. Nie wprowadzajcie ludzi w błąd. Najmniejsza liczba kroków, przy których to można sprawdzić, to 14.

Przeczytaj jeszcze raz mój ostatni komentarz.

komentarz 13 stycznia 2016 przez Wojciech Trojanek Obywatel (1,230 p.)

Czy mieliśmy rację czy nie czy to ma znaczenie grunt że mamy dobrą rozkminę, a zarówno algorytm 10 skoków jak i 14 skoków ma swoje słabsze i mocniejsze strony względem konkretnych wartości. Opisałem wyżej w komentarzu dla jakich. Tutaj należało by zapytać twórcę zadania co miał na myśli mówiąc optymalny algorytm :D

odpowiedź 12 stycznia 2016 przez Colossus Mądrala (6,410 p.)

Będę wybierał piętra z których zrzucić żarówkę metodą "tnij i bij" (dziel i zwyciężaj)

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

To nie jest optymalne rozwiązanie.

Proszę przesledz swój algorytm.

odpowiedź 12 stycznia 2016 przez juriiw Gaduła (3,470 p.)

no i jak CI poszło?

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Jestem jeszcze za kiepski, potrzebowałem naprowadzenia by je rozgryżć.

odpowiedź 12 stycznia 2016 przez Dash Nałogowiec (29,650 p.)

Zrzucam żarówkę z co trzeciego szczebla od dołu. Jak się rozbije na szczeblu x , to zrzucam drugą ze szczebla o jeden niżej(x-1). Jeżeli druga sie rozbije to znaczy że najniższy jest x-2 a jeżeli nie to x -1. Jakoś tak od razu na takie cos wpadłem, ale pewnie istnieje lepszy algorytm.

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Dobrze myślisz, ale czy napewno trzeba drugą próbę robić od góry?

Jak się nad tym zastanowić to wszystko jest już jasne.

komentarz 12 stycznia 2016 przez Dash Nałogowiec (29,650 p.)

Druga próba ma i tak 50% skuteczności, bo są tylko dwa szczeble to wyboru. Nie ważne skąd się ją przeprowadzi (tak myślę).

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Prosze zastanów się co się stanie przy skoku o 5 i druga próba od dołu.

Czy nie bdzie to efektywniejsze niz skok o 2?

Można to sprawdzic np dla szczebla 36?

komentarz 12 stycznia 2016 przez Dash Nałogowiec (29,650 p.)

Nie rozumiem. Jak zrzucę z 5 szczebla i się rozbije, to zostanie mi jedna żarówka i 4 szczeble czyli trzy wymagane próby. Dwie żarówki starczają na sprawdzenie jedynie trzech szczebli. Mógłbyś zrobić jakiś schematyczny rysunek?

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Jeśli rozbije się z piątego to drugą sprawdzasz od pierwszego w górę.

W ten sposób druga rozbije sie na właściwym szczeblu.

Trzeba sie zastanowić nad najgorszym możliwym przypadkiem.

odpowiedź 12 stycznia 2016 przez No Lime Gaduła (4,540 p.)

Skoro mam wybrać najniższy szczebel z którego jak zrzucę żarówkę to ona się nie rozbije, będę próbować zrzucać ją od najniższego szczebla aż do samego szczytu i obserwując kiedy pierwsza żarówka polegnie. Wtedy będę wiedzieć który to ten najniższy szczebel i zachowam ostatnią żarówkę.

To tak słowami a algorytm? Raczej użyłbym do tego pętli z warunkiem licznik<Ilość_Szczebli_Drabiny a w niej instrukcje warunkowe 'Jeżeli żarówka została zniszczona, przerwij wykonywanie pętli i wyświetl licznik'. Teorytycznie licznik wskazałby odpowiedni szczebel. Nie wiem czy w dobrym kierunku idę, daj poprawną odpowiedź bo jestem bardzo ciekawy.

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Wykorzystujesz jedna żarówkę, pomyśl nad algorytmem z dwoma.

odpowiedź 12 stycznia 2016 przez MrMock Bywalec (2,890 p.)

jeśli byłoby x żarówek w tym wypadku 2 to warto iść od samego dołu o te x czyli po 2

2 4 6 8 na 8 sie rozbiła schodze do 7 i rzucam żeby sprawdzić czy sie rozbije jeśli tak to na 7 jeśli nie to na 8

odpowiedź dobra?

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Czy skok o dwa jest optymalny?

Napewno nie da sie tego rozwiązazać mniejsz ilościa kroków?

komentarz 12 stycznia 2016 przez MrMock Bywalec (2,890 p.)

o 1 nie bo w końcu po co jeśli mamy 2

o 2 możemy bo mamy dwie jeśli sie zbije możemy wrócić o jedno niżej i sprawdzić

o 3 chodzimy zbija sie schodzimy o 1 niżej zbija sie i to czy z kolejnej sie zbije czy nie to już 50% na 50% czysta losowość

dzielenie przy 100 szczeblach mając tylko można poweidzieć dwie próby jest też mało optymalne i po prostu pełne losowości

moim zdaniem chodzenie o 2 jest jednocześnie może nie najbardziej optymalne ale jednocześnie i optymalne i najbezpieczniejsze a w końcu bezpieczeństwo w programie jest ważne

czekam na poprawną odpowiedź strasznie mnie ciekawi to zadanie

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Dlazcego uparłeś się by w z drugą żarówką schodzic w dół?

komentarz 12 stycznia 2016 przez MrMock Bywalec (2,890 p.)

jeśli na 1 sie nie zbije ide o 2 dalej to testuje 3 jeśli sprawdze 3 i sie rozbije to skąd mam wiedzieć czy to jest to ta wysokość najniższa z której sie rozbije? a co ze szczeblem numer 2? co jeśli na 3 sie rozbija ale na 2 też sie rozbija? więc wtedy szczebel numer 3 nawet jeśli sie z niego rozbija to jest on szczeblem przed ostatnim a nie ostatnim z którego sie rozbija

chyba że nie mam racji i chętnie przeczytam twoje zdanie i rozwiązanie i licze na wiecej takich zadań jeśli miałbyś kiedyś do takich przyjemnych logicznych dostęp

komentarz 12 stycznia 2016 przez Zero Dyskutant (8,210 p.)

Przypuścmy, że żarówka rozbija się przy szczeblu 47.

Jeśli bedziesz skakał o 2 szczeble to potrzebujesz 25 prób.

Jeśli bedziesz skakał o 5 szczebli i druga zaczynał od dołu to bedzie

10 prób do 50 a potem dwie 46 i 47 razem 12 prób.

Przy skoku o pięć jest dwa razy szybciej?

Da się jeszcze lepiej?

odpowiedź 12 stycznia 2016 przez Vodoo Dyskutant (9,270 p.)

Wchodzę na 50 szczebel i zrzucam, jeśli się rozbije to szukany szczebel jest w przedziale 1-50, jeśli nie 51-100. Potem to samo: 25 lub 75 szczebel (w zależności od poprzedniego wyniku) i zrzucam... Takie dzielenie na pół jest chyba najlepszym pomysłem :D