Discussion :

[samia2]

bonjour mes amis
on a un jeu qui consiste sur un tableau de cartes .on a 2 joueurs qui joue a tour de role chacun doit choisir l'un de cartes la plus gauche ou la plus droite et le joueur gagne la valeur de carte .
je veux travailler sur le principe de l'arbre binaire mais je ne veux pas la construire ,je veux ecrire une fonction qui calcule le gain minimal d'un joueur et m'informe sur la direction que je veux choisir (gauche ou droite).la fonction est recursive ,je veux deborder des feuilles en arrivant a la racine.
j'ai ecrit cette structure pour resoudre mon probleme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct { char joueur; /* nom du joueur(A ou B)*/
                                int T[N];/*tableau de cartes*/
                                int ind_g,ind-d;/*indice de la carte gauche et droite*/
                               }jeu;
int gainA(jeu *j,char *direction) /*fonction qui retourne le gain minimal du joueur A*/
{int g;char d;
if(j->ind_g==j->ind_d) /*cas trivial on a un seul carte*/
if(j->joueur=='A')
return j->T[ind_g];
return -j->T[ind_g];/*s'il est le tour de B il perd la valeur de la carte*/
..............
}

je ne sais pas continuer la fonction comment je veux remonter ????

[kwariz]

Bonjour,

ta question fait donc suite au post arbres binaires.
Il y a plusieurs points à voir, commençons par ce que tu appelles gain. Dans ton post précédent tu définis le gain du joueur A à un instant donné dans le jeu comme la différence entre son score et celui de son adversaire. Il peut être positif, nul ou négatif suivant que le score de A est respectivement >,= ou < à celui de B. Je comprends «gain minimal» comme le «meilleur des pires» gains, si ce n'est pas cela alors le reste de mon message ne sera pas correct. Je m'explique, si à un moment donné le joueur A estime qu'en prenant la carte de gauche (il joue G) son gain sera de +2, alors que prenant la carte de droite (il joue D) son gain sera de +10 alors son gain minimal sera de +2 : la plus petite des deux valeurs. En revanche si en jouant G son gain est de -10 et en jouant D sont gain est de -3 alors son gain minimal sera de -3 (la plus grande des deux valeurs). Un dernier cas à étudier est si en jouant G le gain est +5 et en jouant D le gain est -3 alors son gain minimal sera +5, à nouveau la plus grande des valeurs.
On peut facilement définir le gain minimal Gm à un instant I du jeu (T, ig, id) en évaluant Gm aux instants Ig=(T,ig+1,id) et Id(T,ig,id-1) puis en suivant ce que j'ai décrit ci-dessus :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
gain_gauche=Gm(Ig)±T[ig]
gain_droite=Gm(Id)±T[id]
si gain_gauche>=0 et gain_droite>=0 alors
  Gm(I)=MIN(gain_gauche, gain_droite)
sinon /* au moins l'un des gains gauche ou droite est négatif */
  Gm(I)=MAX(gain_gauche, gain_droite)
fin si

Tu remarques la présence d'un ± dans le calcul des gains à gauche et droite, on ajoute au gain si c'est au joueur pour lequel on calcule le gain à l'instant I qui joue, et on retranche si c'est l'autre joueur qui joue.
On vient de trouver le cœur de ta fonction récursive : nous calculons le gain minimum d'un instant du jeu en fonction des deux instants suivants possibles
Une fois le cœur trouvé, il faut s'intéresser aux conditions d'arrêts. Elle est aisée à trouver, et comme tu l'as déjà indiqué, c'est quand il ne reste qu'une carte (ig=id). Dans ce cas le gain est T[ig] si c'est au joueur pour lequel on calcul Gm qui la prend, et -T[ig] dans le cas contraire.

Bon avec tout ça nous pouvons commencer à construire l'algo. Les paramètres qui se dégagent de notre recherche sont apparemment : le joueur Joueur pour lequel on calcul le gain minimum et l'état Jeu du jeu (ce que j'ai auparavant appelé un instant), ce sera une fonction GainMin qui renvoie le gain minimum. La condition d'arrêt est Jeu.ig=Jeu.id et nous avons déjà décrit ce qui se passe dans chaque cas.
Un algorithme peut donc être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
fonction GainMin(Joueur, Jeu) : entier
début
  /* on commence par la condition d'arrêt */
  si Jeu.ig=Jeu.id alors
    si Joueur=Jeu.Joueur alors /* C'est le joueur qui prend la carte */
      GainMin := Jeu.T[ig]
    sinon /* c'est l'adversaire qui prend la carte */
      GainMin := -Jeu.T[id]
    fin si
  sinon /* ici c'est le cœur */
    si Joueur=Jeu.Joueur alors
      gain_gauche=GainMin(Joueur, Jeu_Gauche(Jeu)) + Jeu.T[ig]
      gain_droite=GainMin(Joueur, Jeu_Droite(Jeu)) + Jeu.T[id]
    sinon
      gain_gauche=GainMin(Joueur, Jeu_Gauche(Jeu)) - Jeu.T[ig]
      gain_droite=GainMin(Joueur, Jeu_Droite(Jeu)) - Jeu.T[id]
    fin si
    si gain_gauche>=0 et gain_droite>=0 alors
      GainMin := Min(gain_gauche, gain_droite)
    sinon
      GainMin := Max(gain_gauche, gain_droite)
    fin si
  fin si /*fin du cœur */
 
  retourner GainMin
fin /*de la fonction */

Dans cet algo, Jeu_Gauche calcule l'état du jeu après la prise de la carte à gauche, et Jeu_Droite après la prise de la carte de droite.

Comme je te l'ai dit en introduction, tout ce que j'ai écrit dépend de l'interprétation de ce qu'est le gain minimum. S'il s'agit du pire score faisable alors c'est nettement plus simple.
On peut et doit également se poser les questions suivantes :

• Quelle est la complexité de cet algorithme ? Pour un jeu de taille n (un jeu avec n cartes) combien y aura-t-il d'appels récursifs (ce n'est pas très compliqué ) ?
• Quel est le lien avec l'arbre que je t'ai dessiné dans ton post précédent ?
• Le gain minimum mesuré avec la fonction ... à quoi correspond-il ?
• Peut-on imaginer d'autres mesures plus concrètes ?
• Peut-on modéliser dans un algo le fait que chaque joueur veut gagner et donc que chaque joueur va certainement jouer le meilleur coup à chaque étape ?
• Qu'est-ce que le meilleur le coup ?

[samia2]

Merci mon ami mais je ne sais pas calculer la complexité des algorithmes récursifs et en plus je ne sais pas les réponses de tes questions tu peux m'aider s'il vous plait et merci d'avance

[kwariz]

Ce n'était que des questions pour enclencher une réflexion sur le problème et sur ce qui est fait ; en un mot prendre du recul ...
Il n'y avait rien d'obligatoire
L'important étant que tu aies compris l'algorithme et que tu puisses ensuite l'implémenter en sachant ce que tu fais.