OCaml (option informatique) · Chapitre 11 · Exercice de TD
Compter les sous-ensembles de somme donnée
Récursivité et retour sur trace · niveau 2
Énoncé
Modifier existe_somme en compte_somme l cible qui compte le nombre de sous-ensembles de somme cible.
Corrigé
let rec compte_somme l cible =
if cible = 0 then 1
else if cible < 0 then 0
else
match l with
| [] -> 0
| x :: reste ->
compte_somme reste (cible - x) + compte_somme reste cibleOn remplace le « trouvé / pas trouvé » (||) par une addition des deux sous-comptes : avec x, sans x. Le cas cible = 0 compte (l'ensemble construit convient) ; cible < 0 compte (on a dépassé).
Exercices semblables
- Liste des coups de Hanoï corrigé
- Permutations corrigé
- Combinaisons corrigé
- Les reines corrigé
- Reconstruire le sous-ensemble corrigé