Apprendre le langage C++ et se perfectionner : exercices corrigés de C++

Résumé du document

Ensemble d'exercices corrigés portant sur le langage C++ réalisé en troisième année de licence informatique. Exercices de gestion des pointeurs, d'apprentissage d'algorithmes de tri ou de gestion des priorités.

Extraits

[...] Un arbre de recouvrement est un arbre connexe avec n-1 arêtes. Tout graphe valué connexe admet un ou plusieurs arbres recouvrant. [...]

[...] T T En particulier : T T T + 1 T + 1 2T(n-1) + 1 + + 1 2T(n-1) + 1 d'où ! else{ initialisation des 2 premieres cases calculs des valeurs successives for(i=2; iFilsGauche=x x->pere=y Fin CODE : void Rotation_gauche(arbre nœud Noeud * racine = Nœud x->fd ; x.fd = y->fg ; If( y->fg !=NULL) y->fg.pere=x ; y.pere=x->pere ; If(x.pere==NULL) a.racine=y ; else { if(x==x->pere->fg) x->pere.fg=y else x->pere.fd=y } y.fg=x x.pere=y } PETERMANN Coralie 46 Effectuons maintenant une rotation droite sur l'arbre ci-dessous : On obtient l'arbre suivant : PETERMANN Coralie 47 ALGO ROTATION DROITE : Paramètres : a : arbre Données : racine , racineaux : pointeur sur Noeud Début y = x->FilsGauche ; x.FilsGauche = y->FilsDroit ; Si non est-vide(y->FilsDroit) alors y->FilsDroit.pere = x Fsi y->pere = x->pere Si est-vide(x->pere) alors a->racine=y Sinon si x=x.pere->FilsDroit alors x.pere->FilsDroit=y Sinon x.pere->FilsGauche=y Fsi Fsi y->FilsDroit=x x->pere=y Fin CODE : void Rotation_droite(arbre Noeud * racine = Nœud x->fg ; x.fg = y->fd ; If( y->fd !=NULL) y->fd.pere=x ; y.pere=x->pere ; If(x.pere==NULL) a.racine=y ; else { if(x==x->pere->fd) x->pere.fd=y else x->pere.fg=y } y.fd=x x.pere=y } PETERMANN Coralie 48 TD EXERCICE 1 : Le but est d'obtenir un arbre couvrant de valuation minimale à partir d'un graphe valué connexe/ non orienté. [...]

[...] COMPTE RENDU de TD INFO51 PETERMANN Coralie 1 SOMMAIRE TD1 Fibonacci Ackermann 1 TD2 Les graphes Tri topologique 14 TD3 Tri par tas 28 TD4 Huffmann 33 TD5 les arbres arbre couvrant de valuation minimale TD6 TD7 Algorithme de Floyd 59 TD8 Arbres rouge et noir Arbres PETERMANN Coralie 2 TD EXERCICE 1 : Soit la suite de Fibonacci. Fib(n)= 0 si si n=1 Fib(n-1) + Fib si n>2 Calculer Fib(5) Fib(5)=5 Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(1) Fib(2) Fib(1) Fib(1) Fib(0) Temps de calcul de fib(5) de façon générale : = T + T + 1 Fib(1) Fib(0) Fib(1) Fib(0) Et on sait que : T T . [...]