Zwei Smartphones ein Hochhaus, von welchem Stockwerk geht das Smartphone zuerst kaputt.
-
µ 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.
-
Aber keine besonders gute Optimierung.
~~
Ausm Bauch heraus, würde ich binäre Suche machen, wobei ich das erste Handy in der Mitte vom letzen Pivot und neuem Pivot werfen würde.~~
Totaler Qutasch...hab ich jetzt aber auch doch keine Lust drüber nachzudenken.
-
'tschuldigung, ich habe es nicht ganz verstanden aber inwiefern ist eine arithmetische reihe besser als eine folge mit konstanten differenzen? ich meine, es gibt bei allen arithmetischen reihen worst-case-situationen (wenn der crash genau bei ist). und wenn ich mich nicht irre, hebt sich das doch wieder damit aus, dass bei einer reihe mit konstanten differenzen mehr würfe mit dem handy 1 gemacht werden müssen.
-
Du beziehst dich auf Mühs Antwort oder?
Weil sich die Bereiche immer um eins verkleinern, gleichen Sie aus, dass man einen Wurf mehr brauch, um in diesen Bereich zu kommen.
Vergleiche Mühs Beispiel mit H=100:
Bei gesuchte Stelle 99 brauch Müh maximal 14 Würfe (hier sogar weniger), Schrittweite 10 brauch
10 20 30 40 50 60 70 80 90 91 92 93 94 95 96 97 98
-
Jester schrieb:
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.
Du hast recht. Entschuldigung, habe das missverstanden bzw nicht richtig gelesen.
Aber naja, für den Fall, dass H bekannt ist, halte ich die Arithmetische Reihe immer noch für optimal.
Falls unbekannt, scheint mir ein Algorithmus mit Wurzelförmiger Komplexität optimal, wie das quadratische Springen von Dir.Grüße und frohe Weihnachten
Edit: Tippfehler
-
Jester schrieb:
Aber dann sollte so ein simples Adversary-Argument wie ich es oben skizziert habe doch eigentlich durchgehen, oder?
Bin mir nicht sicher was Du damit meinst. Kannst Du das erklären?
