# Intelligentes Zahlenraten



## Fenixx (24. Mai 2009)

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


----------



## faetzminator (24. Mai 2009)

Das ist durchaus die effizienteste Lösung, welche es gibt.


----------



## Fenixx (24. Mai 2009)

Ok, danke.


----------



## dergrüne (25. Mai 2009)

Jap schneller gehts imho nicht, das ist die sogenannte "Binäre Suche", funktioniert auf geordneten Reihen und hat die Komplexität von log(n), sprich du kannst die Anzahl der Elemente in der Reihe stark vergrößern und der Aufwand steigt nur minimal.

Was schnelleres wird es, wie schon gesagt, kaum geben, höchstens spezialsuchen die auf nicht auf allgemeine Probleme anwendbar sind.


----------

