TD algorithmique monnayeur

# 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

...