Exercice Trouver le K plus petit élément dans un tableau T
Enoncé :
Ecrire un algorithme qui permet de remplir un tableau T de N entiers positifs de 3 chiffres , de chercher et d’afficher le Kième plus petit élément s’il existe et l’indice de sa première apparition dans le tableau T
L’objectif est de trouver le k-ième plus petit élément dans un tableau sans trier le tableau, puis d’afficher sa première position. Le processus consiste à exclure successivement les plus petits éléments jusqu’à atteindre le k-ième
#Programme Principale
Algorithme K_app
debut
Ecrire("donner la taille du tableau")
lire(N)
Remplir(N)
Min_Tab(T)
Max_Tab(T)
Modifier(T,n,m)
Premier_apparition(T, n)
Kieme(T,K)
Fin.
Commencez par saisir et remplir le tableau t avec les contrôles du saisie
Procédure Remplir(N: Entier)
Début
pour i de 1 à N faire
Répéter
Ecrire ("Donner l'élément ",i)
lire (X)
T[i] <-- X
jusqu'à ( X >0 ET 100<X<999)
Fin Pour
Fin
le maximum et le minimum du tableau on doit utiliser deux fonction qui ont comme type de retour un entier
Fonction Minimum( T:tab ,N: Entier) : Entier Début Min <-- T[0] pour i de 1 à N faire si T[i] < Min alors Min <-- T[i] finsi fin pour retourner Min Fin
Fonction Maximum(T: tab , N: Entier ):Entier Début Max <-- T[0] pour i de 1 à N faire si T[i] > Max alors Max <-- T[i] finsi fin pour retourner Max fin
Le module Modifier est utilisé pour remplacer un élément dans le tableau par une valeur supérieure à tous les autres éléments. Cela nous permet d’exclure cet élément des prochaines recherches.
Procédure Modifier( T:tab , n : entier , m : Entier) Début pour i de 1 à N faire Si T[i] = n Alors # l'élément a rechercher T[i] <-- m # l'élément à remplacer FinSi FinPour Fin
le module Premier_apparition() nous permet de renvoyez l’indice de l’élément
Fonction premier_apparition( T: tab , x : Entier):Entier Début r <-- -1 pour i de 1 à N faire Si T[i] = x Alors r <-- i FinSi FinPour Retourner r Fin
Le module Kieme orchestre tout le processus. Il trouve le k-ième plus petit élément en excluant progressivement les plus petits éléments
Procédure Kieme (T:Tab , K : Entier)
Début
max <-- Maximum (T)
pour i de 1 à N faire
min <-- Minimum(T)
Si i = K Alors
pos <-- premier_apparition(T,min)
Ecrire ("Le ",K,"ime élément est ",min,"à la position",pos)
Sinon
Modifier(T,min,max)
FinSi
finpour
Ecrire ("pas de K ieme élément")
Fin
