Tarkastellaan kahden pelaajan peliä suunnatussa syklittömässä verkossa. Alussa pelinappula on tietyssä solmussa, ja pelaajat siirtävät vuorotellen nappulan johonkin solmuun, johon pääsee suoraan kaarella nykyisestä solmusta. Peli jatkuu, kunnes pelaaja ei voi tehdä mitään siirtoa, jolloin hän häviää pelin ja toinen pelaaja voittaa.
Tehtäväsi on toteuttaa luokka, jonka avulla voi lisätä kaaria verkkoon ja selvittää, onko aloittavan pelaajan mahdollista voittaa peli, jos aloitussolmu on ja molemmat pelaajat pelaavat optimaalisesti.
Voit olettaa, että solmuja on enintään ja luokan metodeita kutsutaan enintään kertaa.
Toteuta tiedostoon graphgame.py
luokka GraphGame
, jossa on seuraavat metodit:
- konstruktori, jolle annetaan solmujen määrä
add_link
lisää kaaren solmusta solmuunwinning
kertoo, voittaako aloittaja pelin solmusta
class GraphGame: def __init__(self,n): # TODO def add_link(self,a,b): # TODO def winning(self,x): # TODO if __name__ == "__main__": g = GraphGame(6) g.add_link(3,4) g.add_link(1,4) g.add_link(4,5) print(g.winning(3)) # False print(g.winning(1)) # False g.add_link(3,1) g.add_link(4,6) g.add_link(6,5) print(g.winning(3)) # True print(g.winning(1)) # False print(g.winning(2)) # False