Logik-Rätsel

Neue Frage »

coffeetown Auf diesen Beitrag antworten »
Logik-Rätsel
Ihr habt nen 100-stöckiges Gebäude und 2 zerbrechliche Gegenstände. Ihr möchtet wissen, genau ab welchem Stockwerk die Gegenstände zerbrechen. Feststellen könnt ihr das, indem ihr von nem x-beliebigen Stockwerk einen Gegenstand werft um dann zu sehen ob er zerbricht oder nicht.

Gesucht ist die effizienteste Vorgangsweise um festzustellen, bei welchem Stockwerk die Gegenstände zerbrechen.

Am effizientesten bedeutet, dass im "ungünstigsten" Fall möglichst wenig versuche notwendig sind.

z.B. könnte ich einfach ab 1 beginnen und bis 100 schrittweise raufwandern bis ein Teil zerbricht, dafür brauche ich im schlimmsten Fall aber 100 Versuche...

wenn ihr die Lösung habt, dann gebt mir bitte paar Denkanstöße, wie ihr darauf gekommen seid :P
lgrizu Auf diesen Beitrag antworten »
RE: Logik-Rätsel
Was mir spontan einfällt, ist erst mal bei 50 zu beginnen, entweder der Krug zerbricht oder nicht. Wenn er zerbricht muss das "optimale" Stockwerk unter 50 liegen, wenn nicht muss es über 50 liegen.

Dann helbiere ich die verbleibenden 50 Stockwerke wieder, und ich bin nach maximal 7 Schritten fertig.

Aber ich habe ja nur zwei Krüge...... verwirrt
 
 
IfindU Auf diesen Beitrag antworten »
RE: Logik-Rätsel
Ich weiß nicht was die optimale Lösung ist, aber ich schätze man startet unten, geht aber nicht immer eins hoch. Da wäre der zweite Gegenstand überflüssig. Wenn man immer 2 hoch geht, gewinnt man doppelt so schnell Höhe, und sobald er zerbricht, kann es nur die gesuchte Höhe sein - oder ein Stockwerk tiefer. Das könnte man mit dem zweiten Gegenstand testen.
Auf der anderen Seite könnte man auch jeweils immer 3 Stockwerke nach oben gehen, und sobald er zerbricht die zweite darunter testen (mit dem unteren zuerst).
lgrizu Auf diesen Beitrag antworten »
RE: Logik-Rätsel
@ IfindU:

Wenn ich unten starte (also in Stockwerk 1) und immer zwei nach oben gehe bin ich nach 7 Schritten erst in Stockwerk 15 angelangt. Gehe ich drei nach oben, so bin ich in 7 Schritten erst in Stockwerk 22.

Halbiere ich die Intervalle bin ich nach spätestens 6 Schritten fertig (der 7. muss nicht mehr ausgeführt werden):

Worst Case:

Stockwerk 50, der Krug zerbricht (nehmen wir mal an, ansonsten ist das weitere Vorgehen analog zu wählen im Intervall (50,100)).

Wir wählen Nun Stockwerk 25, wieder zerbricht o.B.d.A der Krug.

Wir wählen Stockwerk 12, um es ein wenig spannender zu machen bricht der Krug nun mal nicht, das gesuchte Stockwerk liegt also zwischen 12 und 25.

Wir wählen Stockwerk 18, der Krug zerbricht nicht, also ist zwischen 18 und 25 zu suchen.

Wir wählen nun 21 und der Krug zerbricht wieder nicht.

Wir wählen 23, zerbricht der Krug, so ist 22 das gesuchte Stockwerk, zerbricht er nicht, dann ist es 24.

Die ersten zwei Schritte sind stets analog zu führen, es ist etwas günstiger, wenn der Krug in Schritt 3 bereits bricht, wir haben dann zwischen 0 und 12 zu suchen, Schritt 4 wäre Stockwerk 6, Schritt 5 Stockwerk 3 oder 9 und wir sind bereits nach 5 Schritten fertig.

Also unten starten und dann in vorgegebenen Schritten mit Schrittweite <10 hinauf zu gehen ist nicht besonders effizient....

Edit: Aber was ist denn nun, wenn ich nach zwei Schritten nicht zufällig noch einen heilen Krug habe muss ich ja aufhören, da mein kostbares Porzellan vollständig zerbrochen ist oder bekomme ich noch nen dritten bzw. insgesamt 6 Krüge irgendwoher gezaubert? verwirrt

Also ein Verfahren zu finden, das nur zwei Schritte benötigt haöte ich für unmöglich....
IfindU Auf diesen Beitrag antworten »

@lgrizu
Du kannst Krüge aber öfters verwenden, wenn sie nicht zerbrechen. Daher kann man mit einem Krug mit der Methode des Threadstellers die exakte Lösung finden. Mit 2 Krügen kann man dann etwas riskanter werden und größere Schritte durchführen.
Deins ist natürlich optimal, wenn man 6 Krüge hat - wenn man aber nur die 2 hat wird man sich von unten rantasten müssen.
lgrizu Auf diesen Beitrag antworten »

Das stimmt sicherlich. Mir stellt sich -und diese Frage müsste der Threadsteller einmal aufklären- die Frage, ob es sich um zwei Gegenstände mit unterschiedlicher Zerbrechlichkeit handelt, von denen von jedem beliebig viele zur Verfügung stehen oder um genau zwei Krüge mit gleicher Zerbrechlichkeit.

Je nachdem ist der zu verwendende Algorithmus zu wählen.
IfindU Auf diesen Beitrag antworten »

Es macht nicht wirklich Sinn die Aufgabe mit 2 versch. Gegenständen durchzuführen - die Lösung ist 2 mal die optimale Lösung für einen Gegenstand durchzuführen.
Deswegen bin ich davon ausgegangen, man hat 2 identische Krüge da.
coffeetown Auf diesen Beitrag antworten »

Hallo!

1) es handelt sich um zwei identische Gegenstände.

2) zerbricht einer der Gegenstände, dann ist er natürlich futsch! Hat man keine Gegenstände mehr, dann Game Over!

Beispiel: ich werfe einen Gegenstand im 50. Stock. Mein Worst Case liegt bei 50, denn sollte er zerbrechen, müsste ich mit dem verbleibenden Gegenstand von 1 beginnend in +1 Schritten bis 50 ausprobieren, wann denn der Gegenstand zerbricht. Im schlimmsten Fall also 50 Versuche!

Mir ist die Lösung zwar bekannt, aber ich verstehe nicht, wie man darauf kommt ohne eben nur stumpf "auszuprobieren". Aber es steckt auf jeden Fall ne Logik dahinter!

Edit: ok nachdem ich die Lösung nu nochmal durchgegangen bin, ist mir nun endlich ein Licht aufgegangen... kapier's nun endlich, macht alles Sinn.
IfindU Auf diesen Beitrag antworten »

Wenn man in n Schritten hochgeht, braucht man etwa


Vermutlich ist am Ende noch ein wenig Optimierungspotential.

Würde tippen in 10er Schritten wäre diese Methode am schnellsten mit worstcase 19.
coffeetown Auf diesen Beitrag antworten »

Zitat:
Original von IfindU
Wenn man in n Schritten hochgeht, braucht man etwa


Vermutlich ist am Ende noch ein wenig Optimierungspotential.

Würde tippen in 10er Schritten wäre diese Methode am schnellsten mit worstcase 19.


Sehr gut smile Du hast es fast geschafft! Es gibt aber eine noch effizientere Methode mit worstcase 14!

Edit: das "Problem" deiner herangehensweise liegt darin, dass es bei jedem "zerbricht nicht" +1 wächst, eben bis +9 = n-1 im worstcase.
IfindU Auf diesen Beitrag antworten »

Am Ende Optimierungsmöglichkeiten meinte ich: Wenn wir bei 90 sind (9 Schritte) ist es nicht wirklich toll 100 zu probieren. In dem Zeitpunkt wäre es geschickter die 95 zu probieren. Zerbricht es, muss man nur 91 bis 94 hochgehen (14 Möglichkeiten). Wenn es nicht zerbricht kann man 98 probieren. Wenn es nicht zerbricht 100 und ggfs. 99 (höchsten 14) - wenn es zerbricht bleiben nur 96-97, also 13 Möglichkeiten.

Wenn man die Lösung hat, macht es Sinn variabel zu laufen, in der Hoffnung es bringt was. Anstatt jedes mal 10 zu laufen, riskiert man am Anfang etwas mehr - man läuft 13 hoch. (wenn es zerbricht, ist man in 13 Möglichkeiten fertig), dann 12, dann 11, und von da aus wieder 10 (mit Endoptimierung). Damit könnte man vielleicht noch ein besser sein.

Edit: Das oben hat einen Denkfehler - damit wird Worstcase leider nur auf 18 reduziert.
Edit2: Der Denkfehler hat mir zu schaffen gemacht, also läuft man von 14 Schritten aufwärts, dann 13 usw. Sobald er zerbricht überprüft man schrittweise welches es genau war. Mit 13 Schritten (was besser wäre) kommt man nicht auf 100 damit - leider.
coffeetown Auf diesen Beitrag antworten »

Zitat:
Original von IfindU
Am Ende Optimierungsmöglichkeiten meinte ich: Wenn wir bei 90 sind (9 Schritte) ist es nicht wirklich toll 100 zu probieren. In dem Zeitpunkt wäre es geschickter die 95 zu probieren. Zerbricht es, muss man nur 91 bis 94 hochgehen (14 Möglichkeiten). Wenn es nicht zerbricht kann man 98 probieren. Wenn es nicht zerbricht 100 und ggfs. 99 (höchsten 14) - wenn es zerbricht bleiben nur 96-97, also 13 Möglichkeiten.

Wenn man die Lösung hat, macht es Sinn variabel zu laufen, in der Hoffnung es bringt was. Anstatt jedes mal 10 zu laufen, riskiert man am Anfang etwas mehr - man läuft 13 hoch. (wenn es zerbricht, ist man in 13 Möglichkeiten fertig), dann 12, dann 11, und von da aus wieder 10 (mit Endoptimierung). Damit könnte man vielleicht noch ein besser sein.

Edit: Das oben hat einen Denkfehler - damit wird Worstcase leider nur auf 18 reduziert.
Edit2: Der Denkfehler hat mir zu schaffen gemacht, also läuft man von 14 Schritten aufwärts, dann 13 usw. Sobald er zerbricht überprüft man schrittweise welches es genau war. Mit 13 Schritten (was besser wäre) kommt man nicht auf 100 damit - leider.


Bingo! smile Fein gemacht!

Kann man also als Gleichungssystem auffassen:

x + (x - 1) + (x - 2) + (x - 3) + ... + 1 >= n = 100

offensichtlich gültig für alle x >= 14
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »