Matematické Fórum

hessyk · 09. 05. 2011 23:54

ahoj,
mam tu jeden priklad s kterym si nevim rady...mate nekdo napad na algoritmus?dekuji moc za odpoved

Nim je hra, ve které hráči střídavě odebírají zápalky z hromádek. V každém tahu musí hráč odebrat z jedné hromádky libovolný kladný počet zápalek. Na koho žádné zápalky nezbydou, ten prohrál.

Vaším úkolem je zjistit, které pozice jsou prohrané (tj. pokud bude protivník hrát dobře, určitě prohrajete), které vyhrané (tj. pokud budete vy hrát dobře, určitě vyhrajete) a rozhodnout, jak ve vyhraných táhnout.

Na prvním řádku vstupu dostanete číslo N ≤ 1000, které znamená počet hromádek. Na druhém řádku následuje N nezáporných celých čísel ≤ 10000 znamenajících počet zápalek na jednotlivých hromádkách.

V případě, že je zadaná pozice prohraná, vytiskněte
:(

Pokud je vyhraná, vytiskněte na další řádky všechny možné dvojice (číslo hromádky, počet zápalek), kolik musíte odebrat, abyste vyhráli, ve vzestupném pořadí podle čísla hromádky.

Příklad 1
vstup
4
1 3 0 2
výstup
:(

Příklad 2
vstup
5
2 3 4 5 6
výstup
3 2
4 2
5 6

OiBobik

↑ hessyk:
¨
Mimochodem, před týdnem i dnes mi cvičící ukazoval velké tájo - způsob, jak o těchto věcech v této hře rozhodnout bez programu jen tak od pohledu : )) Akorát mi není jasné, proč ten jeho způsob funguje : D

Jinak toto vypadá, že povede na nějaké procházení stromu hry (koukni na Minimax) až k listům - výhře nebo prohře hráče. Vzhledem k tomu, že vždy hráč vyhraje nebo prohraje, a vzhledem k tomu, že můžeme předpokládat strategii obou hráču nejlepší možnou, stačí si tento strom ohodnotit booleanem - vyhraná pozice/prohrané pozice.

musixx · 12. 05. 2011 07:43

Já znám variantu nim, kde se odebírá z jedné hromádky 1 až m zápalek. Pak jde jen o to, aby po mém tahu zůstalo buď 0 nebo 1 (modulo m+1) zápalek na hromádce, podle toho, jaká je podmínka prohry.

Tady to bude dost možná podobné, ale nechápu ten příklad výstupu. To si jako před započetím hry můžu všechny hromádky upravit? Nebo je to posloupnost mých tahů? Ani jedno se mi teda nějak nezdá. Chápu to správně tak, že v každém tahu si vyberu jednu hromádku a z ní odeberu kolik chci?

OiBobik · 12. 05. 2011 08:04

↑ musixx:

Já si myslím, že to jsou všechny možné počáteční tahy nějaké výherní strategie (a proto bych řekl, že to bude úloha na procházení stromy hry).

musixx · 12. 05. 2011 08:10

↑ OiBobik: OK. Pak tedy...

OiBobik

↑ musixx:

Já to právě znám. Ale to ti dá snad jenom jednu výherní strategii (ač by jich mohlo být více).

Edit: ne, blbost, ono to určitě půjde upravit tak, aby jich to dalo více.

musixx · 12. 05. 2011 08:32 — Editoval musixx (12. 05. 2011 08:33)

↑ OiBobik: No, prezentovaná výherní strategie je nulovat tzv. nim-součet. Jak to udělat v počáteční pozici (pokud to vůbec jde a pokud jsem první na tahu, což se předpokládá), to jde dost možná více způsoby a není těžké všechny najít (tam se právě projeví to, je-li omezen počet odebíraných zápalek a jak). Ovšem je-li nulování nim-součtu jediná výherní strategie, resp. je-li každá jiná strategie jejím ekvivalentem, to bude těžší otázka. Možná na ni odpovídá zmíněný text

C. L. Bouton: Nim, a game with a complete mathematical theory, Annals of Mathematics 3 (1901–02), 35–39.

resp. jiné zdroje třeba odtud.

Matematické Fórum

#1 09. 05. 2011 23:54

nim

#2 11. 05. 2011 20:27 — Editoval OiBobik (11. 05. 2011 20:43)

Re: nim

#3 12. 05. 2011 07:43

Re: nim

#4 12. 05. 2011 08:04

Re: nim

#5 12. 05. 2011 08:10

Re: nim

#6 12. 05. 2011 08:17 — Editoval OiBobik (12. 05. 2011 08:19)

Re: nim

#7 12. 05. 2011 08:32 — Editoval musixx (12. 05. 2011 08:33)

Re: nim

Zápatí