Zwei Smartphones ein Hochhaus, von welchem Stockwerk geht das Smartphone zuerst kaputt.
-
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).
-
Ich habe bereits geschrieben, dass es nur geht, wenn man annehmen darf, dass es ein Stockwerk gibt in dem es kaputt geht.
-
Ja, und mit deiner Methode findet man das nicht.
-
Was ist jetzt eigentlich die dem Erwartungswert nach beste Strategie für H bekannt?
Nachdem das erste Handy sqrt(n)-2 Stockwerke überlebt hat, kann man es ja weiter nutzen...
-
Jester schrieb:
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.
Sehe ich nicht so. Handy 2 aus 17 zu werfen und Handy 1 aus 16 ist ein Algorithmus der in allen anderen Fällen versagt, es ist schlicht nicht definiert was dann gemacht werden soll.
Imho heißt Optimalität im Bezug auf ein Verfahren: Das Worstcase-Zielstockwerk, d.h. die maximale Anzahl an Schritten, ist unter allen Algorithmen minimal.Jester schrieb:
Das geht nicht wenn du h nicht kennst. Deswegen behelfsmässig die wuadratzahlen, weil die ungefähr genauso schnell wachsen.
Kann ich auch nicht nachvollziehen. H kann beliebig sein, der darauf angewandte Algorithmus bekommt H aber als Eingabeparameter. Wie ein Sortieralgorithmus der auch auf beliebig langen Listen funktioniert. Zum Start des Verfahrens ist die Anzahl also imho sehr wohl bekannt.
Okay, gleich noch ein paar Gedanken dazu....
-
Ich habe die ganze Zeit schon das Gefühl, es könnte was mit der Arithmetischen Reihe zu tun haben.
H1 = Handy 1
H2 = Handy 2
H = Anzahl StockwerkeAlso mit H1 jeweils +1 Stockwerke weiterspringen als im Schritt davor:
1 (+1) 2 (+2) 4 (+3) 7 (+4) 11 (+5) 16 ...Bei H=100 hätten wir mit H1 folgende Stockwerke zu sondieren:
1 2 4 7 11 16 22 29 37 46 56 67 79 92
Nach 92 im schlimmsten Fall bis 100 durchlaufen ... nee, das geht besser in dem man die Reihenfolge umkehrt und die Sprünge bis zu H verkleinert:9 22 34 45 55 64 72 79 85 90 94 97 99 100
(Anmerkung: Es gibt auch andere, gleichwertige Verfahren gemäß dieser Reihe. Z.B. 14 27 39 51 61 70 78 85 91 96 100. Basiert ebenfalls auf der Arithmetischen Reihe, nur der Start ist etwas verschoben, weil die Höhe des Gebäudes nicht exakt aufgeht)
Das Besondere: Jeder Wurf mit H1 reduziert die Anzahl der notwendigen Würfe mit H2, um die Lücke der letzten Lowerbound zu schließen, um genau eins. (Das ist imho der Grund, warum das Verfahren optimal ist)
Also als Beispiel zwei Fälle, die Handys halten bis Stockwerk 33 und 44.
Dann würde man für 33 untersuchen:
9 22 34 (crash H1 hier) und mit H2 noch 23-33. Sind genau 3+11 = 14 Würfe
Und für 44:
9 22 34 45 (crash H1) und weiter mit H2: 35-44. Macht 4+10 = 14 Würfe.Es sind immer 14 Würfe mit Ausnahme von Fällen bei denen das Handy unterhalb des neuten Stockwerks zerbricht. Dann sind es aber weniger als 14.
Wenn man dieses Verfahren A jetzt gedanklich zu einem Verfahren B variiert, um es zu optimieren, gibt es eine Reihe von Fällen. Ich habe den Verdacht, dass man die Fälle alle systematisch auflisten und untersuchen könnte für eine formale Beweisführung. Es geht darum für Verfahren B Upper- und Lowerbounds sowie Sprungweiten mit H1 zu optimieren, und daraus zu schließen, dass sich der Worstcase verlagert und nicht mehr besser als A sein kann.
Ganz informell und unvollständig:
Wenn B eine kleinere Folge an Einzelschritten mit H2 machen muss, hat das Verfahren sich den Vorteil durch größere Lücken an anderen Stellen erkauft. Egal ob die Upperbound geringer oder die Lowerbound höher ist, gibt es danach oder davor eine entsprechend größere Lücke. Sollte sich das Zielstockwerk dort befinden, gibt es Fälle in denen B schlechter als A wird oder zumindest der Worstcase bestenfalls gleich bleibt.Entsprechendes gilt, wenn B durch größere Sondierungssprünge mit H1 schneller an die Upperbound kommt. Für jeden eingesparten Sprung wächst die größte Lücke darunter und das Worstcase-Zielstockwerk verlagert sich, B verschlechtert sich dort gegenüber A bzw der Worstcase bleibt bestenfalls gleich.
Edit: Nur Tippfehler
-
µ schrieb:
Jester schrieb:
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.
Sehe ich nicht so. Handy 2 aus 17 zu werfen und Handy 1 aus 16 ist ein Algorithmus der in allen anderen Fällen versagt, es ist schlicht nicht definiert was dann gemacht werden soll.
Imho heißt Optimalität im Bezug auf ein Verfahren: Das Worstcase-Zielstockwerk, d.h. die maximale Anzahl an Schritten, ist unter allen Algorithmen minimal.genau, das war mein argument: nur eine worst-case analyse macht sinn.
µ schrieb:
Jester schrieb:
Das geht nicht wenn du h nicht kennst. Deswegen behelfsmässig die wuadratzahlen, weil die ungefähr genauso schnell wachsen.
Kann ich auch nicht nachvollziehen. H kann beliebig sein, der darauf angewandte Algorithmus bekommt H aber als Eingabeparameter. Wie ein Sortieralgorithmus der auch auf beliebig langen Listen funktioniert. Zum Start des Verfahrens ist die Anzahl also imho sehr wohl bekannt.
Also ich weiß nicht wie Du das siehst, aber ich finde die Formulierung aus dem Eingangspost: "Aber welche Schrittzahl soll man nehmen wenn H nicht gegeben ist? Was ist die Optimale Schrittweite fuer H ?" sehr eindeutig. H ist nicht Teil der Eingabe und daher auch nicht bekannt.
-
Die Quadratzahlen zu probieren ist ja letztlich auch nur ne Art arithmetische Reihe, nämlich Summe der ungeraden Zahlen. Du summierst nun halt alle Zahlen, was aber zumindest asymptotisch keinen Unterschied macht.
Was mir gut gefällt ist das Argument, dass Du quasi dafür sorgst, dass mit beiden Smartphones etwa gleich viele Würfe gemacht werden, weil Du in jedem Schritt mit dem ersten Smartphone die Lücke um 1 vergrößerst. Das ist imo ein gutes Indiz dass die Strategie wirklich nah am Optimum ist. Ich vermute aber, dass man das H schon irgendwie groß genug wählen muss, weil man sonst immer irgendwelche fiesen Randeffekte reinbekommt. Aber dann sollte so ein simples Adversary-Argument wie ich es oben skizziert habe doch eigentlich durchgehen, oder?
-
Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.
-
Smartphones schrieb:
Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.
Sorry aber ich glaube Du hast das Problem nicht so ganz verstanden.
-
Blaues Licht schrieb:
Smartphones schrieb:
Glaube, das einfachste und beste ist, mit einem Handy im ersten Stock anzufangen und mit dem zweiten im zweiten Stock. Wenn beide nicht kaputt gegangen sind, macht man mit dem ersten im dritten Stock und dem zweiten im vierte Stock weiter.
Sorry aber ich glaube Du hast das Problem nicht so ganz verstanden.
Das ist eben der Versuch einer anderen Optimierung: Laufwege.
