TD algorithmique monnayeur
TD : TD algorithmique monnayeur. Recherche parmi 300 000+ dissertationsPar Lucas Dupin • 12 Mai 2020 • TD • 1 262 Mots (6 Pages) • 499 Vues
# A. Essais Successifs
A=[]
# Fonction qui permet de faire l'élagage
# Prend en entrée S : la liste des pièces
# X : la valeur de la pièce à rajouter
# Prend en sortie un booléen
def Elagage(S,X) :
if X==100 or X==50 or X==10 or X==5 or X==1 : #Condition d'élagage 1 : 2 pièces identiques
if X in S :
return True # On doit élaguer
elif X==20 or X==2 : #Condition d'élagage 2 : 3 pièces identiques
if len([i for i in range(len(S)) if S[i] == X]) >= 2 :
return True # On doit élaguer
return False # On ne doit pas élaguer
# Fonction qui permet de faire l'algorithme par essais succesifs
# Prend en entrée S : la liste des pièces
# N : la valeur à rendre
#
def EssaisSuccessifs(S,N):
global A # la liste des pièces à rendre
for X in [200,100,50,20,10,5,2,1] : # liste des pièces
if X <= N : # on regarde si la pièce n'est pas trop grosse
Suppr=Elagage(S,X) # Appel de la fonction d'élagage
S.append(X) # ------Enregistrer--------
N=N-X # -------------------------
if Suppr==False : # Elagage
if N == 0 : # ------SolTrouvée--------
if len(S)<len(A) or A==[] : # ------------------------
while A!=[] : # ----On vérifie s'il ----
A.pop() # --- s'agit bien de la---
for k in range(len(S)) : # -- meilleur solution ---
A.append(S[k]) #-------------------------
else :
EssaisSuccessifs(S,N)
N=N+X # --------Défaire---------
S.pop() # ------------------------
#Exemples
print("Pour rendre 2€31 il faut rendre : ")
EssaisSuccessifs([],231)
print(A)
A=[]
print("Pour rendre 0€15 il faut rendre : ")
EssaisSuccessifs([],15)
print(A)
A=[]
print("Pour rendre 1€29 il faut rendre : ")
EssaisSuccessifs([],129)
print(A)
A=[]
#B. Programmation dynamique
import math
# Fonction qui permet de faire l'algorithme par Programmation dynamique
# Prend en entrée i : le coefficient de la pièce maximale
# j : la valeur à rendre
#
def CalculPieceDynamique(i,j) :
c=[1,2,5,10,20,50,100,200]
if j==0 : #Condition d'arret
...