Exercice 1 :
1) a) Puissance version itérative :
entier puissance(entier x, entier n){
si(n == 0){
retourner 1 ;
}sinon{
entier result = x ;
pour(entier i = 2 ; i < =n ; i++){
result *= x;
}
retourner result;
}
}
Puissance version recursive :
entier puiss(entier x, entier n){
si(n == 0){
retourner 1 ;
} sinon
Retourner x*puissance(x, n-1) ;
}
b) Application pour 3^7 :
Appel de puissance(3, 7) pour la version itérative
x = 3 et n = 7
si (7 ==0) ???? -> non
donc entier result = 3
pour(i = 2 ; i <= 7 ; i++)
i=2
result = result*x càd result = 3*3 = 9
i=3
result = result*x càd result = 9*3 = 27
i=4
result = result*x càd result = 27*3 = 81
i=5
result = result*x càd result = 81*3 = 243
i=6
result = result*x càd result = 243*3 = 729
i=7
result = result*x càd result = 729*3 = 2187
b) Application pour 3^7 version récursive :
2) a) Puissance itérative :
entier puissance(entier x, entier n){
entier result = 1 ;
tant que (n != 0{
si(n%2 ==0){
x = x*x ;
n = n/2 ;
}sinon{
result = x*result ;
n = n-1
}
}
}
puissance récursive :
entier puiss(entier x, entier n){
si(n == 0){
retourner 1 ;
} sinon si (n%2 ==0) { //càd n est paire
retourner puiss(x, n/2) * puiss(x, n/2) ;
}sinon{
retourner x*puiss(x,(n-1)/2) * puiss(x, (n-1)/2) ;
}
2)b) Puissance itérative :
Appel de la fonction -> x = 3 et n = 7
result = 1
tantque (n != 0) arrêt quand n == 0
n = 7 ; si (7 !=0) -> oui
si(n%2 ==0) càd (7%2 ==0) non
sinon result = x*result càd result = 3*1 = 3
n = n-1 càd n = 6
n = 6; si (6 !=0) oui
si(n%2 ==0) càd (6%2 ==0) oui
donc x = x*x càd x = 3*3 = 9
n = n/2 càd n = 3
n = 3 ; si (3 !=0) -> oui
si(n%2 ==0) càd (3%2 ==0) non
sinon result = x*result càd result = 9*3 = 27
n = n-1 càd n = 2
n = 2; si (2 !=0) oui
si(n%2 ==0) càd (2%2 ==0) oui
donc x = x*x càd x = 9*9 = 81
n = n/2 càd n = 1
n = 1 ; si (1 !=0) -> oui
si(n%2 ==0) càd (1%2 ==0) non
sinon result = x*result càd result = 81*27= 2187
n = n-1 càd n = 0
si n = 0 ; si (0 != 0) non donc arrêt du tant que
retourner 2187
puissance récursive :
3) Comparaison de complexité :
Méthode 1 : complexité linéaire : O(n)
Méthode 2 : complexité logarithmique O(log2(n))
Exercice 2 :
1) Un algorithme pour vérifier un tableau trié :
booléen est_trier(entier [] tab){
booléen result = vrai ;
pour(i = 0 , i < tab.taille-1 ; i++){
si(tab[i] > tab [i+1]){
retourner faux;
}
}
retourner vrai;
Appelez : est_trier(T)
Pour T = <1,2,4,5,6,9,10,13>
T.taille = 8
result = vrai;
pour(i = 0 ; i < 7; i++)
i=0
si(tab[0] > tab[1] ) càd 1>2 non
i=1
si(tab[1] > tab[2] ) càd 2>4 non
i=2
si(tab[2] > tab[3] ) càd 4>5 non
i=3
si(tab[3] > tab[4] ) -> 5>6 non
i=4
si(tab[4] > tab[5] ) -> 6>9 non
i=5
si(tab[5] > tab[6] ) -> 9>10 non
i=6
si(tab[6] > tab[7] ) -> 10>13 non
retourner result càd retourner vrai
c’est un tableau trié
2) a) algorithme de recherche linéaire :
entier rechercher_valeur(entier [] T, entier v)
pour (entier i = 0 ; i < T.taille ; i++){
si(T[i] == v){
retourner i ;
}
}
retourner -1 ;
b) Appliquons l’algorithme pour trouver 6 et 8
Recherchons 6 donc v = 6
T = [1,2,4,5,6,9,10,13]
pour(entier i = 0 ; i < 8 ; i++)
Donc
i=0
si T[i] == v càd T[0] == 6 càd 1 == 6 non
i=1
si T[i] == v càd T[1] == 6 càd 2 == 6 non
i=2
si T[i] == v càd T[2] == 6 càd 4 == 6 non
i=3
si T[i] == v càd T[3] == 6 càd 5 == 6 non
i=4
si T[i] == v càd T[4] == 6 càd 6 == 6 oui, retourner 4
Recherchons 8 donc v = 8
T = [1,2,4,5,6,9,10,13]
pour(entier i = 0 ; i < 8 ; i++)
Donc
i=0
si T[i] == v càd T[0] == 8 càd 1 == 8 non
i=1
si T[i] == v càd T[1] == 8 càd 2 == 8 non
i=2
si T[i] == v càd T[2] == 8 càd 4 == 8 non
i=3
si T[i] == v càd T[3] == 8 càd 5 == 8 non
i=4
si T[i] == v càd T[4] == 8 càd 6 == 8 non
i=5
si T[i] == v càd T[5] == 8 càd 9 == 8 non
i=6
si T[i] == v càd T[6] == 8 càd 10 == 8 non
i=7
si T[i] == v càd T[7] == 8 càd 13 == 8 non
retourner -1
L’élément 8 est non trouvé
c) la complexité est linéaire donc O(n)
3) a) algorithme de recherche dichotomique
entier R_dicho(entier [] T,entier debut, entier fin, entier v)
{
entier milieu = (debut+fin)/2;
si (T[milieu] == v)
{
retourner milieu;
}
sinon si(debut < fin)
{
si(v >= T[milieu])
{
debut = milieu+1;
si(T[debut] ==v)
retourner debut;
else
retourner R_dicho(T, debut, fin, v);
}sinon
{
fin = milieu -1;
si(T[fin] == v)
retourner fin;
sinon
retourner R_dicho(T, debut, fin, v);
}
}
retourner -1;
}
b) Appliquons l’algorithme pour rechercher 6 puis 8 :
recherche de 6 :
012345 6 7
T = [1,2,4,5,6,9,10,13]
R_dicho(T, 0, 7, 6)
deb = 0 et fin = 7
milieu = (0+7)/2 = 3
si T[milieu] = v càd T[3] == 6 càd 5 == 6 non
si deb < fin càd 0 < 7
si v> T[milieu] càd si 6 > 5 oui
deb = milieu+1 càd deb = 4
si T[deb] == v càd T[4] == 6 càd 6 == 6
retourner 4
indice trouvée est égale à 4
recherche de 8 :
012345 6 7
T = [1,2,4,5,6,9,10,13]
R_dicho(T, 0, 7, 8)
deb = 0 et fin = 7
milieu = (0+7)/2 = 3
si T[milieu] = v càd T[3] == 8 càd 5 == 8 non
si deb < fin càd 0 < 3
si v> T[milieu] càd si 8 > 5 oui
deb = milieu+1 càd deb = 4
si T[deb] == v càd T[4] == 8 càd 6 == 8 non
sinon R_dicho(T, debut, fin, v);
Appel de R_dicho(T, 4, 7, v);
milieu = (4+7)/2 = 5
si T[milieu] = v càd T[5] == 8 càd 9 == 8 non
si deb < fin càd 4 < 5
si v> T[milieu] càd si 8 > 9 non
sinon
fin = milieu -1 càd fin = 4
si T[fin] == v càd T[4] == 8 càd 6 == 8 non
sinon R_dicho(T, debut, fin, v);
Appel de R_dicho(T, 4, 4, v);
milieu = 4
si T[milieu] = v càd T[4] == 8 càd 6 == 8 non
si deb < fin càd 4 < 4 non -> arrêt de récursivité
retourner -1
la valeur 8 n’est pas trouvée dans T
c) la complexité est log2(n)
3) a) Un ABR est un arbre tel que son fils gauche est inférieur au père et son fil droit supérieur au père.
b) les opérations classiques dans un arbre binaire de recherche :
Structure Arbre{
Entier valeur ;
Arbre g ;
Arbre d ;
}
Creer_Arbre(Arbre fg, entier valeur, Arbre fd){
valeur = valeur ;
g = fg ;
d = fd ;
}
Creer_Arbre(entier valeur){
valeur = valeur ;
g = null;
d = null ;
}
afficher_prefixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher(a.valeur) ;
afficher_prefixe(a.g) ;
afficher_prefixe(a.d) ;
}
afficher_infixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher_infixe(a.g) ;
afficher(a.valeur) ;
afficher_infixe(a.d) ;
}
afficher_postfixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher_postfixe(a.g) ;
afficher_postfixe(a.d) ;
afficher(a.valeur) ;
}
afficher_profondeur(Arbre a){
File F;
F.enfiler(a);
tantque(!F.estvide()){
a = F.defiler();
afficher(a);
si(a.g != null){
F.enfiler(a.g);
}
si(a.d != null){
F.enfiler(a.d);
}
}
}
Arbre maximum(Arbre a){
//obtenir la valeur la plus à droite
}
Arbre maximum(Arbre a){
//obtenir la valeur la plus à gauche
}
Arbre supprimer(entier valeure, Arbre a){
si(a == null)
retourner a ;
si (valeur == a.valeur)
retourner InsertionApresSuppression(a) ;
si(valeur < a.valeur){
a = créer_arbre(supprimer(valeur,a.g), a.valeur, a.d)
}sinon{
a = créer_arbre(a.g, a.valeur, supprimer(valeur,a.d))
}
}
//InsertionApresSuppression()
//retourner a.d si a.g null
//retouorner a.g si a.d null
// sinon retourner le plus à gauche de fils droite ou bien le plus à droite de fils gauche
Arbre rotation_droite(Arbre a){
//faire une rotation droite
}
Arbre rotation_gauche(Arbre a){
//faire une rotation gauche
}
Booléen recherche(entier v, arbre a){
si(a == null)
retourner FAUX ;
sinon(a.valeur == v)
retourner vrai ;
sinon si (a.valeur v)
recherche(v, a.g) ;
sinon
recherche (v, a.d) ;
}
d) recherche de 6 et 8
Recherche de 6 :
Recherche de 8 :
e) l’arbre binaire a tendance à être linéaire -> complexité linéaire (non efficace)
4) a) arbre AVL est un ABR équilibré càd différence entre hauteur soit {-1 ; 0 ; 1}
b) les opérations classiques sont pareilles que ABR mais en plus, il y a :
Structure Arbre{
Entier valeur ;
Arbre g ;
Arbre d ;
int hauteurA ;
}
entier hauteur(Arbre a){
si(a == null)
retourner -1 ;
sinon
return hauteurA ;
}
Creer_Arbre(Arbre fg, entier valeur, Arbre fd){
valeur = valeur ;
g = fg ;
d = fd ;
hauteurA =1+ max(hauteur(a.g), hauteur(a.d)) ;
}
Creer_Arbre(entier valeur){
valeur = valeur ;
g = null;
d = null ;
}
afficher_prefixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher(a.valeur) ;
afficher_prefixe(a.g) ;
afficher_prefixe(a.d) ;
}
afficher_infixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher_infixe(a.g) ;
afficher(a.valeur) ;
afficher_infixe(a.d) ;
}
afficher_postfixe(Arbre a){
si(a == null)
retourner ;
sinon
afficher_postfixe(a.g) ;
afficher_postfixe(a.d) ;
afficher(a.valeur) ;
}
afficher_profondeur(Arbre a){
File F;
F.enfiler(a);
tantque(!F.estvide()){
a = F.defiler();
afficher(a);
si(a.g != null){
F.enfiler(a.g);
}
si(a.d != null){
F.enfiler(a.d);
}
}
}
Arbre maximum(Arbre a){
//obtenir la valeur la plus à droite
}
Arbre maximum(Arbre a){
//obtenir la valeur la plus à gauche
}
Arbre supprimer(entier valeure, Arbre a){
si(a == null)
retourner a ;
si (valeur == a.valeur)
retourner InsertionApresSuppression(a) ;
si(valeur < a.valeur){
a = créer_arbre(supprimer(valeur,a.g), a.valeur, a.d)
}sinon{
a = créer_arbre(a.g, a.valeur, supprimer(valeur,a.d))
}
retourner reequilibrer(a) ;
}
//InsertionApresSuppression()
//retourner a.d si a.g null
//retourner a.g si a.d null
// sinon retourner le plus à gauche de fils droite ou bien le plus à droite de fils gauche
Arbre rotation_droite(Arbre a){
//faire une rotation droite
}
Arbre rotation_gauche(Arbre a){
//faire une rotation gauche
}
Booléen recherche(entier v, arbre a){
si(a == null)
retourner FAUX ;
sinon(a.valeur == v)
retourner vrai ;
sinon si (a.valeur v)
recherche(v, a.g) ;
sinon
recherche (v, a.d) ;
}
reequilibrer(Arbre a){
a.hauteur = 1+max(hauteur(a.g), hauteur(a.d))
si(hauteur(a.g)-hauteur(a.d) == 2){
si(hauteur(a.g.g) <= hauteur(a.g.d))
//rotation gauche
//rotation droite
}
si(hauteur(a.d)-hauteur(a.g) == 2){
si(hauteur(a.d.d) <= hauteur(a.d.g))
//rotation droite
//rotation gauche
}
d) recherche de 6 et 8 :
Construction de l’arbre :
Insertion de 4 :
Insertion de 5
Insertion de 6 :
Insertion de 9 :
Insertion de 10 :
Insertion de 13 :
Recherche de 6 :
Recherche de 8 :
