nsi-continuite

Cacher Séance 01

Fiche algorithmes02.pdf

I- Recherche par dichotomie

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

II- Algorithmes gloutons

euros=[200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.01]
plouks=[200, 100, 30, 20, 5, 2, 1, 0.3, 0.2, 0.1, 0.05, 0.01]
def rendu_monnaie(montant,monnaie):
  montant=int(montant*100)
  rendu={}
  for i in monnaie:
    nb=montant//(int(i*100))
    rendu[i]=nb
    montant-=nb*int(i*100)

  return rendu
		

Fiche algorithmes02-suite.pdf

I- Recherche par dichotomie

from random import randint

def tri(n):
    liste = [randint(0,10)]
    for i in  range(1,n):
        liste.append(liste[i-1]+randint(1,10))
    return liste

def recherche(nombre,liste):
    mini,maxi = 0,len(liste)-1
    while (maxi-mini)>1 :
        milieu=(maxi+mini)//2
        if liste[milieu]<nombre:
           mini=milieu
        elif liste[milieu]>nombre:
           maxi=milieu
        else:
           return milieu
    return False,mini,maxi
	

II- Fractions égyptiennes

def egypte(nombre):
    n=2
    sortie=""
    while nombre>1e-7:
        if 1/n<=nombre:
            nombre-=1/n
            sortie+="+1/"+str(n)
        n+=1
    return sortie[1:]
	

III- Le voleur

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