Igra sa novcicima (zadatak za posao)

bmaxa

Buduća legenda
Poruka
25.894
Igraju Pat i Matt igru novcica. Novcica ima do 1000.
Ulaz su ukupni brojevi novcica na osnovu kojih treba da se odredi da li Pat ili Matt pobedjuje.
Broj novcica koji se moze uzeti u jednom potezu je uvek kvadrat broja, pobednik je onaj
koji napravi zadnji potez tj broj novcica ostane 0.
Prvi uvek igra Patt.
Izlaz je niz pobednika tako da uvek igraju najbolje poteze.
 

cronnin

Poznat
Moderator
Poruka
9.943
Колико ја видим треба да пази на један од могућих 31 бројева који завршавају игру. Коме стигне сума од:

1 - добија јер је квадрат
2 - губи (може да узме само 1, што противнику оставља добитничку 1)
3 - добија (може да узме само 1, што противнику оставља губитничку 2)
4 - добија јер је квадрат
5 - губи (може да узме или 1 или 4, што суму противнику своди на добитничке 4 или 1)
6 - добија (може да узме или 1 или 4; што суму противнику своди на губитничке 5 или 2)
7 - губи (може да узме или 1 или 4; што суму противнику своди на добитничке 6 или 3)
8 - добија ( може да узме или 1 или 4; што суму противнику своди на 7 или 4, где у варијанти 7 противник губи)
9 - добија јер је квадрат
10 - губи ( може да узме 1-4-9; што суму противнику своди на добитничке 9-6-1)
11 - добија ( може да узме 1-4-9; што суму противнику своди на губитничке 10-7-2)
12 - губи( мора да узме 1-4-9; што суму противнику своди на добитничке 11-8-3)


И тако до хиљаду. Ако сад уме да направи петљу да му изгенерише ово...
 
Poslednja izmena:

bmaxa

Buduća legenda
Poruka
25.894
Колико ја видим треба да пази на један од могућих 31 бројева који завршавају игру. Коме стигне сума од:

1 - добија јер је квадрат
2 - губи (може да узме само 1, што противнику оставља добитничку 1)
3 - добија (може да узме само 1, што противнику оставља губитничку 2)
4 - добија јер је квадрат
5 - губи (може да узме или 1 или 4, што суму противнику своди на добитничке 4 или 1)
6 - добија (може да узме или 1 или 4; што суму противнику своди на губитничке 5 или 2)
7 - губи (може да узме или 1 или 4; што суму противнику своди на добитничке 6 или 3)
8 - добија ( може да узме или 1 или 4; што суму противнику своди на 7 или 4, где у варијанти 7 противник губи)
9 - добија јер је квадрат
10 - губи ( може да узме 1-4-9; што суму противнику своди на добитничке 9-6-1)
11 - добија ( може да узме 1-4-9; што суму противнику своди на губитничке 10-7-2)
12 - губи( мора да узме 1-4-9; што суму противнику своди на добитничке 11-8-3)


И тако до хиљаду. Ако сад уме да направи петљу да му изгенерише ово...
Mozda to sto je kvadrat koji se uzima povlaci neku matematicku pravilnost ili najjednostavnije napraviti stablo poteza pa backtracking, ne znam.
Deluje mi stablo kao resenje.
 

cronnin

Poznat
Moderator
Poruka
9.943
Ја бих то овако, само три колоне:

да ли добија ?​
тренутна сума​
треба да игра​
0​
0​
нема шта да игра изгубио је​
1​
1​
алгоритам => 1​
0​
2​
1​
1​
3​
1​
1​
4​
4​
0​
5​
1​
1​
6​
1​
0​
7​
1​

Алгоритам:

Од тренутне суме одузимај квадрате природних бројева све док није <0.
За разлику бројева коју добијеш (то је оно што ће противник добити као потез) провераваш прву колону.
  • ако је противнику тамо 1, проверавај даље са већим квадратима
  • ако је противнику тамо 0, играч добија; у текућем реду упиши 1 у прву колону, а тај број који треба да игра у трећу колону
  • ако си стигао до суме која је мања од нуле, значи да не постоји варијанта у којој сигурно добијаш, ираш опортунистички најмањи број 1 у нади да ће противник да се пређе у неком од потеза; у текућем реду упиши 0 у прву колону, а 1 у трећу колону
 

Top
  Blokirali ste reklame
Dragi prijatelju, nemojte da blokirate reklame - isključite Ad Blocker na Forumu, jer će tako mesto vaših susreta na Krstarici ostati besplatno za korišćenje.