Stellen Sie sich vor, Sie befinden sich in einem hohen Gebäude mit einer Katze. Die Katze kann einen Sturz aus einem niedrigen Fenster überleben, stirbt jedoch, wenn sie aus einem hohen Stockwerk geworfen wird. Wie können Sie mit der geringsten Anzahl von Versuchen den längsten Tropfen herausfinden, den die Katze überleben kann?
Wenn Sie nur eine Katze haben, können Sie natürlich nur linear suchen. Wirf zuerst die Katze aus dem ersten Stock. Wenn es überlebt, werfen Sie es von der zweiten. Schließlich wird die Katze sterben, nachdem sie vom Boden f geworfen wurde. Sie wissen dann, dass der Boden f-1 der maximal sichere Boden war.
Aber was ist, wenn Sie mehr als eine Katze haben? Sie können jetzt eine logarithmische Suche durchführen. Nehmen wir an, der Bau hat 100 Stockwerke und Sie haben zwei identische Katzen. Wenn Sie die erste Katze aus dem 50. Stock werfen und sie stirbt, müssen Sie nur 50 Stockwerke linear durchsuchen. Sie können es sogar noch besser machen, wenn Sie für Ihren ersten Versuch eine untere Etage wählen. Nehmen wir an, Sie entscheiden sich dafür, das Problem 20 Stockwerke gleichzeitig anzugehen, und das erste tödliche Stockwerk ist # 50. In diesem Fall überlebt Ihre erste Katze Flüge von den Etagen 20 und 40, bevor sie von der Etage 60 stirbt. Sie müssen nur die Etagen 41 bis 49 einzeln überprüfen. Das sind insgesamt 12 Versuche, was viel besser ist als die 50, die Sie benötigen würden, wenn Sie versucht hätten, die binäre Eliminierung zu verwenden.
Was ist im Allgemeinen die beste Strategie und die Komplexität im schlimmsten Fall für ein n-stöckiges Gebäude mit 2 Katzen? Was ist mit n Böden und m Katzen?
Angenommen, alle Katzen sind gleichwertig: Sie alle überleben oder sterben an einem Sturz aus einem bestimmten Fenster. Außerdem ist jeder Versuch unabhängig: Wenn eine Katze einen Sturz überlebt, ist sie völlig unversehrt.
Dies sind keine Hausaufgaben, obwohl ich sie vielleicht einmal für die Schulaufgabe gelöst habe. Es ist nur ein wunderliches Problem, das mir heute in den Sinn gekommen ist, und ich erinnere mich nicht an die Lösung. Bonuspunkte, wenn jemand den Namen dieses Problems oder des Lösungsalgorithmus kennt.
Antworten:
Sie können leicht ein wenig DP (dynamische Programmierung) für den allgemeinen Fall von n Stockwerken und m Katzen schreiben.
Die Hauptformel
a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n
sollte selbsterklärend sein:k - 1
Boden (alle untenk
) und diem - 1
Katzen (a[k - 1][m - 1]
) überprüfen .n - k
Stockwerke (alle Stockwerke darüberk
) und nochm
Katzen.max
.+ 1
kommt von der Tatsache, dass wir nur einen Versuch unternommen haben (unabhängig davon, ob die Katze überlebt hat oder nicht).min(f(k)) : for k in 1..n
.Es stimmt mit dem Google-Ergebnis von Gaurav Saxenas Link für (100, 2) überein .
Sie können leicht eine Strategie finden (wie man die erste Katze wirft), wenn Sie am besten
k
in einem anderen Array speichern .Es gibt auch eine schnellere Lösung, die keine O (n ^ 3) -Berechnungen beinhaltet, aber ich bin schon ein bisschen müde.
edit
Oh ja, ich erinnere mich, wo ich dieses Problem vorher gesehen habe .
quelle
+ 1
außerhalb der seinmin()
? Wie Sie selbst sagen, ist der Versuch immer noch ein Versuch, ob er erfolgreich ist oder nicht.+1
außerhalbmin
. Oder verschieben Sie es inmax
:)Laut einer kürzlich erschienenen Episode von Radiolab (über "Falling") erreicht eine Katze im 9. Stock die Endgeschwindigkeit. Danach entspannt es sich und es ist weniger wahrscheinlich, dass es verletzt wird. Es gibt völlig unverletzte Katzen nach einem Sturz von über dem 30 .. Die riskantesten Stockwerke sind 5. bis 9 ..
quelle
Die beste Strategie zur Lösung dieses Problems besteht darin, anhand des Gesetzes der Physik zu untersuchen, ob Ihre Annahmen überhaupt wahr sind.
Wenn Sie dies getan hätten, würden Sie feststellen, dass die Überlebenschancen der Katze tatsächlich zunehmen, je größer der Abstand zum Boden ist. Angenommen, Sie werfen es von einem immer höheren Gebäude wie den Petronas-Türmen und nicht von einem immer höheren Berg wie dem Mount Everest.
Bearbeiten:
Eigentlich würden Sie eine unvollendete Kamelverteilung sehen.
Zuerst ist die Wahrscheinlichkeit, dass die Katze stirbt, gering (sehr geringe Höhe), dann wird sie höher (niedrige Höhe), dann wieder niedriger (höhere Höhe) und dann wieder höher (sehr große Höhe).
Die Grafik für die Wahrscheinlichkeit des Sterbens von Katzen in Abhängigkeit von der Höhe über dem Boden sieht folgendermaßen aus:
(Ende 3, da die Kamelverteilung noch nicht abgeschlossen ist)
Update:
Die Endgeschwindigkeit einer Katze beträgt 100 km / h [= 27,7 m / s = 25,4 Yards / s].
Die Endgeschwindigkeit des Menschen beträgt 210 km / h. [= 75 m / s = 68,58 Yards / s]
Quelle für die Terminalgeschwindigkeit:
http://en.wikipedia.org/wiki/Cat_righting_reflex
Credits:
Goooooogle
Ich muss später überprüfen:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html
quelle
Ich habe dieses Problem zuerst in Steven Skienas Algorithm Design Manual (Übung 8.15) gelesen . Es folgte ein Kapitel über dynamische Programmierung, aber Sie müssen keine dynamische Programmierung kennen, um genaue Grenzen der Strategie zu beweisen . Zuerst die Problemstellung, dann die Lösung unten.
Nur 1 Ei
Wenn Sie das Ei von jedem Stockwerk ab dem ersten fallen lassen, wird das kritische Stockwerk in (schlimmstenfalls) n Operationen gefunden.
Es gibt keinen schnelleren Algorithmus. Lassen Sie g zu jedem Zeitpunkt in einem Algorithmus die höchste Etage, aus der das Ei gesehen wurde, nicht zu brechen. Der Algorithmus muss den Boden g + 1 vor einem höheren Stock h> g + 1 testen. Andernfalls könnte er nicht zwischen f = g + 1 und f = h unterscheiden, wenn das Ei vom Boden h abbricht.
2 Eier
Betrachten wir zunächst den Fall k = 2 Eier, wenn n = r ** 2 ein perfektes Quadrat ist. Hier ist eine Strategie, die O (sqrt (n)) Zeit benötigt. Lassen Sie zunächst das erste Ei in Schritten von r Stockwerken fallen. Wenn das erste Ei zerbricht, sagen
ar
wir am Boden , wissen wir, dass der kritische Boden f sein muss(a-1)r < f <= ar
. Wir lassen dann das zweite Ei von jeder Etage ab fallen(a-1)r
. Wenn das zweite Ei zerbricht, haben wir den kritischen Boden gefunden. Wir haben jedes Ei höchstens r fallen gelassen, so dass dieser Algorithmus im schlimmsten Fall 2r-Operationen ausführt, nämlich Θ (sqrt (n)).Wenn n kein perfektes Quadrat ist, nimm r =
ceil(sqrt(n)) ∈ Θ(sqrt(n))
. Der Algorithmus bleibt Θ (sqrt (n)).Beweis, dass jeder Algorithmus mindestens sqrt (n) Zeit benötigt. Angenommen, es gibt einen schnelleren Algorithmus. Betrachten Sie die Reihenfolge der Böden, von denen das erste Ei fallen gelassen wird (solange es nicht bricht). Da es weniger als sqrt (n) abfällt, muss ein Intervall von mindestens n / sqrt (n) vorhanden sein, das sqrt (n) ist. Wenn sich f in diesem Intervall befindet, muss der Algorithmus es mit dem zweiten Ei untersuchen, und dies muss Stockwerk für Stockwerk erfolgen, wobei der 1-Ei-Fall abgerufen wird. WIDERSPRUCH.
k Eier
Der für 2 Eier vorgestellte Algorithmus kann leicht auf k Eier erweitert werden. Lassen Sie jedes Ei mit konstanten Intervallen fallen, die als Potenzen der k-ten Wurzel von n genommen werden sollten. Suchen Sie beispielsweise für n = 1000 und k = 3 Suchintervalle von 100 Stockwerken mit dem ersten Ei, 10 mit dem zweiten Ei und 1 mit dem letzten Ei.
In ähnlicher Weise können wir beweisen, dass kein Algorithmus schneller ist,
Θ(n**(1/k))
indem wir aus dem k = 2-Beweis induzieren.Genaue Lösung
Wir leiten die Wiederholung ab, indem wir optimieren, wo das erste Ei (Boden g) abgelegt werden soll, vorausgesetzt, wir kennen optimale Lösungen für kleinere Parameter. Wenn das Ei zerbricht, haben wir die G-1-Etagen unten, um sie mit K-1-Eiern zu erkunden. Wenn das Ei überlebt, haben wir oben Stockwerke, die wir mit k Eiern erkunden können. Der Teufel wählt das Schlimmste für uns. Also für k> 1 die Wiederholung
quelle
O(k*n**(1/k))
für den schlimmsten Fall? Da muss ich im schlimmsten Falln**(1/k)
genauk
mal durchmachen .Geht das nicht davon aus, dass Sie "The Same Cat" verwenden?
Sie können es mathematisch angehen, aber das ist das Schöne an Mathe ... mit den richtigen Annahmen kann 0 gleich 1 sein (für große Werte von 0).
Aus praktischer Sicht können Sie "Ähnliche Katzen" erhalten, aber Sie können nicht "Die gleiche Katze" erhalten.
Sie könnten versuchen, die Antwort empirisch zu bestimmen, aber ich würde denken, dass es genügend statistische Unterschiede gibt, so dass die Antwort statistisch bedeutungslos wäre.
Sie könnten versuchen, "The Same Cat" zu verwenden, aber das würde nicht funktionieren, da es nach dem ersten Tropfen nicht mehr dieselbe Katze ist. (Ähnlich wie man niemals zweimal in denselben Fluss treten kann)
Oder Sie können die Gesundheit der Katze aggregieren, in extrem engen Abständen Proben entnehmen und die Höhen ermitteln, für die die Katze "größtenteils lebendig" ist (im Gegensatz zu "größtenteils tot" aus "The Princess Bride"). Die Katzen überleben im Durchschnitt (bis zum letzten Intervall).
Ich glaube, ich bin von der ursprünglichen Absicht abgewichen, aber wenn Sie den empirischen Weg gehen, stimme ich dafür, so hoch wie möglich zu beginnen und Katzen weiterhin fallen zu lassen, wenn die Größe abnimmt, bis sie statistisch überleben. Und dann erneut auf überlebende Katzen testen, um sicherzugehen.
quelle
Ich habe eine etwas andere Methode gewählt, um eine Lösung herzustellen.
Ich begann damit, den maximalen Boden zu ermitteln, der mit x Katzen und y Vermutungen mit der folgenden Methode bedeckt werden konnte .
Beginnen Sie mit 1 Etage und erhöhen Sie die Anzahl der Vermutungen, während Sie die Etagen überprüfen, welche Vermutungen sie überprüft haben und wie viele Katzen für jede Etage übrig waren.
Wiederholen Sie dies bis zu y Mal.
Dieser sehr ineffiziente Code zur Berechnung der gegebenen Antwort ist jedoch für eine kleine Anzahl von Katzen / Böden nützlich.
Python-Code:
Für 2 Katzen beträgt die maximale Anzahl an Stockwerken, die in x Vermutungen identifiziert werden können:
1, 3, 6, 10, 15, 21, 28 ...
Für 3 Katzen:
1, 3, 7, 14, 25, 41, 63 ...
Für 4 Katzen:
1, 3, 7, 15, 30, 56, 98 ...
Nach umfangreichen Recherchen (hauptsächlich unter Eingabe von Zahlenfolgen in OEIS ) stellte ich fest, dass die maximale Etage für x einem kombinierten stückweisen Muster folgt .
Für 2 Katzen:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)
Für 3 Katzen:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)
Für 4 Katzen:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)
Von hier aus habe ich den einfachen Ansatz des einfachen Inkrementierens von n gewählt, bis ich die erforderliche Anzahl von Stockwerken passiert habe.
Python-Code:
Dies ergibt die richtige Lösung für (100, 2) = 14.
Für jeden, der etwas weniger Triviales überprüfen möchte, ergibt sich (1 000 000, 5) = 43.
Dies läuft in O (n), wobei n die Antwort auf das Problem ist (je mehr Katzen desto besser).
Ich bin mir jedoch sicher, dass jemand mit einem höheren Mathematikniveau die stückweisen Formeln für die Berechnung in O (1) vereinfachen könnte.
quelle
quelle
Ich kann den Google Blogspot dazu nicht lesen (dank Works Blogwall), aber ich denke nicht, dass eine reine Suche im Binärstil am besten wäre. Der Grund dafür ist, dass eine binäre Suche auf der Vorstellung basiert, dass die gesuchte Antwort die gleiche Chance hat, an einem beliebigen Indexindex in der Liste zu sein. In diesem Fall ist das jedoch nicht wahr. In diesem Fall hat die Antwort eine höhere Wahrscheinlichkeit, näher an einem Ende des Bereichs zu sein als am anderen. Ich habe keine Ahnung, wie ich das in die Suche einbeziehen soll, aber es ist ein interessanter Gedanke.
quelle
all dieses verrückte Gerede über Katzen ... und es ist nur eine Vermutung des Zahlenproblems mit minimalen Vermutungen (Anzahl der Katzen). Es sollte auch nicht notwendig sein, Unendlichkeit künstlich (und falsch) als Teil der Lösung zu definieren. Die Variable sollte als Obergrenze oder Max-Try oder so bezeichnet worden sein. Die Problemdefinition (die Katzensache) weist jedoch einige schwerwiegende Probleme auf: Menschen reagieren auf das Potenzial von Tierquälerei und auch auf die vielen Facetten eines solchen Problems im wirklichen Leben, z. B. Luftwiderstand, Schwerkraft ist Beschleunigung und andere solche realen Parameter von dem Problem. vielleicht hätte es also ganz anders gefragt werden sollen.
quelle