Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

  Page 1 LIFAP3 : Algorithmique et programmation avancée Fascicule de travau

  Page 1 LIFAP3 : Algorithmique et programmation avancée Fascicule de travaux dirigés et de travaux pratiques Nicolas Pronost  Université Claude Bernard Lyon 1 Notes :   Page 2 Table des matières Travaux dirigés ................................................................................................................................ 3 TD1 : Vie et mort des variables en mémoire (1/2) ................................................................................................................................. 4 TD2 : Vie et mort des variables en mémoire (2/2) ................................................................................................................................. 7 TD3 : Classe et objet (1/2) ................................................................................................................................................................................ 9 TD4 : Classe et objet (2/2) ............................................................................................................................................................................. 10 TD5 : Algorithme, invariant de boucle et complexité (1/2) .............................................................................................................. 12 TD6 : Algorithme, invariant de boucle et complexité (2/2) .............................................................................................................. 14 TD7 : Tri fusion (1/2) ........................................................................................................................................................................................ 15 TD8 : Tri fusion (2/2) ........................................................................................................................................................................................ 16 TD9 : Tableau dynamique ............................................................................................................................................................................. 17 TD10 : Liste chaînée ......................................................................................................................................................................................... 18 TD11 : Pile et file ............................................................................................................................................................................................... 20 TD12 : Arbre binaire ........................................................................................................................................................................................ 21 Travaux pratiques ......................................................................................................................... 22 TP1 : De LIFAP1 à LIFAP3… ........................................................................................................................................................................... 23 TP2 : Vie et mort des variables en mémoire .......................................................................................................................................... 28 TP3 : Classe et objet ........................................................................................................................................................................................ 31 TP4 : Fichier et complexité expérimentale .............................................................................................................................................. 33 TP5 : Tableau dynamique .............................................................................................................................................................................. 35 TP6 : Liste doublement chaînée .................................................................................................................................................................. 37 TP7 : Pile et file .................................................................................................................................................................................................. 39 TP8 : Arbre binaire de recherche ................................................................................................................................................................ 41 Annexes .......................................................................................................................................... 43 Annexe A : Commandes Linux usuelles ................................................................................................................................................... 44 Annexe B : Tirage de nombres aléatoires ............................................................................................................................................... 45 Annexe C : Mesure de temps d’exécution .............................................................................................................................................. 46   Page 3 Travaux dirigés Notes :   Page 4 TD1 : Vie et mort des variables en mémoire (1/2) : Procédure récursive sur un tableau Considérons le programme C++ suivant : #include <iostream> using namespace std; void mystere(double t[], int a, int b) { double aux; if (a < b) { aux = t[a]; t[a] = t[b]; t[b] = aux; mystere(t, a+1, b-1); } else { /* dessiner l’état de la mémoire */ } } int main() { double monTab[4] = {9.0, 10.0, 11.0, 12.0}; int i; mystere(monTab, 0, 3); cout << "Tableau apres traitement :\n"; for (i = 0; i < 4; i++) cout << "monTab["<< i <<"] = "<< monTab[i] << endl; return 0; } a. Que fait la procédure mystere ? Autrement dit, si vous deviez lui donner un nom plus explicite, lequel choisiriez-vous ? b. Dessinez l’état de la pile au moment indiqué en commentaire. Vous utiliserez le modèle théorique de pile vu en cours. Vous supposerez que la valeur de retour du main est stockée à l’adresse 3 987 546 988. : Tableaux de structures et fonction récursive Soit le programme C++ suivant : #include <iostream> #include <math.h> using namespace std; struct Point { double x; double y; };   Page 5 double dist (Point p1, Point p2) { return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); } double longueurchemin (const Point * chemin, int nb) { /* Préconditions : chemin est un tableau contenant au moins nb points, avec nb superieur ou égal à 2 Résultat : retourne la longueur du chemin de points */ double res; double d1, d2; if (nb==2) res = dist(chemin[1],chemin[0]); else { d1 = dist(chemin[nb-1],chemin[nb-2]); d2 = longueurchemin(chemin,nb-1); res = d1 + d2; } return res; } int main() { double perimetre; Point cheminTriangle[4]; cheminTriangle[0].x = 0.0 ; cheminTriangle[0].y = 0.0 ; cheminTriangle[1].x = 3.0 ; cheminTriangle[1].y = 0.0 ; cheminTriangle[2].x = 3.0 ; cheminTriangle[2].y = 1.0 ; cheminTriangle[3].x = cheminTriangle[0].x ; cheminTriangle[3].y = cheminTriangle[0].y ; perimetre = longueurchemin(cheminTriangle, 4); cout << "Le perimetre du triangle vaut " << perimetre << endl; return 0; } a. Combien d’octets une variable de type Point occupe-t-elle en mémoire (sur une machine où un int occupe 4 octets et un double 8) ? b. Combien d’octets occupe le tableau cheminTriangle ? c. La fonction longueurchemin est-elle récursive ? Même question pour la fonction dist. d. A quoi sert le mot-clé const dans l’entête de la fonction longueurchemin ? e. Dessinez l’évolution de la pile lors de l’exécution de ce programme, en utilisant le modèle théorique de pile vu en cours. Vous supposerez que la valeur de retour du main est stockée à l’adresse 3 987 546 998. Vous ferez un dessin à chaque fois que vous êtes sur le point de sortir d’un sous-programme (i.e. après l’affectation de la valeur de retour et avant le retour au programme appelant). f. Combien de fois la fonction longueurchemin est-elle appelée ? Même question pour la fonction dist. g. Que pensez-vous de l’implémentation récursive de longueurchemin, en termes de ressources mémoire ?   Page 6 h. Quelle valeur obtenez-vous pour la variable perimetre ? Indication : √10 ≈3.162   Page 7 TD2 : Vie et mort des variables en mémoire (2/2) : Pointeurs et tableaux en C++, arithmétique des pointeurs int monTab[] = {-25, -6, 8, 15, 38, 50, 72, 81, 98}; int * p = monTab; Quelles valeurs ou adresses fournissent les expressions suivantes ? a. *p+2 b. p+2 c. *(p+2) d. &p e. &monTab[4] - 3 f. monTab+3 g. &monTab[7] - p h. *(p+8) - monTab[7] : Pointeurs et allocation dynamique de mémoire Soit le programme C++ suivant : #include <iostream> /* entrées-sorties avec cin et cout */ using namespace std; int main() { int e = 10; double r = 3.14; int * p1; double * p2; int i; p1 = new int [5]; if (p1 == NULL) { cout << "Allocation ratee \n"; exit(1); } p2 = new double; if (p2 == NULL) { cout << "Allocation ratee \n"; exit(1); } for (i=0; i < 5; i++) { p1[i] = e-i; } *p2 = r; /* Faire la trace mémoire (1) */ (*p1)*=5; *p2=p1[3]*2.0; /* Faire la trace mémoire (2) */ e = 25; r = -8.3; /* Faire la trace mémoire (3) */   Page 8 delete [] p1; delete p2; /* Faire la trace mémoire (4) */ return 0; } a. Expliquez ce que signifie l’instruction p1 = new int [5]; b. Proposez une autre façon d’écrire l’instruction (*p1)*=5; c. Faites les quatre traces mémoire de ce programme, en supposant que la valeur de retour du main est stockée à l’adresse 3 566 758 966 et qu’il n’y a pas de problème d’allocation mémoire. : Appel à une fonction qui retourne un tableau Dessinez l’état de la pile et du tas aux endroits indiqués en commentaires. Vous utiliserez le modèle théorique de pile vu en cours et au TD précédent. Vous supposerez que la valeur de retour du main est stockée à l’adresse 3 987 546 988 et qu’il n’y a pas de problème d’allocation dynamique de mémoire. /* Précondition: tab1 et tab2 sont de même taille */ /* Postcondition: de la mémoire est allouée dans le tas, charge à l'utilisateur de la libérer quand il n'en a plus besoin */ float * sommeTab(const float * tab1, const float * tab2, const int taille) { int i; float * resultat = new float [taille]; for (i=0; i < taille; i++) resultat[i] = tab1[i] + tab2[i]; return resultat; /* Faire la trace mémoire (1) */ } int main() { float notes1[] = {8.5, 12.6, 14.5, 10.0, 9.1}; float notes2[] = {12.2, 5.8, 17.3, 11.7, 7.6}; float * somme = NULL; somme = sommeTab(notes1,notes2,5); /* Faire la trace mémoire (2) */ delete [] somme; return 0; }   Page 9 TD3 : Classe et objet (1/2) : Conception et spécificateur On souhaite créer un type de donnée pour représenter une personne. Cette personne est identifiée par son nom, son prénom et son numéro de sécurité sociale (numéro unique). On veut pouvoir saisir et afficher ces informations. a. Ecrivez, en C++, la classe Personne. b. Donner le programme principal, en C++, permettant de saisir puis d’afficher les informations d’une personne. c. En programmant la procédure membre d’affichage, vous avez dû choisir sous quel format la personne est affichée, et en particulier quel(s) caractère(s) de séparation utiliser entre les différentes données membres à afficher. Ecrire une deuxième version de cette procédure, utilisant le principe de surcharge, permettant de paramétrer le(s) caractère(s) utilisé(s). d. Modifier cette procédure pour qu’elle prenne une valeur de paramètre par défaut. Voyez-vous un problème ? e. Que doit-on faire pour interdire aux utilisateurs de la classe de manipuler les données membres directement ? f. Afin de permettre leur manipulation, écrivez des procédures/fonctions dont le rôle est de lire et modifier les données membres. Quels sont les avantages et inconvénients de cette conception ? g. Ecrivez un programme principal qui modifie le nom d’une personne après saisie. : Surcharge d’opérateurs On souhaite pouvoir faire des opérations mathématiques sur des points 2D. Une solution serait de définir des fonctions membres telles que void additionnerPoints(const Point2D & p). Une autre solution consiste à définir les opérateurs élémentaires pour un point 2D de telle façon à ce que l’on puisse exécuter des instructions telles que pt3=pt1+pt2;. a. Ecrire la classe Point2D avec les fonctionnalités nécessaires pour additioner, soustraire et tester l’égalité de deux points. b. Ajouter les fonctionnalités d’affectation et d’incrément préfixé (ajout de 1 à uploads/Ingenierie_Lourd/ polycop-td-tp-lifap3.pdf