Informaticiennes recherchent statisticien(ne) desesperement...

par **domino49** » 14 Mai 2007, 17:39

Bonjour !

Nous devons programmer un jeu de domino. Le plateau de jeu est une matrice.
D'apres les regles du jeu, le premier domino est pose au centre de la matrice. Chaque joueur doit construire sa propre branche sans toucher a celle des autres. Sachant qu'il y a 91 dominos dans le jeu, que chaque joueur (2 joueurs minimum) possede 10 dominos au debut du jeu et qu'il pioche dans le talon (71 dominos maxi donc !) jusqu'a ce qu'il puisse jouer si jamais il n'a pas de possibilité avec son propre jeu. La partie s'arrete quand un joueur a posé tous ses dominos ou quand le jeu est bloqué.Les dominos se posent les uns a la suite des autres suivant une ligne droite (pas de virage possible !). Sachant cela, notre question est la suivante :
Dans le pire des cas, combien de dominos un joueur peut il poser de son cote de la matrice ?

Nous pensons que la reponse est 80. Mais il est vrai qu'une reponse mathematique et bien construite ca fait plaisir !

Merci d'avance et vive la collaboration entre les maths(sans qui l'informatique ne serait pas grand chose... ) et l'informatique ! :we:

par **manu18ck** » 14 Mai 2007, 17:47

je comprend rien a ta règle du jeu mais je peux te retourner la remarque que sans les mathématique l'informatique n'est rien!

par **domino49** » 14 Mai 2007, 18:12

C'est bien ce que nous disions quant au rapport maths/info...
Cependant la regle n'est pas si compliquee que ca..euh... C'est la regle des dominos "normaux" avec pioche sauf que ils doivent etre poses en long et chaque joueur de son cote.

PS : Etudiant ?

par **Blueberry** » 14 Mai 2007, 18:48

Bonsoir,

c'est vrai que ce n'est pas très clair : j'imagine que la matrice est carrée et qu'elle est de dimension paire.

Quant à l'histoire des virages...

par **Flodelarab** » 14 Mai 2007, 19:06

Le nombre maximum de domino ?

TOUS !!!!
A part ceux en main chez l'adversaire

PS: matrice de taille impaire

par **Blueberry** » 14 Mai 2007, 19:12

Comment placer un domino au centre d'une matrice de taille impaire ?

par **Flodelarab** » 14 Mai 2007, 19:29

Blueberry a écrit:Comment placer un domino au centre d'une matrice de taille impaire ?

En le mettant au centre.

Comment mettre un domino dans une matrice de taille paire ?
Tu le mets à droite ou a gauche ?

par **Blueberry** » 14 Mai 2007, 19:36

Oui effectivement elle doit être de taille nxm avec n pair et m impair.

par **Flodelarab** » 14 Mai 2007, 22:07

Je pense que la clause de non-pénétration est idiote.
On va se retrouver avec un matrice énorme et majoritairement vide.

par **buzard** » 14 Mai 2007, 23:19

91? il me semblait que les dominos étaient 28

par **Patastronch** » 15 Mai 2007, 10:01

La matrice est une tres mauvaise structure pour ce probleme. Vous avez de la chance de pas etre mes étudiants ...

par **Flodelarab** » 15 Mai 2007, 10:07

buzard a écrit:91? il me semblait que les dominos étaient 28

Oui

Mais sur yahoo, on voit des dominos allant jusqu'à 9

On est loin des 91 aussi

par **fahr451** » 15 Mai 2007, 10:18

un domino usuel est exactement une 2 combinaison avec répétition parmi 7 "chiffres"

donc 2 parmi 8 = 28 résultats

si on a n "chiffres" c'est 2 parmi n+1 donc pour en avoir 91 il faut 13 chiffres

par **buzard** » 15 Mai 2007, 12:43

et puis le paris d'un tableau statique de 80 cases pour représenter une partie c'est mauvais. C'est énorme comme structure. La plupart des parties s'achèvent de toute manière avant ce L_MAX. Une liste de coups est beaucoup plus adapté pour le jeu.

pour revenir à ton problème initiale, tu recherche donc la longueur de la partie la plus longue. Le mieux c'est encore de construire une partie longue, et de montrer qu'on ne peut pas en construire de plus longue.

C'est une recherche de chemin hamiltonien ou eulerien suiviant que tu modèlise aux arc ou aux aretes. avec d'autre conditions plus spécifique aux jeu lui-même.

par **domino49** » 15 Mai 2007, 13:45

Patastronch a écrit:La matrice est une tres mauvaise structure pour ce probleme. Vous avez de la chance de pas etre mes étudiants ...

La structure de liste etait celle que nous avions choisi au départ mais notre encadrant dit qu'une matrice sera plus facile a representer a l'ecran et un clic est plus facile a associer a une case. Mais il est vrai, qu'il y a une enorme perte de mémoire... c'est bien pour cela que nous voulons faire la plus petite matrice possible.

Le jeu se compose bien de 91 Dominos (chiffres allant de 0 à 12, Double douze mexicain).

Notre idee est qu'il est quand meme tres peu probable qu'un joueur (meme malchanceux) pioche tous les dominos du talon.. c'est cette probabilite qui nous aurait aidé.

par **Flodelarab** » 15 Mai 2007, 14:39

domino49 a écrit:Notre idee est qu'il est quand meme tres peu probable qu'un joueur (meme malchanceux) pioche tous les dominos du talon.. c'est cette probabilite qui nous aurait aidé.

Et le jour où ça arrive ? tu fais koi ? tu fais planter ton programme ????

par **domino49** » 16 Mai 2007, 10:21

Le problème est maintenant réglé. Nous avons décidé de faire évoluer la taille de la matrice au fur et a mesure du jeu.
Merci a tous pour vos commentaires...

Informaticiennes recherchent statisticien(ne) desesperement...

Informaticiennes recherchent statisticien(ne) desesperement...

Qui est en ligne