"Rate eine Zahl zwischen 0 und N" - Spiel

Übersicht

Sonstiges

Smalltalk

	FWeinb ehemals "ich" Betreff: "Rate eine Zahl zwischen 0 und N" - Spiel	Mo, Dez 19, 2011 2:24 Antworten mit Zitat
Durch Zufall (erste "Klausur" in Java...) bin ich mal wieder in den Genuss gekommen ein solches Spiel zu Programmieren. Wie es Funktioniert sollte jedem klar sein. Der PC "denkt" sich eine Zahl aus und man muss diese Raten, den einzigen Hinweiß den man bekommt ist, ob die Zahl größer oder kleiner als die zuletzt eingegeben Zahl ist. Das ganze war natürlich sehr schnell gemacht. Hatte dann noch c.a. 90min Zeit und mich Interessierte es nun einen Algorithmus zu finden, der mit möglichst wenig Zügen zum Ziel kommt. Kein Problem, eine Idee war sofort da: Frage zunächst nach N/2, wobei N die höchste zu wählende Zahl ist. Danach wird immer die ganze Hälfte von dem Niedrigsten Maximum und dem Höchsten Minimum je nachdem ob die Zahl größer oder kleiner ist Addiert oder Subtrahiert. Beispiel für N = 100, und die Gesuchte Zahl ist 49: Code: [AUSKLAPPEN] [EINKLAPPEN] g: größer k: kleiner t: treffer Versuchte Zahl \|Ereignis \| (max - min)/2 \| max - min 50 k 25 50 - 0 25 g 12 50 - 25 37 g 6 50 - 37 43 g 3 50 - 43 46 g 2 50 - 46 48 g 1 50 - 48 49 t Um nun den schlechtesten Fall, also den Fall wo die meisten Versuche benötigt werden, zu berechnen, hatte ich folgende Überlegung: Wie lange muss ich N durch 2 Teilen bis es kleiner als eins wird. Formel bedeutet das also: Gut, das lässt sich Recht einfach nach x umstellen: Code: [AUSKLAPPEN] [EINKLAPPEN] N * (1/2)^x < 1 \| / N (1/2)^x < 1/N \| log (dekadisch) x * log(1/2) > log(1/N) \| log (1/2) x > log(1/N) / log(1/2) Logarithmus Gesetzt: log (a/b) = log a - log b x > log(1) - log (N) / log (1) - log (2) x > - log (N) / - log (2) x > log(N) / log(2) Man braucht also log(N) / log(2) mal bis so oft die Hälfte von N gebildet wurde das sie kleiner als eins ist. Soweit so gut, jetzt gibt es aber genau zwei Fälle in denen man länger braucht. Nämlich bei N und bei 0 dort sind es (log(N) / log(2)) + 1 Versuche, das wird damit zutun haben, das nur ganze Zahlen betrachtet werden und die Hälfte einer ungeraden Zahl genau zwischen zwei ganzen Zahlen liegt. Wo ich jetzt aber draus hinaus will ist die statistische Verteilung. Das heißt auf die durchschnittliche Zahl der Versuche die benötigt werden um aus N Zahlen die Richtige zu wählen. Der Anfang ist noch ganz einfach, am Beispiel N = 100, Worst Case : w = (log(100)/log(2)) + 1 = 8 : Mit einem Zug kann immer nur ein Treffer erzielt werden, im Beispiel wäre es die 50. Mit zwei Zügen können schon zwei Treffer gemacht werden, im Beispiel die 25 und die 75. Mit drei Zügen können schon vier Treffer gemacht werden, im Beispiel die 13, 37 und die 63, 87. usw. Daraus folgt also: Anzahl der möglichen Treffer = 2^(z-1) Wobei z die Anzahl der Züge ist. Das ganze geht aber nur bis z = w - 2 gut. Der Wert für z = w ist für jedes N zwei, man erinnere sich an den Grund für das +1 bei der Berechnung des schlechtesten Falles. Aus diesen Überlegungen würde sich diese Formel ergeben: Meine Frage ist nun, ob man diese Formel noch etwas "Handlicher" bekommt, der Zusammenhang zwischen N und der maximalen Zugfolge w ist so schön zu beschreiben, das muss hier doch auch gehen. Ich hoffe ich konnte es einigermaßen Verständlich darstellen und hoffe mir kann jemand helfen. Mit freundlichen Grüßen Ich
"Wenn die Menschen nur über das sprächen, was sie begreifen, dann würde es sehr still auf der Welt sein." Albert Einstein (1879-1955) "If you live each day as if it was your last, someday you'll most certainly be right." Steve Jobs

FWeinb

ehemals "ich"

Betreff: "Rate eine Zahl zwischen 0 und N" - Spiel

Mo, Dez 19, 2011 2:24
Antworten mit Zitat

Durch Zufall (erste "Klausur" in Java...) bin ich mal wieder in den Genuss gekommen ein solches Spiel zu Programmieren. Wie es Funktioniert sollte jedem klar sein. Der PC "denkt" sich eine Zahl aus und man muss diese Raten, den einzigen Hinweiß den man bekommt ist, ob die Zahl größer oder kleiner als die zuletzt eingegeben Zahl ist. Das ganze war natürlich sehr schnell gemacht. Hatte dann noch c.a. 90min Zeit und mich Interessierte es nun einen Algorithmus zu finden, der mit möglichst wenig Zügen zum Ziel kommt.

Kein Problem, eine Idee war sofort da:

Frage zunächst nach N/2, wobei N die höchste zu wählende Zahl ist.
Danach wird immer die ganze Hälfte von dem Niedrigsten Maximum und dem Höchsten Minimum je nachdem ob die Zahl größer oder kleiner ist Addiert oder Subtrahiert.

Beispiel für N = 100, und die Gesuchte Zahl ist 49:
Code: [AUSKLAPPEN]

g: größer
k: kleiner
t: treffer
Versuchte Zahl |Ereignis | (max - min)/2 | max - min
50 k 25 50 - 0
25 g 12 50 - 25
37 g 6 50 - 37
43 g 3 50 - 43
46 g 2 50 - 46
48 g 1 50 - 48
49 t

Um nun den schlechtesten Fall, also den Fall wo die meisten Versuche benötigt werden, zu berechnen, hatte ich folgende Überlegung:
Wie lange muss ich N durch 2 Teilen bis es kleiner als eins wird. Formel bedeutet das also:
user posted image

Gut, das lässt sich Recht einfach nach x umstellen:

Code: [AUSKLAPPEN]

N * (1/2)^x < 1 | / N

(1/2)^x < 1/N | log (dekadisch)

x * log(1/2) > log(1/N) | log (1/2)

x > log(1/N) / log(1/2)

Logarithmus Gesetzt: log (a/b) = log a - log b

x > log(1) - log (N) / log (1) - log (2)

x > - log (N) / - log (2)

x > log(N) / log(2)

Man braucht also log(N) / log(2) mal bis so oft die Hälfte von N gebildet wurde das sie kleiner als eins ist. Soweit so gut, jetzt gibt es aber genau zwei Fälle in denen man länger braucht. Nämlich bei N und bei 0 dort sind es (log(N) / log(2)) + 1 Versuche, das wird damit zutun haben, das nur ganze Zahlen betrachtet werden und die Hälfte einer ungeraden Zahl genau zwischen zwei ganzen Zahlen liegt.

Wo ich jetzt aber draus hinaus will ist die statistische Verteilung. Das heißt auf die durchschnittliche Zahl der Versuche die benötigt werden um aus N Zahlen die Richtige zu wählen.

Der Anfang ist noch ganz einfach, am Beispiel N = 100, Worst Case : w = (log(100)/log(2)) + 1 = 8 :
Mit einem Zug kann immer nur ein Treffer erzielt werden, im Beispiel wäre es die 50.
Mit zwei Zügen können schon zwei Treffer gemacht werden, im Beispiel die 25 und die 75.
Mit drei Zügen können schon vier Treffer gemacht werden, im Beispiel die 13, 37 und die 63, 87.
usw.
Daraus folgt also:
Anzahl der möglichen Treffer = 2^(z-1)
Wobei z die Anzahl der Züge ist.

Das ganze geht aber nur bis z = w - 2 gut.
Der Wert für z = w ist für jedes N zwei, man erinnere sich an den Grund für das +1 bei der Berechnung des schlechtesten Falles.

Aus diesen Überlegungen würde sich diese Formel ergeben:
user posted image

Meine Frage ist nun, ob man diese Formel noch etwas "Handlicher" bekommt, der Zusammenhang zwischen N und der maximalen Zugfolge w ist so schön zu beschreiben, das muss hier doch auch gehen.

Ich hoffe ich konnte es einigermaßen Verständlich darstellen und hoffe mir kann jemand helfen.

Mit freundlichen Grüßen
Ich

"Wenn die Menschen nur über das sprächen, was sie begreifen, dann würde es sehr still auf der Welt sein." Albert Einstein (1879-1955)
"If you live each day as if it was your last, someday you'll most certainly be right." Steve Jobs

	ChaosCoder	Mo, Dez 19, 2011 7:53 Antworten mit Zitat
Konnte es in deinem Beitrag nicht finden, deswegen hier mal das Stichwort: Binäre-Suche Das ist das Verfahren, das du anwendest. Vielleicht hilft dir das weiter Und das was dich interessiert ist die Komplexität. BTW: Man sieht deine Formel nicht^^
Projekte: Geolaria \| aNemy Webseite: chaosspace.de

ChaosCoder

Mo, Dez 19, 2011 7:53
Antworten mit Zitat

Konnte es in deinem Beitrag nicht finden, deswegen hier mal das Stichwort:
Binäre-Suche

Das ist das Verfahren, das du anwendest. Vielleicht hilft dir das weiter Smile

Und das was dich interessiert ist die Komplexität.

BTW: Man sieht deine Formel nicht^^

Projekte: Geolaria | aNemy
Webseite: chaosspace.de