[shkola] Re: Malko teoriq na igrite (long)

> Ta za tova stavashe duma. Znaeh che vyprosa e v kodirane i zatova
> pochnah da si izlagam ideite. 
Wsxshtnost wxprosxt mozhe i da ne e w kodiraneto. No predi towa. 
Neka ti dam edna mnogo podobna igra. Imash n redici i wxw wsqka nqkakxw 
broj klechki. Ot proizwolna redica mozhe da wsimash proizwolen broj ot 
1 do K klechki(K e fiksirano za cqlata igra, dazhe ima i modifikaciq, 
kogato nqmash ogranichenie, kolko da wzimash), kato razlikata e che tuk 
ne delish redicata na dwe t.e. mozhesh da wzimash klechki samo ot kraq.
Pecheli, tozi, kojto wzeme poslednata(ite) klechka(i).

Towa e edna mnogo populqrna igra. Naricha se NIM. I sega ti dawam 
zadachata za n = 200, broj na klechkite do 10^6 i k = 10^4. Napishi 
programa, koqto da igrae optimalno! Az moga da napisha takawa tochno na 
15 reda s iziskwaniq za wreme i pamet: O(n). 
Ideqta tuk e, che wsqka situaciq mozhe da bxde opredelena za wreme O(n) 
dali e pecheliwsha. I oshte za wreme O(n) moga da namerq takxw hod, 
kojto postawq loshiq w gubeshta situaciq. O(n) + O(n) = O(n). 

Ostawqm te sam da pomislish kak se prawi tazi igra. Ako ne uspeesh, 
potxrsi w Net-a, no imaj predwid che trqbwa da nauchish strategiite za 
popeda pri populqrnite i prosti igri, kakwato e NIM. Ako se zatrudnish 
- pitaj, shte ti obqsnq!

Pozdrawi,       
        Ivo

-- 
Ivaylo Riskov <ivaylo_riskov@xxxxxxx>

Other related posts: