Façons de rendre la monnaie

Messages : 7

Inscription : 08 juin 2020 23:17

Profil de l'utilisateur : Élève de lycée

Façons de rendre la monnaie

Message par Mathavore » 30 nov. 2021 21:46

Bonjour
je bloque sur cet exercice ou il faut coder en python
Écrivez une fonction qui dénombre le nombre de façons différentes de construire une certaine somme S en utilisant uniquement certaines pièces, dont les valeurs sont indiquées en paramètre de la fonction (ça pourrait être par exemple des pièces de 1,2, 5 et 10).

Vous pouvez diviser le nombre de façons de construire la somme S avec les pièces [a, b,..., n] en deux (selon que vous utilisez ou non la valeur a) :

* les façons de construire la somme S - a avec les pièces [a, b,..., n]
* les façons de construire la somme S avec les pièces [b,..., n]

Messages : 778

Inscription : 01 juin 2020 16:26

Profil de l'utilisateur : Parent

Re: Façons de rendre la monnaie

Message par H2Fooko » 01 déc. 2021 06:56

Bonjour Mathavore,

En info tu peux dénombrer en cherchant toutes les solutions de façon exhaustive.
Tu prends un bout de la pelote de laine et tu tires dessus. 😉

C'est bien aussi de voir comment on ferait en maths (dénombrement) pour corroborer les résultats.

Maintenant les 2 derniers paragraphes peuvent aussi laisser penser d'utiliser une fonction récursive ? par dichotomie ?

Commence par quelques exemples sur le papier
отец (un autre père ENSICAENnais) сынок (& fils PCSI▸PC▸PC* 2020-23 à B.Pascal (63)EC Lille) и Дух мира :flag_ua: (& esprit de 🕊)

Messages : 778

Inscription : 01 juin 2020 16:26

Profil de l'utilisateur : Parent

Re: Façons de rendre la monnaie

Message par H2Fooko » 04 déc. 2021 22:32

Bonjour Mathavore,

Voici comment je poserais le problème :
On cherche donc le nombre de n-uplet $ (x_{1}, x_{2},\cdots ,x_{i},\cdots , x_{n}) $ qui vérifient $ S_{n}=\sum_{i=1}^{n}x_{i}.f_{i} $ où $ (f_{1}, f_{2},\cdots ,f_{i},\cdots , f_{n}) $ sont les valeurs faciales données et $ S_{n} $ est la somme $ S $ donnée dans ton énoncé que J'ai renommé $ S_{n} $ pour introduire les dernières lignes de ton énoncé justement.
En effet on peut écrire : $ S_{n}= x_{1}.f_{1}+S_{n-1} $ où $ S_{n-1}=S_{n}- x_{1}.f_{1}=\sum_{i=2}^{n}x_{i}.f_{i} $

En termes informatique on voit apparaitre une fonction récursive :

$ Total=0 $
$ S\left( S_{n},(x_{1}, x_{2},\cdots ,x_{i},\cdots , x_{n}),(f_{1}, f_{2},\cdots ,f_{i},\cdots , f_{n}) \right) $ :
$ \qquad $pour tous les $ x_{1} $ possibles :
$ \qquad|\qquad $traitement de $ Total $+=$ x_{1}.f_{1} $
$ \qquad|\qquad $appel récursif de $ S\left( S_{n-1},( x_{2},\cdots ,x_{i},\cdots , x_{n}),(f_{2},\cdots ,f_{i},\cdots , f_{n}) \right) $
$ \qquad|\qquad\qquad\qquad $soit $ S\left( S_{n}- x_{1}.f_{1},( x_{2},\cdots ,x_{i},\cdots , x_{n}),(f_{2},\cdots ,f_{i},\cdots , f_{n}) \right) $
$ \qquad $jusqu'à $ i==n $

C'est un peu brouillon mais c'est l'idée 😁
Es tu allé au bout ?
отец (un autre père ENSICAENnais) сынок (& fils PCSI▸PC▸PC* 2020-23 à B.Pascal (63)EC Lille) и Дух мира :flag_ua: (& esprit de 🕊)

Messages : 778

Inscription : 01 juin 2020 16:26

Profil de l'utilisateur : Parent

Re: Façons de rendre la monnaie

Message par H2Fooko » 19 déc. 2021 07:45

Bonjour Mathavore,

Il y a ici plusieurs solutions à ton exo, et je dois dire que la solution proposée est élégante. Car à relire l'énoncé on ne te demande pas de lister les n-uplets solutions (même si on peut le faire) mais de les dénombrer !

Juste au cas où le lien vers le site StackOverflow.com venait à se perdre :
SPOILER:

Code : Tout sélectionner

def countChange(amount, coins):
    if (amount == 0):
        return 1
    elif (amount < 0 or coins == []):
        return 0
    else:
    return (countChange(amount, coins[:-1]) + countChange(amount - coins[-1], coins))
Sinon j'avais commencé à dérouler la pelote (mais pas de manière recursive)
SPOILER:

Code : Tout sélectionner

def AddElemt2Tuple(T, e):   # Ajout d'un élément au Tuple
    L = list(T)
    L.append(e)
    T=tuple(L)
    return T
def DelElemt2Tuple(T,e):    # Effacement d'un élément au tuple
    L = list(T)
    L.remove(e)
    T=tuple(L)
    return T
def AffCoeff (N):   # pour un affichage ligne par ligne de chaque élément d'un Tuple
    for I in N:
        print (I)
def GetMaxMult (S, F):  # Pour une somme donnée S, on cherche le multiple maximum de chaque 
    D=()                # valeur faciale pour borner les possibilités de solutions à chercher.
    for i in range (0, len(F)):
        D = AddElemt2Tuple(D, S//F[i])  # Ce multiple maximum est le résultat de la dicision entière 
    return D                            # de S par la valeur faciale en question
def SCrt (C, F):    # C étant le n-uplet de coefficients, et F le n-uplet de valeurs faciales,
    S=0             # cette fonction revoit la somme S des Ci.Fi
    for j in range(0, len(F)):
        S += C[j]*F[j]
    return S
def GoodOldBallOfWool(S, F, D, E):
    print("===== c'est parti ======")
    # Cette méthode n'utilise pas de récursivité et s'arrête à 4 valeurs faciales distinctes (soit 3 retenues).
    i = 0; j = 0; k = 0; Sol=();
    Fin = False
    while not Fin:
        E[j] = i
        if E[j] == D[j]+1:  # c'est l'équivalent d'une première retenue pour incrémenter ...
            E[j+1] += 1     # ... le digit suivant ...
            E[j] = 0        # ... et on remet à zéro le digit précédent
            if E[j+1] == D[j+1]+1:  # 2ème retenue
                E[j+2] += 1
                E[j+1] = 0
                if E[j+2] == D[j+2]+1:  # 3ème retenue
                    E[j+3] += 1
                    E[j+2] = 0
            i = 0           # Quelque soit la retenue on remet à zéro le compteur
        if SCrt (tuple(E), F)== S:  # pour chaque valeur du n-uplet E de test on teste si la somme est celle visée.
            Sol = AddElemt2Tuple(Sol, tuple(E))     # on mémorise la solution courante
            k+=1                                    # et on incrémente le nombre de solutions trouvées
        i += 1
        Fin = tuple(E)==D   # lorsque le n-uplet de test E a atteint le n-uplet des valeurs maxi on s'arrête
    AffCoeff (Sol)
    print ("Soit",k,"solution(s) pour faire",S,"avec comme valeurs faciales : ",F,"\n")

#--------------------------------------------------------------------------------------------------------
# voir le site https://stackoverflow.com/questions/44575298/recursive-generator-for-change-money-python
#--------------------------------------------------------------------------------------------------------
def countChange(amount, coins):
    if (amount == 0):
        return 1
    elif (amount < 0 or coins == []):
        return 0
    else:
        return (countChange(amount, coins[:-1]) + countChange(amount - coins[-1], coins))
#--------------------------------------------------------------------------------------------------------
def change_gen(amount, coins):
    if amount == 0:
        yield 1
    elif amount < 0 or not coins:
        yield 0
    else:
        for element in change_gen(amount, coins[:-1]):
            yield element
        for element in change_gen(amount - coins[-1], coins):
            yield element
#--------------------------------------------------------------------------------------------------------


def main():
    # Données d'entrée :
    S = 71          # la somme à atteindre,
    F = (1,2,5,10)  # les valeurs faciales sur lesquelles on souhaite décomposer la somme.
    D = GetMaxMult (S, F)   # Valeurs max que peuvent prendre les multiples des valeurs faciales
    E=[0 for p in range(0, len(D))]     # On commence à tester le n-uplet identiquement nul.

    GoodOldBallOfWool(S, F, D, E)
    print("Selon la 1ère méthode sur StackOverflow 'countChange' on a : ",countChange(S, list(F)),"solutions")
    print("Selon la 2ème méthode sur StackOverflow 'change_gen' on a : ",sum(change_gen(S, list(F))),"solutions")


    
main()
отец (un autre père ENSICAENnais) сынок (& fils PCSI▸PC▸PC* 2020-23 à B.Pascal (63)EC Lille) и Дух мира :flag_ua: (& esprit de 🕊)

Répondre