Une suite logique, pas si logique ?

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Doraki
Habitué(e)
Messages: 5008
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 23 Nov 2009, 18:57

Trém a écrit:L'objectif de l'appli est de donner un nombre d'allumette et en partant de ce nombre et en retirant un nombre n d'allumette compris entre 1 et 2m (m le nombre allumette choisi par le joueur précédent qui est donc une fois l'ordinateur, une fois la personne).

Le premier joueur retire 1 ou 2 allumette, le suivant 1 à ( m-1) et celui qui retire la dernière gagne

Si au coup précédent notre opposant a retiré m allumettes, on a le droit de retirer jusqu'à 2m allumettes ou jusqu'à (m-1) allumettes ?



Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 23 Nov 2009, 20:08

Sauf erreur de ma part, dans un jeu déterminé (comme ici) tu cherche les "situations gagnantes" (i.e. celles qui permettent de gagner à coup sûr)
Je pense (et fait je suis sur) que, dans ton jeu, la donnée seule du nombre d'allumettes restantes n'est pas sufisante pour conaitre la situation actuelles. Les situations "gagnantes" sont des COUPLES (n,m) où n est le nombre d'allumettes restante et m le dernier coup joué.

Exemple : si je te donne 3 alumettes alors
Si je viens d'en enlever une seule, tu as perdu.
Si je vient d'en enlever 2 ou plus, tu as gagné.

P.S. (pour doraki) le m-1 est forcément une faute de frappe sinon le jeu n'a aucun interêt...
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 23 Nov 2009, 21:44

La méthode (informatique ou manuelle) est de construire un tableau des couples (n,m). Dans chaque case il faut arriver à mettre un G(gagné) ou P(perdu)
Déjà il faut s'entendre sur ce que veut dire G et P. Ma convention est de dire G=je gagne si je donne cette situation à l'adversaire.

Une situation est alors Gagnante lorsque TOUTES celle qui en découlent (en respectant la régle du jeu) sont Perdante : je lui donne la situation et, QUOI QU'IL JOUE, il perd.
Une situation est Perdante si AU MOINS UNE de celles qui en découle est Gagnante : si je lui donne la situation (et qu'il est malin) il vas me renvoyer à la gueule une situation gagnante et il va... gagner.

Pour remplir le tableau, on part de la(les) situations finales : ici ce sont les situations (0,?) et elle sont Gagnantes (car si je lui donne 0 alumettes, c'est que... j'ai gagné).
Ensuite, on remplit les cases (1,?) du tableau, puis (2,?) etc...

Remarque :
Il me semble que j'ai déjà fait au moins une fois ce tableau et il est "assez mathématique" c'est à dire qu'en fait il y a une "formule assez simple" pour savoir si le couple (n,m) est gagnant. Pour le moment, contente toi de faire le programme.

Bon courage.

P.S. : Il me semble que les informaticiens parlent d'un algorithme de MINI-MAX (comprend tu pourquoi ?)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 23 Nov 2009, 22:29

Il n'est pas super utile de "remonter les coups" : cherche à remplir le tableau "bètement" (ou mieux, fait le faire par le programme) colonne par colonne :
Départ :
(0,m) = Gagnant pour tout m
Toi (ou l'ordi) teste :
(1,1) on peut passer à (0,1)=G donc (1,1)=P
(1,2) on peut passer à (0,1)=G donc (1,2)=P
si c'est toi qui rempli le tableau tu vois que (1,m)=P pour tout m, si c'est l'ordi. il fait tout les calculs et... trouve la même chose.
Pour les (2,m) tu trouve aussi =P pour tout m.
Pour (3,1) on a le droit de passer à (2,1)=P (en enlevant une alumette) ou à (1,2)=P en enlevant 2 alumettes donc (3,1)=G
Pour (3,2), on a le droit de passer à (2,1)=P, à (1,2)=P, à (0,3)=G donc (3,2)=P. De même (3,m)=P pour tout m>1 (mais (3,1)=G)
etc,etc,etc,

Avec cette méthode, tu te "rendra compte" que tu peut gagner lorsqu'il reste 357 alumettes et que tu as le droit d'en enlever 392 au moment ou tu remplira la colonne 357... (ou alors tu vois ca dés le début et tu peut remplir tout plein de case avec des P mais il reste les case difficile à 'intuiter' : j'enlève 1 alumette et il en reste 3275 tu gagne ou pas ?)

A mon avis, c'est ca que tu dois programmer : faire calculer le tableau à l'ordinateur AVANT même qu'il ne commence à jouer.

P.S. Le mot "minimax" vient du fait que, quand c'est à toi de jouer tu cherche a maximiser le "résultat" et, quand c'est à l'adversaire, il cherche à le minimiser.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6609
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 23 Nov 2009, 23: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 :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Nov 2009, 00:04

Casse tête (pour Fatal-Error) connait tu la "fonction mathématique" permetant de savoir si (n,m) est gagnant ?

(c'est super vicieux : il y a les nombres de fibbonacci qui rentre dans la démonstration...)

Si Trem se reconnecte, il faudrai quand même lui expliquer que le truc qu'on lu demande de faire c'est simplement un programme (sans doute qui qui calcule le tableau....)

(c'est pour ca que le casse tête, c'est que pour toi)

Indic : sont gagnant (en plus des (0,?) )
(3,1)
(5,1) (5,2)
(8,1) (8,2) (8,3)
(11,1)
(13,1) (13,2) ... (13,6)
(16,1)
(18,1) (18,2)
(21,1) (21,2) ... (21,10)
.
.
.
?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Nov 2009, 16:06

Une première remarque, il me semble que, partant de (5,3), on peut enlever de 1 à 6 alumettes (au max le double du coup précédent)

Mais, à part cela, c'est effectivement la bonne idée.

Normalement, si tu procède "collonne par colonne", au moment ou tu cherche à savoir si (5,3) est gagnant ou perdant, tu as déjà rempli les colonnes (0,?) (1,?) (2,?) (3,?) et (4,?) donc tu sait si les fameux coups
(4,2) (3,4)... sont ou pas gagnant.

(c'est d'ailleurs pour cela que j'insistait sur le fait qu'il vaut mieux remplir le tableau colonne par colonne)

P.S.
Il semblerait que toi et moi ne notons pas tout à fait de la même façon les "coups".
Pour moi, (n,m) veut dire "il en reste n et le dernier coup joué est m"
alors que pour toi, le m est le double du mien (c'est le max que l'on aura le droit de jouer).
Ma solution parrait plus "économique" car ton m est toujour pair !!!

Pour moi, TON (5,3) -> (4,2) ou (3,4) ou (2,6)
s'écrirait plutot (5,2) -> (4,1) ou (3,2) ou (2,3) ou (1,4)
(IL en a enlevé 2 => je peut en enlever de 1 à 4)
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6609
Enregistré le: 22 Nov 2007, 14:00

par fatal_error » 24 Nov 2009, 21:52

re,

juste pour dire qu'a mon avis je trouverai pas une formule explicite pour ta fonction. Manque d'envie pis aussi de talent lol.
Apres, c'est sur que c'est mieux que construire un graphe puis la fonction(méthode classique que je proprose), mais bon, (celle que jpropose) constitue une approche qu'on peut toujours appliquer.
la vie est une fête :)

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Nov 2009, 22:13

Salut fatal_error,
Je n'ai ABSOLUMENT PAS DIT que ta méthode était mauvaise !!!!
Je suis même persuadé que ce que le prof. d'info attend de Trém est un programme calculant la table. Le casse tête (trouver la formule), c'était juste si tu avais la curiosité et envie de le faire....

Désolé d'avoir pu te sembler désobligeant, c'était TOTALEMENT INVOLONTAIRE !!!!
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Doraki
Habitué(e)
Messages: 5008
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 24 Nov 2009, 22:15

Après expérimentation,
la stratégie gagnante est d'écrire le nombre d'allumettes en base fibonacci :
n = F(a1) + F(a2) + ... + F(ak) avec a(i+1) < ai-1 et de retirer F(ak) allumettes si on peut.
Si on peut pas, on a perdu.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 24 Nov 2009, 22:20

BINGO
(peut être à un point virgule prés sur combien il faut en enlever, j'ai plus le résultat en tête, mais c'est bien la "base fibonnacci" qui fait marcher le truc)

P.S. (pour Trem)
Je pense que ce n'est pas la réponse de doraki que ton prof. attend de toi mais, bien plus bêtement le fameux tableau avec des G et des P...

2em P.S. (pour doraki)
a) Il y a bien un point virgule d'écart : dans certains cas, il y a plusieurs possibilitées qui conduisent au gain.
b) A tu une PREUVE ?
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 20696
Enregistré le: 11 Nov 2009, 23:53

par Ben314 » 25 Nov 2009, 00:21

Bien le bonsoir,

Je pense que le "tableau" est presque plus simple à programmer que la méthode "fibonnacci", c'est trés trés mécanique... (par contre, la méthode "tableau" est plus gourmande en place mémoire, m'enfin, avec les ordi actuels, je pense que tu peut jouer avec disons largement 10000 alumettes)

Bon courage

P.S. si tu as des soucis avec la méthode "fibonacci", n'hésite pas.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

ffpower
Membre Complexe
Messages: 2542
Enregistré le: 13 Déc 2007, 06:25

par ffpower » 25 Nov 2009, 03:22

Amusant, ca change de la version classique 1,2,3 allumettes..

Doraki
Habitué(e)
Messages: 5008
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 25 Nov 2009, 10:01

Si tu galères avec un tableau trop gros,
Tu peux observer que si recevoir (n,m) te mets en situation gagnante, alors (n,m') avec m'>=m aussi vu que tu peux faire le même coup gagnant qu'avec (n,m).
Ainsi, pour tout n, il existe un plus petit m, m0, tel que recevoir (n,m) te permette de gagner à coup sûr, tandis que recevoir (n,m') avec m'C'est un peu plus rapide de calculer le tableau qui te donne ce m0 en fonction de n.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 63 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite