Exercices td algorithmique recherche et traitement dans les
Télécharger PDFRecherche dans un tableau
Trouver le maximum d'un tableau
Cet algorithme permet de trouver le plus grand élément (le maximum) dans un tableau de nombres réels. Il parcourt le tableau en comparant chaque élément à la valeur maximale trouvée jusqu'alors, et met à jour cette valeur si un élément plus grand est rencontré.
CONST TAILLE = 50
TYPE TABL = TABLEAU [1..TAILLE] DE REEL
FONCTION max_tableau(T: TABL; N: ENTIER): REEL
VAR
i : ENTIER
Maximum : REEL
DEBUT
Maximum ← T[1]
POUR i DE 2 A N FAIRE
SI (T[i] > Maximum) ALORS
Maximum ← T[i]
FINSI
FINPOUR
Retourner(Maximum)
FINCompter les valeurs négatives
Cet algorithme compte le nombre d'éléments négatifs présents dans un tableau d'entiers. Il initialise un compteur à zéro et parcourt le tableau, incrémentant le compteur pour chaque valeur inférieure à zéro.
ALGORITHME compter_Nbre_Négatives
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] d'ENTIER
VAR
T : TABL
N, i, Compteur : ENTIER
DEBUT
ECRIRE("Entrer le nombre d'éléments dans le tableau (N < ", TAILLE, ")")
LIRE(N)
SAISIR(T, N)
Compteur ← 0
POUR i DE 1 A N FAIRE
SI T[i] < 0 ALORS
Compteur ← Compteur + 1
FINSI
FINPOUR
ECRIRE("Le nombre des valeurs négatives est : ", Compteur)
FINUne alternative pour la boucle de parcours du tableau serait d'utiliser une boucle TANTQUE :
Compteur ← 0
i ← 1
TANTQUE (i ≤ N) FAIRE
SI T[i] < 0 ALORS
Compteur ← Compteur + 1
FINSI
i ← i + 1
FINTANTQUERechercher l'élément le plus proche
Cet algorithme trouve l'élément d'un tableau qui est le plus proche en valeur d'un entier donné. Il affiche cet élément ainsi que son indice dans le tableau.
Exemple :
Tableau T : [15, -1, 22, 25, 34, 13]
Entier donné : 23
Résultat attendu :
L'élément le plus proche est : 22
Son indice est : 3L'idée est de calculer la différence absolue entre l'entier donné et chaque élément du tableau, puis de retenir l'élément pour lequel cette différence est minimale.
ALGORITHME PLUSPROCHE
CONST TAILLE = 50
TYPE TABL = TABLEAU [1..TAILLE] de REEL
VAR
T : TABL
Element_donne, Difference_min : REEL
N, i, Indice_proche : ENTIER
DEBUT
ECRIRE("Entrer le nombre d'éléments du tableau (N < ", TAILLE, ")")
LIRE(N)
SAISIR(T, N)
ECRIRE("Entrer un élément à comparer :")
LIRE(Element_donne)
Difference_min ← ABS(T[1] - Element_donne)
Indice_proche ← 1
POUR i DE 2 A N FAIRE
SI Difference_min > ABS(T[i] - Element_donne) ALORS
Difference_min ← ABS(T[i] - Element_donne)
Indice_proche ← i
FINSI
FINPOUR
ECRIRE("L'élément le plus proche est : ", T[Indice_proche], " son indice est ", Indice_proche)
FINRechercher la plus longue suite de caractères identiques
Cet algorithme permet de trouver la suite la plus longue de caractères identiques consécutifs dans un tableau de caractères. Il affiche le caractère concerné et le nombre de fois qu'il est répété.
Exemple : Pour le tableau [b, c, c, d, a, b, a, b, b, b, x, x, b], la plus longue suite est 'b' répétée 3 fois (indices 8, 9, 10).
ALGORITHME chaine_plus_longue
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] de CARACTERE
VAR
T : TABL
Premier_car_actuel, Car_plus_long : CARACTERE
i, Compteur_actuel, Nbre_plus_longue : ENTIER
DEBUT
SAISIR(T, TAILLE) (* Supposons que N éléments sont saisis jusqu'à TAILLE *)
i ← 1
Nbre_plus_longue ← 0
Car_plus_long ← ' ' (* Initialisation avec un caractère par défaut *)
SI TAILLE > 0 ALORS
Nbre_plus_longue ← 1
Car_plus_long ← T[1]
FINSI
REPETER
Compteur_actuel ← 1
Premier_car_actuel ← T[i]
TANTQUE (i < TAILLE ET T[i] = T[i+1]) FAIRE
Compteur_actuel ← Compteur_actuel + 1
i ← i + 1
FINTANTQUE
SI Compteur_actuel > Nbre_plus_longue ALORS
Car_plus_long ← Premier_car_actuel
Nbre_plus_longue ← Compteur_actuel
FINSI
i ← i + 1 (* Passer au prochain caractère pour la recherche de suite *)
JUSQU’À (i > TAILLE)
ECRIRE("Le caractère de la suite la plus longue est : ", Car_plus_long)
ECRIRE("Le nombre de fois répété est : ", Nbre_plus_longue)
FINModification et tri dans un tableau
Inverser l'ordre des éléments d'un tableau
Cet algorithme permet de réorganiser les éléments d'un tableau d'entiers de manière à inverser leur ordre. Deux méthodes principales sont présentées : l'une utilisant un tableau temporaire, l'autre effectuant l'inversion directement en place.
Méthode 1 : Utilisation d'un tableau auxiliaire
Cette approche crée un nouveau tableau et y copie les éléments du tableau original dans l'ordre inverse, puis recopie ces éléments dans le tableau original.
ALGORITHME inverseTab_avec_auxiliaire
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] d'ENTIER
VAR
T, T1 : TABL
i, N : ENTIER
DEBUT
ECRIRE("Entrer le nombre d'éléments du tableau N :")
LIRE(N)
SAISIR(T, N)
POUR i DE 1 A N FAIRE
T1[i] ← T[N + 1 - i]
FINPOUR
POUR i DE 1 A N FAIRE
T[i] ← T1[i]
FINPOUR
FINMéthode 2 : Inversion en place (plus efficace)
Cette méthode inverse le tableau sans utiliser d'espace de stockage supplémentaire (en dehors de quelques variables). Elle échange les éléments symétriques par rapport au milieu du tableau.
ALGORITHME inverseTab_en_place
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] d'ENTIER
VAR
T : TABL
i, N, Milieu : ENTIER
PROCEDURE Echanger(VAR T: TABL; i, j: ENTIER)
VAR
aux : ENTIER
DEBUT
aux ← T[i]
T[i] ← T[j]
T[j] ← aux
FIN
DEBUT
ECRIRE("Entrer le nombre N :")
LIRE(N)
SAISIR(T, N)
Milieu ← N DIV 2 (* division entière *)
POUR i DE 1 A Milieu FAIRE
Echanger(T, i, N + 1 - i)
FINPOUR
FINInsérer un élément dans un tableau trié
Cet algorithme permet d'insérer un nouvel élément dans un tableau d'entiers qui est déjà trié, tout en maintenant l'ordre de tri. Si l'élément est plus grand que tous les éléments existants, il est ajouté à la fin, pourvu qu'il y ait de la place.
Exemple visuel d'insertion de 19 dans un tableau trié :
Tableau original : [-12, -3, 0, 14, 27, 28, ..., 39, 39, 126]
Élément à insérer : 19
Recherche de l'emplacement : T[i] > 19
Décalage à droite des éléments supérieurs à 19.
Tableau après insertion : [-12, -3, 0, 14, 19, 27, 28, ..., 39, 39, 126]ALGORITHME inserer_element
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] d'ENTIER
VAR
T : TABL
N, i, Element_a_inserer : ENTIER
Position_trouvee : BOOLEEN
PROCEDURE INSERER_A_POSITION(VAR T: TABL; VAR N: ENTIER; Pos: ENTIER; Val: ENTIER)
VAR
j : ENTIER
DEBUT
POUR j DE N A Pos PAR Pas -1 FAIRE
T[j + 1] ← T[j]
FINPOUR
T[Pos] ← Val
N ← N + 1 (* Augmente la taille logique du tableau *)
FIN
DEBUT
ECRIRE("Entrer le nombre d'éléments dans le tableau (N < ", TAILLE, ")")
LIRE(N)
SAISIR(T, N)
ECRIRE("Entrer l'élément à insérer :")
LIRE(Element_a_inserer)
i ← 1
Position_trouvee ← FAUX
TANTQUE (i ≤ N ET NON Position_trouvee) FAIRE
SI (T[i] > Element_a_inserer) ALORS
INSERER_A_POSITION(T, N, i, Element_a_inserer)
Position_trouvee ← VRAI
FINSI
i ← i + 1
FINTANTQUE
SI NON Position_trouvee ET N < TAILLE ALORS (* Si l'élément est le plus grand et qu'il reste de la place *)
T[N + 1] ← Element_a_inserer
N ← N + 1
FINSI
(* Un message d'erreur pourrait être ajouté si le tableau est plein et l'insertion échoue *)
FINCompter et éliminer les zéros d'un tableau
Cet algorithme parcourt un tableau d'entiers pour compter le nombre de zéros qu'il contient et les élimine en décalant les éléments suivants vers la gauche. La taille logique du tableau est ajustée en conséquence.
ALGORITHME compter_eliminer_zero
CONST TAILLE = 100
TYPE TABL = TABLEAU [1..TAILLE] d'ENTIER
VAR
T : TABL
N, i, Compteur_zeros : ENTIER
PROCEDURE decalage_gauche(VAR T : TABL; VAR N : ENTIER; Pos : ENTIER)
VAR
indice : ENTIER
DEBUT
POUR indice DE Pos A N - 1 FAIRE
T[indice] ← T[indice + 1]
FINPOUR
N ← N - 1 (* Réduit la taille logique du tableau *)
FIN
DEBUT
ECRIRE("Entrer le nombre d'éléments dans le tableau (N < ", TAILLE, ")")
LIRE(N)
SAISIR(T, N)
Compteur_zeros ← 0
i ← 1
TANTQUE (i ≤ N) FAIRE
SI T[i] = 0 ALORS
Compteur_zeros ← Compteur_zeros + 1
decalage_gauche(T, N, i) (* N est modifié dans la procédure *)
(* L'indice i ne doit pas être incrémenté ici, car l'élément suivant a pris sa place à T[i] *)
SINON
i ← i + 1
FINSI
FINTANTQUE
ECRIRE("Le nombre de zéros éliminés est : ", Compteur_zeros)
(* Le tableau T contient maintenant les éléments sans les zéros, et sa nouvelle taille est N *)
FINFusionner deux tableaux triés
Cette procédure permet de fusionner deux tableaux (A et B) qui sont déjà triés par ordre croissant en un troisième tableau (TAB_FUS) également trié par ordre croissant. Le tableau résultant aura une dimension égale à la somme des dimensions des deux tableaux originaux.
CONST MAX_TAILLE_A = 50
CONST MAX_TAILLE_B = 50
CONST MAX_TAILLE_FUS = MAX_TAILLE_A + MAX_TAILLE_B
TYPE TABLN = TABLEAU [1..MAX_TAILLE_A] DE REEL
TYPE TABLM = TABLEAU [1..MAX_TAILLE_B] DE REEL
TYPE TABLF = TABLEAU [1..MAX_TAILLE_FUS] DE REEL
PROCEDURE FUSION(VAR TAB_FUS : TABLF; A : TABLN; N_A : ENTIER; B : TABLM; N_B : ENTIER)
(* N_A et N_B sont les tailles réelles des tableaux A et B *)
VAR
i, j, k : ENTIER
DEBUT
i ← 1 (* Indice pour le tableau A *)
j ← 1 (* Indice pour le tableau B *)
k ← 1 (* Indice pour le tableau TAB_FUS *)
(* Tant qu'il y a des éléments dans les deux tableaux *)
TANTQUE (i ≤ N_A) ET (j ≤ N_B) FAIRE
SI A[i] < B[j] ALORS
TAB_FUS[k] ← A[i]
i ← i + 1
SINON
TAB_FUS[k] ← B[j]
j ← j + 1
FINSI
k ← k + 1
FINTANTQUE
(* Compléter TAB_FUS avec les éléments restants de A, s'il y en a *)
TANTQUE i ≤ N_A FAIRE
TAB_FUS[k] ← A[i]
k ← k + 1
i ← i + 1
FINFAIRE
(* Compléter TAB_FUS avec les éléments restants de B, s'il y en a *)
TANTQUE j ≤ N_B FAIRE
TAB_FUS[k] ← B[j]
k ← k + 1
j ← j + 1
FINFAIRE
FINTrier un tableau par la méthode du tri à bulle
Le tri à bulle (Bubble Sort) est un algorithme de tri simple qui parcourt le tableau plusieurs fois, en comparant les éléments adjacents et en les échangeant s'ils ne sont pas dans le bon ordre. Les plus grands éléments "remontent" progressivement vers la fin du tableau comme des bulles, d'où son nom. Il est facile à comprendre mais peu efficace pour les grands tableaux.
PROCEDURE TriBulle (VAR T : TABL; N : ENTIER)
VAR
aux, i, borne : ENTIER
Est_trie : BOOLEEN
DEBUT
borne ← N
REPETER
Est_trie ← VRAI (* Supposons que le tableau est trié pour cette passe *)
POUR i DE 1 A borne - 1 FAIRE
SI T[i] > T[i + 1] ALORS (* Compare 2 éléments successifs *)
(* Permuter les éléments *)
aux ← T[i]
T[i] ← T[i + 1]
T[i + 1] ← aux
Est_trie ← FAUX (* Une permutation a eu lieu, le tableau n'est pas encore trié *)
FINSI
FINPOUR
borne ← borne - 1 (* Le dernier élément de cette passe est à sa place finale *)
JUSQU'À (Est_trie OU borne = 1) (* Arrêter si aucune permutation n'a eu lieu ou si le tableau est entièrement parcouru *)
FINFoire aux questions (FAQ)
Qu'est-ce qu'un tableau en algorithmique ?
En algorithmique, un tableau (ou "array" en anglais) est une structure de données linéaire qui permet de stocker une collection d'éléments du même type (par exemple, des entiers, des caractères, des nombres réels) sous un nom unique. Les éléments sont organisés séquentiellement en mémoire et sont accessibles directement grâce à un indice numérique qui représente leur position.
Pourquoi est-il utile de savoir manipuler des tableaux (recherche, insertion, suppression, tri) ?
La maîtrise des manipulations de tableaux est fondamentale en programmation car ils sont des structures de données très courantes et efficaces pour organiser des informations. Savoir rechercher permet de retrouver rapidement des données spécifiques. L'insertion et la suppression sont essentielles pour gérer des collections de données dynamiques. Le tri permet d'ordonner les données, ce qui facilite grandement les recherches ultérieures (par exemple, avec une recherche dichotomique) et la présentation des informations à l'utilisateur.
Existe-t-il des méthodes de tri plus efficaces que le tri à bulle ?
Oui, le tri à bulle est l'un des algorithmes de tri les moins efficaces pour les grands ensembles de données, car sa complexité temporelle est quadratique (O(n²)). Pour des performances significativement meilleures, il existe des algorithmes comme le tri rapide (Quick Sort), le tri fusion (Merge Sort) ou le tri par tas (Heap Sort), qui offrent généralement une complexité temporelle quasi-linéaire (O(n log n)) en moyenne, les rendant beaucoup plus adaptés pour le traitement de volumes importants de données.