Wyrzucanie kotów przez okna

Wyobraź sobie, że jesteś w wysokim budynku z kotem. Kot może przetrwać upadek z okna na niskim piętrze, ale zginie, jeśli zostanie wyrzucony z wysokiego piętra. Jak obliczyć najdłuższy spadek, jaki kot może przeżyć, przy jak najmniejszej liczbie prób?

Oczywiście, jeśli masz tylko jednego kota, możesz wyszukiwać tylko liniowo. Najpierw wyrzuć kota z pierwszego piętra. Jeśli przeżyje, rzuć go od drugiego. W końcu po wyrzuceniu z piętra f kot umrze. Wtedy wiesz, że podłoga f-1 była maksymalną bezpieczną podłogą.

Ale co, jeśli masz więcej niż jednego kota? Możesz teraz spróbować jakiegoś wyszukiwania logarytmicznego. Powiedzmy, że budynek ma 100 pięter i masz dwa identyczne koty. Jeśli wyrzucisz pierwszego kota z 50 piętra i zginie, to wystarczy przeszukać 50 pięter liniowo. Możesz zrobić to jeszcze lepiej, jeśli za pierwszym podejściem wybierzesz niższe piętro. Powiedzmy, że zdecydowałeś się rozwiązać ten problem na 20 piętrach naraz, a pierwsze fatalne piętro ma numer 50. W takim przypadku twój pierwszy kot przetrwa loty z piętra 20 i 40, zanim umrze z piętra 60. Wystarczy sprawdzić indywidualnie piętra od 41 do 49. To w sumie 12 prób, co jest znacznie lepsze niż 50, których potrzebowałbyś, gdybyś próbował użyć eliminacji binarnej.

Ogólnie rzecz biorąc, jaka jest najlepsza strategia i najgorsza złożoność w przypadku n-piętrowego budynku z 2 kotami? A co z n podłogami i m kotami?

Załóżmy, że wszystkie koty są równoważne: wszystkie przeżyją lub zginą w wyniku upadku z danego okna. Ponadto każda próba jest niezależna: jeśli kot przeżyje upadek, nic mu nie stanie.

To nie jest praca domowa, chociaż być może kiedyś rozwiązałem ją do zadania szkolnego. To tylko kapryśny problem, który przyszedł mi do głowy dzisiaj i nie pamiętam rozwiązania. Dodatkowe punkty, jeśli ktoś zna nazwę tego problemu lub algorytm rozwiązania.

Możesz łatwo napisać trochę DP (programowanie dynamiczne) dla ogólnego przypadku n pięter im kotów.

Podstawowa formuła a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..npowinna być oczywista:

• Jeśli pierwszy kot zostanie wyrzucony z k-tego piętra i zginie, mamy teraz k - 1podłogi do sprawdzenia (wszystkie poniżej k) i m - 1koty ( a[k - 1][m - 1]).
• Jeśli kot przeżyje, n - kpozostały podłogi (wszystkie piętra wyżej k) i nadal mkoty.
• Dlatego należy wybrać najgorszy przypadek dwóch max.
• + 1 wynika z tego, że podjęliśmy tylko jedną próbę (niezależnie od tego, czy kot przeżył, czy nie).
• Dlatego staramy się, aby każda podłoga była jak najlepsza min(f(k)) : for k in 1..n.

Zgadza się z wynikiem Google z linku Gaurav Saxena dla (100, 2).

int n = 100; // number of floors
int m = 20; // number of cats
int INFINITY = 1000000;

int[][] a = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
    // no cats - no game
    a[i][0] = INFINITY;
}

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        // i floors, j cats
        a[i][j] = INFINITY;

        for (int k = 1; k <= i; ++k) {
            // try throw first cat from k-th floor
            int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1;
            a[i][j] = Math.min(a[i][j], result);
        }
    }
}

System.out.println(a[n][m]);

Możesz łatwo znaleźć strategię (jak rzucić pierwszego kota), jeśli najlepiej zapiszesz kw innej tablicy.

Jest też szybsze rozwiązanie, nie wymagające obliczeń O (n ^ 3), ale jestem już trochę śpiący.

edytuj
O tak, pamiętam, gdzie widziałem ten problem wcześniej .

Według niedawnego odcinka Radiolabu (o „Falling”) kot osiąga prędkość graniczną na 9. piętrze. Następnie odpręża się i jest mniej prawdopodobne, że zostanie zraniony. Po upadku z powyżej 30-ego roku są całkowicie nieuszkodzone koty. Najbardziej ryzykowne są piętra od 5 do 9.

Wyobraź sobie, że jesteś w wysokim budynku z kotem. Kot może przetrwać upadek z okna na niskim piętrze, ale zginie, jeśli zostanie wyrzucony z wysokiego piętra. Jak obliczyć najdłuższy spadek, jaki kot może przeżyć, przy jak najmniejszej liczbie prób?

Najlepszą strategią rozwiązania tego problemu jest zbadanie, używając prawa fizyki, przede wszystkim prawdopodobieństwa, że ​​twoje założenia są prawdziwe.

Gdybyś to zrobił, zdałbyś sobie sprawę, że szanse kota na przeżycie faktycznie rosną, im większa jest odległość od ziemi. Oczywiście, zakładając, że rzucisz go z coraz wyższego budynku, takiego jak wieże Petronas, a nie z coraz wyższej góry, takiej jak Mount Everest.

Edycja:
Właściwie zobaczyłbyś niedokończoną dystrybucję wielbłądów.
Najpierw prawdopodobieństwo zgonu kota jest małe (bardzo mała wysokość), potem rośnie (mała wysokość), potem znowu maleje (większa wysokość), a potem znowu rośnie (bardzo duża wysokość).

Wykres prawdopodobieństwa śmierci kota w funkcji wysokości nad ziemią wygląda następująco:
(koniec na 3, ponieważ niedokończone rozmieszczenie wielbłądów)

Aktualizacja:
maksymalna prędkość kota wynosi 100 km / h (60 mil na godzinę) [= 27,7 m / s = 25,4 jarda / s].
Końcowa prędkość człowieka wynosi 210 km / h (130 mil na godzinę). [= 75 m / s = 68,58 jardów / s]

Źródło prędkości terminala:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Kredyty:
Goooooogle

Muszę zweryfikować później:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html

Po raz pierwszy przeczytałem ten problem w Podręczniku projektowania algorytmów Stevena Skieny (ćwiczenie 8.15). Było to następstwem rozdziału o programowaniu dynamicznym, ale nie musisz znać programowania dynamicznego, aby udowodnić dokładne ograniczenia strategii . Najpierw opis problemu, a następnie poniższe rozwiązanie.

Jajka pękają, gdy są upuszczane z dostatecznie dużej wysokości. Biorąc pod uwagę budynek n-piętrowy, musi istnieć podłoga f taka, aby jaja upuszczone z piętra f pękały, ale jaja upuszczone z piętra f-1 przeżyły. (Jeśli jajko rozbije się z dowolnej podłogi, powiemy f = 1. Jeśli jajko przeżyje z dowolnej podłogi, powiemy f = n + 1).

Próbujesz znaleźć krytyczne piętro f. Jedyną operacją, jaką możesz wykonać, jest upuszczenie jajka z jakiejś podłogi i zobaczenie, co się stanie. Zaczynasz z k jaj i starasz się upuszczać jajka tak kilka razy, jak to możliwe. Uszkodzone jaja nie mogą być ponownie użyte (puszka z jajami nienaruszonymi). Niech E (k, n) będzie minimalną liczbą odchodów jaj, która zawsze będzie wystarczająca.

1. Pokaż, że E (1, n) = n.
2. Pokaż to E(k,n) = Θ(n**(1/k)).
3. Znajdź powtarzanie dla E (k, n). Jaki jest czas wykonywania programu dynamicznego w celu znalezienia E (k, n)?

Tylko 1 jajko

Upuszczenie jajka z każdego piętra, zaczynając od pierwszego, znajdzie piętro krytyczne w (w najgorszym) n operacjach.

Nie ma szybszego algorytmu. W dowolnym momencie w dowolnym algorytmie pozwól, aby najwyższe piętro, z którego jajo nie pękło. Algorytm musi przetestować podłogę g + 1 przed jakąkolwiek wyższą kondygnacją h> g + 1, w przeciwnym razie, jeśli jajko miałoby oderwać się od podłogi h, nie może rozróżnić między f = g + 1 if = h.

2 jajka

Najpierw rozważmy przypadek k = 2 jaj, gdy n = r ** 2 to idealny kwadrat. Oto strategia, która zajmuje O (sqrt (n)) czasu. Zacznij od upuszczenia pierwszego jajka w przyrostach r pięter. Kiedy pęknie pierwsze jajko, powiedzmy na podłodze ar, wiemy, że musi być krytyczna podłoga f (a-1)r < f <= ar. Następnie upuszczamy drugie jajko z każdego piętra, zaczynając od (a-1)r. Kiedy drugie jajko pękło, znaleźliśmy krytyczne piętro. Upuszczaliśmy każde jajko najwyżej w czasie r, więc ten algorytm wykonuje w najgorszym przypadku 2r operacje, czyli Θ (sqrt (n)).

Kiedy n nie jest idealnym kwadratem, weź r = ceil(sqrt(n)) ∈ Θ(sqrt(n)). Algorytm pozostaje Θ (sqrt (n)).

Udowodnij, że każdy algorytm zajmuje co najmniej czas sqrt (n). Załóżmy, że istnieje szybszy algorytm. Weź pod uwagę kolejność pięter, z których zrzuca pierwsze jajko (o ile się nie rozbije). Ponieważ spada mniej niż sqrt (n), musi istnieć przedział co najmniej n / sqrt (n), który wynosi sqrt (n). Kiedy f znajduje się w tym przedziale, algorytm będzie musiał zbadać to z drugim jajkiem i to musi być zrobione piętro po piętrze, przypominając sobie przypadek z jednym jajkiem. SPRZECZNOŚĆ.

k jaj

Algorytm przedstawiony dla 2 jaj można łatwo rozszerzyć na k jaj. Upuść każde jajko w stałych odstępach czasu, które należy traktować jako potęgę k-tego pierwiastka z n. Na przykład dla n = 1000 i k = 3, przeszukaj przedziały 100 pięter z pierwszym jajkiem, 10 z drugim jajkiem i 1 z ostatnim jajkiem.

Podobnie możemy udowodnić, że żaden algorytm nie jest szybszy Θ(n**(1/k))przez indukcję z dowodu k = 2.

Dokładne rozwiązanie

Wywracamy się, optymalizując miejsce upuszczenia pierwszego jajka (podłoga g), zakładając, że znamy optymalne rozwiązania dla mniejszych parametrów. Jeśli jajko pęknie, mamy piętra g-1 poniżej do zbadania z jajami k-1. Jeśli jajko przeżyje, mamy piętra wyżej do zbadania za pomocą k jaj. Diabeł wybiera dla nas najgorsze. Zatem dla k> 1 powtarzanie

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Czy to nie zakłada, że ​​używasz „tego samego kota”?

Możesz podejść do tego matematycznie, ale to fajna rzecz w matematyce ... przy właściwych założeniach, 0 może równać się 1 (dla dużych wartości 0).

Z praktycznego punktu widzenia możesz otrzymać „Podobne koty”, ale nie możesz otrzymać „Tego samego kota”.

Możesz spróbować określić odpowiedź empirycznie, ale myślę, że byłoby wystarczająco dużo różnic statystycznych, aby odpowiedź byłaby statystycznie bez znaczenia.

Możesz spróbować UŻYĆ „tego samego kota”, ale to nie zadziała, ponieważ po pierwszym upuszczeniu nie jest już tym samym kotem. (Podobnie jak, jeden nie może nigdy dwa razy wejść do tej samej rzeki)

Możesz też podsumować stan zdrowia kota, pobierając próbki w bardzo małych odstępach czasu i znaleźć wysokości, na których kot jest „przeważnie żywy” (w przeciwieństwie do „głównie martwego” z „Narzeczonej księżniczki”). Koty przeżyją średnio (do ostatniej przerwy).

Myślę, że odszedłem od pierwotnego celu, ale jeśli idziesz drogą empiryczną, głosuję za rozpoczęciem jak najwyżej i kontynuowaniem upuszczania kotów w miarę zmniejszania się wzrostu, aż statystycznie przeżyją. A następnie powtórz test na kotach, które przeżyły, aby mieć pewność.

Wybrałem nieco inną metodę, aby stworzyć rozwiązanie.

Zacząłem od ustalenia maksymalnej podłogi, którą można pokryć za pomocą x kotów i domysłów y, stosując następującą metodę.

Zacznij od 1 piętra i zwiększaj liczbę domysłów, sprawdzając jednocześnie piętra, na których zostały sprawdzone i ile kotów pozostało na każdym piętrze.
Powtórz to do y razy.

Ten bardzo nieefektywny kod do obliczenia podanej odpowiedzi, ale mimo to przydatny w przypadku małej liczby kotów / podłóg.

Kod Pythona:

def next_step(x, guess):
  next_x = []
  for y in x:
    if y[0] == guess:
      if y[1] != 1:
        next_x.append((guess+1, y[1] - 1))
    next_x.append(y)
    if y[0] == guess:
      next_x.append((guess+1, y[1]))
  return next_x

x = [(1, TOTAL_NUM_CATS)]
current_floor = 1
while len(x) <= TOTAL_NUM_FLOORS:
  x = next_step(x, current_floor)
  current_floor += 1
  print len(x)

Dla 2 kotów maksymalne piętra, które można zidentyfikować w x domysłach to:
1, 3, 6, 10, 15, 21, 28 ...

Dla 3 kotów:
1, 3, 7, 14, 25, 41, 63 ...

Dla 4 kotów:
1, 3, 7, 15, 30, 56, 98 ...

Po szeroko zakrojonych badaniach (głównie obejmujących wpisywanie sekwencji liczb w OEIS ) zauważyłem, że maksymalne piętra dla x wynikają z kombinacji odcinków.

Dla 2 kotów:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Dla 3 kotów:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

Dla 4 kotów:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)

Stąd podjąłem łatwe podejście polegające na prostym zwiększaniu n, aż przekroczę wymaganą liczbę pięter.

Kod Pythona:

def find_smallest(floors, eggs):
  maximum_floors = 0
  n = 0
  while maximum_floors < floors:
    maximum_floors = 0
    n += 1
    if n < eggs:
      maximum_floors = 2**n - 1
    else:
      count = 0
      for x in xrange(1, eggs+1):
        maximum_floors += combination(n, x)
  print n

To daje poprawne rozwiązanie dla (100, 2) = 14.
Dla każdego, kto chce sprawdzić coś mniej trywialnego, daje (1 000 000, 5) = 43.

Działa to w O (n), gdzie n jest odpowiedzią na problem (im więcej kotów, tym lepiej).
Jednak jestem pewien, że ktoś z wyższym poziomem matematyki mógłby uprościć formuły fragmentaryczne do obliczenia w O (1).

O(m*(n^(1/m))) algorithm.

Let 'x' be the maximum number of attempts needed.  

m = 1 => linear => x=n

m = 2:  
Let the floors be split into 'k' partitions. The first cat is thrown at the end of each partition (max 'k' times). 
When it dies, the second cat is used to go up from the beginning of this partition.   
x = k + n/k.   
Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2).

m = 3:  
x = k + 2*(y^(1/2)), where y = n/k  
diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3)

for general m:  
x = m * n^(1/m). 

Nie mogę przeczytać o tym Google Blogspot (dzięki działaniom Blogwall), ale nie sądzę, aby proste wyszukiwanie w stylu binarnym było najlepsze. Przyczyną jest to, że wyszukiwanie binarne opiera się na założeniu, że odpowiedź, której szukasz, ma równe szanse na znalezienie się w dowolnym indeksie na liście. Jednak w tym przypadku nie jest to prawdą. W takim przypadku odpowiedź będzie miała większe prawdopodobieństwo, że będzie bliżej jednego końca zakresu niż drugiego. Nie mam pojęcia, jak uwzględnić to w wyszukiwaniu, ale to interesująca myśl.

cała ta szalona gadka o kotach… i to tylko zgadywanie, problem z liczbą przy minimalnej liczbie domysłów (liczba kotów). nie powinno być również potrzeby sztucznego (i niepoprawnego) definiowania nieskończoności jako części rozwiązania. zmienna powinna zostać nazwana upper-bound lub max-try lub coś takiego. definicja problemu (rzecz z kotem) wiąże się jednak z poważnymi problemami, ponieważ ludzie reagują na potencjał okrucieństwa wobec zwierząt, a także wiele aspektów tego problemu występujących w prawdziwym życiu, np. opór powietrza, grawitacja to przyspieszenie i inne takie rzeczywiste parametry problemu. więc może należało o to zapytać w zupełnie inny sposób.