Langages et programmation

I- Introduction

Il est très souvent possible d'écrire des algorithmes totalement différents pour effectuer une tâche, résoudre un problème.
Comment comparer ces différentes solutions si elles donnent le même résultat ?
Le but de cette partie va être d'aborder la notion de complexité : ce qu'elle signifie et comment on la détermine.
Enfin, nous verrons comment s'assurer qu'un algorithme simple donnera toujours une solution correcte.

Afficher Partie 1 : Complexité

Cacher Partie 1 : Complexité

II- Algorithmes de recherche

Cliquez sur Fiche algorithmes01.pdf pour récupérer l'énoncé du TD.
Travail préalable : créer une fonction alea_liste(n) qui retourne une liste de n nombres entiers aléatoires xi, avec 0 ≤ xi ≤ n dans le second cas

Affiche l'algorithme

Cacher l'algorithme

Il est possible d'écrire cette fonction en une seule ligne, mais l'import de la fonction randint(début,fin) présente dans le module random est nécessaire.
from random import randint
def alea_liste(n):
	return [randint(0,n) for i in range(n)]
1) Algorithmes de parcours d'un tableau
Pour les exercices suivants, on utilisera la liste :
test=[19, 16, 28, 26, 50, 16, 0, 36, 1, 45, 38, 27, 37, 16, 45, 41, 3, 19, 49, 43, 19, 44, 40, 23, 33, 25, 30, 38, 28, 49, 31, 37, 8, 48, 34, 12, 25, 6, 37, 23, 32, 36, 44, 45, 36, 29, 17, 11, 32, 27]
  • a. Écrire une fonction indice(liste,valeur) qui retourne l’indice de la premiere occurrence de valeur dans liste.
    Exemple : indice(test,36) doit retourner la valeur 7, car test[7]=36.
  • Affiche l'algorithme

    Cacher l'algorithme

    def indice(liste,valeur):
        for i in range(len(liste)):
            if liste[i]==valeur:
                return i
        return -1
    
    Remarque : il est nécessaire de prévoir le cas où la valeur ne serait pas présente.
    Il peut être dangereux de retourner False car cela risquerait d'être considéré comme la valeur 0. D'où le choix de retourner un nombre négatif.
  • b. Écrire une fonction maximum(liste) qui retourne la plus grande valeur contenue dans liste. Quelle valeur maximum(test) doit-elle retourner ?
  • Affiche l'algorithme

    Cacher l'algorithme

    def maximum(liste):
         maxi=liste[0]
         for i in range(len(liste)):
             if liste[i]>maxi:
                 maxi=liste[i]
         return maxi
    
  • c. Écrire une fonction moyenne(liste) qui retourne la moyenne des valeurs contenues dans liste.
  • Affiche l'algorithme

    Cacher l'algorithme

    def moyenne(liste):
        somme=0
        for i in liste:
            somme+=i
        moyenne=somme/len(liste)
        return moyenne
    

    III- Evaluation du coût d'un algorithme

    1) Mesure expérimentale
    Le module time contient une fonction time_ns() retournant le temps écoulé en nanosecondes depuis le 01/01/1970. Il est possible grâce à elle d’évaluer le temps que met une série d’instructions à se réaliser :
  • a. En combien de temps moyenne(test) s’est executé ?
  • b. Mesurer maintenant le temps que met moyenne(test) pour des listes plus grandes (générées à l’aide alea_liste(n))
  • c. Que constatez-vous ? Les résultats sont-ils toujours les mêmes ?
  • Affiche l'algorithme

    Cacher l'algorithme

    from time import time_ns
    def bench(fonction,liste):
        
        chrono=time_ns()
        fonction(liste)
        return time_ns()-chrono
    
    Avec la fonction précédente, on se rend compte qu'il est impossible sur une machine récente de mesurer le temps que met la fonction moyenne(liste) à s'executer !
    Il est donc nécessaire d'utiliser des listes plus longues pour pouvoir mesurer le temps d'execution :
    from time import time_ns
    from matplotlib import pyplot as plt
    
    def bench(fonction,l_liste):
        liste=alea_liste(l_liste)
        chrono=time_ns()
        fonction(liste)
        return time_ns()-chrono
    
    def bench_fonctions(liste_fonctions,depart,fin,pas,nb_tests=1,labels=False):
        k=0
        plt.ylabel("temps (ns)")
        plt.xlabel("nombre d'éléments")
        for fonction in liste_fonctions:
            x=[]
            y=[]
            increment=depart
            while increment<fin:
                print(increment)
                increment+=pas
                x.append(increment)
                y.append(moyenne([bench(fonction,increment) for i in range(nb_tests)]))
            if labels is False:
                lab=str(k)
            else:
                lab=labels[k]
            plt.plot(x,y,label=lab)
            k+=1
            #recherche relation de proportionnalité par méthode des moindres carrés
            sum_xi2,sum_xi_yi=0,0
            for i in range(len(x)):
                sum_xi2 +=x[i]**2
                sum_xi_yi +=x[i]*y[i]
            a=sum_xi_yi/sum_xi2
            plt.plot(x,[a*x[i] for i in range(len(x))])
    		#fin du tracé de la droite
        plt.legend(loc="upper left")
        plt.show()
    
    La fonction bench_fonctions va tester une liste de fonction sur un pour des valeurs à définir, puis tracer le graphe du temps de calcul en fonction de la longueur de la liste.
    En utilisant les fonctions précédentes, et en lançant la commande
    bench_fonctions([moyenne],100,1e5,1000,10,["temps de calcul"])
    on obtient le graphique suivant :
    graphique représentant le temps de calcul de la moyenne en fonction du nombre d'éléments d'une liste
    On remarque que si les valeurs sont irrégulières (en effet un ordinateur effectue beaucoup d'autres tâches pendant qu'il exécute un script en python), elles sont cependant en accord avec une relation de proportionnalité : Le temps d'éxécution semble proportionnel au nombre d'éléments présents dans la liste.
    2) Vérification
    Il n'est pas possible à notre niveau de déterminer exactement combien de temps va prendre le calcul dans le cas de python et d'un ordinateur de bureau, cependant on peut compter le nombre d'opération que fait l'algorithme dans le cas d'une moyenne.
    → Pour chaque indice de la liste en entrée, il va ajouter à la variable somme la valeur présente à l'indice. Il réalise cette opération n fois et on suppose qu'elle prend un temps t1. Ensuite, il divise somme par le nombre d'éléments, cela prend un temp t2.
    On a donc un temps total de l'ordre de :
    ttotal = n × t1 + t2
    Si n est suffisamment grand, on peut négliger le temps pris par la division, on retrouve bien un temps proportionnel au nombre d'éléments.
    On dit alors que la complexité est en O(n) ("grand O (la lettre o) de n").
    On ne connait pas forcément le coefficient de proportionnalité, qui dépend notamment des caractéristiques de la machine, mais on peut affirmer que si un calcul pour n éléments (et n suffisamment grand) a pris un temps t alors pour 2×n éléments, le calcul prendra un temps 2×t.

    IV- Algorithmes de tri

    Il existe plusieurs façons de trier une liste :
    • Le tri par sélection
      Celle qui me semble la plus simple est de chercher le maximum d’une liste, puis une fois celui-ci trouvé, échanger sa position avec l’élément en première position de la liste (tri décroissant) ou dernière position (tri croissant).

      Affiche l'algorithme

      Cacher l'algorithme

      En pseudo-code cela donne :
      	procédure tri_selection(tableau t)
      		n ← longueur(t) 
      		pour i de 0 à n - 2
      			min ← i       
      			pour j de i + 1 à n - 1
      				si t[j] < t[min], alors min ← j
      			
      			si min ≠ i, alors échanger t[i] et t[min]
      	
    • Le tri par insertion
      on peut aussi prendre consécutivement les éléments de la liste et les remplacer correctement un à un parmi les éléments déjà ordonnés de la liste.

      Affiche l'algorithme

      Cacher l'algorithme

      	procédure tri_insertion(tableau T)
      	   n ← taille(T)
      	   pour i de 1 à n - 1
      
      		  # mémoriser T[i] dans x
      		  x ← T[i]                            
      
      		  # décaler vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que x en partant de T[i-1]
      		  j ← i                               
      		  tant que j > 0 et T[j - 1] > x
      			   T[j] ← T[j - 1]
      			   j ← j - 1
      
      		   # placer x dans le "trou" laissé par le décalage
      		   T[j] ← x 
      	
    • Le tri à bulles
      On peut enfin balayer progressivement la liste en inversant 1 à 1 chaque couple de nombres consécutivement de façon à ce qu’ils soient dans l’ordre de rangement, et cela jusqu’à ce que la liste soit ordonnée.

      Affiche l'algorithme

      Cacher l'algorithme

      	procédure tri_insertion(tableau T)
      	   n ← taille(T)
      	   pour i de 1 à n - 1
      		  # mémoriser T[i] dans x
      		  x ← T[i]                            
      		  # décaler vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que x en partant de T[i-1]
      		  j ← i                               
      		  tant que j > 0 et T[j - 1] > x
      			   T[j] ← T[j - 1]
      			   j ← j - 1
      		   # placer x dans le "trou" laissé par le décalage
      		   T[j] ← x 
      	
    Implémenter ces 3 algorithmes en python

    Affiche l'algorithme

    Cacher l'algorithme

    def tri_selection(liste):
        for i in range(len(liste)):
            maxi=liste[0]
            indice=0
            for j in range(len(liste)-i):
                if liste[j]>maxi:
                    maxi=liste[j]
                    indice=j
            liste[indice],liste[len(liste)-i-1]=liste[len(liste)-i-1],liste[indice]
        return liste
    
    def tri_insertion(liste):
        for i in range(1,len(liste)):
            temp=liste[i]
            for j in range(1,i):
                if liste[i]<liste[j]:
                    for k in range(i-j):
                        liste[k+1]=liste[k]
                    liste[j]=temp
                    break
        return liste
    
    def tri_bulle(liste):
    
        for i in range(len(liste)):
            for j in range(len(liste)-i-1):
                if liste[j+1]<liste[j]:
                    liste[j+1],liste[j]=liste[j],liste[j+1]
        return liste
    Ces trois algorithmes retournent une liste correctement ordonnée, comment les classer ?
  • Par taille, on constate que le tri à bulle est le plus concis
  • Par nombre de calculs, on constate que le tri à bulles recommence systématiquement et inverse les positions une à une, là où les deux autres algorithmes n'inversent qu'un certain nombre de valeurs, voire une seule.
  • Par temps d'exécution : il est possible d'utiliser la fonction
    bench_fonctions([tri_selection,tri_insertion,tri_bulle],125,2.5e3,125,10,["tri par sélection","tri par insertion","tri à bulles"]).
  • On obtient alors le graphique suivant :
    graphique représentant le temps de tris pour les 3 algorithmes en fonction du nombre d'éléments
    Le tri à bulles est (beaucoup) plus lent que les deux autres méthodes !
    On remarque également que le temps de calcul n'est plus proportionnel au nombre d'éléments de la liste mais augmente plus vite que le nombre d'éléments.
    Pour voir si ce temps augmente bien en fonction de n2, il suffit de changer l'axe vertical : au lieu de tracer t en fonction de n, on peut tracer √t en fonction de n.
    Dans cette représentation, les relations proportionnelle à n2 sont visibles :
    graphique représentant le temps de tris pour les 3 algorithmes en fonction du nombre d'éléments
    Même si le tri à bulles est le moins efficace, ces trois tris ont une complexité en O(n2)
    Remarque :
    Ces 3 tris ne sont pas considérés commes efficaces, il existe des tris bien plus rapides, comme le tri fusion ou le tri rapide dont la complexité est inférieure à O(n2).
    graphique représentant le temps de tris pour les 3 algorithmes en fonction du nombre d'éléments

    Afficher Partie 2 : Dichotomie & Glouton

    Cacher Partie 2 : Dichotomie & Glouton

    V- Recherche par dichotomie

    Cliquez sur Fiche dichotomie.pdf pour récupérer l'énoncé du TD.
    1) Akinator
    Vous jouez à essayer de deviner le nombre auquel pense votre adversaire : en début de partie, celui-ci pense à un nombre entre 0 et 100, le note sur une feuille qu’il retourne (pour éviter la triche). Vous devez trouver ce nombre en un minimum de propositions. L’adversaire ne peut dire que "c’est plus", "c’est moins" et "bravo".
    1. Essayez de décrire votre stratégie.
    2. En justifiant votre réponse, indiquez quel serait le nombre minimum de questions à poser afin de trouver le résultat de façon sûre et certaine.
    3. Écrire une fonction akinator(n) qui va chercher à deviner le nombre x auquel vous pensez (0 ≤ x ≤ n) en utilisant la même stratégie que vous.

    Affiche corrigé

    Cacher corrigé

    1. La meilleure méthode est de diviser systématiquement l'intervalle en deux et de prendre le milieu.
      Si par exemple le nombre à trouver est 37, commencer par demander 50 ("c'est moins"), puis 25 ("c'est plus"), puis 37 ("Bravo !").
    2. On se rend compte qu'on a une démarche binaire : comme il est possible de coder 128 nombres sur 7 bits, il est possible de deviner n'importe quel nombre en 7 questions.
    3. def akinator(n):
        mini=0
        maxi=n
        while (maxi-mini)>1 :
          milieu=(maxi+mini)//2
          print("Est-ce qu’il s’agit de :",milieu,"?")
          reponse=input("Répondre par \"+\" ou \"-\" ou \"oui\"")
          if reponse=="+":
             mini=milieu
      
          elif reponse=="-":
             maxi=milieu
          else:
             return True
      
    2) Encadrer la solution d'une équation de type f(x)=0
    Application : La fonction f(x)=x3-1,45x2-11,55x+5,39 admet une solution s telle que f(s)=0 avec 0 ≤ s ≤ 1
    On donne
    def f(x):return x**3-1.45*x**2-11.55*x+5.39
    → Proposer une adaptation de l’algorithme akinator pour trouver une valeur de s arrondie à 10-3 près.

    Affiche corrigé

    Cacher corrigé

    def f(x):return x**3-1.45*x**2-11.55*x+5.39
    
    def resolv(fonction,mini,maxi,intervalle):
    
      while (maxi-mini)>intervalle :
        milieu=(maxi+mini)/2
    
    
        if fonction(maxi)*fonction(milieu)>0:
           maxi=milieu
    
        elif fonction(maxi)*fonction(milieu)<0:
           mini=milieu
        else:
           return milieu
    
      return mini,maxi
    
    La partie la plus compliquée de l'algorithme est mathématique : comment écrire un équivalent de "c'est plus" ou "c'est moins" ?
    Il se trouve que si la fonction est strictement monotone et qu'elle admet une solution dans un intervalle, alors les 2 extrêmités de cet intervalle n'ont pas le même signe => f(mini)×f(maxi)<0.
    On teste donc f(maxi)×f(milieu). Si la valeur est positive, c'est que la solution se trouve entre mini et milieu et donc que notre nouvel intervalle est [mini;milieu].
    3) Rechercher une valeur dans une liste ordonnée par dichotomie
    Une liste de nombres est générée par la commande
    liste=[randint(0,10)]
    for i in range(1,100000) :
      liste.append(liste[i-1]+randint(1,10))
    
    On souhaite rechercher si un nombre est présent dans cette liste le plus rapidement possible.
    1. D’après ce code, la liste est-elle déjà ordonnée ? Si oui, en ordre croissant ou décroissant ?
    2. Est-il possible que la liste contienne deux fois le même nombre ?
    3. Écrire une fonction recherche_dicho(nombre,liste) qui recherche par dichotomie le nombre dans liste et retourne si elle le trouve son indice et si elle ne le trouve pas les 2 indices encadrant la position qu’il aurait dû avoir
    4. Utiliser le benchmark de la séance algorithmes01 pour vérifier si cette méthode est réellement plus rapide que l’algorithme indice(liste,valeur) écrit précédemment.
      Attention : votre fonction bench génère par défaut une liste aléatoire, ce qui n’est pas le cas de la liste ci-dessus, modifiez la fonction en conséquence !

    Affiche corrigé

    Cacher corrigé

    1. On voit que chaque terme est égal au terme précédent augmenté de randint(1,10). Cette liste est donc ordonnée en ordre strictement croissant.
    2. répondu juste au-dessus
    3. A vous de chercher !
    4. A vous de chercher !

    VI- Algorithmes gloutons

    Cliquez sur Fiche algo glouton pour récupérer l'énoncé du TD.
    1) Introduction
    Il y a certains problèmes problèmes pour lesquels il existent un très grand nombre de solutions. Parmi ces solutions quelques unes sont optimales, mais l'écrasante majorité ne le sont pas. Il n'est dans certains cas pas possible de trouver une solution optimale car cela demanderait un nombre de calculs hors de portée ou trop coûteux par rapport aux moyens à disposition.
    Dans ce cas, il peut être intéressant de disposer d'un algorithme qui, s'il ne donne pas la solution optimale, est tout du moins capable de trouver une solution, de préférence pas trop mauvaise.
    Ce genre d'approche, on l'a déjà abordée au moins une fois : pour faire sortir le robot du labyrinthe : en gardant toujours le mur à droite, on s'assure de pouvoir sortir, mais on ne trouvera généralement pas le trajet le plus court vers la sortie.
    Les algorithmes gloutons répondent à cette problématique. En choissant systématiquement l'option qui les rapproche le plus de l'objectif, ils permettent de trouver une solution qui si elle n'est pas systématiquement optimale est généralement satisfaisante.
    2) Problème du rendu de monnaie
    photo d'une caisse automatique
    Vous êtes employé par l’entreprise CashExpress, spécialisée dans la vente de caisses enregistreuses automatiques : pour éviter les contacts entre les employés et la clientèle, le client dépose directement l’argent dans un automate qui se charge de lui rendre la monnaie.
    On suppose que la monnaie peut-être rendue avec toutes les pièces et billets existant en euros :
    [200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.01]
    (En effet, les billets de 500€ ne sont plus produits depuis 2018)
  • a. Un client vous présente un billet de 50€ pour payer sa chocolatine a 0,85€, indiquez le détail du rendu de monnaie que vous allez faire.
  • Un algorithme évident afin de rendre systématiquement correctement la monnaie, serait de rendre uniquement des pièces de 1 cent.
    Cela présente 2 inconvénients majeurs :
    • il est nécessaire de prévoir un très gros volume de pièce de 1 cent afin de pouvoir continuer à rendre la monnaie tout au long de la journée
    • Vous risquez d’irriter vos clients
  • b. Proposez une stratégie vous permettant systématiquement de rendre la monnaie en utilisant un nombre minimal de pièces/billets.
  • c. Écrire la fonction rendu_monnaie(montant) qui retourne un dictionnaire contenant le détail du rendu de monnaie pour un montant donné.
    Exemple : Le client a payé sa baguette à 1,05€ avec un billet de 5€ → l’automate doit lui rendre 3,95€
    rendu_monnaie(3,95) → 	{'200':0, '100':0, '50':0, '20':0, '10':0, '5':0, '2':1, '1':1, '0.5':1, '0.2':2, '0.1':0, '0.05':1, '0.01':0}
    En effet, le rendu optimal est 2€ + 1€ + 50ct + 2x20ct + 5ct
  • Une boulangerie basée en Absurdistan souhaite se procurer une de vos machine. Leur monnaie est le Plouk, dont le taux de change est proche de l’Euro : 1 Pk = 1 €.
    Leur monnaie est différemment échelonnée : [200, 100, 30, 20, 5, 2, 1, 0.3, 0.1, 0.05, 0.01]
  • d. En adaptant la fonction rendu_monnaie(montant) aux différentes valeurs disponibles dans ce pays, quel retour propose-t-elle pour 45 Pk ?
    Ce rendu est-il optimal ?
  • Affiche corrigé

    Cacher corrigé

    1. Je dois lui rendre 50 - 0.85 = 49.15€
      Le meilleur rendu est 2×20€, 1×5€, 2×2€, 1×0.10€, 1×0.05€.
    2. Pour rendre le moins de monnaie possible, il faut toujours rendre la plus grande valeur possible.
    3. monnaie=[200,100,50,20,10,5,2,1,0.5,0.2,0.1,0.05,0.02,0.01]
      
      def rendu_monnaie(montant,monnaie):
          rendu={}
          montant=int(100*montant)
          for piece in monnaie:
              if montant>=100*piece:
                  rendu[piece]=int(montant//(piece*100))
                  montant-=rendu[piece]*(piece*100)
                  
          return rendu
      Remarque : Il faut faire attention à la façon dont Python travaille sur les nombres flottants. Pour éviter un problème, il faut s'assurer que les nombres sont entiers en les mutipliant par 100.
    4. Une fois le programme ci-dessus écrit de cette façon, il suffit d'ajouter une nouvelle liste pour les pièces en Plouks.
      monnaie_Pk=[200, 100, 30, 20, 5, 2, 1, 0.3, 0.1, 0.05, 0.01]
      On lance ensuite
      rendu_monnaie(45,monnaie_Pk)
      Out[24]: {30: 1, 5: 3}
      L'algorithme propose alors de rendre 4 devises, tandis que la solution optimale était de 3 : 2×20Pk, 1×5Pk.
    3) Les fractions égyptiennes
    Si les égyptiens ne connaissaient pas la notation décimale, ils connaissaient les fractions, sous une forme particulière (voir Wikipédia ) : leurs fractions étaient de la forme 1p 1over p p * p in setN ^"*" . On parle de fraction unitaire.
    Ils pouvaient donc écrire n’importe quel nombre rationnel (un nombre qui peut s’écrire comme le quotient de 2 nombres entiers) en le décomposant d’une infinité de façons à l’aide de fractions unitaires.
    Par exemple 25 = 1 5+ 1 6+ 1 30 = 1 5+ 1 8+ 1 20+ 1 40 2over5=1over5+1over6+1over30=1over5+1over8+1over20+1over40 .
    Cette solution les satisfaisait probablement d’autant plus qu’il n’est pas sûr qu’ils savaient que certains nombres ne pouvaient être rationnels, comme √2 ou π!
    Il vous faudrait écrire un algorithme glouton egypte(nombre) qui décompose n’importe quel nombre 0<x<1 en somme de fractions unitaires…
    Bien sûr, du fait des spécificités de la prise en charge des nombres et le fait que certains nombre se décomposent nécessairement en une somme infinie de fractions, il faudra accepter une approximation de cette décomposition.

    Affiche corrigé

    Cacher corrigé

    def egypte(nombre,epsilon=1e-7):
        n=2
        sortie=""
        while nombre>epsilon:
            if 1/n<=nombre:
                nombre-=1/n
                sortie+="+1/"+str(n)
            n+=1
        return sortie[1:]
    L'algorithme est "simple" : il part de la fraction 1/2 puis comme dans le problème du rendu de monnaie, regarde s'il peut retrancher la fraction à la valeur à décomposer. Le cas échéant, il ajoute son écriture à la décomposition. Il continue jusqu'à ce que le reste soit inférieur à une valeur de référence facultative epsilon.
    In [2]: egypte(2/3)
    Out[2]: '1/2+1/7+1/43+1/1807+1/3263443'
    
    Remarque : cette façon de décomposer un nombre décimal devrait vous rappeler quelque chose, puisque c’est de cette façon que l’on détermine l’écriture binaire d’un décimal, en utilisant des fractions unitaires de la forme 1 2n 1over2 .
    4) Le voleur
    Il s'agit d'un grand classique de l'algorithme glouton, vous le retrouverez facilement sur Internet
    Marcel Lupin est un voleur prévoyant. Avant de perpétrer ses larcins, il prend soin de lister les objets de valeur présents chez ses futures malheureuses victimes. Il n’emporte sur les lieu qu’un seul sac de 50kg, il doit être sélectif !
    Il établit donc une liste (enfin, nous dirions plutôt dictionnaire, mais Marcel n’est pas informaticien) des objets présents, en indiquant tout d’abord leur masse en kg puis leur valeur en Brouzoufs (c’est la monnaie d’Andorrsbourg, riche petite principauté voisine de l’Absurdistan dans laquelle se déroule notre histoire).
    Cette liste est disponible ci-dessous :

    Affiche liste

    Cacher liste

    {'A': [4, 54], 'B': [2, 9], 'C': [14, 91], 'D': [14, 4], 'E': [8, 18], 'F': [1, 98], 'G': [5, 56], 'H': [15, 85], 'I': [7, 61], 'J': [3, 83], 'K': [2, 75], 'L': [10, 70], 'M': [7, 73], 'N': [14, 71], 'O': [7, 3], 'P': [6, 75], 'Q': [9, 91], 'R': [14, 16], 'S': [9, 48], 'T': [9, 37], 'U': [13, 83], 'V': [3, 30], 'W': [12, 81], 'X': [3, 72], 'Y': [2, 10], 'Z': [3, 24]}
    → Proposez une fonction a_voler(dictionnaire) qui pour un dictionnaire donné retourne la liste des items à voler en priorité afin d’avoir la plus grande valeur dans le sac.
    → Cette fonction calcule également la valeur du contenu du sac.

    Affiche corrigé

    Cacher corrigé

    victime={'A': [4, 54], 'B': [2, 9], 'C': [14, 91], 'D': [14, 4], 'E': [8, 18], 'F': [1, 98], 'G': [5, 56], 'H': [15, 85], 'I': [7, 61], 'J': [3, 83], 'K': [2, 75], 'L': [10, 70], 'M': [7, 73], 'N': [14, 71], 'O': [7, 3], 'P': [6, 75], 'Q': [9, 91], 'R': [14, 16], 'S': [9, 48], 'T': [9, 37], 'U': [13, 83], 'V': [3, 30], 'W': [12, 81], 'X': [3, 72], 'Y': [2, 10], 'Z': [3, 24]}
    """
    rech_max cherche la plus grande valeur d'un dictionnaire de listes
    en permettant de choisir sur quel indice de la liste on fait la comparaison
    """
    def rech_max(dictionnaire,indice):
        cles=list(dictionnaire.keys())
        max=dictionnaire[cles[0]][indice]
        cle_max=cles[0]
        for i in cles:
            if dictionnaire[i][indice]>max:
                max=dictionnaire[i][indice]
                cle_max=i
        return cle_max
    
    """
    la fonction a_voler(dictionnaire,capacite_sac) fait 3 choses
    - calcule la valeur/kg de chaque objet et l'ajoute au dictionnaire
    - ajoute récursivement l'objet le plus rentable dans le dictionnaire 'sac',
        à la condition que celui-ci puisse encore rentrer
    - supprime cet objet dans le dictionnaire
    """
    def a_voler(dictionnaire,capacite_sac):
        sac={}
        valeur=0
        for i in dictionnaire.keys():
            dictionnaire[i].append(dictionnaire[i][1]/dictionnaire[i][0])
        while capacite_sac>0 or len(dictionnaire)>0:
            cle_max=rech_max(dictionnaire,2)
            if dictionnaire[cle_max][0]<=capacite_sac:
                print("on ajoute",cle_max,dictionnaire[cle_max])
                capacite_sac-=dictionnaire[cle_max][0]
                sac[cle_max]=dictionnaire[cle_max]
                valeur+=dictionnaire[cle_max][1]
            del(dictionnaire[cle_max])
        return valeur,sac
    #lancer la fonction avec a_voler(victime,50)
    #la fonction remplira un sac de 50kg avec les objets de victime.
    	
    La principale difficulté de cet algorithme est de trouver à quel paramètre appliquer l'algorithme glouton !
    Ce n'est pas forcément la valeur de l'objet, car celui-ci peut valoir beaucoup mais remplir le sac à lui seul.
    Le paramètre de la valeur rapportée au kilogramme est plus judicieux, car il nous assure de maximiser le butin à chaque prise.
    En revanche, cet algorithme ne sera pas forcément optimal !
    Je vous laisse chercher un exemple dans lequel ce ne sera pas le cas :)