Zeigen Sie, dass man die zweitkleinste Zahl einer Folge a1, a2, a3, a4 mit höchstens 4 Vergleichen bestimmen kann.

Question

Aufgabe:

a) Zeigen Sie, dass man die zweitkleinste Zahl einer Folge a₁, a₂, a₃, a₄ mit höchstens 4 Vergleichen bestimmen kann.

b) Zeigen Sie, dass man das Minimum und das Maximum einer Folge a₁, ..., a_n zusammen in weniger als (n-1)+(n-2) Vergleichen bestimmen kann, wenn n groß genug ist.

Problem/Ansatz:

Ich weiß leider nicht wie ich die Behauptungen Zeigen soll. Kann mir da jemand helfen?

Comments

a) hier stand Falsches

---

Dann kennst du die zweitkleinste Zahl

Das steht in krassem Widerspruch zu folgendem Gegenbeispiel :
3 - 6 - 2 - 1  vs 3 - 6 - 4 - 1

Answer 1

Du hast die Zahlen a, b, c, d. Lass und zunächst mal die kleinste herausfinden

Vergleiche also a mit b und c mit d und vergleiche dann die kleinste von {a, b} mit der kleinsten von {c, d}.

Jetzt hast du bereits die kleinste Zahl. Hast du jetzt auch bereits die zweitkleinste?

Vermutlich nicht, aber du hast ja letztendlich noch einen Vergleich übrig. Also nutze ihn.