Eine Frage von Mathe-Kampf . Diese spezielle Frage wurde mir auch in einem meiner Vorstellungsgespräche gestellt.
"Ein Affe hat zwei Kokosnüsse. Er macht herumalbern, indem er Kokosnuss von den Balkonen herunterwirft M-stöckiges Gebäude. Der Affe will den untersten Stock wissen, wenn Kokosnuss gebrochen ist. Was ist die minimale Anzahl von Versuchen, um diese Tatsache festzustellen? "
Bedingungen: Wenn eine Kokosnuss gebrochen ist, können Sie sie nicht wiederverwenden. Du bist nur mit der anderen Kokosnuss übrig.
Mögliche Ansätze / Strategien, die ich mir vorstellen kann, sind
Ich frage mich, ob es andere Möglichkeiten gibt, dies zu tun.
Eine binäre Suche ist nicht die Antwort, weil Sie nur eine Chance haben, zu überschätzen. Die binäre Suche erfordert log m maximale Überschätzungen.
Dies ist ein zweiphasiger Ansatz. Die erste besteht darin, mit relativ großen Schritten über die Stockwerke zu iterieren. Nachdem die erste Kokosnuss zerbrochen ist, ist die zweite Phase, jede Etage nach dem letzten sicheren Boden zu versuchen.
Die großen Schritte sind ungefähr sqrt(m) , aber sie sind früher größer und später kleiner, denn wenn die erste Kokosnuss früh bricht, können Sie sich in der zweiten Phase weitere Iterationen leisten.
Interviewfragen wie diese sind so konzipiert, dass Sie sehen, wie Sie denken. Also würde ich wahrscheinlich eine O (N ^ 0.5) Lösung wie oben erwähnen, aber ich würde auch die folgende Diskussion geben ...
Da die Kokosnüsse im Laufe der Zeit innere Risse bilden können, sind die Ergebnisse möglicherweise nicht so konsistent mit einer O (N ^ 0,5) -Lösung. Obwohl die O (N ^ 0,5) -Lösung effizient ist, ist sie nicht völlig zuverlässig.
Ich würde eine lineare O (N) -Lösung mit der ersten Kokosnuss empfehlen und dann das Ergebnis mit der zweiten Kokosnuss verifizieren. Wobei N die Anzahl der Stockwerke im Gebäude ist. Also für die erste Kokosnuss versuchen Sie den 1. Stock, dann den 2., dann den 3., ...
Wenn man davon ausgeht, dass beide Kokosnüsse strukturell genau gleich aufgebaut sind und genau auf denselben Winkel fallen, dann kann man die zweite Kokosnuss direkt auf den Boden werfen, wo der erste gebrochen ist. Nennen Sie diesen Kokosnuss brechenden Boden B.
Für Kokosnuss # 2 müssen Sie nicht auf 1..B-1 testen, weil Sie bereits wissen, dass das erste Cocounut nicht auf dem Boden B-1, B-2, ... gebrochen hat Sie müssen es nur auf B. versuchen.
Wenn die 2. Kokosnuss auf B bricht, dann weißt du, dass B der fragliche Boden ist. Wenn es nicht bricht, können Sie schlussfolgern, dass die Kokosnuss im Laufe der Zeit Risse im Inneren und den Abbau aufweist und dass der Test von vornherein fehlerhaft ist. Du brauchst mehr Kokosnüsse.
Da die Gebäudegrößen ziemlich begrenzt sind, ist das zusätzliche Vertrauen in Ihre Lösung die O (N) -Lösung wert.
Wie @ Rafał Dowgird erwähnt, hängt die Lösung auch davon ab, ob der betreffende Affe ein afrikanischer Affe oder ein europäischer Affe ist. Es ist allgemein bekannt, dass afrikanische Affen mit einer viel größeren Kraft werfen. Dadurch wird der brechende Boden B nur mit einer Abweichung von +/- 2 Stockwerken genau gemacht.
Um zu garantieren, dass der Affe von all diesen Treppen nicht müde wird, wäre es auch ratsam, eine Schnur an der ersten Kokosnuss anzubringen. So müssen Sie nicht 1 + 2 + .. + B = B * (B + 1) / 2 Treppen für die erste Kokosnuss machen. Sie müssten nur genau B Treppenläufe machen.
Es mag scheinen, dass die Anzahl der Treppenläufe für dieses Problem nicht relevant ist, aber wenn der Affe überhaupt müde wird, kommen wir vielleicht nie zu einer Lösung. Dies gibt neue Überlegungen zum Problem beim Anhalten .
Wir gehen auch davon aus, dass das Gebäude auf der Erde liegt und die Schwerkraft auf 9,8 m / s ^ 2 eingestellt ist. Wir nehmen auch an, dass keine Gravitationswellen existieren.
Die beste Lösung, die ich kenne, ist 2 * sqrt (n). Lassen Sie die erste Kokosnuss von sqrt (n), 2 * sqrt (n), ... bis zu n (oder bis sie bricht) fallen. Lassen Sie dann den zweiten vom letzten bekannten "sicheren" Punkt in einem Stockwerk fallen, bis er bricht. Beide Stufen benötigen höchstens sqrt (n) Würfe.
Edit: Sie können die Konstante innerhalb von O (sqrt (n)) verbessern, siehe Kommentar rekursiv. Ich denke, der erste Schritt sollte um sqrt (2 * n) herum sein und bei jedem Wurf um 1 abnehmen, so dass der letzte Schritt (wenn die Bruchhöhe tatsächlich n ist) genau 1 ist. Details, die von Lesern herausgefunden werden müssen :)
Da es sich um eine Interviewfrage handelt, sollten Sie
berücksichtigenDie teure Operation ist der Affe, der die Treppe rauf und runter geht und die Kokosnuss nicht wirft. Wenn man so darüber nachdenkt, ist der "lineare" Ansatz tatsächlich N 2 .
Die Energie, die der Kokosnuss beim Fallen gegeben wird, ist ungefähr proportional zur Höhe des Tropfens. Wenn die Schale gebrochen ist, nachdem sie eine Menge Energie in ALLEN davon absorbiert hat, fällt es ...
Schwierige Interviewfrage. Es hat mehrere Tage gedauert.
Ich glaube, die Anzahl der Versuche ist 1,5 mal SQRT von # Etagen. (Für 100 Etagen und 2 Coco ist es 15)
Wir möchten die Größe jedes Versuches und die Anzahl der Versuche minimieren, indem wir beide zusammen verwenden, um alle möglichen Stockwerke abzudecken. In solchen Fällen stellt sich heraus, dass ein Quadratwuchs ein guter Ausgangspunkt ist, aber wir variieren die Größe jedes Versuches und den Durchschnitt um den Quadratwurzel herum. Auf diese Weise haben wir das Beste aus beiden Welten: Wenn wir die Größe jedes Versuches gleichmäßig auf dem Quadrat verteilt haben, erhalten wir die besten Ergebnisse. Für 100 und 2 ist dies 15,14,13,12,11,10,9,8,7,6 Das ergibt 1,5 mal 10.