---
# System prepended metadata

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

---

# ALGO6 : TD5 
###### tags: `algo` `2021`

## Exercice 1 :
1. x
2. x
3. x
4. x
5.  Prendre en compte le fait qu'il y ait un nombre pair ou impair de valeur,
    regarder du plus petit et du plus grand. Prendre le total de la liste et     diviser le tout par deux et trouver un rapport entre les valeurs.
    
    
## Exercice 2 :
1.  Il n'admet pas toujours de solution. [1, 2, 4] ou [1, 5, 8, 26]
    
2.  Non -> [10,5,5,10,20,5,5]
    [20,10] [10,5,5,5,5]
    [20,5,5] [10,10,5,5]


3.  **[3, 4, 5, 7, 9, 10, 12, 13, 14, 17]** -> total de 94 (moitié = 47)
    [5,12,13,17] [3,4,7,9,10,14]
    [4,5,9,12,17] [3,7,10,13,14]
\
    **[ 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]** -> total : 12 (moitié: 6) 
    [2+2+1+1] [1+1+1+1+1+1]
    [2,1,1,1,1] [2,1,1,1,1]
\
    **[5, 7, 8, 10, 12, 15, 17, 20, 22, 30]** -> total de 146 (moitié = 73)
    [8,15,20,30] [5,7,10,12,17,22]
\
    **[5, 7, 8, 10, 12, 15, 17, 21, 22, 30]** -> total de 147 (moitié = 73.5) -> impossible
    
4.  Si le total des valeurs est impairs. [1, 2, 4]
    Il faut que le terme le plus grand soit <= moitié du total. [1, 5, 8, 26]

## Exercice 3 :
### 1. Écrire un algorithme qui énumère toutes les solutions possibles :
#### Récursif :
```c
void resoudre_rec(Table T, int i, int valeur, Table solution) {
    if (valeur == 0){
        AfficherSolution(solution);
    } else if(
        valeur > 0 && 
        valeur % 2 == 0 && 
        /* Somme(valeurInitiale, valeurFinale, sommeAFaire) */
        Somme(j=i, finTab, T[j]) > valeur
    ) { 
        resoudre_rec(T, i+1, valeur, solution);
        solution[i] = 1;
        resoudre_rec(T, i+1, valeur - T[i], solution);
    }
}
```

#### Itératif :
Parcourir l'ensemble des combinaisons possibles (2<sup>n</sup>/2)
T = [4, 6, 7, 9] 
Si 4 et 9 a été testé, 9 et 4 n'a pas besoin d'être testé.

On rajoute le dernier élément, l'avant dernier. Puis le dernier et l'avant dernier, etc. Comme une table de vérité. Ainsi on teste tout (jusqu'a la moitié de la somme).

### 2. Faire la preuve de cet algorithme (ou s’il n’est pas correct donner un contre-exemple).