Recap algo
Tri par insertion¶
l'Algorithme¶
VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j=2
tant que j<=longueur(t): //boucle 1
i=j-1
k=t[j]
tant que i>0 et que t[i]>k: //boucle 2
t[i+1]=t[i]
i=i-1
fin tant que
t[i+1]=k
j=j+1 fin tant que
FIN
Le python¶
def tri_insertion(list):
n = len(list)
for i in range(1, n):
# Stocker la valeur courante pour insertion ultérieure
cle = list[i]
j = i - 1
# Déplacer les éléments de la liste triée vers la droite
# jusqu'à ce qu'une position appropriée pour la valeur_courante soit trouvée
while j >= 0 and cle < list[j]:
list[j + 1] = list[j]
j -= 1
# Insérer la valeur_courante à sa position correcte
list[j + 1] = cle
# Exemple d'utilisation avec le liste (merci gabrielle) t
t = [4,1,3,5,2]
print(" liste (merci gabrielle) non trié :", t)
tri_insertion(t)
print(" liste (merci gabrielle) trié :", t)
Les exercices¶
Exercice 1 1. Adapter le tri par insertion vu en cours pour trier le tableau de tuples suivants en fonction du second élément des tuples:
tab = [(5, "a"), (8, "b"), (1, "e"), (5, "d"), (7, "f"), (8, "c")]
Exercice 7
- Construire par compréhension un tableau de cent éléments aléatoires compris entre 0 et 10.
- En s’aidant du tri par insertion, écrire la fonction max_occurrences(tab: list) → int qui renvoie l’élément le plus présent dans le tableau. Indication: dans un tableau trié les éléments identiques se suivent.
tri par selection¶
l'Algorithme¶
VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i=1
tant que i<longueur(t): //boucle 1
j=i+1
min=i
tant que j<=longueur(t): //boucle 2
si t[j]<t[min]:
min=j
fin si
j=j+1
fin tant que
si min≠i :
échanger t[i] et t[min]
fin si
i=i+1 fin tant que
FIN
L'implémentation python¶
def tri_selection(tab):
n = len(tab)
for i in range(n - 1):
# Trouver l'indice du minimum non trié
indice_min = i
for j in range(i + 1, n):
if tab[j] < tab[indice_min]:
indice_min = j
# Échanger l'élément minimum avec le premier élément non trié
tab[i], tab[indice_min] = tab[indice_min], tab[i]
print(tab)
# Exemple d'utilisation avec le tableau t
t = [15, 16, 11, 13, 12]
print("Tableau non trié :", t)
tri_selection(t)
print("Tableau trié :", t)
Recherche du max et min dans une liste¶
l'Algorithme¶
VARIABLE
L=[1,3,5,-4,7]
DEBUT
min <- le premier element de la liste L
max <- le premier element de la liste L
Pour chaque élément de la liste faire
si élement est inférieur à min
min <- element
si élément est supérieur à max
max <- element
afficher min max FIN
L'implémentation python¶
L=[1,3,5,-4,7]
min=L[0]
max=L[0]
for elt in L:
if elt<min:
min=elt
elif elt>max:
max=elt
print("Le min est {} et le max est {}".format(min,max))
print(f"Le min est ${min} et le max est ${max}")
Recherche dichotomique¶
VARIABLE
t : tableau d'entiers trié
x : entier (valeur à chercher)
début : entier
fin : entier
milieu : entier
trouvé : booléen
DEBUT
début = 0
fin = longueur(t) - 1
trouvé = faux
tant que début <= fin et non trouvé: // boucle
milieu = (début + fin) / 2
si t[milieu] = x:
trouvé = vrai
sinon si t[milieu] < x:
début = milieu + 1
sinon:
fin = milieu - 1
fin si fin tant que
si trouvé:
afficher "Élément trouvé à l'index", milieu
sinon:
afficher "Élément non trouvé"
fin si
FIN
L'implémentation python¶
def recherche_dichotomique(t, x):
debut = 0
fin = len(t) - 1
trouve = False
while debut <= fin and not trouve:
milieu = (debut + fin) // 2
if t[milieu] == x:
trouve = True
elif t[milieu] < x:
debut = milieu + 1
else:
fin = milieu - 1
if trouve:
print(f"Élément trouvé à l'index {milieu}")
else:
print("Élément non trouvé")
# Exemple d'utilisation
t = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 7
recherche_dichotomique(t, x)
K plus proches voisins¶
VARIABLE
t : tableau de points (chaque point ayant des coordonnées dans un espace à d dimensions)
p : point (le point pour lequel on cherche les k plus proches voisins)
k : entier (le nombre de voisins à trouver)
distances : tableau de paires (distance, point)
i : entier
j : entier
DEBUT
distances = tableau vide
// Calculer la distance de chaque point du tableau à p
pour i de 1 à longueur(t):
distance = distance_entre(p, t[i])
ajouter (distance, t[i]) à distances fin pour
// Trier le tableau des distances par distance croissante
trier distances par le premier élément de chaque paire (distance)
// Sélectionner les k premiers éléments du tableau trié
voisins_proches = sous-tableau de distances des indices 1 à k
afficher voisins_proches
FIN
FONCTION distance_entre(p1, p2)
somme = 0
pour j de 1 à longueur(p1):
somme = somme + (p1[j] - p2[j])^2
fin pour
retourner racine_carrée(somme) FIN FONCTION
L'implémentation python¶
import math
def distance_entre(p1, p2):
return math.sqrt(sum((p1[i] - p2[i]) ** 2 for i in range(len(p1))))
def k_plus_proches_voisins(t, p, k):
distances = []
for point in t:
distance = distance_entre(p, point)
distances.append((distance, point))
# Trier par distance
distances.sort(key=lambda x: x[0])
# Sélectionner les k premiers voisins
voisins_proches = distances[:k]
return voisins_proches
# Exemple d'utilisation
t = [(1, 2), (2, 3), (3, 4), (5, 5), (1, 1)]
p = (2, 2)
k = 3
voisins_proches = k_plus_proches_voisins(t, p, k)
print("Les k plus proches voisins sont :", voisins_proches)
algorithme glouton (le sac à dos / le rendu de monnaie)¶
VARIABLE
valeurs : tableau des valeurs des objets
poids : tableau des poids des objets
capacite : entier (capacité maximale du sac à dos)
n : entier (nombre d'objets)
ratio : tableau de paires (ratio, index)
poids_total : entier
valeur_totale : entier
i : entier
DEBUT
// Calculer le ratio valeur/poids pour chaque objet
pour i de 1 à n:
ratio[i] = (valeurs[i] / poids[i], i)
fin pour
// Trier les objets par leur ratio valeur/poids décroissant
trier ratio par le premier élément de chaque paire (ratio) en ordre décroissant
poids_total = 0
valeur_totale = 0
// Ajouter les objets au sac à dos jusqu'à atteindre la capacité maximale
pour i de 1 à n:
si poids_total + poids[ratio[i].index] <= capacite:
poids_total = poids_total + poids[ratio[i].index]
valeur_totale = valeur_totale + valeurs[ratio[i].index]
fin si fin pour
afficher "Valeur totale dans le sac à dos:", valeur_totale
FIN
L'implémentation python¶
def knapsack_glouton(valeurs, poids, capacite):
# Calculer le ratio valeur/poids pour chaque objet
ratio = [(valeurs[i] / poids[i], i) for i in range(len(valeurs))]
# Trier les objets par leur ratio valeur/poids décroissant
ratio.sort(key=lambda x: x[0], reverse=True)
poids_total = 0
valeur_totale = 0
# Ajouter les objets au sac à dos jusqu'à atteindre la capacité maximale
for r, i in ratio:
if poids_total + poids[i] <= capacite:
poids_total += poids[i]
valeur_totale += valeurs[i]
return valeur_totale
# Exemple d'utilisation
valeurs = [60, 100, 120]
poids = [10, 20, 30]
capacite = 50
valeur_totale = knapsack_glouton(valeurs, poids, capacite)
print("Valeur totale dans le sac à dos:", valeur_totale)
Le rendu de monnaire (A connaitre)¶
Entrées :
montant : le montant à rendre
valeurs : une liste des valeurs des pièces et billets disponibles, triée par ordre décroissant
Sorties : Une liste des pièces et billets utilisés pour rendre le montant
DEBUT
fonction rendre_monnaie_glouton(montant, valeurs):
rendu = liste vide
pour chaque valeur dans valeurs:
tant que montant est supérieur ou égal à valeur:
ajouter valeur à rendu
montant = montant - valeur
si montant != 0:
afficher "Impossible de rendre le montant avec les valeurs disponibles"
retourner rendu
def rendu_monnaie_glouton(somme_a_rendre, pieces_disponibles):
nombre_total_pieces = 0
pieces_disponibles = sorted(pieces_disponibles, reverse=True)
for piece in pieces_disponibles:
while somme_a_rendre >= piece:
somme_a_rendre -= piece
nombre_total_pieces += 1
return nombre_total_pieces
# Test avec une somme à rendre de 2,63 €
somme_test = 2.63
pieces_disponibles_test = [2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
resultat = rendu_monnaie_glouton(somme_test, pieces_disponibles_test)
print(f"Pour rendre {somme_test} €, le nombre minimal de pièces est : {resultat}")
Exercice bac epreuve pratique¶
On dispose d’un ensemble d’objets dont on connaît, pour chacun, la masse. On souhaite ranger l’ensemble de ces objets dans des boites identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacitécde la boîte. On souhaite utiliser le moins de boîtes possibles pour ranger cet ensemble d’objets.
Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun des objets dans la première boîte où cela est possible.
Par exemple, pour ranger dans des boîtes de capacitéc = 5un ensemble de trois objets dont les masses sont représentées en Python par la liste[1, 5, 2], on procède de la façon suivante :
- Le premier objet, de masse 1, va dans une première boite.
- Le deuxième objet, de masse 5, ne peut pas aller dans la même boite que le premier objet car cela dépasserait la capacité de la boite. On place donc cet objet dans une deuxième boîte.
- Le troisième objet, de masse 2, va dans la première boîte.
On a donc utilisé deux boîtes de capacitéc = 5pour ranger les 3 objets.
Compléter la fonction Pythonempaqueter(liste_masses, c)suivante pour qu’elle renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble d’objets dont les masses sont contenues dans la listeliste_masses. On supposera que toutes les masses sont inférieures ou égales à c.
def empaqueter(liste_masses, c):
"""Renvoie le nombre minimal de boîtes nécessaires pour
empaqueter les objets de la liste liste_masses, sachant
que chaque boîte peut contenir au maximum c kilogrammes"""
n = len(liste_masses)
nb_boites = 0
boites = [ 0 **for** _ **in** range(n) ]
**for** masse **in** ...:
i = 0
**while** i < nb_boites **and** boites[i] + ... > c:
i = i + 1
**if** i == nb_boites:
...
boites[i] = ...
*return** ...Exemples :
empaqueter([1, 2, 3, 4, 5], 10)
2
empaqueter([1, 2, 3, 4, 5], 5)
4
empaqueter([7, 6, 3, 4, 8, 5, 9, 2], 11)
5