Hi zusammen,
angenommen man hat folgende Aufgabe zu lösen:
1.) Spieler A denkt sich eine Zahl in einem Intervall von 1 bis 1000 aus, die Spieler B zu erraten
versucht. Spieler A antwortet wahrheitsgemäß mit "kleiner", "größer" oder "gleich".
Gib eine möglichst gute Strategie für die Fragen von Spieler B an. Wie viele Fragen muss Spieler
B dabei maximal stellen, um die Zahl herauszufi nden?
2.) Gib eine Zahl von Spieler A an (und begründe deine Wahl), für die Spieler B die maximale Anzahl an Fragen stellen muss.
3.)Angenommen, Spieler B darf maximal fünf Fragen stellen; wie groß darf dann bei deiner Strategie
das Intervall der Zahlen höchstens sein, damit Spieler B gewinnt?
Mein Lösungsansätze:
Zu 1.) Verwendung von binärer Suche.
Man unterteilt das Intervall pro Frage in immer 2 gleichgroße Intervalle.
D.h. in diesem Fall im Worst-Case (beispielhaft für das untere Intervall von 1-500, 501-100 ist ebenfalls möglich):
Spieler B stellt folgende Fragen:
I. 500?
Antwort von A: kleiner
II. 250?
Antwort von A: kleiner
III. 125?
Antwort von A: kleiner
IV: 62?
Antwort von A: kleiner
V: 31?
Antwort von A: kleiner
VI: 15?
Antwort von A: kleiner
VII: 7?
Antwort von A: kleiner
VIII: 3?
Antwort von A: kleiner
VIV: 2?
Antwort von A: kleiner
X: 1?
Antwort von A: gleich
=> Nach maximal 10 Fragen ist die Zahl gefunden. Der Worst-Case beinhaltet damit die maximale Anzahl der Unterteilung der Intervalle. Wobei das eigentliche Maximalintervall auch 1024 sein könnte, da 2^10 = 1024.
Zu 2.) Anhand des oben genannten Beispiels ist ein Beispiel für eines Zahl des Worst-Cases 1.
Zu 3.) 2^5 = 32
=> Das Intervall darf maximal 32 Zahlen beinhalten.
Ist meine Lösung soweit korrekt, oder kennt jemand eine effizientere Lösung?
Gruß
Fenixx
angenommen man hat folgende Aufgabe zu lösen:
1.) Spieler A denkt sich eine Zahl in einem Intervall von 1 bis 1000 aus, die Spieler B zu erraten
versucht. Spieler A antwortet wahrheitsgemäß mit "kleiner", "größer" oder "gleich".
Gib eine möglichst gute Strategie für die Fragen von Spieler B an. Wie viele Fragen muss Spieler
B dabei maximal stellen, um die Zahl herauszufi nden?
2.) Gib eine Zahl von Spieler A an (und begründe deine Wahl), für die Spieler B die maximale Anzahl an Fragen stellen muss.
3.)Angenommen, Spieler B darf maximal fünf Fragen stellen; wie groß darf dann bei deiner Strategie
das Intervall der Zahlen höchstens sein, damit Spieler B gewinnt?
Mein Lösungsansätze:
Zu 1.) Verwendung von binärer Suche.
Man unterteilt das Intervall pro Frage in immer 2 gleichgroße Intervalle.
D.h. in diesem Fall im Worst-Case (beispielhaft für das untere Intervall von 1-500, 501-100 ist ebenfalls möglich):
Spieler B stellt folgende Fragen:
I. 500?
Antwort von A: kleiner
II. 250?
Antwort von A: kleiner
III. 125?
Antwort von A: kleiner
IV: 62?
Antwort von A: kleiner
V: 31?
Antwort von A: kleiner
VI: 15?
Antwort von A: kleiner
VII: 7?
Antwort von A: kleiner
VIII: 3?
Antwort von A: kleiner
VIV: 2?
Antwort von A: kleiner
X: 1?
Antwort von A: gleich
=> Nach maximal 10 Fragen ist die Zahl gefunden. Der Worst-Case beinhaltet damit die maximale Anzahl der Unterteilung der Intervalle. Wobei das eigentliche Maximalintervall auch 1024 sein könnte, da 2^10 = 1024.
Zu 2.) Anhand des oben genannten Beispiels ist ein Beispiel für eines Zahl des Worst-Cases 1.
Zu 3.) 2^5 = 32
=> Das Intervall darf maximal 32 Zahlen beinhalten.
Ist meine Lösung soweit korrekt, oder kennt jemand eine effizientere Lösung?
Gruß
Fenixx
