nsi-continuite
Affiche séance 01
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.