Binäre Suche - Aufgaben

In Vertretungsstunden spielen kleinere Klassen gerne HiLo. Die Klasse wird in zwei Gruppen aufgeteilt. Abwechselnd stellt jede Gruppe eine Spielleiterin oder einen Spielleiter, die/ der sich eine Zahl aus einem Zahlbereich (z.B. 1 bis 1000) ausdenkt. Die Mitglieder der anderen Gruppe raten die Zahl, die Spielleitung kommentiert jeden Rateversuch:

• Die genannte Zahl ist richtig
• Die genannte Zahl ist zu groß
• Die genannte Zahl ist zu klein

1. Die ratende Gruppe geht strategisch gut vor. Bestimmen Sie die maximale Anzahl der Rateversuche, die die Gruppe benötigt, um eine beliebige Zahl zu erraten.

   Es sind Rateversuche erforderlich.

   prüfen löschen lösen
    

2. Beschreiben Sie eine gute Spielstrategie.

3. Der Zahlbereich wird geändert (1 bis 2000). Die gute Spielstrategie soll auch hier benutzt werden. Bestimmen Sie die maximale Anzahl der Rateversuche, die jetzt notwendig sind.
   Es sind Rateversuche erforderlich.

   prüfen löschen lösen

Aufgabe 2

In Aufgabe 1 ist das HiLo-Spiel beschrieben und es ist eine gute Strategie entwickelt worden. (Spielvariante 1) Spielvariante 2: Bei einer alternativen Spielvariante antwortet die Spielleitung wie folgt. Die genannte Zahl ist richtig Die genannte Zahl ist falsch Es soll eine Zahl zwischen 1 und 15 erraten werden. Bestimmen Sie die Anzahl der Rateversuche für beide Spielvarianten, die notwendig sind, um die gesuchte Zahl sicher zu bestimmen. Bei Spielvariante 1 sind Rateversuche erforderlich. prüfen löschen lösen Bei Spielvariante 2 sind Rateversuche erforderlich. prüfen löschen lösen Das Spiel wird in Spielvariante 1 gespielt. Ein Mitschüler behauptet: „Man muss nicht unbedingt die Mitte aus dem infrage kommenden Zahlbereich bestimmen, ein beliebiger zufälliger Wert aus dem Zahlbereich liefert das gleiche Ergebnis bei der Anzahl der Rateversuche.“ Nehmen Sie Stellung zu dieser Aussage.

Die Lebensdaten von bekannten Informatikerinnen und Informatikern liegen in einem ARRAY vor. Es soll eine Person mit einem bestimmten Geburtsjahr gesucht werden. Dabei sollen zwei Suchstrategien (lineare Suche, binäre Suche) angewandt werden und die Anzahl der Suchschritte miteinander vergleichen werden. Es gibt eine Testumgebung, in der die Suchstrategien ausprobiert werden können. Hier ist die Downloadmöglichkeit der Testumgebung. 

Hinweis zur Testumgebung

1. Implementieren Sie die Methode lineareSuche der Klasse IfVerwaltung. 
   Hinweis zur Implementation
   Der Bezeichner des Arrays ist ifFeld. Bitte den Zähler für die Suchschritte nicht vergessen (Bezeichner lSuchAnz).
    
2. Implementieren Sie die Methode binaereSuche der Klasse IfVerwaltung. 
   Hinweis zur Implementation
   Der Bezeichner des Arrays ist ifFeld. Bitte den Zähler für die Suchschritte nicht vergessen (Bezeichner bSuchAnz).
3. Wenn man beide Methoden mit gleichen Suchschlüsseln auf die gleiche ARRAY-Belegung anwendet, so kann es zu unterschiedlichen Suchergebnissen kommen.

Erläutern Sie, wie es zu den unterschiedlichen Suchergebnissen kommen kann.