163 lines
4.8 KiB
Markdown
163 lines
4.8 KiB
Markdown
# Rendu de Monnaie
|
||
|
||
### Le problème
|
||
|
||
> **Énoncé** : On dispose d'un ensemble de pièces de valeurs données (par exemple : 1€, 3€, 5€). On souhaite rendre une somme exacte en utilisant le **moins de pièces possible**.
|
||
|
||
**Exemple :** Rendre 11€ avec des pièces de 1€, 3€ et 5€.
|
||
|
||
Une solution possible : 5 + 3 + 3 = 11€ → **3 pièces**
|
||
|
||
---
|
||
|
||
### Pourquoi l'algorithme glouton ne suffit pas
|
||
|
||
En classe de Première, vous avez étudié l'**algorithme glouton** : à chaque étape, on choisit la plus grande pièce possible.
|
||
|
||
```python
|
||
def rendu_glouton(pieces, somme):
|
||
pieces_triees = sorted(pieces, reverse=True)
|
||
nb_pieces = 0
|
||
for piece in pieces_triees:
|
||
while somme >= piece:
|
||
somme -= piece
|
||
nb_pieces += 1
|
||
return nb_pieces
|
||
```
|
||
|
||
Le glouton fonctionne bien avec les pièces européennes (1, 2, 5, 10, 20, 50 centimes...). Mais il échoue sur d'autres systèmes :
|
||
|
||
**Contre-exemple :** pièces = [1, 3, 4], somme = 6
|
||
|
||
- Glouton : 4 + 1 + 1 = **3 pièces**
|
||
- Optimal : 3 + 3 = **2 pièces**
|
||
|
||
Le glouton n'est **pas optimal** dans le cas général. La programmation dynamique, elle, trouve toujours la solution optimale.
|
||
|
||
---
|
||
|
||
### Formulation récursive
|
||
|
||
Notons `rendu(s)` le nombre minimum de pièces pour rendre la somme `s`.
|
||
|
||
- **Cas de base :** `rendu(0) = 0` (aucune pièce nécessaire pour rendre 0)
|
||
- **Cas récursif :** pour chaque pièce `p` disponible telle que `p ≤ s` :
|
||
|
||
```
|
||
rendu(s) = 1 + min( rendu(s - p) ) pour toute pièce p ≤ s
|
||
```
|
||
|
||
On essaie toutes les pièces et on garde le minimum.
|
||
|
||
---
|
||
|
||
### Version naïve (récursive)
|
||
|
||
```python
|
||
def rendu_naif(pieces, somme):
|
||
if somme == 0:
|
||
return 0
|
||
minimum = float('inf') # infini : pas encore de solution trouvée
|
||
for piece in pieces:
|
||
if piece <= somme:
|
||
nb = 1 + rendu_naif(pieces, somme - piece)
|
||
if nb < minimum:
|
||
minimum = nb
|
||
return minimum
|
||
```
|
||
|
||
**Problème :** Comme pour Fibonacci, de nombreux sous-problèmes sont recalculés plusieurs fois. La complexité est exponentielle.
|
||
|
||
---
|
||
|
||
### Version Top-Down (mémoïsation)
|
||
|
||
```python
|
||
def rendu_memo(pieces, somme):
|
||
memo = {}
|
||
|
||
def rendu(s):
|
||
if s == 0:
|
||
return 0
|
||
if s in memo:
|
||
return memo[s]
|
||
minimum = float('inf')
|
||
for piece in pieces:
|
||
if piece <= s:
|
||
nb = 1 + rendu(s - piece)
|
||
if nb < minimum:
|
||
minimum = nb
|
||
memo[s] = minimum
|
||
return memo[s]
|
||
|
||
return rendu(somme)
|
||
```
|
||
|
||
Chaque valeur de `rendu(s)` n'est calculée qu'une seule fois et mémorisée dans le dictionnaire.
|
||
|
||
---
|
||
|
||
### Version Bottom-Up (tableau)
|
||
|
||
On remplit un tableau `tableau` où `tableau[s]` représente le nombre minimum de pièces pour rendre la somme `s`, en partant de `s = 0` jusqu'à `s = somme`.
|
||
|
||
```python
|
||
def rendu_bottom_up(pieces, somme):
|
||
tableau = [float('inf')] * (somme + 1)
|
||
tableau[0] = 0 # cas de base : 0 pièce pour rendre 0€
|
||
|
||
for s in range(1, somme + 1):
|
||
for piece in pieces:
|
||
if piece <= s:
|
||
if tableau[s - piece] + 1 < tableau[s]:
|
||
tableau[s] = tableau[s - piece] + 1
|
||
|
||
return tableau[somme]
|
||
```
|
||
|
||
---
|
||
|
||
### Visualisation du tableau
|
||
|
||
**Exemple :** pièces = [1, 3, 4], somme = 6
|
||
|
||
On initialise : `tableau = [0, ∞, ∞, ∞, ∞, ∞, ∞]`
|
||
|
||
| s | Pièce testée | Calcul | tableau[s] |
|
||
|---|-------------|--------|------------|
|
||
| 1 | 1 | `tableau[0] + 1 = 1` | **1** |
|
||
| 2 | 1 | `tableau[1] + 1 = 2` | **2** |
|
||
| 3 | 1 | `tableau[2] + 1 = 3` | 3 |
|
||
| 3 | 3 | `tableau[0] + 1 = 1` | **1** |
|
||
| 4 | 1 | `tableau[3] + 1 = 2` | 2 |
|
||
| 4 | 3 | `tableau[1] + 1 = 2` | 2 |
|
||
| 4 | 4 | `tableau[0] + 1 = 1` | **1** |
|
||
| 5 | 1 | `tableau[4] + 1 = 2` | 2 |
|
||
| 5 | 3 | `tableau[2] + 1 = 3` | 2 |
|
||
| 5 | 4 | `tableau[1] + 1 = 2` | **2** |
|
||
| 6 | 1 | `tableau[5] + 1 = 3` | 3 |
|
||
| 6 | 3 | `tableau[3] + 1 = 2` | **2** |
|
||
| 6 | 4 | `tableau[2] + 1 = 3` | 2 |
|
||
|
||
Résultat final : `tableau[6] = 2` → 2 pièces (3 + 3). L'algorithme a bien trouvé la solution optimale que le glouton avait ratée.
|
||
|
||
---
|
||
|
||
### Complexité
|
||
|
||
| Version | Temps | Espace |
|
||
|---------|-------|--------|
|
||
| Naïve | exponentielle | O(somme) pile |
|
||
| Top-Down | O(n × somme) | O(somme) |
|
||
| Bottom-Up | O(n × somme) | O(somme) |
|
||
|
||
Avec n = nombre de pièces différentes.
|
||
|
||
---
|
||
|
||
Auteur : Florian Mathieu
|
||
|
||
Licence CC BY NC
|
||
|
||
<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/"><img alt="Licence Creative Commons" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" /></a> <br />Ce cours est mis à disposition selon les termes de la <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International</a>.
|