Discussion :

[lakissovos]

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).

[alyma]

Bonjour,

Est ce que tu peux nous montrer les structures que tu as déjà créées?
Quel est réellement ton problème?
Tu dis ne pas savoir construire l'arbre mais si tu as définis les structures le décrivant, tu es sur le bon chemin, reste à savoir si tes structures sont adaptées et décrivent correctement l'arbre.
Si tel est le cas, il faut les utiliser, les remplir ....

[ternel]

Bonjour,

Il te faut deux séries de fonctions.
Une première pour les manipulations "locales" ou "basiques":
un arbre binaire est essentiellement un noeud avec deux noeud fils potentiels (gauche, droit)

Code :

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

1
2
3
4
5
6
7
8
typedef ? valeur_t;//le type de ton choix.
typedef struct s_noeud{
	valeur_t valeur;
	s_noeud *gauche, *droit;
	s_noeud *pere;
}noeud;
 
#define PAS_UN_NOEUD NULL

il te faut donc les fonctions suivantes:

• void liberer_noeud(noeud);
• noeud* creer_noeud(valeur);
• noeud* attacher_fils_droit(noeud* pere, noeud* fils); qui remplace le fils droit par un noeud spécifique, et retourne l'ancien fils
• noeud* attacher_fils_gauche(noeud* pere, noeud* fils); idem pour le fils gauche
• noeud* detacher_fils_droit(noeud* pere); qui remplace le fils droit de pere par PAS_UN_NOEUD et retourne l'ancien fils
• noeud* detacher_fils_gauche(noeud* pere); idem pour le fils gauche
• noeud* creer_fils_droit(noeud* pere, valeur_t valeur); qui crée un noeud directement comme fils droit de pere
• noeud* creer_fils_gauche(noeud* pere, valeur_t valeur); idem pour le fils gauche

Je te laisse réfléchir pour liberer_noeud(), creer noeud() et attacher_fils_*().

Pour les autres, ce sont de simples raccourcis:

Code :

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

1
2
3
4
5
6
7
noeud* detacher_fils_droit(noeud* pere) {
	return attacher_fils_droit(pere, PAS_UN_NOEUD);
}
 
noeud* creer_fils_droit(noeud* pere, valeur_t valeur) {
	return attacher_fils_droit(pere, creer_noeud(valeur));
}

Une second série de fonctions pour les manipulations "globales" ou "pratiques":
supposons les deux types de fonctions suivantes:

Code :

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

1
2
typedef void (*action_noeud_f) (noeud*);
typedef valeur_t (*accumulation_noeud_f) (noeud*, valeur_t);

• noeud* racine(noeud*)
• int est_racine(noeud*)
• int est_feuille(noeud*)
• void modification_en_profondeur(noeud* racine, action_noeud_f action)
• void modification_en_largeur(noeud* racine, action_noeud_f action)
• valeur_t accumulation_en_profondeur(noeud* racine, accumulation_noeud_f action)
• valeur_t accumulation_en_largeur(noeud* racine, accumulation_noeud_f action)

Cette partie demandera probablement plus de travail.

[kwariz]

Bonjour,

cet énoncé me rappelle d'autres discussions concernant exactement le même sujet :

• arbres binaires
• tableau des cartes

la construction de l'arbre est expliquée dans le premier lien.