0 Daumen
58 Aufrufe

Frage: Hat jemand eine Idee für den Folgenden Algorithmus mit ! sublinearer ! Laufzeit?

Es geht konkret um ein Regal mit der Höhe n ∈ ℕ.

In jede Höhe kann ein Brett eingefügt werden und es soll die maximale Fallhöhe r ermittelt werden, wo ein Brett nicht kaputt geht.

Es stehen zwei Bretter zur Verfügung die kaputt gehen dürfen. Ein Brett geht erst kaputt, sobald es die Höhe (r+1) erreicht hat (heißt: oberhalb der max. Fallhöhe ist). Vorher darf man mit einem Brett so oft testen wie man möchte.

Es gilt zusätzlich:

- Wenn ein Brett nicht bei Höhe x bricht, bricht es auch bei keiner Höhe x' < x.

- Ein Fall aus Höhe 0 führt nicht zum zerbrechen.

- Es gibt keine Materialermüdung, unterschiedliche Fall-/Aufprallverhalten o.Ä.

- Ein Regal kann beliebig hoch werden

Theoretisch könnte man einfach linear von unten nach oben suchen und sobald ein Brett kaputt geht impliziert das die max. Fallhöhe r = (h-1).

Jedoch soll der Suchalgorithmus eine sublineare Laufzeit haben, heißt: f ∉ Ω(g) mit g(n) = n.

Bin dankbar für jede Hilfe!:)

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community