Prüfung Algorithmen und Programmierung in C

[cloidnerux]

Ich komme auf 7, vorausgesetzt ich habe die Aufgabe verstanden und rechne das richtige

Das will ich sehen

Aufgabe etwas anders Formuliert:
Finde das höchste Stockwerk, aus dem man ein Ei fallen lassen kann, ohne das es kaputt geht. Man hat zwei Eier und 100 Stockwerke.
Mit welchem Algorithmus schafft man das in der geringsten Worst-Case Laufzeit?

[Xin]

Ich komme auf 18 plus die Erkenntnis, dass ich schon ziemlich lange keine Kurvendiskussion mehr gemacht habe.

Ich komme auf 7, vorausgesetzt ich habe die Aufgabe verstanden und rechne das richtige

Das will ich sehen

Ich wäre schon begeistert, wenn jemand ein Ei vom Erdgeschoss fallen lässt und es bleibt heil

[canlot]

Ich komme auf 18 plus die Erkenntnis, dass ich schon ziemlich lange keine Kurvendiskussion mehr gemacht habe.

Achso darum gehts Dann versteh ich nicht wie ich die Aufgabe rechnen soll
Ich habe die Stockwerke immer durch zwei gerechnet bis ich bei weniger als einem angekommen bin, aber da bräuchte man dann mindestens 7 Eier.
Anscheinend bin ich die Aufgabe völlig falsch angegangen, ich fühle mich dumm kann mir jemand bitte erklären wie man es rechnet?

[cloidnerux]

Anscheinend bin ich die Aufgabe völlig falsch angegangen, ich fühle mich dumm kann mir jemand bitte erklären wie man es rechnet?

Man hat zwei Grundbedingungen:
Ein Ei wird zerstört, wenn es aus einem bestimmten Stock x oder darüber fallen gelassen wird.
Ein Ei wird nicht zerstört, wenn es aus einem Stock x-1 oder darunter fallen gelassen wird.

Daraus ergeben sich einige Grundgedanken:
Es macht keinen Sinn im stock 100 anzufangen, da es sehr wahrscheinlich ist, dass das Ei zerstört wird und das nächste auch.
Sobald ich ein Stockwerk habe, von dem ich weiß das es >=x ist, brauche ich keine Stockwerke über diesem zu testen.

Der einfachste Weh wäre es also, das Ei aus jedem Stockwerk beginnend bei 1(0 Erdgeschoss?) fallen zu lassen.
Nach n versuchen bist du bei einem Stock angekommen, bei dem es kaputt geht.
Worst-Case dafür: 100,

Eine bessere Möglichkeit wäre es nun, ein Ei erst aus dem 50ten Stock fallen zu lassen. Geht es kaputt, muss der Stock x unterhalb von 50 sein, bleibt es heil >x.
Dann gehst du wieder linear von unten nach oben durch(je nach dem bei 1 oder 50 anfangen).
Worst-Case hier: 50.

Ich hoffe ich konnte dir einen möglichen Ansatz verständlich machen.

[canlot]

Eine bessere Möglichkeit wäre es nun, ein Ei erst aus dem 50ten Stock fallen zu lassen. Geht es kaputt, muss der Stock x unterhalb von 50 sein, bleibt es heil >x.
Dann gehst du wieder linear von unten nach oben durch(je nach dem bei 1 oder 50 anfangen).
Worst-Case hier: 50.

Dann lag ich doch gar nicht so falsch, oder?
Ich nehme immer die Hälfte, ich lasse das Ei aus dem 50 Stock fallen, nehmen wir an es geht kaputt.
Dann wieder die Hälfte also 25, das Ei geht auch hier kaputt, wieder die Hälfte also 12,5 das Ei geht auch hier kaputt.
Die Hälfe von 12,5 ist 6,25 das Ei bleibt heile also addiere ich die Hälfte von 6,25 das wären 6,25 + 3,125 = 9,375, Ei geht kaputt, 9,375 - (die Hälfte von 3,125) 1,5625 = 7,8125 Stockwerke.
Das Ei bleibt heile also addiere ich wieder, diesmal die Hälfte von 1,5625 was 0,78125 ist dazu und erhalte 7,8125 + 0,78125 = 8,59375 Stockwerke.
Die worst case Laufzeit-Schritte wären 7.

[Xin]

Ich nehme immer die Hälfte, ich lasse das Ei aus dem 50 Stock fallen, nehmen wir an es geht kaputt.
Dann wieder die Hälfte also 25, das Ei geht auch hier kaputt, wieder die Hälfte also 12,5 das Ei geht auch hier kaputt.

Welches Ei?
Du hast nur zwei Eier und die sind dann Matsch. ^^

Wer hat eigentlich die Aufgabe gestellt...? Allein die Vorstellung daran zu glauben, dass man ein Ei aus dem 2. Stock werfen könnte und hoffen, dass es dabei nicht zerbricht ist irre und die Antworten wie "Du hast nur zwei Eier und die sind dann Matsch." klingen auch irgendwie nicht komplett jugendfrei.

[cloidnerux]

Wer hat eigentlich die Aufgabe gestellt...? Allein die Vorstellung daran zu glauben, dass man ein Ei aus dem 2. Stock werfen könnte und hoffen, dass es dabei nicht zerbricht ist irre und die Antworten wie "Du hast nur zwei Eier und die sind dann Matsch." klingen auch irgendwie nicht komplett jugendfrei.

Du und dein Bezug zur realität

Dann lag ich doch gar nicht so falsch, oder?
Ich nehme immer die Hälfte, ich lasse das Ei aus dem 50 Stock fallen, nehmen wir an es geht kaputt.
Dann wieder die Hälfte also 25, das Ei geht auch hier kaputt, wieder die Hälfte also 12,5 das Ei geht auch hier kaputt.

Du hast nur zwei Eier, daher machst du das zwei mal, und dann ist vorbei.
Deswegen geht das nicht.

Du musst zwangsweise ab irgendeinem Punkt jedes Stockwerk durchprobieren und zwar von unten nach oben.

[canlot]

Du hast nur zwei Eier, daher machst du das zwei mal, und dann ist vorbei.
Deswegen geht das nicht.

Wenn ich nur zwei Eier hätte und wären es Hühnereier würde ich sie essen statt von irgendwo runterschmeißen

[cloidnerux]

Wenn ich nur zwei Eier hätte und wären es Hühnereier würde ich sie essen statt von irgendwo runterschmeißen

Und der nächste der zu sehr in der Realität lebt. Ich dachte das wäre in Programmierforum hier

[cloidnerux]

Und es kommt keiner auf 14 im Worst-Case?