Discussion :

[Gasimoto]

Bonjour,

j'ai un TP à rendre sur les arbres binaires de recherche. Mais bizarrement je bloque sur cette question:

Définir une fonction qui permet de savoir si son argument est un arbre de recherche

Ainsi, j'ai écrit deux fonctions:l'une(arbre_correct?) qui teste si l'arbre est un arbre binaire et l'autre qui reprend cette fonction et qui se spécialise sur les caractéristiques d'un arbre binaire de recherche

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
 
(defun arbre_correct?(a)
	(or	(arbre_vide? a)
		(and	(listp (arbre_sag a))
			(listp (arbre_sad a))
			(null (cdddr a))
			(arbre_correct? (arbre_sag a))
			(arbre_correct? (arbre_sad a))
		)
	)
)
 
 
(defun arbre_bon?(a)
	(and		(arbre_correct? a)
			(if (not (null (arbre_sad a)))(< (arbre_rac a) (arbre_rac (arbre_sad a))))
			(if (not (null (arbre_sag a)))(> (arbre_rac a) (arbre_rac (arbre_sag a))))
			(arbre_bon? (arbre_sag a))
			(arbre_bon? (arbre_sad a))
	)
)

Apparemment, ce qui coince c'est l'appel récursif.Car j'obtiens un true sans les deux dernières lignes de arbre_bon?Mais je comprend pas pourquoi, peut être que quelqu'un peux m'aiguiller?

Merci d'avance pour votre aide
Si j'ai oublié des détails demandez moi.

[Garulfo]

Bonjour,

j'ai un TP à rendre sur les arbres binaires de recherche. [...]

Quelle est ta définition d'un « arbre binaire de recherche » ?
Quelle est la structure de ton arbre ?
Je suppose que c'est une liste à trois éléments ?
arbre_vide?
arbre_rac
arbre_sag
arbre_sad
sont respectivement null, car, cadr et caddr ?
En supposant ça, ton prédicat arbre_correct? est mal pensé.
Mais ça ça ne provoque pas d'erreur a priori.

Finalement je ne comprends pas ce que tu obtiens comme erreur :
« j'obtiens un true sans les deux dernières lignes de arbre_bon? »
Ça veut dire que tu obtiens toujours true si tu n'as pas les deux dernières lignes ?

[Gasimoto]

Effectivement j'avais zappé quelques détails importants.

Je dois suivre cette définition:

Un arbre binaire sera représenté soit par une liste vide, soit par une liste à 3 constituants : (noeud sag sad), où "sag", acronyme de sous-arbre gauche, et "sad", acronyme de sous-arbre droit, sont eux-mêmes des arbres et "noeud" est l'information d'un type arbitraire stockée sur le noeud.

Un arbre de recherche est un arbre binaire dont les noeuds sont des éléments d'un ensemble ordonné (on pourra prendre l'ensemble des entiers naturels, sans perte de généralité) et qui vérifie :

chaque noeud est supérieur ou égal à toutes les valeurs des noeuds de son sous-arbre gauche ;
chaque noeud est inférieur ou égal à toutes les valeurs des noeuds de son sous-arbre droit.

Voici les codes pour définir un arbre vide, obtenir la racine,le sous arbre gauche,le sous arbre droit et enfin tester si un arbre est vide:

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
(setq arbre_vide ())
 
(defun arbre_rac(a)
	(car a)
)
 
 
(defun arbre_sag(a)
	(cadr a)
)
 
 
(defun arbre_sad(a)
	(caddr a)
)
 
(defun arbre_vide?(a)
	(eq a arbre_vide)
)

Je vais exposer mon problème d'une autre manière. J'ai construit un arbre binaire de recherche qui repecte bien la définition:

Code :

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

(10 (1 NIL (9 (3 (2 NIL NIL) (8 (5 NIL NIL) NIL)) NIL)) (17 (16 NIL NIL) NIL))

Ainsi, j'ai testé arbre_bon? dessus et j'obtiens nil. Mais si je retire

Code :

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

1
2
3
 
(arbre_bon? (arbre_sag a))
(arbre_bon? (arbre_sad a))

de la fonction arbre_bon? j'obtiens true.

Sinon la fonction arbre_correct? a été fourni par le prof.

[Gasimoto]

Personne pour m'aider rien qu'un peu ?

PS:joyeux noël

[Garulfo]

Personne pour m'aider rien qu'un peu ?

PS:joyeux noël

Tu sais que c'était Noël hier, non ?
Et tu n'es pas patient ?!

Pour la peine, j'attendrais avant de te répondre... Ça t'apprendra à être impatient

[Gasimoto]

Je sais que c'était noël, la preuve j'ai souhaité un joyeux noël.

Mais c'est parce que je me suis bien pris la tête dessus et c'est la seule question qui me reste pour finir ce TP noté. Et derrière j'ai encore trois autres TP(dans d'autres disciplines), y sont sympa les profs pour les vacances.

Sinon bah j'attendrais ...

En attendant je vais continuer à chercher

[Garulfo]

[...]
En attendant je vais continuer à chercher

Excellente initiative

Un conseil : avant de faire des tests avec un exemple aussi long, commence par faire de petit test. Tu aurais pu trouver ton erreur tout seul avec l'arbre '(1 (2 nil nil) nil) et en l'évaluant à la main. Une des richesses du lisp est que le calcul d'un résultat est très simple à obtenir.

Par curiosité, sais tu ce que renvoie

Code :

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

(if nil 'nimportequoi)

et sais-tu ce que renvoie

Code :

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

(and nil 'nimportequoi)

?
De manière similaire sais-tu ce que renvoie

Code :

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

(if T 'nimportequoi)

et sais-tu ce que renvoie

Code :

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

(and T 'nimportequoi)

?
Parce que tu te rendras peut-être compte de qqchose d'important: tu n'aurais pas du faire des if.

[Gasimoto]

Merci pour tes indications, j'ai vu que mes if renvoie des valeurs qui brouillent mon and.

tu n'aurais pas du faire des if

J'ai testé avec un cond mais c'est pareil

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
 
(defun arbre_bon?(a)
	(or	(arbre_vide? a)
		(and	
			(listp (arbre_sag a))
			(listp (arbre_sad a))
			(null (cdddr a))
			(cond	((numberp (arbre_sad a)) 	(< (arbre_rac a) (arbre_sad a)))
					((numberp (arbre_sag a)) 	(> (arbre_rac a) (arbre_sag a)))
			)
			(arbre_bon? (arbre_sag a))
			(arbre_bon? (arbre_sad a))
		)
	)
)

ça me donne toujours les mêmes résultats et c'est de moins en moins clair à lire. Je continue à chercher, mais j'ai vraiment l'impression de bidouiller. J'espère un coup de bol ...

[Garulfo]

Quand je disais que tu n'aurais pas du faire un if c'est parce que tu aurais du faire un and. Si tu as bien évalué chacun des cas que je t'ai donné tu auras remarqué qu'en Common Lisp, un if est un and de la façon que tu l'as utilisé.

Tu bidouilles effectivement pour pas grand chose. Il suffit de rajouter un deuxième cas à ton if (le else). Par contre à ce moment, tu vas avoir un autre problème.

Il faut que tu revois ton algorithme, il n'est pas bon.

[Garulfo]

Ah oui autre chose...

Tu as des fonctions de manipulations de ton arbre qui correspondent à l'interface. Tu dois faire un effort pour n'utiliser qu'elles autant que possible.
Ainsi ici tu n'aurais pas du faire

Code :

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

(if (not (null (arbre_sad a))) 'EXP)

mais

Code :

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

(if (not (arbre_vide? (arbre_sad a))) 'EXP)

Ceci est important car il te préserve d'un changement de structure interne de ton arbre (au prix d'un recodage des fonctions interfaces). C'est une des deux raisons pour laquelle la fonction arbre_correct? n'est pas géniale.

[Gasimoto]

J'ai pas tout suivi car tu me dis de mettre un and au lieu du if et ensuite tu me dis de mettre un deuxième cas au if.

if ou pas if ?

J'ai testé ça avec un deuxieme cas pour le if qui permet d'éviter de renvoyer nil quand le if n'est pas satisfait

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
(defun arbre_bon?(a)
	(and		(arbre_correct? a)
			(if	(not (arbre_vide? (arbre_sad a)))(< (arbre_rac a) (arbre_rac (arbre_sad a)))
				t)
			(if (not (arbre_vide? (arbre_sag a)))(> (arbre_rac a) (arbre_rac (arbre_sag a)))
				t)
			(arbre_bon? (arbre_sag a))
			(arbre_bon? (arbre_sad a))
	)
)

Quand l'arbre n'est pas un arbre de recherche j'ai bien nil mais quand c'en ai un il me met Program stack overflow. RESET(peut être le souci dont tu m'a parlé)

Mais si tu me dis que mon algo est faux, ça sert à rien de bosser dessus

J'ai vu des programmes pour faire la vérification d'un arbre de recherche en caml mais je comprends pas du tout comment ils sont écrits.

Je suis en manque d'inspiration ...

[Garulfo]

J'ai pas tout suivi car tu me dis de mettre un and au lieu du if et ensuite tu me dis de mettre un deuxième cas au if.

if ou pas if ?

Non je t'ai dit, que avec ce que tu as écris tu aurais du mettre un and au lieu d'un if. Car en fait tu as écris un and si on regarde le comportement, car (if c a) est strictement la même chose que (and c a). Et c'est là ton erreur
Car tu aurais dû mettre un cas « else » à ton if.
Donc, si tu avais remarqué que ce que tu as écris était un and, tu aurais vu ton erreur, puisque tu voulais un if. J'espère avoir été plus clair. Mais reste que ton problème est maintenant ailleurs :

J'ai testé ça avec un deuxieme cas pour le if qui permet d'éviter de renvoyer nil quand le if n'est pas satisfait

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
(defun arbre_bon?(a)
	(and		(arbre_correct? a)
			(if	(not (arbre_vide? (arbre_sad a)))(< (arbre_rac a) (arbre_rac (arbre_sad a)))
				t)
			(if (not (arbre_vide? (arbre_sag a)))(> (arbre_rac a) (arbre_rac (arbre_sag a)))
				t)
			(arbre_bon? (arbre_sag a))
			(arbre_bon? (arbre_sad a))
	)
)

Quand l'arbre n'est pas un arbre de recherche j'ai bien nil mais quand c'en ai un il me met Program stack overflow. RESET(peut être le souci dont tu m'a parlé)

voilà ton erreur !! Tu as une boucle infini mon cher.
Ce qui signifie que tu as merdé dans ton cas d'arrêt de ta boucle récursive.

Il faut donc revoir ton algo car :

[...]si [...] mon algo est faux, ça sert à rien de bosser dessus

ce qui est totalement vrai
Enfin, disons plutôt que si ton algo est faux ça sert à rien d'essayer de l'implémenter, sauf pour trouver l'erreur.

Comment fait-on pour concevoir un algorithme récursif ?
Il y a trois choses à penser... enfin pour commencer disons deux : le cas d'arrêt et la réduction du pas.

Tu as oublié la première : le cas d'arrêt.

[Gasimoto]

J'ai trouvé une solution qui m'a l'air de fonctionner. Mais peut être s'agit t il d'un faux espoir et que ma fonction but sur des cas particuliers.

Je mettrai bien ma fonction mais sachant que cette page arrive n°1 sur google et que ce TP est noté je suis un peu embété.

Puis-je te l'envoyer en message privé Garulfo ?

[Garulfo]

[...]
Puis-je te l'envoyer en message privé Garulfo ?

Ah non il faut assumer
Et en plus, je doute que ton prof t'enlèves des points parce que tu aurais pris la peine de réfléchir et de faire des recherches
En tout cas, j'ai même toujours conseillé au mien de faire ça.
En informatique, la recherche personnelle est fondamentale.
Et je ne t'ai donnée aucune solution.
T'as qu'à mettre ton prénom ou je ne sais pas quoi et indiquer à ton prof que tu as fait des recherches ici. C'est honnête et donc ce n'est pas du plagiat.

Si tu as peur pour les autres étudiants, ne t'inquiètes pas. Le jour de l'examen, eux n'auront pas travaillés.

[Gasimoto]

Je pensai aux autres étudiants car ce TP compte autant qu'un partiel

Sinon je te remercie de ton aide, même si tu m'a laissé mijoter avant de me dire que l'algo était faux

à une prochaine

[Garulfo]

Je pensai aux autres étudiants car ce TP compte autant qu'un partiel

Sinon je te remercie de ton aide, même si tu m'a laissé mijoter avant de me dire que l'algo était faux

à une prochaine

Ça serait trop facile si je t'avais tout dit tout de suite
Mais je suppose que ce que je t'ai fais subir fait que la prochaine fois, tu vas y penser à ta condition d'arrêt
Et tu n'oublieras pas qu'en CommonLisp un if de la forme (if c e1) est équivalent à un (and c e1). Attention ceci n'est pas vrai en Scheme où (if c e1) renvoie #<void> si c est faux, qui est interprété comme vrai (tout ce qui n'est pas #f est vrai, un peu comme pour le CommonLisp où tout ce qui n'est pas nil est vrai).

Sinon, tu ne devrais pas t'inquièter des autres. Tu essaie d'obtenir un diplôme pour toi.

[Gasimoto]

C'est sûr que là j'y pensera à ma condition d'arrêt

Je sais pas si je vais faire du Scheme, mais là on va passer à caml

J'espère bien l'avoir mon diplome, mais c'est pas gagné

[Garulfo]

[...]
J'espère bien l'avoir mon diplome, mais c'est pas gagné

Mais si ! Du bon travail mène à de bons résultats.

Peut-on dire que c'est ?

[Gasimoto]

On m'a dit que le sérieux était toujours récompensé et ça s'est révélé faux à un moment de mes études.

Merci quand même pour l'encouragement

Enfin bref, RESOLU

[Garulfo]

On m'a dit que le sérieux était toujours récompensé et ça s'est révélé faux à un moment de mes études.[...]

Non tu parles de court termes.
Le sérieux dans les études ne portent pas forcément fruit à court terme, mais à long termes. ^_^ Attention cependant, sérieux ne veut pas dire bachotter bêtement, mais travailler intelligemment ce qui est très différent.

En tout cas, bon courage.