par fatal_error » 23 Nov 2009, 22:38
salut,
en fait, ici min max est un peu particulier, parce que ya que deux valeurs, 0 et 1 (perdant et gagnant).
On peut aussi regarder du coté des noyaux avec grundy (cqui donne au final la même approche, mais la pensée est pas pareil).
Bon la base, c'est : t'es dans le noyau, cad tu gagne.
Au lieu de commencer par le bas, on va commencer par le haut!
Donc tu pars de 10 (un ptit nombre certes).
10 tu n'as que 9 comme successeur.
Plus précisément, le successeur est (9,1), c'est important de garder le 1 pour savoir combien de successeur peut avoir 9.
(9,1) a pour successeur (8,1) et (7,2).
Rq on distingue donc le noeud (9,1) du noeud (9,2)
Pour tous les noeuds, tu creees leurs successeurs.
Tu arrives dans des noeuds (a,b), qui sont gagnants, si 2b>=a.
ex :
(2,1) : on peut enlever 2 alumettes (pas plus mais tout pil!) et on a tout pris.
ex2 :
(3,2) : on peut enlever (3 (4 mais yen a plus)) donc on a tout pris.
La fonction de Grundy, elle consiste à marquer tous les noeuds terminaux (tu gagnes) par zero.
Ensuite, pour un noeud donné, tu le marques par le plus petit entier naturel non marqué par les successeurs.
Ex :
(4,1) a pous successeurs (3,1,1),(2,2,0),(1,3,0) (j'ai pas testé supposes que ce soient ces successeurs)
bon, ben tu as min(N - {0,1}) = 2, et tu marques donc (2,1)-->(2,1,2)
Tu construits tous les noeuds marqués.
Au final, tu nas plus qua te démerder pour tomber dans le kernel. Pour ca, faut que tu cherches parmi les successeurs du noeud, un noeud marqué 1. c'est un noeud perdant cad l'autre pourra jamais aller dans le kernel s'il est dans un noeud 1.
on a donc la construction des noeuds de haut en bas.
Le marquage des noeuds de bas en haut.
la vie est une fête
