szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 15 kwi 2015, o 13:53 
Użytkownik

Posty: 5668
Lokalizacja: Kraków
Zadanie

Cytuj:
Szklana kula zrzucona z jakiegoś piętra n piętrowego wieżowca może się rozbić. Zależy to nie od kuli, lecz od wysokości. Mamy k takich kul. Należy ustalić minimalna ilość prób , które trzeba wykonać, zrzucając kule z pięter, aby zawsze wykryć numer najwyższego pietra, z którego zrzucona kula nie rozbije się.
*

Niech f(n, k)=m to będzie szukaną ilością prób.

Jeśli jest tylko jedna kula, to należy sprawdzać czy się nie rozbije ostrożnie, tj. „od dołu” (przy „maksymalnym pechu” rozbije się ona dopiero rzucona z ostatniego piętra); tj. mamy f(n, 1) = n.

k=2

Przykład
Obliczyć f(6,2)
Jedna próba to za mało, ale dwie także (f(3,2)= 2). Wystarczą jednak trzy próby (można zacząć od trzeciego piętra: jeśli kula się nie rozbije: to rzucić ją z piątego piętra...), tj. f(6,2)=3.

Można udowodnić, że f(n,2)= \rfloor \frac{\sqrt{8n+1}-1}{2} \lfloor
gdzie \rfloor x \lfloor oznacza najmniejszą liczbą całkowitą która jest nie mniejsza niż x.
Np. f(100, 2) = 14. Należy sprawdzać piętra: 14, \ 27, \ 39, \ 50, \ 60, \ 69, \ 77, \ 84, \ 90, \ 95 ,  \ 99, \ 100. np. jeśli po raz pierwszy kula rozbije się rzucona z 60-tego piętra (tj. po piątej próbie), to jest do sprawdzenia 9 pięter (od 51 do 59) itd.

Algorytm jest bowiem taki: zaczynamy od piętra o numerze m, potem z piętrem o numerze m + (m-1)=2m-1, potem z piętrem o numerze m + (m-1)+ (m-2)=3m-3 itd. z coraz mniejszymi o jeden skokami.

k=3

Przykłady
Tu także obliczanie f dla małych n nie jest zbyt trudne i może być rozwijające. Mamy np. f(6,3)=f(7, 3)= 3 ale f(8,3)= 4 itd.
Okazuje się, że f(100, 3) = 9. Zacząć należy wpierw od pięter:
37, \ 66, \ 88, \ 100
W przypadku trzech kul pierwszą próbę należy wykonać z piętra \frac{(m-1)m}{2} + 1, kolejną z piętra \frac{(m-1)m}{2} + 1 +\frac{(m-2)(m-1)}{2}+1 itd.
Daje to wynik \frac{m(m^2+5)}{6} \geq n
(przy m tej próbie jesteśmy na ostatnim piętrze bądź „w chmurach”).
Co nie daje się tak łatwo „rozwikłać” jak dla dwóch kul. (\frac{m(m+1)}{2} \geq n).

Zakończenie
W cytowanym artykule autor gustownie formułuje zagadnienie, wyprowadza wzory na dla k \in \{ 1, 2, 3 \}, nie zajmując się sytuacją k>3 oraz podaje wartości f dla niektórych małych n i k. Oblicza też wreszcie f(100,2) i f(100, 3).


Problemy
■ Jakie jest najmniejsze, a jakie największe n takie, że f(n,2)=14 ?
■ Jak się stabilizuje (maleje) f gdy wzrasta k, zaś n jest ustalone; obliczyć f(100, k) dla k>  3
■ Być może nie istnieje wieżowiec z n> 206 pięter, ale istnieje gdy n=206 (tzw. Burdż Chalifa, ZEA); obliczyć f(206, 4); zbadać głębiej sytuację z k=4
■ pomijając realia z wieżowcami - czy można efektywnie obliczać f(n, k) dla dużych wartości n i k ?
■ kontynuować własne badania nad własnościami funkcji f(n,k)
*
Ukryta treść:    
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem wiewiórek  mol_ksiazkowy  2
 Zagadka - Problem - Kostka Rubika  Mrlos  5
 Problem z asymptotyka - zadanie 2  juuuve  0
 Reszty z dzielenia i liczby pierwsze - problem.  Kamilek:)  1
 Podstawowy problem kombinatoryczny  K.Inc.  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl