22bis Exos Correction
Exercice 1 : Tri par sélection⚓︎
Reprendre votre code python du tri par selection.
def tri_selection(L):
'''Prend en argument une liste et la retourne triée'''
assert type(L) is list, "Fournir un type list en argument !"
for i in range(len(L) - 1):
indice_du_min = i # l'indice temporaire du plus petit élément
for j in range(i + 1, len(L)):
# parcours de la liste partielle à la recherche de l'indice du plus petit élément de la sous-liste
if L[j] < L[indice_du_min]:
indice_du_min = j
L = echanger(L, i, indice_du_min)
return L
Donner un invariant pour chacune des deux boucles itératives de l’algorithme, afin de montrer la correction de ce tri.
Exercice 2 : Tri par insertion⚓︎
Reprendre votre code python du tri par insertion.
def tri_insertion(L):
"""
Entrée : une liste d'éléments int ou float, ou str
Sortie : la liste constituée des même éléments, triée par ordre croissant
"""
for i in range(1, len(L)):
en_cours = L[i]
j = i
# décalage des éléments de la liste
while j > 0 and L[j - 1] > en_cours:
L[j] = L[j - 1]
j -= 1
# on insère l'élément à sa place
L[j] = en_cours
return L
Donner un invariant pour chacune des deux boucles itératives de l’algorithme.
Exercice 3 - Recherche séquentielle dans une liste⚓︎
On écrit une fonction est_element qui prend en paramètres un objet a et une liste L et retourne un booléen traduisant la véracité de l’affirmation « l’objet a est un élément de la liste L ».
def est_element(a, L):
"""
Paramètres : objet a et liste L
Résultat : booléen
Exemples :
>>> element(6, [-3, 8, 6, 11])
True
>>> element(-2, [-5, 3, 0])
False
>>> element("chat", [-3, "douze", "12", 12, "chien", "chat"])
True
"""
for elt in L:
if elt == a:
return True
return False
L’algorithme fait-il ce pourquoi il est conçu ? (prouver la correction)
Exercice 4 - Recherche par dichotomie⚓︎
On écrit en Python le programme de recherche par dichotomie.
def recherche_dichotomique(liste, element):
"""
liste doit être triée dans l'ordre croissant
Renvoie True si l'élément est dans la liste, False sinon
"""
indice_debut = 0
indice_fin = len(liste) - 1
while indice_debut <= indice_fin:
indice_centre = (indice_debut + indice_fin) // 2
valeur_centrale = liste[indice_centre]
if valeur_centrale == element: # element est trouvé !
return indice_centre
elif valeur_centrale < element:# on cherche dans la seconde moitié
indice_debut = indice_centre + 1
else:# on cherche dans la première moitié
indice_fin = indice_centre - 1
return -1
L’algorithme fait-il ce pourquoi il est conçu ? (prouver la correction)
Exercice 5 - Recherche d’un extremum⚓︎
On écrit un programme en Python recherchant le plus grand élément d’une liste de flottants.
def recherche_max(liste):
"""
Paramètre : une liste de nombres
Résultat : maximum de la liste
Exemples
>>> recherche_max([11, -12, 31, 14, -8])
31
>>> recherche_max([]) is None
True
"""
if not(liste):
return None
val = liste[0]
for elt in liste:
if elt > val:
val = elt
return val
L’algorithme fait-il ce pourquoi il est conçu ? (prouver la correction)
Exercice 6 - Calcul de moyenne⚓︎
On écrit un programme en Python calculant de la moyenne d’une liste de flottants.
def moyenne(liste):
"""
Paramètre : une liste de nombres
Résultat : la moyenne des valeurs de la liste
Exemples
>>> moyenne([11, -12, 31, 13, -8])
7
>>> moyenne([]) is None
True
"""
if not(liste):
return None
somme = 0
for val in liste:
somme += val
return somme / len(liste)
L’algorithme fait-il ce pourquoi il est conçu ? (prouver la correction)
Exercice 7 - Factorielle⚓︎
On considère le programme suivant :
def factorielle(n):
i = 0
f = 1
while i < n:
i = i + 1
f = f * i
return f
- On note \(n!\) le nombre entier défini par \(n=n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1\) (on dit « n factorielle »).
- Calculer
factorielle(4)et \(4!\), puisfactorielle(7)et \(7!\). - Que fait cette fonction ?
- Calculer
- Montrer que \(f=i!\) est un invariant la boucle.
- Prouver que cet algorithme est correct.