Suchen und Sortieren — Verfahren, die vergleichen

Searching and Sorting — Procedures That Compare

Informatik Klasse 4 13 Aufgaben
InformatikInformatisches DenkenAlgorithmen

Die Kinder vergleichen Verfahren, die zum selben Ergebnis führen: Zahlenraten von 1 bis 100 mit „größer/kleiner“ (Halbieren braucht höchstens 7 Tipps, Hochzählen bis zu 100), Suchen in sortierten und unsortierten Karten, Sortieren durch Vergleichen von Nachbarn — und sie zählen die Vergleiche. Aufgabenformen nach den Bebras-Aufgaben (Dagienė) und CS Unplugged. Gegen die Fehlvorstellungen, alle richtigen Verfahren seien gleich schnell, man müsse immer jede Karte ansehen, und Halbieren gehe auch bei unsortierten Karten. Trägt die Effizienz von Algorithmen in Klasse 11.

Leicht
Multiple Choice #1 15s â–¶ Testen

Zahlenraten von 1 bis 100, du hörst nur „größer“ oder „kleiner“. Welcher erste Tipp ist am besten?

  • â—‹ 1
  • â—‹ 10
  • â—Ź 50
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.
LĂĽckentext #2 15s â–¶ Testen

Zahlenraten von 1 bis 100. Ben zählt hoch: 1, 2, 3 … Die geheime Zahl ist 100. Wie viele Tipps braucht Ben? ___

âś“ Antwort: 100
Beim Hochzählen schließt jeder Tipp nur eine Zahl aus. Ben braucht 100 Tipps — Halbieren bräuchte höchstens 7.
Wahr / Falsch #3 18s â–¶ Testen

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.

âś“ Falsch
Beide finden die 64, aber Lea braucht 64 Tipps, Ben höchstens 7. Richtige Verfahren können sehr verschieden schnell sein.
Wahr / Falsch #4 12s â–¶ Testen

Im Wörterbuch suchst du „Zebra“. Du schlägst die Mitte auf, dort steht „Maus“. Jetzt blätterst du nach hinten.

âś“ Wahr
Z kommt im Alphabet nach M. Weil das Wörterbuch sortiert ist, kann „Zebra“ nur hinten stehen.
Mittel
Multiple Choice #1 18s â–¶ Testen

Zahlenraten von 1 bis 100. Dein Tipp 50, die Antwort: „kleiner“. Welcher Tipp ist jetzt am besten?

  • â—‹ 75
  • â—Ź 25
  • â—‹ 49
Ăśbrig sind 1 bis 49. Die Mitte davon ist 25. 49 schlieĂźt nur eine Zahl aus, 75 ist schon ausgeschlossen.
Multiple Choice #2 25s â–¶ Testen

Zahlenraten von 1 bis 16, du tippst immer die Mitte. Wie viele Tipps brauchst du höchstens?

  • â—Ź 5
  • â—‹ 16
  • â—‹ 8
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.
LĂĽckentext #3 25s â–¶ Testen

Zahlenraten von 1 bis 100, du tippst immer die Mitte. Wie viele Tipps brauchst du höchstens, bis du die Zahl triffst? ___

âś“ Antwort: 7
Nach jedem Tipp bleibt höchstens die Hälfte: 100 → 50 → 25 → 12 → 6 → 3 → 1. Spätestens der 7. Tipp trifft.
Wahr / Falsch #4 15s â–¶ Testen

Zahlenraten von 1 bis 100, du tippst immer die Mitte. Du brauchst jedes Mal genau 7 Tipps.

âś“ Falsch
7 ist das Höchste, nicht immer genau. Ist die Zahl 50, triffst du schon mit dem 1. Tipp.
Multiple Choice #5 18s â–¶ Testen

10 Karten liegen verdeckt und durcheinander. Wie viele musst du höchstens umdrehen, bis du die 7 siehst?

  • â—‹ 4
  • â—Ź 10
  • â—‹ 5
Durcheinander verrät eine Karte nichts über die anderen. Im schlechtesten Fall liegt die 7 ganz zuletzt. Halbieren geht nur bei sortierten Karten.
Multiple Choice #6 18s â–¶ Testen

10 Karten liegen verdeckt und sortiert, die kleinste links. Du suchst die 7. Die mittlere Karte zeigt 12. Wo suchst du weiter?

  • â—‹ rechts von der 12
  • â—‹ ganz vorne bei der ersten Karte
  • â—Ź links von der 12
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.
Multiple Choice #7 25s â–¶ Testen

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?

  • â—Ź 3 7 2 9
  • â—‹ 2 3 7 9
  • â—‹ 3 7 9 2
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.
LĂĽckentext #8 20s â–¶ Testen

Karten 8, 1, 6, 3, 5. Du vergleichst jedes Nachbarpaar einmal von links nach rechts. Wie viele Vergleiche sind das? ___

âś“ Antwort: 4
Bei 5 Karten gibt es 4 Nachbarpaare: 8-1, 1-6, 6-3, 3-5. Also 4 Vergleiche, nicht 5.
LĂĽckentext #9 20s â–¶ Testen

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? ___

âś“ Antwort: 7
Die erste Karte wird nicht verglichen, jede der 7 anderen genau einmal. So findest du die kleinste mit 7 Vergleichen.