Wenn folgender Ausdruck eine gerade Zahl ergibt, gewinnt der erste
Spieler, sonst der zweite:
Für 2≤n≤9 gewinnt der erste Spieler, und für n=1 ist es eine Frage der
Definition, da das Spiel ja endet, bevor überhaupt jemand einen Zug
gemacht hat. Ich würde sagen, der zweite Spieler gewinnt in diesem Fall.
Man sollte allerdings die Logarithmen nicht mit FP-Funktionen berechnen,
da durch die Aufrundfunktion schon kleine Rundungsfehler zu falschen
Ergebnissen führen. Besser ist es, ganzzahlige Potenzen in einer Schlei-
fe hochzuzählen, bis das Argument erreicht oder überschritten ist, z.B.
so:
1 | int gewinner(unsigned int n) {
|
2 | unsigned long long n4 = 4ULL*n, n36=36ULL*n, p;
|
3 | int i, ret;
|
4 |
|
5 | if(n == 1)
|
6 | ret = 2;
|
7 | else if(n < 10)
|
8 | ret = 1;
|
9 | else {
|
10 | p = 1;
|
11 | while(p < n4)
|
12 | p *= 18;
|
13 | i = 0;
|
14 | while(p < n36) {
|
15 | p *= 2;
|
16 | i++;
|
17 | }
|
18 | ret = i&1 ? 2 : 1;
|
19 | }
|
20 | return ret;
|
21 | }
|
Die Spielstrategie:
Wenn es für die aktuelle Zahl k ein i gibt, so dass
dann multipliziere die Zahl mit 9, sonst mit 2. Vielleicht gibt es etwas
einfacheres, mir ist aber nichts eingefallen
D. I. schrieb:
> Ich hab das mal in ein kleines Ruby-Programm gegossen. Ich denke das
> sollte passen, was meint ihr?
Das scheint mit meinen Ergebnissen zusammenzupassen:
1 | von bis Gewinner
|
2 | ——————————————————————————————————
|
3 | 1 1 2
|
4 | 2 9 1
|
5 | 10 18 2
|
6 | 19 36 1
|
7 | 37 72 2
|
8 | 73 162 1
|
9 | 163 324 2
|
10 | 325 648 1
|
11 | 649 1296 2
|
12 | 1297 2916 1
|
13 | 2917 5832 2
|
14 | 5833 11664 1
|
15 | 11665 23328 2
|
16 | 23329 52488 1
|
17 | 52489 104976 2
|
18 | 104977 209952 1
|
19 | 209953 419904 2
|
20 | 419905 944784 1
|
21 | 944785 1889568 2
|
22 | 1889569 3779136 1
|
23 | 3779137 7558272 2
|
24 | 7558273 17006112 1
|
25 | 17006113 34012224 2
|
26 | 34012225 68024448 1
|
27 | 68024449 136048896 2
|
28 | 136048897 306110016 1
|
29 | 306110017 612220032 2
|
30 | 612220033 1224440064 1
|
31 | 1224440065 2448880128 2
|
32 | 2448880129 4294967295 1
|
33 | ——————————————————————————————————
|
Das Ganze geht auch mit dynamischer Programmierung, wie du es ursprüng-
lich vorgehabt hast. Du macht eine Tabelle mit allen möglichen Zahlen-
werten
1 | | 9⁰ 9¹ 9² 9³ ...
|
2 | ———————————————————————————
|
3 | 2⁰ | 1 9 81 729 ...
|
4 | |
|
5 | 2¹ | 2 18 162 1458 ...
|
6 | |
|
7 | 2² | 4 36 324 2916 ...
|
8 | |
|
9 | 2³ | 8 72 648 5832 ...
|
10 | : | : : : :
|
und markierst alle Zahlen, die größer oder gleich n sind, als "Gewinn-
zahlen". Danach werden die restlichen Zahlen von rechts nach links und
von unten nach oben ebenfalls als Gewinn- oder Verlustzahlen markiert:
Eine Zahl ist genau dann eine Gewinnzahl, wenn der rechte und der untere
Nachbar beide Verlustzahlen sind.
Als letztes wird die 1 markiert. Ist sie eine Gewinnzahl, gewinnt der
zweite Spieler, sonst der erste.
Letztendlich ist das genau das gleiche wie dein rekursiver Algorithmus,
nur von hinten aufgezäumt und eben nicht rekursiv.
