GoldenLine
Zaloguj się
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Niebieskie jajka :)

Karol Stępniewski:
Darek J.:
III sposób (ciut zmodyfikowany sposób Małgosi)

Rzucamy jednym jajkiem na 14 piętrze, jeżeli się rozbije to rzucamy drugim jajkiem po kolei od 1 do 13 pietra. Jeżeli jajko się nie rozbije, to nastepnie rzucamy pierwsze jajko z 27 pietra (14+13), następnie z 39 piętra (27+11), itd. Razem to bedzie co najwyżej 14 rzutów.

Correcto :)

Taak?

To ile przy takim algorytmie będzie rzutów, jeśli jajka wytrzymują 99 pięter, a 100 już nie?

Podejdźmy do sprawy analitycznie.
Załóżmy, ze pierwszym jajkiem rzucamy co N pieter.
Pierwsze jajko da nam więc maksymalnie 100/N prób.
Teraz drugim jajkiem mamy maksymalnie N prób (bo tyle jest pięter pomiędzy próbami z pierwszym jajkiem).
Sumaryczna ilość prób dla obu jajek wynosi więc N + 100/N . Wystarczy więc znaleźć minimum funkcji f(x) = x + 100/x i już.
Oczywiście minimum wynosi 20, dla x = 10.
Oznacza to, że uda nam się to zawsze określić maksymalnie w 20-tu rzutach.
Co ciekawe, algorytm poprzedników, cytowany przeze mnie wyżej, daje wynik identyczny: 13 + 100 / 13 = 20, co wynika z faktu, że dziedziną badanej funkcji są liczby całkowite.
Link do wypowiedziLink

konto usunięte

Temat: Niebieskie jajka :)

Ciekawe uwagi, proponuję jednak przeczytanie dokładnie i ze zrozumieniem poprzednich postów w wątku, pozdrawiam :)Darek J. edytował(a) ten post dnia 12.05.10 o godzinie 18:37
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Niebieskie jajka :)

Dobra, minimalnie w jednym - jak rzucę z 100-go piętra i się nie zbije. to już wiem, że wytrzymuje 100. Ale to chyba jest jednak błąd w tekście zagadki - powinno być maksymalnie.
Link do wypowiedziLink
Andrzej O.

Andrzej O. Haters gonna hate,
ainters gonna aint

Temat: Niebieskie jajka :)

Piotr G.:
Sumaryczna ilość prób dla obu jajek wynosi więc N + 100/N . Wystarczy więc znaleźć minimum funkcji f(x) = x + 100/x i już.
Oczywiście minimum wynosi 20, dla x = 10.
19 dla 8 <= x <= 13 (bo 100/x + x - 1)
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Niebieskie jajka :)

Fakt.
Link do wypowiedziLink
Karol S.

Karol S. Software Engineer @
VMware, Palo Alto,
USA

Temat: Niebieskie jajka :)

Piotr G.:
Dobra, minimalnie w jednym - jak rzucę z 100-go piętra i się nie zbije. to już wiem, że wytrzymuje 100. Ale to chyba jest jednak błąd w tekście zagadki - powinno być maksymalnie.

Dlatego właśnie w treści zagadki mowa jest o pesymistycznym przypadku.
Link do wypowiedziLink
Błażej Matuszewski

Błażej Matuszewski Lead Software
Development Engineer
/ .NET, Xamarin

Temat: Niebieskie jajka :)

Karol Stępniewski:
Darek J.:
III sposób (ciut zmodyfikowany sposób Małgosi)

Rzucamy jednym jajkiem na 14 piętrze, jeżeli się rozbije to rzucamy drugim jajkiem po kolei od 1 do 13 pietra. Jeżeli jajko się nie rozbije, to nastepnie rzucamy pierwsze jajko z 27 pietra (14+13), następnie z 39 piętra (27+11), itd. Razem to bedzie co najwyżej 14 rzutów.

Correcto :)

Jak to..

log2(100) = 6,6... i jakieś tam przecinki

Wersja z podziałem na połowy jest najszybsza.

W jednym z wariantów: 50->25->12->6->3->2->1
Pozostałem warianty to tylko inne numery piętr (zawsze przedział sprawdzony testujemy w środku zakresu)

Max 7 rzutów
Link do wypowiedziLink
Andrzej O.

Andrzej O. Haters gonna hate,
ainters gonna aint

Temat: Niebieskie jajka :)

ale jajka masz tylko dwa...

(to zadanie chyba powstało dla tej odpowiedzi :D )
Link do wypowiedziLink
Błażej Matuszewski

Błażej Matuszewski Lead Software
Development Engineer
/ .NET, Xamarin

Temat: Niebieskie jajka :)

Andrzej O.:
ale jajka masz tylko dwa...

(to zadanie chyba powstało dla tej odpowiedzi :D )

w sumie... ;)
Link do wypowiedziLink
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Niebieskie jajka :)

Błażej Matuszewski:

Jak to..

log2(100) = 6,6... i jakieś tam przecinki
To prawda, tyle że mówimy o dwóch jajkach, a nie o 6-ciu.
W ten sposób to możesz policzyć, ile jajek wystarczy do tego, żeby okreslić ich wytrzymałość.
Wersja z podziałem na połowy jest najszybsza.

W jednym z wariantów: 50->25->12->6->3->2->1
Pozostałem warianty to tylko inne numery piętr (zawsze przedział sprawdzony testujemy w środku zakresu)

Max 7 rzutów

No więc rzucam jajko nr 1 z 50 piętra - stłukło się :(
Rzucam więc jajko nr 2 z 25 piętra - stłukło się :(

I co?
Link do wypowiedziLink
Andrzej O.

Andrzej O. Haters gonna hate,
ainters gonna aint

Temat: Niebieskie jajka :)

Błażej Matuszewski:
Andrzej O.:
ale jajka masz tylko dwa...

(to zadanie chyba powstało dla tej odpowiedzi :D )

w sumie... ;)
taki sam mialem pomysł na początku :)
Link do wypowiedziLink
Wojciech Kroczak

Wojciech Kroczak DYSANT Software Sp.
z o.o.

Temat: Niebieskie jajka :)

Wszyscy wiedzą, że niebieskie jajka wytrzymują min. 200 pięter. Nie trzeba podejmować żadnych prób.
W razie wątpliwości najlepiej zwrócić się z pytaniem do producenta - tych od niebieskich jaj przecież nie może być dużo.
Link do wypowiedziLink
Krzysztof Piotr Żyliński

Krzysztof Piotr Żyliński
www.rekuperacja-inve
nter.pl

Temat: Niebieskie jajka :)

Rzucamy co 3 pietra - z 3go, 6 go, 9go itd.
Jak się zbije np przy 24-tym, to drugim rzucamy z 22 lub 23 (bez różnicy).
Inaczej po prostu się nie da- jak zbijemy pierwsze jajko to żeby określić szukany poziom możemy drugim zrobić tylko rzut z poziomu N-2.
Link do wypowiedziLink
Natalia T.

Natalia T. x

Temat: Niebieskie jajka :)

Sądzę, że rozwiązałam tę zagadkę.
Minimalna liczba rzutów nawet w najgorszym wypadku to 10.
Moje rozwiązanie ,,sprawdza" wszystkie piętra.

Zaczynamy od 10 piętra. Zonk - jajo zbiło się.(opcja 1wsza) Pozostaje nam max 9 rzutów drugim jajkiem, zaczynając od 1go piętra oczywiście.

Pierwsze jajo nie zbiło się. No to je z 19go piętra (rzut 2gi).
Zonk - zbiło się. No to max 8 rzutów 2gim jajkiem.

Załóżmy, że się nie zbiło. Zrzućmy je (pierwsze jajo) z 27 piętra (rzut 3ci).
Zbiło się. Max 7 rzutów 2gim jajkiem.

Pierwsze jajo znów nie zbiło się. Zrzućmy je więc z 34 piętra (rzut 4ty).
Zbiło się. Max 6 rzutów 2gim jajkiem.

Pierwsze jajo nie zbiło się i tym razem. Czas zrzucić je z 40 piętra (rzut 5ty).
Zbiło się. + 5 rzutów 2gim jajkiem.

Teraz zrzućmy pierwsze jajo z 45 piętra. (rzut 6ty)
Zbiło się. + 4ry rzuty drugim.

Nie zbiło się. No to pierwsze jajo z 49 piętra (rzut 7my).
Zbiło się. + max 3 rzuty drugim jajkiem.

Nie zbiło się. Zrzućmy pierwsze jajo z 50 piętra (rzut 8my).
Zbiło się. Tadam. Nie zbiło się (autor zagadki oszukiwał i niepotrzebnie zrzucaliśmy te wszystkie jajka :-)))

Minimalna liczba rzutów to w najprostszym myśleniu piętro, z którego po raz pierwszy zrzucimy pierwsze jajko. Próbowałam też z wersją zaczynając od 9 piętra, ale pod koniec sprawa się komplikuje.

Z drugim jajkiem trzeba już postępować ostrożnie i po prostu po kolei zrzucać je z coraz wyższych pięter, dopóki się nie zbije.

Autorze - czy poprawnie rozwiązałam tę zagadkę? A może istnieje jakieś inne rozwiązanie z jeszcze mniejszą liczbą rzutów minimalnych???Natalia Sulanowska edytował(a) ten post dnia 12.07.10 o godzinie 21:06
Link do wypowiedziLink
Natalia T.

Natalia T. x

Temat: Niebieskie jajka :)

Krzysztof "Kiju" Żyliński:
Rzucamy co 3 pietra - z 3go, 6 go, 9go itd.
Jak się zbije np przy 24-tym, to drugim rzucamy z 22 lub 23 (bez różnicy).

Jest różnica :-) Nie masz już pierwszego jajka, które zbiło się na 24tym piętrze. Zrzucasz 2gie z 23 piętra i zbiło się. Teraz nie wiesz i nie możesz już ustalić, czy na 22 piętrze też by się zbiło, czy nie.

Tym drugim jajkiem trzeba rzucić po kolei: najpierw z 22, potem 23...
Inaczej po prostu się nie da- jak zbijemy pierwsze jajko to żeby określić szukany poziom możemy drugim zrobić tylko rzut z poziomu N-2.

W tym rozwiązaniu minimalna liczba rzutów w najgorszym wypadku to 17...Natalia Sulanowska edytował(a) ten post dnia 12.07.10 o godzinie 21:38
Link do wypowiedziLink
Natalia T.

Natalia T. x

Temat: Niebieskie jajka :)

Błażej Matuszewski:
Karol Stępniewski:
Darek J.:
III sposób (ciut zmodyfikowany sposób Małgosi)

Rzucamy jednym jajkiem na 14 piętrze, jeżeli się rozbije to rzucamy drugim jajkiem po kolei od 1 do 13 pietra. Jeżeli jajko się nie rozbije, to nastepnie rzucamy pierwsze jajko z 27 pietra (14+13), następnie z 39 piętra (27+11), itd. Razem to bedzie co najwyżej 14 rzutów.

Correcto :)

Jak to..

log2(100) = 6,6... i jakieś tam przecinki

Wersja z podziałem na połowy jest najszybsza.

W jednym z wariantów: 50->25->12->6->3->2->1
Pozostałem warianty to tylko inne numery piętr (zawsze przedział sprawdzony testujemy w środku zakresu)

Max 7 rzutów

Niestety. Jeżeli zrzucisz jajko z 50 piętra na początku i ono się zbije, to potem, żeby ustalić na którym piętrze jajka się zbijają, w wypadku, gdy jest to 49 piętro, potrzebujesz 49 rzutów 2gim jajkiem.

W takim przypadku, twoja minimalna liczba rzutów w najgorszym wypadku to... 50.
Link do wypowiedziLink
Andrzej O.

Andrzej O. Haters gonna hate,
ainters gonna aint

Temat: Niebieskie jajka :)

dlaczego rzucasz tylko do 50 piętra? budynek ma 100 pięter.
Link do wypowiedziLink
Natalia T.

Natalia T. x

Temat: Niebieskie jajka :)

Andrzej O.:
dlaczego rzucasz tylko do 50 piętra? budynek ma 100 pięter.

Ups....

Bo mamy kryzys i nasz budynek skrócono...

Nie zauważyłam tych bagatela 50 kolejnych pięter.
Poprawiam się: 14 rzutów minimalnie. Była już taka odpowiedź na forum.Natalia Sulanowska edytował(a) ten post dnia 12.07.10 o godzinie 22:02
Link do wypowiedziLink
Mateusz Chodkowski

Mateusz Chodkowski Student

Temat: Niebieskie jajka :)

temat jest mocno stary, ale szukałem rozwiązania podobnego problemu w programowaniu.wg mnie rzucamy dzieląc zakresy na połowy ( jak w binsearch'u ) do momentu kiedy pozostanie nam ostatnie jajko. jeżeli pozostanie nam ostatnie jajko, to lecimy od dołu obecnego zakresu, do momentu w którym się zbije ;) pozdrawiam MCH
Link do wypowiedziLink
Jakub L.

Jakub L. Programista

Temat: Niebieskie jajka :)

Mateusz Chodkowski:
temat jest mocno stary, ale szukałem rozwiązania podobnego problemu w programowaniu.wg mnie rzucamy dzieląc zakresy na połowy ( jak w binsearch'u ) do momentu kiedy pozostanie nam ostatnie jajko. jeżeli pozostanie nam ostatnie jajko, to lecimy od dołu obecnego zakresu, do momentu w którym się zbije ;) pozdrawiam MCH

Litości, na tej samej stronie http://www.goldenline.pl/forum/1668754/niebieskie-jajk... a na samej górze tej strony jest dowód jak to policzyć.
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj