Algorithmes

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
   

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

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 !

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.

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:]

In [2]: egypte(2/3)
Out[2]: '1/2+1/7+1/43+1/1807+1/3263443'

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 and 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.