Uproszczona wersja gry Nim

[SciTuber]

Cześć, chciałbym abyście mnie nakierunkowali na rozwiązanie uproszczonej wersji gry Nim.

Mamy do dyspozycji tylko jeden stos patyczków. Gra polega na wyciąganiu 1, 2 lub 3 patyczków w danym ruchu gracza. Wygrywa ten gracz, który wyciągnie ostatni patyczek.

Z wiki znalazłem takie rozwiązanie: "Wystarczy w pierwszym ruchu zmniejszyć wartość wszystkich stosów (początkowo ai) do (ai modulo k+1)." gdzie k to maksymalna możliwa liczba patyczków do wyciągnięcia w jednym ruchu.

Acz nie do końca rozumiem koncepcji tej wskazówki. Gdy mamy 13 patyczków stos należy zmniejszyć do 1. Ale jak w pierwszym ruchu?

Proszę o jakaś wskazówkę, rade. Rozwiązanie będę implementowal w języku programowania.
Pozdrawiam

[Tulio]

Możesz pokazać link do tego wiki? Coś raczej pomyliłeś. Prawdopodobnie chodziło o to by sprawić by kamyczków/patyczków było tyle by reszta z dzielenia dawała \(\displaystyle{ 1}\) lub coś w ten deseń.

Mamy \(\displaystyle{ 5}\) patyczków więc zabierasz jeden i zostaje \(\displaystyle{ 4}\) patyczki \(\displaystyle{ \left( 4 \mod 3 = 1\right)}\). Teraz bez względu na ruch drugiego gracza - wygrywasz.

[SciTuber]

Możesz pokazać link do tego wiki? Coś raczej pomyliłeś. Prawdopodobnie chodziło o to by sprawić by kamyczków/patyczków było tyle by reszta z dzielenia dawała \(\displaystyle{ 1}\) lub coś w ten deseń.

Mamy \(\displaystyle{ 5}\) patyczków więc zabierasz jeden i zostaje \(\displaystyle{ 4}\) patyczki \(\displaystyle{ \left( 4 \mod 3 = 1\right)}\). Teraz bez względu na ruch drugiego gracza - wygrywasz.

Pewnie,

Kod: Zaznacz cały

https://pl.m.wikipedia.org/wiki/Nim

, zakładka "gra z limitem elementów"

[Tulio]

To nie Ty pomyliłeś, tylko na wiki jest błąd. W angielskiej wersji jest lepiej i bliżej tego co ja pisałem:

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Nim

Zakładka (Variations) i pierwsza z nich. Zabrakło na polskiej znaczka \(\displaystyle{ \equiv}\)

[SciTuber]

Czyli reasumujac po analizie. Idealna strategia to zabieranie n mod (k+1) patyczkow gdzie n to aktualna ich liczba na stosie. Jeżeli wynik n mod (k+1) = 0 to zabieramy k.
Przy idealnej strategii obu graczy możemy określić, kto odniesie zwycięstwo korzystając właśnie z kongurencji modulo n ≡ 0 (mod k + 1) (in normal play). Jeżeli zasada przystawania modulo nie jest spełniona to wygrywa ten kto pierwszy wykona ruch.

Dobrze rozumiem?

[Tulio]

Chyba tak, ale używaj LaTeXa bo trudno się czyta i nie mam pewności. Sprawdź swoją teorię dla kilku przypadków.