Arbres binaires

Version imprimable

Arbres binaires

bonjour mes amis
je vous demande de m'aider ,j'ai un problème on a un projet sur les arbres binaires et je rencontre des difficultés dans mon projet j'ai écrit les structures de donnes correspondantes mai je ne sais pas comment construire l'arbre
c'est mon projet:
On considère un jeu de cartes dans lequel deux joueurs (A et B) enlèvent à tour de rôle soit la carte la plus à gauche, soit la carte la plus à droite d’une rangée de cartes disposées linéairement. A chaque fois qu’un joueur tire une carte, il gagne la valeur indiquée dessus. Le jeu s’arrête quand toutes les cartes sont tirées et le joueur qui a le plus de points gagne la partie.
Une situation est définie par le joueur à qui le tour, un n-uplet représentant les cartes restantes et les gains respectifs de A et de B.
Ex: <B,(4,10,8,5,1,2),(15,9)> représente la situation où B doit jouer, il reste les cartes suivantes : 4 10 8 5 1 2, et A a déjà gagné 15 points et B en a gagné 9 (A gagne donc 6 points).
Une partie peut donc être représentée par un arbre binaire de situations
on désire développer un programme permettant de simuler une partie entre un humain et une machine intelligente. L’intelligence de la machine est assurée par un algorithme lui permettant d’évaluer le gain (ou la perte) provoqué par le tirage d’une carte. En effet, à chaque situation, la machine a le choix entre les deux cartes aux bords et doit choisir celle qui maximise son gain dans tout le jeu et non pas la plus grande
1. Créer une configuration initiale aléatoirement.
2. Simuler une partie.
3. Déterminer le gain minimal d’un joueur donné à partir d’une situation initiale sans développer l’arbre de jeu (penser récursivement).

les structures de données que j'ai écrit sont:
Code:

1 2 3 4 struct gain{int gainj,gainm;};/*pour les gains joueurs et machine*/ struct carte{int t[n],nb_carte;};/*por la liste des cartes*/ struct element{gain a;carte t;char c;};/*ce sont les éléments du nœud*/ struct noeud{element e;noeud *sag,sad;};
je ne sais pas comment je veux commencer dans mon projet je désire que vous m'aider et merci beaucoup à vous

02/05/2013, 23h51
Flynet

Si je comprends bien ton arbre binaire va être composé de tous les chemins possibles de la partie. Donc en début de jeu, il faut générer cette arbre en fonction des cartes présentes.

Renseigne toi sur la structure d'un arbre binaire. Il y aura un élément root, des structures Element représentant les noeuds avec un pointeur sur l'élément à gauche et un autre pour la droite ainsi que la valeur de la situation (gain?) actuelle.

La branche à droite aura plus de poids que celle à gauche donc un gain supérieur. Ton chemin est tout tracé :).
03/05/2013, 12h00
samia2

Citation:

Envoyé par Flynet

Si je comprends bien ton arbre binaire va être composé de tous les chemins possibles de la partie. Donc en début de jeu, il faut générer cette arbre en fonction des cartes présentes.

Renseigne toi sur la structure d'un arbre binaire. Il y aura un élément root, des structures Element représentant les noeuds avec un pointeur sur l'élément à gauche et un autre pour la droite ainsi que la valeur de la situation (gain?) actuelle.

La branche à droite aura plus de poids que celle à gauche donc un gain supérieur. Ton chemin est tout tracé :).

salut mon ami
mon probleme est comment construire l'arbre je ne sais pas comment je veux ecrire le code correctement tu peux m'aider dans l'ecriture du code en language c :rose2: et mercie a vous.
04/05/2013, 11h55
diogene

Sur les arbres en C, tu peux consulter le tutoriel Introduction aux arbres

Bonjour,

Pour comprendre ce qui se passe on peut faire des dessins, même si dans un forum ce n'est pas forcément très pratique :)
Donc on va dessiner ta structure ainsi :
http://i1283.photobucket.com/albums/...ps13d92d4f.png

Prenons pour exemple le jeu [1,10,5,10]. La racine de ton arbre ressemblera à :
http://i1283.photobucket.com/albums/...ps3301638d.png
Ce noeud est facile à créer car tu possèdes toutes les infos pour ça. À partir de ce nœud tu peux créer les sous arbres correspondant à chaque choix. Déjà les deux sous arbre auront comme joueur l'autre joueur, pour le sous arbre gauche (=le joueur a choisi de prendre la carte à gauche) le tableau sera le tableau courant privé de son élement le plus à gauche, le score du joueur A sera augmenté de la valeur de la carte tirée. On obtient donc un noeud comme celui-ci comme racine du sous arbre-gauche :
http://i1283.photobucket.com/albums/...ps58d993a3.png.
La construction de la racine du sous arbre droit est similaire et on obtient :
http://i1283.photobucket.com/albums/...ps4d91df64.png
Tu peux ensuite créer les liens entre ces nœuds :
http://i1283.photobucket.com/albums/...ps755eeb1f.png

Là on a une méthode qui à partir d'un nœud lui en ajoute deux, chacun avec le bon joueur, un tableau de taille n-1 et le score mis-à-jour.
Il faut faire attention quand le tableau n'a qu'un élément. Dans ce cas, qu'on joue «à gauche» ou «à droite» on obtient le même résultat. Comme il est souvent préférable de ne pas dupliquer des positions de jeu identiques, je te propose de ne créer que le sous arbre gauche et de laisser le droit vide :
http://i1283.photobucket.com/albums/...psf18957a5.png
Dans ce cas il n'est pas nécessaire de construire l'arbre plus loin car c'est la fin du jeu (plus de carte à jouer).

On vient donc de créer une méthode récursive pour construire ton arbre. L'algo est :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 noeud_dilater( n : noeud ) début si longueur(n.tableau)=1 alors n.sag = noeud_creer(autre_joueur(n.joueur), // le joueur [], // le tableau de cartes gain_ajouter(n.gain, valeur_carte_gauche(n.tableau)), // màj des gains NULL, // sag NULL) // sad sinon n.sag = noeud_creer(autre_joueur(n.joueur), // le joueur [2:k], // le tableau de cartes sans la carte de gauche gain_ajouter(n.gain, valeur_carte_gauche(n.tableau)), // màj des gains NULL, // sag NULL) // sad n.sad = noeud_creer(autre_joueur(n.joueur), // le joueur [1:k-1], // le tableau de cartes sans la carte de droite gain_ajouter(n.gain, valeur_carte_droite(n.tableau)), // màj des gains NULL, // sag NULL) // sad // on a créé les racines des sous arbres, ne reste plus qu'à les dilater également noeud_dilater(n.sag) noeud_dilater(n.sad) fin si fin
Ensuite il te faut la procédure pour créer la racine de la simulation :
Code:

1 2 3 4 5 6 noeud créer_simulation(cartes : int[], nbre_carte : int) début racine = noeud_creer('A', cartes, (0,0), NULL, NULL) noeud_dilater(racine) renvoyer racine fin
Implémenter ça en C peut être un peu fastidieux ...
Si j'étais toi, je me créerais une structure simulation qui contient le tableau de cartes du départ. Les nœuds eux ne contiendront qu'un pointeur vers ce tableau, ainsi que deux indices : un pour la carte la plus à gauche dispo, l'autre pour la carte la plus à droite disponible. Mais bon, ce ne sont que des détails d'implémentations :)

Un arbre complet donnerait :
http://i1283.photobucket.com/albums/...ps54313460.png

Voilà pour la première partie, la seconde est un peu différente. Essaye déjà de coder ça et on embrayera par la suite :)

Plusieurs remarques:

L'arbre peut vite devenir grand. On peut (doit ?) se poser la question sur le nombre de noeuds qu'il va contenir. On peut facilement montrer que pour N cartes au départ tu vas construire un arbre dont les N premiers niveau sont complets et le dernier rempli à moitié. On aura donc hauteur arbre = N+1, nombre de nœuds = 2^N-1 + 2^(N-1)=3x2^(N-1)-1 (pour N>0). Si on estime que la structure nœud fait dans les 40 octets (à vue de nez sur une architecture 32bits en partageant le tableau de carte ...), alors 15 cartes font 2Mo, 20 cartes frisent les 60Mo, 25 cartes les 1.9Go (ce qui est énorme pour une architecture 32bits ...).
On peut (doit ?) remarquer que le dernier niveau de nœuds ne sert pas à grand chose, on pourrait (devrait ?) s'en passer pour gagner de la place si c'est utile.
On peut aussi se dire qu'à un moment donné on a pas forcément besoin d'avoir tout l'arbre de développé ...

11/06/2013, 14h54
ternel

En fait, la situation présente une caractéristique attrayante.

Pour une représentation plus complete de l'état, on peut naviguer dans l'arbre en modifiant l'état lui-même, et donc ne pas construire l'arbre du tout.

on aurait une structure contenant:
la pile de carte
la liste des identifiants de cartes piochés par chaque joueur.

Salut,

En fait, je ne vois absolument pas pourquoi tu as besoin d'un arbre binaire dans le cas présent :aie:

Tu aurais largement plutôt besoin d'une liste doublement chainée au départ de laquelle tu peux accéder au "premier élément" (enfin, à celui qui se trouve le plus à gauche, mettons) et au "dernière élément" (enfin, celui qui se trouve le plus à droite)

Tu pourrais très bien avoir donc une structure de carte qui ressemblerait à quelque chose comme

Code:

1
2
3
4
5
6
typedef struct _Carte{
    int valeur; // de AS à roi :D
    int couleur; // coeur, pique, carreau, treffle :D 
    Carte * gauche;
    Carte * droite;
}Carte;

Du moment que toutes les cartes qu'un joueur a sont reliées entre elles, il n'a besoin que de la première (une addition aura le meme résultat quel que soit le sens dans lequel on la fait :D )

Code:

1
2
3
typedef struct Joueur{
    Carte * top;
} Joueur;

On a ensuite le "paquet" de carte, qui correspond à quelque chose comme

Code:

1
2
3
4
typedef struct _Paquet{
    Carte * gauche; //celle qui est "le plus à gauche"
    Carte * droite; // celle qui est "le plus à droite"
}Paquet;

On étale les cartes de gauche à droite en fait, on sélectionne aléatoirement une carte parmi celles dont on dispose, et on la place à la droite de la dernière qui est à droite :D

Code:

1
2
3
4
5
6
7
8
9
10
11
12
void etalerCartes(Paquet * p, Carte* nouvelle){
    // la première carte est à l'extreme gauche
    if(p->gauche == NULL)
        p->gauche = nouvelle;
    //s'il y a une carte à l'extrême droite, on rajoute la nouvelle à sa droite
    if(p->droite != NULL)
        p->droite->droite = nouvelle;
    // l'ancienne carte de droite devient celle de gauche de la nouvelle
    nouvelle->gauche  = p->droite;
    // la nouvelle carte devient la carte à l'extrême droite
   p->droite = nouvelle;
}

On peut prendre une carte à gauche:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
Carte * prendreGauche(Paquet * p ){
    if(p->gauche = NULL)
        return NULL;
    Carte * temp = p->gauche;
    // la première carte de gauche devient celle qui suit l'actuelle carte de gauche
    p->gauche = temp->droite;
    p->gauche->gauche = NULL;
    // on retire la carte du paquet
    temp->gauche = NULL; // normalement, ca devrait déjà l'être
    temp->droite = NULL;
    return temp;
 
}

On peut prendre une carte à droite:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
Carte * prendreDroite(Paquet * p ){
    if(p->droite= NULL)
        return NULL;
    Carte * temp = p->droite;
    // la première carte de gauche devient celle qui suit l'actuelle carte de gauche
    p->droite= temp->gauche;
    p->droite->droite= NULL;
    // on retire la carte du paquet
    temp->gauche = NULL;
    temp->droite = NULL; // normalement, ca devrait déjà l'être
    return temp;
 
}

Un joueur peut choisir de prendre la carte de gauche ou la carte de droite

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int joueurPrendre(Joueur * j, int cote, Paquet * p){
    Carte * temp = NULL;
    if(cote == 0){
        temp = prendreGauche(p);
    }else{
        temp = prendreDroite(p);
    }
    // le joueur place sa carte en haut de son paquet
    if(temp != NULL){
        temp->droite = j->top;
        j->top = temp;
        return 1;
    }
    return 0;
}

Et, enfin, on peut calculer les points d'un joueur

Code:

1
2
3
4
5
6
7
8
9
int points(Joueur * j){
    int total = 0;
    Carte * temp = j->top;
    while(temp!= NULL){
        total+=temp->valeur;
        temp=temp->droite;
    }
    return total;
}

Au final, on peut avoir une fonction main qui sera composée, entre autre de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main(){
    Paquet p;
    Joueur un;
    Joueur deux;
    Joueur * courent = &un;
    Carte * temp;
    int cote;
    int recu;
    // à toi de voir comment faire en sorte que temp soit tiré aléatoirement
    while(temp!= NULL){ 
        etalerCartes(&p, temp){
    }
    while(recu == 1){ // tant qu'on recoit une carte;
        // à toi de demander le coté au joueur
        recu = joueurPrendre(courent, cote, p);
        if(courent ==&un)
            courent = &deux;
        else 
            courent = & un;
    }
    /* afficher ici les résultat des deux joueurs */
    /* ne pas oublier de libérer la mémoire à la fin du jeu (ca, je te laisse faire ;)) */
    return 0;
}

Bon, je suis allé très loin dans le raisonnement, mais je ne devrais pas avoir occasionné de bug majeur (à partir du moment où tu veilles à créer des cartes de manière dynamique ;))