Zwei Smartphones ein Hochhaus, von welchem Stockwerk geht das Smartphone zuerst kaputt.
-
Hi,
ich habe letztens in einem Interview folgende Frage bekommen:
Du hast zwei Smartphones und ein Hochhaus mit Anzahl H an Stockwerken, finde das Stockwerk heraus von dem das Smartphone zuerst kaputt geht. Wenn das Smartphone kaputt ist kann man es nicht mehr benutzen, wenn es heile bleibt kann man wieder benutzen.
Mein erster Gedanke war. Ein Smartphone von H/2 Stockwerk zu werfen und gucken ob es kaputt geht, wenn ja, schmeiss das andere Smartphone vom ersten Stockwerk und falles es heile bleibt vom zweiten usw.
Wenn das Smartphone beim Wurf vom H/2 Stockwerk heile bleibt, schmeiss es vom (H/2)+1 usw.Aber das ist sehr ineffizient. Wenn H gegeben ist habe ich errechnet ist die beste Anzahl an Wuerfen: y = (H/sqrt(H)) + (sqrt(H)-2)
Aber welche Schrittzahl soll man nehmen wenn H nicht gegeben ist? Was ist die Optimale Schrittweite fuer H ?
mfg
-
Quadratzahlen probieren und dann schrittweise? Das braucht wurzel h schritte bis es kaputt geht und dann nochmal 2 wurzel h - 1 einzelschritte. Wie kriegt man ne lower bound?
-
Man könnt auch einfach unten anfangen!
-
ScottZhang schrieb:
Man könnt auch einfach unten anfangen!
Wenn das Hochhaus 1 Millionen Stockwerke hat und das Smartphone im 999999 kaputt geht braucht man 999999 Wuerfe. Ausserdem brauchte man dann nur ein Smartphone. Sehr ineffizient.
-
Wo in der Aufgabenstellung steht, dass das Smartdings fallen gelassen wird? Weiterhin ist H/sqrt(H) = sqrt(H) in allen hier relevanten Faellen.
-
knivil schrieb:
Wo in der Aufgabenstellung steht, dass das Smartdings fallen gelassen wird?
Von was sollte es denn sosnt kaputt gehen?
-
qweasdyxc schrieb:
Von was sollte es denn sosnt kaputt gehen?
Der Punkt ist, das die Frage kacke ist bzw. unsauber gestellt.
Quadratzahlen probieren und dann schrittweise? Das braucht wurzel h schritte bis es kaputt geht und dann nochmal 2 wurzel h - 1 einzelschritte. Wie kriegt man ne lower bound?
Wenn du meinst erst Stockwerk 1,4,9 16, 25, ... zu testen und im Defektfall alle im letzten Intervall einzeln zu untersuchen, dann gibt es wahrscheinlich einen besseren Weg.
-
Wichtig ist hier doch, dass man nur genau zwei Telefone hat. Das heißt, man kann nicht beliebig viele Tests durchführen, sondern muss seine Ressourcen clever einteilen.
Daher:
1. Clever einen lower und upper bound bestimmen mit dem ersten Telefon. Bei der Bestimmung des lower-bound bleibt das Telefon heile, beim upper-bound geht das erste Telefon kaputt.
2. Dann linear zwischen diesen Grenzen mit dem zweiten Telefon suchen, von unten nach oben.Der Knackpunkt ist natürlich 1. Naiver Vorschlag: Bei Stockwerk 2 anfangen, dann immer verdoppeln. So bekommt man irgendwann ein lower-bound 2^N (der letzte, wo es heile blieb) und upper-bound 2^(N+1) (der erste, wo es kaputt war) und hat dazwischen noch 2^N-1 Stockwerke linear zu durchsuchen.
Ich vermute, den meisten Fragestellern würde diese Lösung schon reichen. Mir auch, daher höre ich hier auf. Aber wenn es die Note 1+ mit Sternchen sein soll, dann sollte man noch Zeigen, welches Vorgehen bei 1. optimal ist. Intuitiv würde ich schon vermuten, dass Verdoppeln optimal ist, aber das muss man natürlich noch zeigen.
-
errechnet ist die beste Anzahl an Wuerfen
Ist sie wahrscheinlich, komme selbst auf nix besseres. Mir fehlt aber ein Beweis.
-
mit verdoppeln hast du im schlimmsten fall h/2 stockwerke einzeln zu durchsuchen. sind also log(h) + h/2 versuche.
mit der methode von jester sind es nur sqrt(h) stockwerke für die lower/upper-bound und nochmart soviele einzelstockwerke. (nur im sinne der komplexität! keine exakten zahlen hier).deine methode also linear, jesters wurzelförmig.
-
Kniffelfix schrieb:
ScottZhang schrieb:
Man könnt auch einfach unten anfangen!
Wenn das Hochhaus 1 Millionen Stockwerke hat und das Smartphone im 999999 kaputt geht braucht man 999999 Wuerfe. Ausserdem brauchte man dann nur ein Smartphone. Sehr ineffizient.
Stimmt, aber ich wette das Scheissding geht schon im ersten kaputt.
-
deine methode also linear, jesters wurzelförmig
Trotzdem ist jesters Methode nicht optimal. Bei einem Haus mit 10000 Stockwerken braucht sein etwa 300 Wuerfe, die vorgeschlagene benoetigt 200.
Desweiteren geht es darum, wenn die Anzahl der Stockwerke unbekannt/unendlich ist. Hier ist es noch schwieriger eine begruendet gute Suchstrategie zu entwerfen.
-
Schrittweite sqrt(h) schlage ich vor.
-
SeppJ schrieb:
1. Naiver Vorschlag: Bei Stockwerk 2 anfangen, dann immer verdoppeln. So bekommt man irgendwann ein lower-bound 2^N (der letzte, wo es heile blieb) und upper-bound 2^(N+1) (der erste, wo es kaputt war) und hat dazwischen noch 2^N-1 Stockwerke linear zu durchsuchen.
Der Trick geht zwar oft, aber hier nicht. Das erste Handy wird log(N) benutzt, das zweite Handy N/2 mal. Bei der optimalen Strategie sollten die beiden in etwa ausgeglichen sein.
2. Naiver Vorschlag:
Das erste Handy von den Stockweren 1², 2², 3³, 4², 5², ..., k²,(k+1)² runterfallen lassen (bei (k+1)² geht es dann kaputt).
Dann mit dem zweiten Handy k²,k²+1,k²+2,...,(k+1)²-1 überprüfen.Das wären k+1 Schritte mit dem ersten Handy und (k+1)²-1 - k²=2k Schritte mit dem zweiten, also insg. 3k+1 Schritte.
Weil wir hier x mit (k+1)²-1 substituiert haben kommt man auf etwa . Damit sind wir schon auf vorgedrungen. Das sieht asymptotisch schon mal gut aus. Der Faktor sollte sich aber noch verbessern lassen.
3. Naiver Vorschlag:
1. Handy: a 1²,a 2²,... a (k+1)²
2. Handy: a k², a k²+1, ..., a(k+1)²-1
Ansatz: Würfe Handy 1 = Würfe Handy 2
k+1 = -1 + a + 2 a k
=> a = (2 + k)/(1 + 2 k)Wir lassen k gegen unendlich streben -> a=1/2.
D.h. wir hätten hier k+1 + -1 + 1/2 + 2/2 k = 1/2 + 2 k Versuche, weil wir hier wieder x mit 1/2(k+1)²-1 substituiert haben müssen wir wieder k mit ersetzen, das ergibt Versuche oder ungefähr , was minimal besser ist als der 2. Naive Vorschlag.
-
knivil schrieb:
deine methode also linear, jesters wurzelförmig
Trotzdem ist jesters Methode nicht optimal. Bei einem Haus mit 10000 Stockwerken braucht sein etwa 300 Wuerfe, die vorgeschlagene benoetigt 200.
Desweiteren geht es darum, wenn die Anzahl der Stockwerke unbekannt/unendlich ist. Hier ist es noch schwieriger eine begruendet gute Suchstrategie zu entwerfen.
Wenn man die anzahl nicht kennt macht eigentlich nur eine asymptotische analye sinn. Ansonsten gibt es nämlich garkeine optimale strategie. Wenn zum beispiel das 17. stockwerk das zielstockwerk ist, dann ist es offensichtlich optimal einmal aus dem 17. und einmal aus dem 16. zu werfen.
Meine strategie ist genau für den asymptotischen fall... Man muss die zahl der stockwerke dafür nicht kennen. Im prinzip funktioniert Seppjs Strategie ja auch, besonders wenn er genug handys hätte.
Ich vermute auch, dass die strategie asymptotisch optimal ist: nehmen wir an ich bestimme wo es kaputt geht und du sollst es rausfinden. Ich schau also bei deiner strategie zu. Sobald du einen zu großen schritt machst, sage ich das handy ist kaputt. Das zwingt dich dann den großen teil nochmal abzulaufen (wenn du was überspringst mach ich dein handy kaputt :)) und zeigt, dass man keine großen sprünge machen darf beim suchen. Wenn man umgekehrt nur kleine sprünge macht, dann braucht man viel zeit um zu großen bereichen vorzudringen. Eine genaue formalisierung seh ich aber grad nicht.
-
Jockelx schrieb:
Schrittweite sqrt(h) schlage ich vor.
Das geht nicht wenn du h nicht kennst. Deswegen behelfsmässig die wuadratzahlen, weil die ungefähr genauso schnell wachsen.
-
mein spontaner Vorschlag wären ja Fibonacci-Zahlen gewesen. Das skaliert irgendwann auch exponentiell, aber Fib(k+1)-Fib(k) ist nicht so groß wie "2{k+1}-2k". Ausserdem wird das Handy eh in den ersten Stockwerken zerdeppern
-
irgendwie find ich's fast ein bissel erschütternd
-
Gehe mit Sepp D'Accord:
Man nehme das erste Handy und lässt es bei h/2 fallen(falls h ungerade eben passend). Geht es kaputt sucht man darunter bei 2 anfangend in zweier Schritten (geht es kaputt muss es das darunter liegende Stockwerk sein (oder es gibt gar keins)) bis man das passende Stockwerk hat.
-
Wenn es das vierte Stockwerk überlebt hat und im sechsten kaputt geht, woher weißt du dann, ob es das fünfte überlebt hätte?
Außerdem ist h/2, also praktisch nur ein Einsatz des ersten Handies, vermutlich Verschwendung. Das erspart dir gerade mal einen Faktor von 2 zum Einsatz nur eines Handies, du bleibst in O(x).
