Suchen und Sortieren — Verfahren, die vergleichen
Zahlenraten von 1 bis 100, du hörst nur „größer“ oder „kleiner“. Welcher erste Tipp ist am besten?
Erklärung: 50 teilt die Zahlen in zwei Hälften. Nach der Antwort bleibt nur noch eine Hälfte übrig. Mit 1 oder 10 schließt du fast nichts aus.
Zahlenraten von 1 bis 100. Dein Tipp 50, die Antwort: „kleiner“. Welcher Tipp ist jetzt am besten?
Erklärung: Übrig sind 1 bis 49. Die Mitte davon ist 25. 49 schließt nur eine Zahl aus, 75 ist schon ausgeschlossen.
Zahlenraten von 1 bis 16, du tippst immer die Mitte. Wie viele Tipps brauchst du höchstens?
Erklärung: Nach jedem Tipp bleibt höchstens die Hälfte: 16 → 8 → 4 → 2 → 1. Der 5. Tipp trifft sicher. 16 wäre Hochzählen, 8 nur einmal halbiert.
Zahlenraten von 1 bis 100, du tippst immer die Mitte. Wie viele Tipps brauchst du höchstens, bis du die Zahl triffst? ___
Erklärung: Nach jedem Tipp bleibt höchstens die Hälfte: 100 → 50 → 25 → 12 → 6 → 3 → 1. Spätestens der 7. Tipp trifft.
Zahlenraten von 1 bis 100. Ben zählt hoch: 1, 2, 3 … Die geheime Zahl ist 100. Wie viele Tipps braucht Ben? ___
Erklärung: Beim Hochzählen schließt jeder Tipp nur eine Zahl aus. Ben braucht 100 Tipps — Halbieren bräuchte höchstens 7.
Zahlenraten von 1 bis 100, die Zahl ist 64. Lea zählt ab 1 hoch, Ben tippt immer die Mitte. Beide brauchen gleich viele Tipps.
Erklärung: Beide finden die 64, aber Lea braucht 64 Tipps, Ben höchstens 7. Richtige Verfahren können sehr verschieden schnell sein.
Zahlenraten von 1 bis 100, du tippst immer die Mitte. Du brauchst jedes Mal genau 7 Tipps.
Erklärung: 7 ist das Höchste, nicht immer genau. Ist die Zahl 50, triffst du schon mit dem 1. Tipp.
10 Karten liegen verdeckt und durcheinander. Wie viele musst du höchstens umdrehen, bis du die 7 siehst?
Erklärung: Durcheinander verrät eine Karte nichts über die anderen. Im schlechtesten Fall liegt die 7 ganz zuletzt. Halbieren geht nur bei sortierten Karten.
10 Karten liegen verdeckt und sortiert, die kleinste links. Du suchst die 7. Die mittlere Karte zeigt 12. Wo suchst du weiter?
Erklärung: 7 ist kleiner als 12, und die kleineren Karten liegen links. Rechts kann die 7 nicht sein. Von vorne anfangen verschenkt, was du schon weißt.
Im Wörterbuch suchst du „Zebra“. Du schlägst die Mitte auf, dort steht „Maus“. Jetzt blätterst du nach hinten.
Erklärung: Z kommt im Alphabet nach M. Weil das Wörterbuch sortiert ist, kann „Zebra“ nur hinten stehen.
Karten 7, 3, 9, 2. Du gehst einmal von links nach rechts, vergleichst Nachbarn und tauschst, wenn links die größere liegt. Wie liegen die Karten danach?
Erklärung: 7 und 3: tauschen → 3 7 9 2. 7 und 9: bleiben. 9 und 2: tauschen → 3 7 2 9. Ein Durchgang sortiert noch nicht alles; „3 7 9 2“ hat den letzten Vergleich vergessen.
Karten 8, 1, 6, 3, 5. Du vergleichst jedes Nachbarpaar einmal von links nach rechts. Wie viele Vergleiche sind das? ___
Erklärung: Bei 5 Karten gibt es 4 Nachbarpaare: 8-1, 1-6, 6-3, 3-5. Also 4 Vergleiche, nicht 5.
8 Karten liegen offen durcheinander. Du nimmst die erste und vergleichst sie mit jeder weiteren; die kleinere behältst du. Wie viele Vergleiche brauchst du? ___
Erklärung: Die erste Karte wird nicht verglichen, jede der 7 anderen genau einmal. So findest du die kleinste mit 7 Vergleichen.