Façons de rendre la monnaie
Façons de rendre la monnaie
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]
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]
Re: Façons de rendre la monnaie
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
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) и Дух мира (& esprit de 🕊)
Re: Façons de rendre la monnaie
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 ?
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) и Дух мира (& esprit de 🕊)
Re: Façons de rendre la monnaie
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 :
Sinon j'avais commencé à dérouler la pelote (mais pas de manière recursive)
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:
SPOILER:
отец (un autre père ENSICAENnais) сынок (& fils PCSI▸PC▸PC* 2020-23 à B.Pascal (63) ➠ EC Lille) и Дух мира (& esprit de 🕊)