UTBM theorie de la programmation tda et structures de donnees 2005 gi

Publié par

UTBM le 16 janvier 2006 Final – LO42 Les documents sont autorisés (La copie ou les idées du voisin non). Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). L’élégance de la solution sera jugée. Sauf indication contraire, dans le cas d’algorithmes, les réponses doivent être rédigées en pseudo code. L’exercice 3 est à faire sur une feuille séparée 1) La multiplication des pins (5) (en Java) Voici une classe java : public class ArbreBinaire { public ArbreBinaire droit() { return d; } Object r; // la racine de l'arbre public ArbreBinaire setDroit(ArbreBinaire a) { ArbreBinaire g, d; // les sous-arbres return (d = a); } protected ArbreBinaire(Object r, ArbreBinaire g, ArbreBinaire d) { // construction de l'arbre : a = f.cons(r,d) this.r = r; public ArbreBinaire cons(Object r, ArbreBinaire d) { this.g = g; return new ArbreBinaire (r,this, d); this.d = d; } } protected ArbreBinaire(Object r) { this(r,creer,creer); } /** Le seul moyen d'initialiser un nouvel arbre binaire : protected ArbreBinaire() { this(null,creer,creer); } * ArbreBinaire a = ArbreBinaire.creer; */ public Object racine() { return r; } static public final ArbreBinaire creer = new ArbreBinaire (); public Object setRacine(Object r) { return (this.r = r) ; } public boolean estVide() { public ArbreBinaire gauche() { return g; } ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 126
Nombre de pages : 3
Voir plus Voir moins
UTBM
le 16 janvier 2006
Final –LO42 Les documents sont autorisÈs (La copie ou les idÈes du voisin non). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). L’ÈlÈgance de la solution sera jugÈe. Sauf indication contraire, dans le cas d’algorithmes, les rÈponses doivent Ítre rÈdigÈes en pseudo code. L’exercice 3 est ‡ faire sur une feuille sÈparÈe 1) Lamultiplication des pins(5) (en Java)Voici une classe java : public class ArbreBinaire {public ArbreBinaire droit() { return d; }  Objectr; //la racine de l'arbrepublic ArbreBinaire setDroit(ArbreBinaire a) {  ArbreBinaireg, d;// les sousarbresreturn (d = a);  }  protectedArbreBinaire(Object r, ArbreBinaire g, ArbreBinaire d) {// construction de l'arbre : a = f.cons(r,d)  this.r= r;public ArbreBinaire cons(Object r, ArbreBinaire d) {  this.g= g;return new ArbreBinaire (r,this, d);  this.d= d;}  }  protectedArbreBinaire(Object r) { this(r,creer,creer); }/** Leseulmoyen d'initialiser un nouvel arbre binaire :  protectedArbreBinaire() { this(null,creer,creer); }* ArbreBinairea = ArbreBinaire.creer;  */  publicObject racine() { return r; }static public final ArbreBinaire creer = new ArbreBinaire ();  publicObject setRacine(Object r) { return (this.r = r) ; }  publicboolean estVide() {  publicArbreBinaire gauche() { return g; }return this == creer;  }  publicArbreBinaire setGauche(ArbreBinaire a) {  return(g = a);  } a) Ajoutezune mÈthode permettant de cloner l’arbre binaire. b) Supposezque le type dern’est plusObjectmaisint. Ajoutez une mÈthode permettant de vÈrifier que l’arbre a la propriÈtÈ de maxtas. (On ne se prÈoccupe pas de savoir si l’arbre est quasi parfait) 2) Lapousse tirÈe par les cheveux(7)Nous travaillons sur une application de recherche prÈsentant comme particularitÈ que les derniers ÈlÈments introduits sont les ÈlÈments les plus demandÈs. Nous souhaitons donc insËrer dans un arbre de recherche un ÈlÈment non pas comme une feuille mais ‡ la racine afin que la recherche des derniers ÈlÈments introduits soit la plus rapide possible. Voici par exemple un arbre binaire dans lequel nous insÈrons la valeur 23. 23 15 30 12 30 15 35 25 35 12 25 20 40 29 40 20 29 a) Vousdevez Ècrire la sÈquence permettant de partager l’arbre existant en deux sous arbresgaucheetdroit
lo42  final A2005  page1/3
UTBM
le 16 janvier 2006
contenant respectivement les ÈlÈments infÈrieurs et supÈrieurs ‡ une valeur donnÈe.  Vousdisposez de l’opÈrationajouterde signature ´ajouter(var Arbretronc ; Arbre branche)ª qui rÈalise un parcours de recherche et ajoute dans l’arbre dÈsignÈ par tronc le sous arbre dÈsignÈ par branche.  Letraitement ne doit pas entraÓner la dÈgÈnÈrescence des sous arbres. Note : vous pouvez considËrer qu’un arbre est implantÈ selon la structure ci dessous  StructureDÈbut  Teltval ;  ABRfG, fD ;  Fin;  ouencore utilisez des opÈrations comme valeur(ARB a), filsG(ABR a), filsD(ABR a), setFilsG(ABR a, fg) et setFilsD(ABR a, fd). b) ComplËtezvotre sÈquence pour obtenir une procÈdure qui permet l’insertion d’une valeur dans l’arbre au niveau de la racine. c) AprËsavoir ÈtudiÈ o˘ sont faites les insertions rÈalisÈes successivement sur les deux arbresgaucheetdroitlorsque vous crÈez un nouvel arbre en insÈrant la valeur 23 dans l’arbre cidessous, modifiez votre procÈdure afin de rÈduire au maximum les parcours d’arbres. (On Èvitera donc d’utiliser l’opÈrationajouterqui rÈalise un parcours de recherche.) 32 40 15 45 12 29 37 50 19 25 22 d) Onveut procÈder autrement en rÈalisant l’insertion de l’ÈlÈment puis en remontant le nœud jusqu’‡ la racine par des rotations successives. Ecrivez un procÈdure insertion de signature insertion (Var ABR A; entier x) rÈalisant l’insertion de cette faÁon. 3) Etendonsnous sur le sujet(8)Comme nous nous rapprochons des arbres dÈployÈs nous souhaitons utiliser ceuxci. Nous voulons approcher de la mise en œuvre de l’opÈration dÈployer. Rappel :L'opÈration dÈployer Soit A un arbre binaire non vide quelconque et soitsun sommet de cet arbre. On note A[sB] la greffe de l'arbre B dans A ‡ la positions. Si l'arbre A est un arbre binaire de recherche et si B est un arbre obtenu par rotation de l'arbre As, la greffe A[sB] est un arbre binaire de recherche. Pour dÈployer l'arbre A ‡ partir des, on applique les rËgles suivantes : a) sisdÈployer(A;est la racine de l'arbre A,s) = A: b) RËglezig. Si AsdÈployer(A;est le fils gauche de la racine de l'arbre A,s) = rotationDroite(A): c) RËglezag. Si AsdÈployer(A;est le fils droit de la racine de l'arbre A,s) = rotationGauche(A): Si les conditions prÈcÈdentes ne sont pas vÈrifiÈes, le sommets‡ un pËrepet un grandpËregp. d) RËglezigzig. Sipest le fils gauche degpet sisest le fils gauche dep, dÈployer(A;s) = dÈployer(A[gprotationDroiteDroite(Agp)];s): e) RËglezagzag. Sipest le fils droit degpet sisest le fils droit dep, dÈployer(A;s) = dÈployer(A[gprotationGaucheGauche(Agp)];s): f) RËglezagzig. Sipest le fils gauche degpet sisest le fils droit dep, dÈployer(A;s) = dÈployer(A[gprotationGaucheDroite(Agp)];s): g) RËglezigzag. Sipest le fils droit degpet sisest le fils gauche dep,
lo42  final A2005  page2/3
UTBM
le 16 janvier 2006
dÈployer(A;s) = dÈployer(A[gprotationDroiteGauche(Agp)];s): Par exemple, si on dÈploie ‡ partir du sommet 1 4 41 dans l'arbre, l'application des rËgles provoque une rotation droitedroite en 3, suivie d'une3 14 rotation droite en 4 : 2 22 1 33 1) Ecrivezla fonctionrotationDroiteDroite, de signatureABR rotationDroiteDroite(ABR a), qui rÈalise la rotation vue cidessus. (Vous n’utiliserez pasrotationDroite). 2) Dansla procÈdure dÈployer nous tavaillons sur le pËre et le grandpËre. On Introduit un champperedans la structure de base de l’arbre, modifiez votre fonctionrotationDroiteDroitepour en tenir compte. 3) Ecrivezla fonctionABR greffer(ABR A, s, B) 4) Supposonsdisponibles les fonctionsrotationGauche,rotationDroite,rotationGaucheGauche, rotationGaucheDroite,rotationDroiteGaucheet bien s˚rrotationDroiteDroite. Etudiez et Ècrivez la sÈquence de dÈtermination de la rotation nÈcessaire. Expliquez pourquoi on ne peut utiliser la fonction greffer Ècrite plus haut une fois la rotation faite. Ecrivez la fonctionABR dÈployer(ABRA, s)
lo42  final A2005  page3/3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.