Algorithme - sept exercices corrigés

Résumé du document

Ce document propose sept exercices d'Algorithme, sur les tris et dénombrement et les implémentations de pile et de file, chacun accompagné de sa correction détaillée. Voici un extrait du premier exercice portant sur le tri par dénombrement : « Le tri par dénombrement, nommé TRI – DENOMBREMENT, suppose que chacun des n éléments d'entrée est un entier de l'intervalle [1 k] tel que k est un entier naturel. Le principe consiste à déterminer, pour chaque élément x de l'entrée, le nombre d'éléments inférieurs ou égaux à x. cette information peut servir à déplacer l'élément x directement à sa position dans le tableau de sortie.

Par exemple, s'il existe 14 éléments inférieurs ou égaux à x, alors x se trouvera en sortie à la position 15. Le schéma doit être légèrement modifié pour gérer la situation dans laquelle plusieurs éléments ont la même position. Dans le tri par dénombrement, on suppose que l'entrée est un tableau A de longueur n.

Deux autres tableaux sont alors indispensables : un tableau B de longueur n qui contient la sortie triée et un tableau C de longueur k qui servira d'espace de stockage temporaire. En voici une illustration sur un tableau A = {3, 6, 4, 1, 3, 4, 1, 4} "

Extraits

[...] Pseudo code correspondant à EMPILER EMPILER , Début Succ[ x ] tête[L] tête[ L ] x Fin Pseudo code correspondant à DEPILER DEPILER ( P ) Début tête[ L ] succ[ tête[ L ] ] Fin Implémentation d'une file par une liste chainée 4 - On implémente une file à l'aide d'une liste chainée en faisant les ajouts d'u côté et les suppressions de l'autre La liste doublement chainée avec sentinelle est la mieux adaptée pour implémenter une file pseudo code correspondant à ENFILER ENFILER , Début Succ[ pred[ NIL[ F ] ] ] x pred[ x ] pred[ NIL[F ] ] succ[ x ] NIL[ F ] pred[ NIL[F] ] x Fin Pseudo code correspondant à DEFILER DEFILER Début succ[ NIL[F] ] succ[ succ[ NIL[F] ] ] pred[ succ[ succ[ NIL[F] ] ] ] Exercice 3 (polynôme) Représentation du polynôme La liste chainée correspondante, telle que décrite dans l'énoncé, est la liste simplement chainée : Algorithme SOMME_POLYNÔME , Début x tête[P] y tête[Q] z NIL tête[R] z tant que NIL) et NIL) faire si (exp[x] = exp[y]) alors exp[z] exp[x] coe[z] coe[x] +coe[y] x succ[x] y succ[y] sinon si (exp[x] > exp[y]) alors exp[z] exp[x] coe[z] coe[x] x succ[x] sinon si (exp[x] [...]

[...] En voici une illustration sur un tableau A = { Etape A Etape C Etape B Etape B Etape B Etape C Etape C Les éléments en fin d'algorithme à l'étape sont ragés dans l'ordre croissant. Exercice 2 (implémentation de pile et de file) On implémente une pile à l'aide d'une liste chainée en faisant les ajouts et les suppressions du même côté. Plus précisément en tête de liste pour éviter de parcourir toute la liste. La liste chainée la mieux adaptée pour implémenter une pile est la liste simplement chainée car les ajouts et les suppressions requièrent moins de mise à jour des pointeurs. [...]

[...] Pseudo code : MOYENNE_PILE Début Si (sommet[P] = alors Retourner la pile est vide Sinon Si (sommet[P] = alors Retourner sommet[P] ] Sinon K Pour i 2 à sommet[P] faire K k + Fin pour i Somme k Moyenne (somme) / (sommet[P]) Retourner Moyenne Fin si Fin si Fin Exercice 5 ( échange de clés au sein de listes doublement chainées ) Analyse préliminaire : On recherche tout d'abord l'objet dont le pointeur a pour successeur NIL. Cet objet est le dernier élément de la liste doublement chainée, par conséquent son prédécesseur est l'avant dernier élément de celle-ci. On effectue ensuite l'échange des clés. [...]

[...] Algorithme - sept exercices corrigés BLE DROH DIOMANDE (béni humble) SOMMAIRE PREMIERE PARTIE : EXERCICES Exercice 1 (TRI_DENOMBREMENT) Exercice 2 (implémentation de pile et de file) Exercice 3 (polynôme) Exercice 4 (moyenne d'une pile) Exercice 5 (échange de clés au sein de listes doublement chainées) Exercices 6 (pile ajouts et suppressions) Exercices 7 (file ajouts et suppressions) DEUXIEME PARTIE : SOLUTIONS DES EXERCICES Exercice 1 (TRI_DENOMBREMENT) Exercice 2 (implémentation de pile et de file) Exercice 3 (polynôme) Exercice 4 (moyenne d'une pile) Exercice 5 (échange de clés au sein de listes doublement chainées) Exercices 6 (pile ajouts et suppressions) Exercices 7 (file ajouts et suppressions) EXERCICES Exercice 1 ( TRI DENOMBREMENT ) Le tri par dénombrement, nommé TRI DENOMBREMENT, suppose que chacun des n éléments d'entrée est un entier de l'intervalle tel que k est un entier naturel. Le principe consiste à déterminer, pour chaque élément x de l'entrée, le nombre d'éléments inférieurs ou égaux à x. cette information peut servir à déplacer l'élément x directement à sa position dans le tableau de sortie. Par exemple s'il existe 14 éléments inférieurs ou égaux à alors x se trouvera en sortie à la position 15. [...]

[...] Le schéma doit être légèrement modifié pour gérer la situation dans laquelle plusieurs éléments ont la même position. Dans le tri par dénombrement, on suppose que l'entrée est un tableau A de longueur n. on a de plus besoin de deux autres tableaux à savoir : Un tableau B de longueur n qui contient la sortie triée. Un tableau C de longueur k qui servira d'espace de stockage temporaire. [...]