Corrigé Algorithmique examen
Exercice 1:
Renvoie l'indice du plus grand élément du tableau
int max-ind(int tab[], int taille)
{
// on considère que le plus grand élément est le premier
int i=0, indice_max=0;
while(i < taille) Échange deux éléments d'un tableau
{
if(tab[i] > tab[indice_max])
indice_max = i;
i++; void echanger(int tab[], int x, int y)
} {
int tmp;
return indice_max;
}
tmp = tab[x];
tab[x] = tab[y];
tab[y] = tmp;
}
Version itérative
void tri_selection(int tab[], int taille)
{
int indice_max;
// à chaque tour de boucle, on va déplacer le plus grand élément
// vers la fin du tableau, on diminue donc à chaque fois sa taille
// car le dernier élément est obligatoirement correctement
// placé (et n'a donc plus besoin d'être parcouru/déplacé)
for(; taille > 1 ; taille--) // tant qu'il reste des éléments non triés
{
indice_max = max-ind(tab, taille);
echanger(tab, taille-1, indice_max);
// on échange le dernier élément avec le plus grand
}
}
VERSION RÉCURSIVE
void tri_selection_recursif(int tab[], int taille)
{
// un tableau d'un seul élément ou moins n'a pas besoin d'être trié
if(taille <= 1)
return;
echanger(tab, taille-1, max-ind(tab, taille));
// on échange le dernier élément avec le plus grand
// on rappelle la fonction en diminuant la taille du tableau
// on peut faire cela car on est certain que le dernier élément
// est le plus grand (donc plus besoin de le déplacer)
return tri_selection_recursif(tab, taille-1);
}
COMLEXITE
À la première itération, on effectue n−1 comparaisons. À la ième itération, on effectue
donc n−i comparaisons (puisque à chaque itération on décrémente la taille du tableau).
En résumé, lorsque on utilise le tri par sélection :
- On effectue environ n(n−1)/2 comparaisons ;
- On effectue environ n échanges ;
- La complexité moyenne et dans le pire des cas est quadratique Ɵ(n2) .
Exercice 2:
/* Returns true if binary tree with root as root is height-balanced */
bool isBalanced(struct node* root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if (root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);
if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
function AVL() returns true if the given tree is AVL otherwise false.
if(root == NULL)
return 1
leftheight = height(root->left)
rightheight = height(root->right)
if(abs(leftheight-rightheight) <= 1 && AVL(root->left) && AVL(root->right))
return 1
return 0
End
S 50,40,60,20,45,10,30,55,70,65,80
Exercice 3:
Liste fusion_iterative (Liste d1,Liste d2)
{
Liste d,p ;
if (d1 == NULL) return d2 ;
else if (d2 == NULL) return d1 ;
d = d1;
d1 = d1->nxt;
p=d;
while ((d1 != NULL) && (d2 !=NULL))
{
p->nxt = d2;
p = d2;
d2 = d2->nxt;
p->nxt = d1;
p = d1;
d1 = d1->nxt;
}
if (d1 == NULL) p->nxt = d2;
else p->nxt = d1;
return d;
}
Liste fusion_recursive(Liste L1, Liste L2)
{
if (L1 == NULL) return L2;
else if (L2 == NULL) return L1;
else {
recur = fusion_recursive (L1->next, L2->next);
result = L1; // one node from a
L1->next = L2; // one from b
L2->next = recur; // then the rest
return(result);
}
