Exercice langage C: Jeu des allumettes

On décrit le jeu des allumettes : au départ, il y a un tas de 50 allumettes, (ou tout autre objet : cailloux, jetons, . . .).

Chacun à son tour, les deux joueurs ôtent obligatoirement entre 1 et 6 allumettes. Celui qui ôte la dernière allumette gagne.

Travail à Faire :

1. Préférez-vous commencer ou jouer en deuxième ? Justifiez votre choix par une stratégie gagnante. Conseil : commencer par raisonner avec un petit nombre d’allumettes, puis généraliser.

2. Ecrire un programme qui joue au jeu des allumettes contre l’utilisateur.

1) On peut démontrer qu’une position est gagnante pour celui qui a la main si et seulement si le nombre d’allumettes n’est pas divisible par 7.

Preuve : supposons que cela soit faux, et considérons le plus entier n qui contredirait ce qu’on veut montrer. Si 1 ? n ? 7, c’est évident. Supposons n ? 8.

Si n est divisible par 7 tandis que la position est gagnante, il y a une contradiction, car tout coup jouable mène à un entier non divisible par 7 qui par hypothèse de récurrence est une position gagnante. C’est bien une contradiction : d’une position gagnante il doit y avoir au moins un coup donnant `a mon adversaire une position perdante.

Si n n’est pas divisible par 7 tandis que la position est perdante, il y a une contradictions, car enlever n mod 7 allumette mène à un entier divisible par 7 qui par hypothèse de récurrence est une position perdante. C’est bien une contradiction : d’une position perdante, tout coup doit donner `a mon adversaire une position gagnante.

2)

#include
#define ORDI 0
#define HUMAIN 1
main(){
int coup, pos, joueur;
printf("Combien d’allumettes : ");
scanf("%i", &pos);
printf("Qui commence (%i pour l’ordi, %i pour vous) : ", ORDI, HUMAIN);
scanf("%i", &joueur);
while(pos!=0){
if (joueur == ORDI){
coup = pos%7;
if (coup == 0) coup = 1;
printf("Il y a %i allumettes, j’en enleve %i.\n", pos, coup);
}
else{
printf("Il y a %i allumettes. Votre coup svp : ", pos);
scanf("%i", &coup);
}
pos = pos - coup;
joueur = !joueur;
}
if (joueur == ORDI) printf("Vous avez gagne !\n");
else printf("Vous avez perdu...\n");
return 0;
}