Vissza
Labor
2, haladóknak
Zsetonrakás
Adott egy n zsetonból
álló rakás, melyben kétféle
színű zsetont használtunk. Két
játékos felváltva levesz a rakás
tetejéről legalább egy, egyszínű zsetont. Az nyer,
akinek az utolsó zseton marad. Bizonyos rakások
esetében a kezdőnek mindig nyerő stratégiája van.
Írjunk programot, mely megvizsgálja az adott
rakást és jelzi, ha a kezdőnek nyerő
stratégiája van. Ebben az esetben szimuláljuk a
játékot, ahol a kezdő legyen a
számítógép.
Használjunk különböző színeket a
kiírásokhoz, illetve a következő
implementációs lehetőségek mindegyikét
írjuk meg:
a. a zseton
értékeket szövegállományból
olvassuk ki
b. a zseton
értékeket
véletlenszerűen generáljuk
c. a zseton
értékeknek dinamikusan
foglaljunk helyet
Feltételezzük,
hogy a zsetonrakás színezése az a
tömbben található, melynek elemszáma n. A nyerő stratégia
megállapítását a
legalsó zseton (a 0-ás pozíciójú)
vizsgálatával kezdjük és egyesével
haladunk
felfele. Felépítünk egy egydimenziós
tömböt, legyen ez c, mely elemszáma
megegyezik a rakásban levő zsetonok számával. A c
tömbben az i pozíción levő
érték az i-ik
zseton elhúzásakor meglévő stratégia
típusát jelzi, 1-est, ha nyerő, 0-ást, ha
vesztes.
- A
c[0] = 0, mivel a
legalsó zseton elhúzása a nyertesé.
- A
c[n-1] pozíción
levő érték pedig azt jelezi, hogy a kezdő
játékosnak milyen a stratégiája.
A c[n-1] értéket
kell
tehát meghatározni, az előző értékek
alapján:
- Ha
az i-1 és az i pozíciójú
zsetonok színei megegyeznek akkor, a soron következő
játékosnak nyertes
stratégiája van, azaz c[i]
= 1.
- Ha
az i-1 és az i pozíciójú
zsetonok színei különböznek, akkor a soron
következő játékos el kell vegye a i-ik
pozíciójú zsetont, tehát
stratégiája győztes ha c[i-1] = 0 volt (azaz az
ellenfele stratégiája vesztes volt), és vesztes,
ha c[i-1] = 1 (azaz az ellenfele
stratégiája nyertes volt).
pl.
Zs Zs Zs Zs Zs Zs Zs Zs Zs Zs - nyerő
stratégiája van a kezdőnek (a jobb oldal a rakás
tetje )
pl.
Zs Zs Zs Zs Zs Zs Zs Zz Zs Zs - nincs nyerő
stratégiája a kezdőnek