Algorithmique

Les élèves doivent savoir
  • Écrire un algorithme de recherche d’une occurrence sur des valeurs de type quelconque.
  • Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne.
  • Écrire un algorithme de tri.
  • Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.
  • Écrire un algorithme qui prédit la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins.
  • Montrer la terminaison de la recherche dichotomique à l’aide d’un variant de boucle.
  • Résoudre un problème grâce à un algorithme glouton.

22.    Parcours séquentiel d’un tableau

Complexité des algorithmes

En programmation, certains algorithmes vont revenir très souvent : recherches dans un tableau, tri de tableaux, calculs de moyenne…. Il est important de comprendre quelles sont les méthodes les plus efficaces pour résoudre ces problèmes, à la fois du point de vue de l’écriture du code que de son exécution.

En informatique on parle de notion de « coût » d’exécution, que l’on nomme « complexité »,  qui indique grossièrement le temps d’exécution de l’algorithme.

Pour calculer cette complexité, on cherchera quelle est l’instruction qui est exécutée le plus souvent et on cherchera à savoir combien de fois cette instruction est exécutée dans deux situations :

  • Le pire des cas : si l’ensemble des données de départ doivent être traitées
  • Le cas moyen : si chaque élément de l’ensemble peut être une solution au problème.

En considérant que l’ensemble de données de départ possède « n » éléments, la complexité d’un algorithme va être donnée en fonction de ce nombre « n ».

Par exemple, s’il faut parcourir une fois toute la liste, on dira que « la complexité est en n » et donc qu’elle est « linéaire ». Par exemple, une liste de 1000 éléments nécessitera 1000 opérations.

Si l’algorithme doit imbriquer deux boucles et parcourir n fois un ensemble de données pour chaque donnée présente, « la complexité sera en n2 » et on dira qu’elle est « quadratique ». Par exemple une liste de 1000 éléments nécessitera 1 000 000 opérations.

Il existe d’autres types de complexités que nous verrons au fur et à mesure des algorithmes étudiés.

Algorithme de recherche d’occurrence

La recherche d’occurrence consiste à trouver combien de fois un élément apparaît dans un ensemble de données. Il existe des fonctions intégrées à python, ou des bibliothèques pour effectuer cet algorithme, mais il est important de comprendre comment il fonctionne, ce qui sera également le cas des algorithmes suivants.

Pour les besoins des exemples, nous allons travailler sur une liste indexée comprenant plusieurs fois un même élément et dont on cherche le nombre d’éléments identiques. On pourrait par exemple cherche dans une liste d’élèves combien ont eu la moyenne.

Le principe est de parcourir la liste et d’incrémenter un index à chaque fois que l’on trouve l’élément cherché. Il faut donc utiliser une boucle « for » et parcourir tout l’ensemble de données, ce qui donne une complexité linéaire.

Voici un exemple de fonction de recherche d’occurrence dans une liste indexée à une dimension :

def occurence(liste,recherche):
     occ = 0
     for element in liste:
         if element == recherche:
             occ += 1
     return occ
 assert occurence([1,2,3,5,1,6,7,1],1)==3

La dernière ligne sert à tester notre fonction pour vérifier qu’elle donne le résultat escompté, comme nous l’avons déjà vu dans un chapitre précédent.

Recherche d’un extremum

Rechercher un extremum consiste à trouver le plus grand ou le plus petit élément dans un ensemble de données.

La fonction est très proche de la recherche d’occurrence, à la différence près que l’on va comparer par rapport au premier élément de l’ensemble de données et que l’on va conserver dans une variable le plus grand (ou le plus petit, selon ce que l’on cherche) élément de l’ensemble.

Il faut donc parcourir tout l’ensemble de données une fois, ce qui donne encore une complexité linéaire.

def extremum(liste):
     plusgrand = liste[0]
     for element in liste:
         if element > plusgrand:
             plusgrand = element
     return plusgrand
 assert extremum([1,2,3,5,1,6,7,1])==7

On voit ici qu’un test est fait pour chaque élément de la liste. Si celui-ci est plus grand, on remplace le contenu de la variable « plusgrand » par cette nouvelle valeur.

Calcul de moyenne

Pour calculer une moyenne, il suffit d’additionner les éléments d’une liste (numérique) et de diviser par le nombre d’éléments de cette liste que l’on obtient par la fonction « len(liste) ».

Il faut également parcourir l’ensemble de données une fois entièrement, ce qui donne une complexité linéaire.

L’exemple qui suit est la version la plus simple possible de cet algorithme, mais il serait possible de rajouter des coefficients ou d’insérer des conditions pour ne pas prendre en compte certaines valeurs.

def moyenne(liste):
     somme = 0
     for element in liste:
         somme = somme + element
     return somme/len(liste)
 assert moyenne([10,20,15])==15

23.    Trier une liste

Méthodes de tri

Quand une liste indexée contient des éléments dans le désordre, il est souvent nécessaire d’en effectuer le tri. Python comprend la méthode « sort() » qui implémente une méthode de tri optimisée, aussi appelée « quick sort ». Nous allons toutefois voir deux méthodes de tri de base, plus simples, le tri par insertion et le tri par sélection.

Pour chaque méthode de tri il faudra vérifier que l’algorithme est fonctionnel en effectuant la « preuve » de sa correction. Pour cela on prendra une table exemple et on effectuera une exécution simulée de l’algorithme « à la main » en notant la valeur des variables utilisées et en essayent de prévoir tous les cas de figure.

Ce faisant on vérifiera également combien d’instructions sont nécessaires en fonction de la taille de la liste afin de déterminer la complexité de l’algorithme.

Tri par sélection du minimum

Le tri par sélection consiste à parcourir toute la liste pour trouver l’élément le plus petit. Une fois celui-ci trouvé, on échange sa place avec le premier élément de la liste avant de recommencer en parcourant la liste à partir du second élément et ainsi de suite.

Dans les représentations qui vont suivre, comme ci-dessus, le nombre en rouge représente la donnée non triée et la petite case en haut à gauche de chaque case représente l’indice de la case du tableau indexé.

Pour effectuer l’échange entre les deux éléments, on va utiliser une variable temporaire.

Dans cette méthode de tri on modifie directement l’ordre de la liste et on ne crée par de copie de celle-ci.

Si un même élément est présent deux fois dans la liste, il faudra décider si un échange aura lieu.

Le code ressemblera à celui-ci en Python :

def tri_selection_min(tableau:list):
    """
    Algorithme de tri par sélection du minimum d'un tableau
    :param tableau: tableau envoyé (list)
    :return: tableau : tableau trié (list)
    """
    for i in range(len(tableau)-1):
        # on enregistre le contenu de la première case
        valeur_origine=tableau[i]
        # on note la position de la valeur minimum
        position_mini=i
        for j in range(i+1,len(tableau)):
            if tableau[j]<tableau[position_mini]:
                position_mini=j
        # permutation des valeurs
        tableau[i]=tableau[position_mini]
        tableau[position_mini]=valeur_origine

tableau_test=[9,5,3,8,4,6,2,1,7]
tri_selection_min(tableau_test)
print(tableau_test)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

On peut faire la preuve de la bonne exécution de cet algorithme en effectuant une simulation manuelle de la façon suivante :

On voit bien ici le stockage successif de l’index de la case du tableau contenant la plus petite valeur.

L’instruction caractéristique de cet algorithme est le test  :
« if tableau[j]<tableau[position_mini]: ».
Pour un tableau contenant n éléments, les valeurs de i, j et le nombre de tests vont variés de la façon suivante :

iJNombre de tests
01 à n-1n-1
12 à n-1n-2
………
n-2n-1 à n-11

Si on additionne les tests effectués (dernière colonne), on trouve :

(n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}{2} \approx \frac{n^{2}}{2}

On dira que la complexité de cet algorithme est quadratique (de l’ordre de n2) dans tous les cas.

Tri par insertion

L’idée de ce tri est de commencer par trier le début du tableau, puis d’insérer les éléments plus petits qui suivent dans la partie déjà triée, en décalant les éléments triés d’une case vers la droite jusqu’à l’endroit non trié. On conserve la valeur à trier dans une variable clé.

def tri_insertion(tableau:list):
    """
    Algorithme de tri par insertion d'un tableau
    :param tableau: tableau envoyé (list)
    :return: tableau : tableau trié (list)
    """
    for j in range(1,len(tableau)):
        # on conserve la valeur courante dans clé
        cle=tableau[j]
        i = j-1
        # tant que i est positif et que la valeur clé
        # est plus grande, on décale vers la gauche
        while i>=0 and tableau[i]>cle:
            tableau[i+1]=tableau[i]
            i=i-1
        #on insert la clé à sa place
        tableau[i+1]=cle

On peut faire la preuve de la bonne exécution de cet algorithme en effectuant une simulation manuelle de la façon suivante :

Concernant la complexité, il faut prendre en compte deux cas de figures extrêmes : le tableau déjà trié et la tableau trié en sens inverse.

Si le tableau est déjà trié, il ne sera parcouru qu’une fois et la complexité est linéaire (d’ordre n).

Si le tableau est trié en sens inverse, il faudra parcourir entièrement la partie triée à chaque nouvel élément considéré et la complexité sera alors quadratique (d’ordre n2/2 comme pour le tri par sélection)

La plus grande probabilité est donc que ce test soit plus rapide que le tri par sélection et cela sera particulièrement vrai pour des petits tableaux ou des tableaux partiellement triés.

24.    Algorithme des k plus proches voisins

KNN : prédiction d’une classe

Un des sujets les plus importants en informatique actuelle est celui de « l’intelligence artificielle ». Bien que nous soyons encore très loin de savoir écrire des programmes qui seraient capables d’avoir des pensées autonomes, des émotions ou de mener des raisonnements complexes, il existe des algorithmes qui permettent de simuler des raisonnements simples dans des cas particuliers.

L’un de ces algorithmes est le K Nearest Neighborgs (KNN : K plus proche voisin), qui est un algorithme dit d’apprentissage machine (machine learning) supervisé.

Imaginez que vous devez apprendre à un enfant à reconnaître un chien. Pour cela vous allez lui montrer différentes sortes de chien et lui dire que ce sont des chiens, puis lui montrer des animaux qui ressemblent aux chiens, mais dont certaines caractéristiques sont différentes (taille, couleur, longueur des oreilles…) et dire que ce sont des chats, des moutons, des vaches…

Petit à petit, l’enfant va intégrer les paramètres correspondants à ce qu’est un chien : c’est de l’apprentissage supervisé.

Cela ne veut pas dire qu’il ne peut pas se tromper, s’il tombe sur un très grand chien, il pourra éventuellement ne pas le reconnaître comme tel et penser qu’il s’agit d’un autre animal.

En informatique, l’algorithme KNN va procéder de façon similaire pour résoudre des problèmes de classification (est-ce un chien ? Est-ce une personne sur une photo ?…) ou de régression (prévoir la masse à partir de la taille par exemple).

 Pour cela, l’algorithme KNN suppose que des « objets » similaires ont des propriétés proches des « objets » qui l’entourent. Il se base donc sur des caractéristiques chiffrées qui permettent de mettre des objets d’une même famille en relation en calculant la distance entre l’objet inconnu et un nombre « k » d’objets voisins et en déduisant ainsi la nature de l’objet inconnu :

Dans l’illustration ci-dessus, on cherche à savoir si l’objet inconnu est un chien ou une vache en se basant sur sa taille et sa couleur. Selon le nombre k d’objets voisins étudiés, on pourra avoir une certitude plus ou moins établie.

Le choix du nombre k de voisins considérés est primordial : il ne doit être ni trop grand, ni trop petit. S’il est trop grand, on considère finalement un ensemble très grand des données de bases et l’objet indéterminé correspond à une pondération de leurs nombres respectifs. S’il y avait plus de vaches que de chiens, un k très grand donnerait comme résultat une vache.

À l’inverse, si k est petit et que le hasard fait que le premier voisin de l’objet inconnu est une petite vache, ce chien inconnu serait pris pour une vache !

Pour calculer la distance du plus proche voisin, on effectue généralement un calcul de distance euclidienne selon le principe de Pythagore :

La distance entre deux points A(xA,yA) et B(xB,yB) se calcule avec la diagonale entre la différence des coordonnées x et la différence des coordonnées y :

d^{2}=(x_{A}-x_{B})^{2}+(y_{A}-y_{B})^{2}

donc

d=\sqrt{(x_{A}-x_{B})^{2}+(y_{A}-y_{B})^{2}}

D’après Pythagore, le carré de la diagonale du triangle rectangle est égal à la somme des carrés des deux côtés perpendiculaires :

Algorithme KNN

L’algorithme KNN fonctionne donc de la façon suivante :

  • Charger l’ensemble des données (généralement un tableau avec des données mesurables)
  • Décider de la valeur de K (nombre de voisins à considérer)
  • Pour chaque ligne de donnée
    • Calculer la distance entre l’objet inconnu et la donnée en cours
    • Enregistrer cette valeur dans une liste
  • Trier la liste des distances par ordre croissant des distances
  • Choisir les K premiers éléments de la liste
  • Déterminer le type de ces K premiers éléments et en déduire la nature de l’élément inconnu (par moyenne ou par plus grand nombre).
import math

def distance_euclidienne(reference, cible):
    """
    Calcul de la distance euclidienne entre deux points
    :param reference: point de référence
    :param cible: cible considérée
    :return: distance entre les deux
    """
    a = cible[0]-reference[0]
    b = cible[1]-reference[1]
    return math.sqrt(a*a+b*b)

def KNN(jeu_donnees, cible, k):
    """
    Algorithme du K plus proche voisin
    :param jeu_donnees: jeu de données de base
    :param cible: objet à classifier
    :param k: nombre de voisins considéré
    :return: liste des plus proches voisins
    """
    distances = []
    # déterminer les distances avec le jeu de données
    # créer un tableau de tuple avec la distance
    for donnee in jeu_donnees:
        d=distance_euclidienne(donnee,cible)
        tupdata = (d, donnee)
        distances.append(tupdata)

    # trier la table des distances
    tabletriee = sorted(distances, key = lambda donnee:donnee[0])

    # Prendre les k premières valeurs de la table triée
    proches_voisins = tabletriee[:k]

    # Renvoyer proches_voisins
    return proches_voisins  

L’exemple de code ci-dessus est un code « générique » qui ne fonctionne pas en tant que tel car il doit être adapté à l’ensemble de données de base dont il faut connaitre les paramètres.

Utilisations possibles et limites

Initialement développé par les mathématiciens Evelyn Fix et Joseph Hodges en 1951, l’algorithme KNN est couramment utilisé pour effectuer des classifications ou des régressions. Il est assez simple à mettre en œuvre, ne nécessite pas de créer un modèle complexe avec de nombreux paramètres et peut être utilisé dans de nombreux domaines.

Son principal inconvénient est qu’il devient très long à exécuter quand on augmente la taille du jeu de données et le nombre de paramètres à considérer (dans les exemples précédents, on se limitait à 2 paramètres, mais on peut en avoir beaucoup plus).

L’algorithme peut être utilisé pour faire de la classification : films par types, fleurs par caractéristiques, mots par langue… mais aussi de la prédiction avec des régressions : taille en fonction de la masse, cours de bourse en fonction d’une conjoncture, recette d’une entreprise en fonction des habitudes des clients….

Il est à noter que la distance entre les objets du jeu de donnée et l’objet considéré peut être calculée par d’autres méthodes que la distance euclidienne : par exemple sur un seul axe (en prenant la valeur absolue de xA-xB), avec les distances de Manhattan (|(x_{A}-x_{B})|+|(y_{A}-y_{B})| ) ou avec la distance de Tchebychev (max(|(x_{A}-x_{B})|,|(y_{A}-y_{B})|))

25.    Recherche dichotomique

Recherche dans un tableau trié

Dans une partie précédente nous avons vu comment trier un tableau. Une fois ce tableau trié, comment y chercher, le plus efficacement possible, une valeur ?

13815162531353942

Tableau contenant dix valeurs trié.

Une première solution serait de parcourir le tableau depuis le début, avec une boucle, pour y trouver la valeur recherchée. Mais si cette valeur se trouve en fin de tableau, nous allons perdre beaucoup de temps (car il faudra parcourir presque tout le tableau), alors même que le tableau est déjà trié et qu’il y a donc un ordre dans les données.

Nous allons donc utiliser cet ordre pour effectuer une recherche dichotomique :

  • Nous allons prendre le milieu du tableau et vérifier si la valeur à cet endroit est supérieure ou inférieure à ce que l’on cherche :
    • Si le milieu est plus petit : on cherche à droite
    • Si le milieu est plus grand : on cherche à gauche
  • Le tableau est alors divisé en deux et on ne conserve que la partie où est susceptible de se trouver la valeur
  • On recommence l’opération en divisant à nouveau le demi-tableau jusqu’à tomber sur la bonne valeur.

Si l’on implémente cet algorithme sous la forme d’une fonction de recherche, il est important de considérer également le cas où le tableau est vide de façon à ne pas perdre de temps et à ne pas planter le programme en cherchant à couper un tableau vide.

Enfin il est possible que l’élément recherché ne se trouve pas dans le tableau.

Voici ce que donne l’exécution de l’algorithme sur un tableau trié :

def dichotomique(liste: list,cherche : int):
    """
    Algorithme de recherche dichotomique
    :param liste: liste dans laquelle on cherche
    :param cherche: valeur cherchée
    :return: indice de l'élément cherché ou "-1" si absent
    """
    indice=-1 # si la liste est vide renverra cette valeur
    debut = 0
    fin = len(liste)-1
    while debut <= fin: #boucle de recherche
        centre = (debut+fin)//2 #donne l'indice du centre
        valeur_centre=liste[centre]
        if valeur_centre==cherche: #comparaison
            return centre
        elif valeur_centre<cherche: #on garde la droite
            debut=centre+1
        else: #on garde la gauche
            fin=centre-1
    return indice

assert dichotomique([1,2,3,4],6)==-1
assert dichotomique([1,2,3,4],3)==2

trie=[1,2,3,7,9,10,12,15,19,21,22,30,34,35,36,40,48,49]
print(dichotomique(trie,34))
print(dichotomique([],10))  
12 
-1

Preuve de la correction

Il suffit donc de 4 passage de boucle pour trouver la bonne solution.

Nous pouvons chercher quel sera le nombre d’opérations à effectuer au maximum pour trouver l’élément que l’on recherche et en profiter pour comparer la recherche dichotomique et la recherche séquentielle (qui cherche depuis le début et ensuite case par case) :

Taille liste028163264n
Séquentielle028163264n
Dichotomique024567log2(n)

On voit ici que la recherche dichotomique a une complexité en log2(n), ce qui se traduit (courbe) par un temps beaucoup plus court pour la recherche comparée à la recherche séquentielle.

26.    Algorithmes gloutons

Certains problèmes de la vie quotidienne sont parfois très difficile à résoudre pour un ordinateur, comme le rendu de monnaie ou le remplissage d’un sec par valeur et masse optimale.

Même s’ils nous semblent très intuitifs, une méthode de résolution est de procéder par une construction pas à pas en cherchant à chaque étape la solution la plus optimale et en espérant que la solution globale du problème sera également optimale.

Problème du rendu de monnaie

Voici un problème qui apparaît quotidiennement et qui peut être exprimé de la façon suivante :

« Un client donne un billet de 100 € pour acheter pour 35,28 € de marchandise. Le commerçant doit choisir le billets et pièce à rendre pour ne pas lui donner 6472 pièces de 1 cent »

Pour rendre la monnaie, le commerçant dispose des billets et pièces habituelles : 50 €, 20 €, 10€, 5€, 2€, 1€, 0.5 €, 0.2 €, 0.1€, 0.05€, 0.02 € et 0.01 €.

On veut donc rendre la monnaie en rendant le moins de pièces et de billets possibles.

La solution gloutonne va être de rendre la plus grosse valeur d’abord :

  • On rend 50 €, il reste à rendre 14,72 €
  • On rend 10 €, il reste à rendre 4,72 €
  • On rend 2€, il reste à rendre 2,72 €
  • On rend 2€, il reste à rendre 0,72 €
  • On rend 0,5 €, il reste à rendre 0,22 €
  • On rend 0,2 €, il reste à rendre 0,02 €
  • Enfin on rend 0,02 €

On voit ici que cette méthode gloutonne donne une solution optimale.

Ce ne sera toutefois pas toujours le cas : par exemple, s’il faut rendre 12 € et qu’on ne dispose que de pièces de 1, 4 et 5 euros :

  • L’algorithme glouton va proposer : 2×5+2×1, donc 4 pièces
  • La solution optimale donne : 3×4, donc 3 pièces
def RenduMonnaieGlouton (somme, listepieces):
   nbpieces=0
   rendu = []
   i=0
   while (somme!=0) & (i < len(listepieces)):
      rendu.append(somme//listepieces[i])
      nbpieces += somme//listepieces[i]
      somme=somme%listepieces[i]
      i +=1
   return (rendu,nbpieces)

def AfficherRendu (rendu, listepieces):
   i=0
   while i < len(rendu):
      if rendu[i]>0:
         print(rendu[i],"pièces de",listepieces[i]/100," €")
      i +=1
   return " "

#initialisation des variables
e=0
liste=[]
resultat=[]
nbpiecesmin=0

# les données sont lues dans un fichier texte
# les valeurs sont en cent
# la première ligne du fichier texte est la somme
# la semonde ligne est la liste de pièce séparée par une virgule
# le fichier est découpé et les pièces mises dans une liste
fichier = open("piece.txt", "r") #accès au fichier
s=int(fichier.readline()) #lecture de la somme
zeline=fichier.readline() #lecture des pièces
for e in zeline.split(','): #découpage dans une liste
   liste.append(int(e))

# affichage de la monnaie à rendre
print("Rendre la monnaie sur",s/100," Euros\n")

# chercher le résultat Glouton
resultat,nbpiecesmin=RenduMonnaieGlouton(s,liste)

print(AfficherRendu(resultat,liste))
print(nbpiecesmin," pièces rendues")
fichier.close()  

Pour résoudre ce problème en python, le plus simple est d’indiquer les valeurs des pièces, billets et sommes à rendre en centimes. De cette façon on travaille avec des entiers.

Dans l’exemple de code précédent, les valeurs à utiliser sont conservées dans un fichier texte qui est lu par le programme.

Voici ce que peut contenir ce fichier texte :

12040
5000,1000,500,400,100,50,40,20,10,1

La première ligne contient la somme à rendre et la ligne suivante contient les valeur des pièces et billets en cent.

  • Au lancement du programme, la somme est lue et conservée dans la variable « s » et les valeurs à rendre sont placées dans une liste « liste ».
  • Ces valeurs sont passées à la fonction RenduMonnaieGlouton
    • On passe alors en revue la liste des valeurs disponibles (avec une boucle while sur i, indexe de la liste).
    • On ajoute à la liste des pièces à rendre le résultat de la division entière de la somme par la valeur en cours.
    • On ajoute le nombre de pièces utilisées à une variable « nbpieces »
    • On affecte à somme le résultat du reste de la division entière (avec « % »). Si la pièce à une valeur supérieure à la somme restante, le reste est la somme restante.
  • Une fois que la liste à rendre est établie, la fonction AfficherRendu sert simplement à effectuer un affichage lisible des pièces à rendre.

Problème du sac à dos

Dans le problème du sac à dos, nous disposons d’un sac pouvant contenir une masse maximale. Par ailleurs, une pièce contient un ensemble d’objets ayant chacun une masse ainsi qu’une valeur.

Quels objets prendre afin d’emporter la plus grande valeur possible sans dépasser la masse maximale que peut emporter le sac ?

Ce problème existe en deux variantes, selon que les objets sont en exemplaires uniques ou que chaque objet peut être pris plusieurs fois.

Voici un exemple d’algorithme glouton pour le sac à dos dans le cas où un objet peut être pris plusieurs fois :

def keysort(elem):
   return elem[0]

def TriObjet (listeobjet):
   ListeTemp = []
   ratio=0
   masse=0
   valeur=0
   i=0
   for i in range(len(listeobjet)):
      masse=int(listeobjet[i][0])
      valeur=int(listeobjet[i][1])
      ratio=(valeur/masse)*100
      ListeTemp.append([int(round(ratio)),masse,valeur])
   ListeTemp.sort(key=keysort, reverse=True)
   return ListeTemp
  
def TriSac (masse, listetrie):
   ListeResultat = []
   poids=masse #pour faire hurler les physiciens !
   i=0
   while (poids!=0) & (i < len(listetrie)):
      ListeResultat.append(poids//listetrie[i][1])
      poids=poids%listetrie[i][1]
      i +=1
   return (ListeResultat,poids)

def AfficherRendu (listesac, listeobjet):
   i=0
   valeur=0
   while i < len(listeobjet):
      if listesac[i]>0:
         print(listesac[i],"objets de masse ",listeobjet[i][1]," et de valeur ",listeobjet[i][2])
         valeur += listesac[i]*listeobjet[i][1]
      i +=1
   print("Valeur totale des objets : ",valeur)
   return " "
        
#Lecture dans un fichier :
# ligne 1 : Masse,
# Lignes suivantes : les couples d'objets : Masse,Valeur

fichier = open("sac.txt", "r")
e=0
f=0
liste=[]
tmp=[]
s=int(fichier.readline())
masse=s
z=fichier.readline().rstrip('\n\r').split(',')
while e < len(z):
   tmp=[int(z[e]),int(z[e+1])]
   liste.append(tmp)
   e += 2
print("Masse maximum du sac",s," kilogrammes\n")
ListeObjetsTriee=TriObjet(liste)
Resultat,masse=TriSac(s,ListeObjetsTriee)
print(AfficherRendu(Resultat,ListeObjetsTriee))
print("Masse restante dans le sac : ",masse," kilogrammes\n")
fichier.close()  
Masse maximum du sac 677  kilogrammes   
96 objets de masse  7  et de valeur  45 
1 objets de masse  4  et de valeur  9 
Valeur totale des objets :  676   
Masse restante dans le sac :  1  kilogrammes

La compréhension de ce code fera l’objet d’une séance de travaux dirigés.

Chapitre précédentChapitre suivant