---
# System prepended metadata

title: 'ALGO6 : TD6'
tags: ['2021', algo]

---

# ALGO6 : TD6
###### tags: `algo` `2021`

## Exercice 1 : Algorithme glouton : le cas des euros
En euros, les valeurs de v sont (1, 2, 5, 10, 20, 50, 100, 200, 500)

1. Proposer une solution optimale et une solution non-optimale pour rendre 8 euros.
* Solution optimale :
8 = 5 + 2 + 1

* Solution non-optimale :
8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2. Proposer une solution pour rendre 143 euros. Est-elle optimale ?
143 = 100 + 20 + 20 + 2 + 1
Cette solution est optimale car il n'est pas possible de rendre moins de monnaie.

3. Proposer un algorithme simple pour rendre la monnaie.

    * On parcourt toutes les valeurs de v en partant de la plus grande. 
    * On compare la valeur que l'on prend avec le rendu. 
    * Si on peut mettre la valeur dans le rendu, on l'ajoute au rendu, sinon on passe à la prochaine valeur. 
    * Cet algorithme peut se répeter sur les mêmes valeurs de v pour rajouter par exemple 2 billets de 20.


```c
rendu(value):
    T = [1, 2, 5, 10, 20, 50, 100, 200, 500]
    resultat = []
    i = T.size
    while(i >= 0 && value != 0):
        if(value - T[i] >= 0):
            jet.add(T[i])
            value -= T[i]
        else 
            i--
    return jet
```

* truc avec la division euclidienne c'est chelou    
```c
for i -> 0:
    nombre(1) = N / v[i]
    N = N - nombre[i] v[i]
print nombre
```
 
4. Cet algorithme rend-il une solution optimale (dans le cas du rendu d’euros) ?
    * Oui car il commence par les plus grandes valeurs et retourne donc un nombre minimal de pièces.


5. Quelle est la complexité de votre algorithme ?
    * On peut trouver un majorant de l'algorithme. Donc :
    nombre_soustraction &leq; n/200.
    * Ou bien, il faut utiliser la division euclidienne. Ce qui donne :
    comp &leq; nombre(valeurs)



## Exercice 2 : Systèmes canoniques
1. On suppose que v = (1, 3, 4). L’algorithme développé à l’exercice précédent rend-il une solution optimale ?

    Non, par exemple pour 6 :
    * L'algo donne : [4, 1, 1]
    * Résultat optimal : [3, 3]

    Ou pour 9 :
    * L'algo donne [4, 3, 1, 1]
    * L'optimal est [3, 3, 3]

2. On suppose que v = (1, 4, 9). L’algorithme développé à l’exercice précédent rend-il une solution optimale ?

    Non, par exemple pour 12 :
    * L'algo donne : [9, 1, 1, 1]
    * Résultat optimal : [4, 4, 4]


## Exercice 3 : Énumération
1. Soit v = {1, 5, 6, 9, 20}. Calculer un rendu de monnaie optimal pour x = 17.
    * [6,6,5]

2. Écrire un algorithme prenant en entrée un entier x et un vecteur v = (v1, . . . , vn) qui retourne le nombre minimal de pièces à rendre pour obtenir x. Cette algorithme utilisera une énumération de parties.

```c
rendu2(N, i):
    si N < 0 ou i < 0: return +inf
    si N == 0: return 0
    return min(1 + rendu2(N - V[i], i), rendu2(N, i - 1))
```

3. Quelle est la complexité de votre algorithme ?
O($\infty$) :scream: :tent: 
Sacré complexité -> oui



4. Si ce n’est pas fait, utiliser de la programmation dynamique pour améliorer votre algorithme