.
Travaux Pratiques (TP) 6 - Informatique 1 (Algorithmique 1/Python) -
Tronc Commun MIP (Mathématiques-Informatique-Physique) - Semestre 1
Objectifs
- Utiliser les algorithmes de tri en Python pour trier des tableaux.
- Utiliser l’algorithme de recherche dichotomique en Python pour chercher une valeur dans un
tableau trié.
Exercice 1 : Le tri d’un tableau par sélection
Écrire un programme en Python permettant de trier un tableau T selon l’algorithme du tri par sélection
dans l’ordre croissant. Le programme doit afficher les étapes de tri itération par itération.
Le déroulement du processus d’exécution doit suivre les étapes suivantes :
On donne l’algorithme de tri par sélection suivant :
Algorithm 1 : Tri tab par sélection
Variables : tableau : T[n] :entier ;
n, x, i, j, posmin : entier ;
Début
écrire(”Entrez la taille du tableau T : ”) ;
lire(n) ;
Pour i 0 jusqu’à n-1 faire
écrire(”entrez la valeur de T[”, i, ”]= ”) ;
lire(T[i]) ;
FinPour
Pour i 0 jusqu’à n-2 faire
posmin i;
Pour j i+1 jusqu’à n-1 faire
si (T[j]<T[posmin]) alors
posmin j;
Finsi
FinPour
x T[posmin] ;
T[posmin] T[i] ;
T[i] x;
FinPour
Pour i 0 jusqu’à n-1 faire
écrire(T[i], ” ”) ;
FinPour
Fin
Tronc Commun MIP 1 2024-2025
# Algorithme de t r i par s e l e c t i o n
# Demander a l ’ u t i l i s a t e u r de s a i s i r l a t a i l l e du t a b l e a u
t a i l l e = i n t ( i n p u t ( ”E ntre z l a t a i l l e du t a b l e a u : ”) )
T = [0] * taille
x , i , j , posmin = 0 , 0 , 0 , 0
# S a i s i e d e s v a l e u r s dans l e t a b l e a u
f o r i in range ( t a i l l e ) :
T[ i ] = i n t ( i n p u t ( f ”Entre z l a v a l e u r de T[ { i }]= ”) )
# A f f i c h a g e du t a b l e a u avant l e t r i
p r i n t ( ”Tableau avant l e t r i : ” , T)
# T r i par s e l e c t i o n
f o r i in range ( t a i l l e = 1) :
posmin = i
f o r j in range ( i + 1 , t a i l l e ) :
i f T [ j ] < T [ posmin ] :
posmin = j
# Etape de p e r m u t a t i o n
x = T[ posmin ]
T[ posmin ] = T [ i ]
T[ i ] = x
# A f f i c h a g e de l ’ e t a p e de t r i
p r i n t ( f ”Etape { i + 1} : {T} ”)
# A f f i c h a g e du t a b l e a u t r i e
p r i n t ( ”Tableau t r i e : ” , T)
Exercice 2 : Le tri d’un tableau par insertion
Écrire un programme en Python permettant de trier un tableau T selon l’algorithme du tri par insertion
dans l’ordre croissant. Le programme doit afficher les étapes de tri itération par itération.
Le déroulement du processus d’exécution doit suivre les étapes suivantes :
Tronc Commun MIP 2 2024-2025
On donne l’algorithme de tri par insertion suivant :
Algorithm 2 : Tri tab par insertion
Variables : tableau : T[n] :entier ;
n, i, j, elt suivant : Entier ;
Début
écrire(”Entrez la taille du tableau T : ”) ;
lire(n) ;
Pour i 0 jusqu’à n-1 faire
écrire(”entrez la valeur de T[”, i, ”]= ”) ;
lire(T[i]) ;
FinPour
Pour i 1 jusqu’à n-1 faire // on commence par le 2ème élément (début de la partie non triée)
elt suivant T[i] ;
j i - 1 ; // indice du 1er élément à droite de la partie triée
Tantque ((j >= 0) ET (elt suivant < T[j])) faire
T[j+1] T[j] ; // Décalage
j j - 1;
FinTantque
T[j +1] elt suivant ; // Insertion de l’élément suivant
FinPour
Pour i 0 jusqu’à n-1 faire
écrire(T[i], ” ”) ;
FinPour
Fin
# Algorithme de t r i par i n s e r t i o n avec a f f i c h a g e d e s e t a p e s
# Demander a l ’ u t i l i s a t e u r de s a i s i r l a t a i l l e du t a b l e a u
t a i l l e = i n t ( i n p u t ( ”E ntre z l a t a i l l e du t a b l e a u T : ”) )
T = [0] * taille
i , j , elt suivant = 0 , 0 , 0
# S a i s i e d e s v a l e u r s dans l e t a b l e a u
f o r i in range ( t a i l l e ) :
T[ i ] = i n t ( i n p u t ( f ”Entre z l a v a l e u r de T[ { i }]= ”) )
# A f f i c h a g e du t a b l e a u avant l e t r i
p r i n t ( ”Tableau avant l e t r i : ” , T)
# T r i par i n s e r t i o n
f o r i in range (1 , t a i l l e ) :
e l t s u i v a n t = T[ i ]
j = i = 1
w h i l e j >= 0 and e l t s u i v a n t < T [ j ] :
T[ j + 1 ] = T [ j ] # D e c a l a g e
j == 1
T[ j + 1 ] = e l t s u i v a n t # I n s e r t i o n de l ’ e l e m e n t s u i v a n t
# A f f i c h a g e de l ’ e t a p e de t r i
p r i n t ( f ”Etape { i } : {T} ”)
# A f f i c h a g e du t a b l e a u t r i e
p r i n t ( ”Tableau t r i e : ” , T)
Tronc Commun MIP 3 2024-2025
Exercice 3 : La recherche dichotomique
Écrire un programme en Python qui effectue la recherche d’une valeur V dans un tableau trié par
ordre croissant T, en suivant l’algorithme de recherche dichotomique.
Exemple : Prenant un tableau trié T de 6 éléments et la valeur recherchée V=10 :
L’algorithme de recherche dichotomique fourni est le suivant :
Algorithm 3 : Recherche dichotomique
Variable : tableau : T[n] : entier
V, inf, sup, mil, n, i : entier
Début
Pour i 0 jusqu’à n-1 faire
écrire(” Entrez la valeur de T[”,i,”]= ”) ;
lire(T[i]) ;
Finpour
écrire (”Donner la valeur à rechercher :”) ;
lire (V) ;
inf 0;
sup n-1 ;
mil (inf+sup)/2 ;
Tantque (inf<=sup et V<>T[mil]) faire
Si (V<T[mil]) alors
sup mil-1 ;
Sinon
inf mil+1 ;
Finsi
mil (inf+sup)/2 ;
Fintantque
Si (T[mil] = V) alors
écrire (”la valeur ”, V , ” existe dans le tableau T en position ”, mil) ;
Sinon
écrire (”La valeur de ”, V, ” n’existe pas dans le tableau”) ;
Finsi
Fin
Tronc Commun MIP 4 2024-2025
# Algorithme de r e c h e r c h e d i c h o t o m i q u e
# Variables
T = []
V, i n f , sup , mil , n , i = 0 , 0 , 0 , 0 , 0 , 0
# Demander a l ’ u t i l i s a t e u r de s a i s i r l a t a i l l e du t a b l e a u
n = i n t ( i n p u t ( ”En tre z l a t a i l l e du t a b l e a u t r i e : ”) )
# S a i s i e d e s v a l e u r s dans l e t a b l e a u
f o r i in range (n) :
T. append ( i n t ( i n p u t ( f ”Entrez l a v a l e u r de T[ { i }]= ”) ) )
# Demander l a v a l e u r a r e c h e r c h e r
V = i n t ( i n p u t ( ”Donnez l a v a l e u r a r e c h e r c h e r : ”) )
# I n i t i a l i s e r l e s indices i n f e r i e u r , superieur et milieu
i n f , sup = 0 , n = 1
m i l = ( i n f + sup ) // 2
# Recherche b i n a i r e
w h i l e i n f <= sup and V != T [ m i l ] :
i f V < T[ mil ] :
sup = m i l = 1
else :
i n f = mil + 1
m i l = ( i n f + sup ) // 2
# V e r i f i e r s i la valeur a ete trouvee
i f T[ m i l ] == V:
p r i n t ( ”La v a l e u r ” , V, ” e x i s t e dans l e t a b l e a u T en p o s i t i o n ” , m i l )
else :
p r i n t ( ”La v a l e u r de ” , V, ”n ’ e x i s t e pas dans l e t a b l e a u ”)
Tronc Commun MIP 5 2024-2025
