Arbeitsblatt: Weitere Aktivitäten

Laden Sie hier das Arbeitsblatt im PDF-Format herunter.

1. Lasse die SchülerInnen unter Verwendung der drei Vorlagen ihre eigenen Spiele erstellen. Für das zweite Spiel müssen sie die Zahlen in steigender Ordnung eintragen. Frage sie, wie sie das Hashing-Spiel sehr schwer machen können. (Das Spiel ist am schwersten, wenn alle Schiffe in derselben Spalte sind.) Wie kann man es aber so einfach wie möglich machen? (Man sollte versuchen, in jeder Spalte gleich viele Schiffe einzutragen.)

2. Was würde passieren, wenn das gesuchte Schiff gar nicht vorhanden ist? (In der linearen Suche müssen dafür 26 Schüsse abgegeben werden. In der binären Suche sind zum Beweis fünf Schüsse nötig. Wird Hashing benutzt hängt es davon ab, wie viele Schiffe in der relevanten Spalte sind.)

3. Wie viele Schüsse wären, wenn die binäre Suche verwendet wird, für Hundert Standorte (ungefähr sechs), für Tausend Standorte (ungefähr neun) oder eine Million Standorte (ungefähr neunzehn) notwendig? (Bemerke, dass die Anzahl der Schüsse gegenüber der Anzahl der Schiffe nur langsam zunimmt. Nur ein weiterer Schuss ist jedes Mal notwendig, wenn sich die Anzahl verdoppelt. Es ist also proportional zum Logarithmus der Anzahl der Schiffe.)

Laden Sie hier das Arbeitsblatt im PDF-Format herunter.