dot net pro contest 04/2015

Klingt einfach ... hat aber Tiefgang!

Montag 23 März 2015 at 07:54 am. Stichwörter: , , ,

Am letzten Wochenende habe ich mich an den nächsten Programmier Wettbewerb der dot net pro gesetzt. Die Aufgabe klingt erstmal sehr einfach.
Die zu erstellende Routine soll eine unbekannte Zahl aus dem Bereich des Datentyps Decimal erraten. Dafür darf das Programm 10, 50 oder 100 mal beim "Gegner" nachfragen. Als Antwort gibt es nur ein "zu hoch" oder "zu niedrig" zurück. Das Programm, dass am wenigsten Versuche braucht, bzw. welches am Ende die geringsten Abweichungen liefert, hat gewonnen.

Das klingt doch einfach... oder?

Nachdem der erste Ansatz mit einer binären Suche schnell umgesetzt war, kamen mir Zweifel.
Die Zahl in der Beispiellösung wurde erst in Schritt 96 gefunden. Die Zahl Decimal.MaxValue wurde in den 100 Schritten gar nicht gefunden. Das musste doch noch besser gehen.

Ja, es geht wirklich besser. Meine Lösung werde ich jedoch erst nach der Auswertung veröffentlichen ;-)

[Nachtrag : der Quelltext der Lösung liegt bei github. Einfach diesem Link folgen.]

Hier aber ein paar meiner Ergebnisse:

Tests und Ergebnisse bei 100 Schritten
gesuchte Zahl Anzahl der Schritte Differenz
Decimal.MinValue 6  ---
Decimal.MinValue +1 97  ---
-1.99112m 100 (Abbruch) 0,0000000000000000000000000003
-1.0m 70  ---
-0.918237128344444444m 86  ---
0.0m 1  ---
1.0m 70  ---
Decimal.MaxValue 6  ---
0.918237128344444444m 86  ---
4409328459932839.29184729m 100  ---

Gelb markiert ist der Wert, der im Demo Host verwendet wurde. Die anderen Werte wurden zusätzlich als Test hinzugefügt. Die Differenz "---" bedeutet die Zahl wurde exakt gefunden.

Nachtrag:
Bevor Ihr nachfragt... Die Werte Decimal.MaxValue und Decimal.MinValue werden gesondert geprüft. Dadurch werden Sie so schnell gefunden. Ich glaube jedoch nicht, dass diese Werte bei der Auswertung verwendet werden. Ich habe Sie nur als Test für die Extremwerte drin.

In den Postings auf der dotnetpro Seite (http://www.dotnetpro.de/newsgroups/ThreadList.aspx?groupId=15) wurde angemerkt, dass die einfache binäre Suche die schnellste Lösung sei. Dem Widerspreche ich ausdrücklich. Ich verwende einen rein algorithmischen Ansatz, der natürlich auch auf der binären Suche basiert. Er nähert sich jedoch deutlich schneller dem gesuchten Wert an. Mehr Infos dazu gibt es aber erst wenn der Wettbewerb abgeschlossen ist.

Nachträgliche Anmerkung (24.3.2015):Die binäre Suche ist natürlich die schnellste Lösung, wenn man von gleichverteilten Zahlen ausgeht. Ich gehe in diesem Fall davon aus, dass es sich nicht um eine gleichverteilte Zahlenmenge handelt. Und deswegen gibt es eine, sich schneller annähernde, Lösung.

Aufgrund von Nachfragen hier meine Ergebnisse bei 50 Schritten:

Tests und Ergebnisse bei 50 Schritten
gesuchte Zahl Anzahl der Schritte Differenz
Decimal.MinValue 6  ---
Decimal.MinValue +1 50 (Abbruch) 140737488355326
-1.99112m 50 (Abbruch)  0,000000000001267597353943040
-1.0m 50 (Abbruch)  0,000000000000070107153825792
-0.918237128344444444m 50 (Abbruch)  0,000000000000013777107556352
0.0m 1  ---
1.0m 50 (Abbruch) 0,000000000000070107153825792
Decimal.MaxValue 6  ---
0.918237128344444444m 50 (Abbruch) 0,000000000000013777107556352
4409328459932839.29184729m 50 (Abbruch) 1,1125879840887

Viel Spaß beim mitmachen...

Christof Konstantinopoulos

24 Kommentare

Einer oder mehrere Kommentare sind noch nicht freigeschaltet.



(optionales Feld)
(optionales Feld)

Auf dieser Seite werden die Kommentare moderiert.
Das bedeutet, dass die Kommentare erst dann veröffentlicht werden, wenn sie freigeschaltet wurden.

Persönliche Informationen speichern?
Hinweis: Alle HTML-Tags außer <b> und <i> werden aus Deinem Kommentar entfernt. URLs oder Mailadressen werden automatisch umgewandelt.