Force Brute

Vocabulaire

Un algorithme dit « de force brute » consiste à énumérer toutes les solutions possibles à un problème puis à identifier, parmi ces solutions, laquelle est la plus pertinente.

Exemple

Pour acheter une bouteille d'eau qui coûte 1 euro, un client glisse un billet de 10 euros dans le distributeur. Celui-ci doit rendre 9 euros de monnaie.

Un algorithme de force brute va énumérer les huit façons différentes de rendre cette somme en utilisant les valeurs 1, 2, 5, 10, 20, 50, 100 et 200.

Sur votre cahier, détaillez les huit décompositions possibles.

Une réponse

Répartition	Nombre de pièces et/ou de billets
9 × 1 €	9
7 × 1 € + 1 × 2 €	8
5 × 1 € + 2 × 2 €	7
3 × 1 € + 3 × 2 €	6
1 × 1 € + 4 × 2 €	5
4 × 1 € + 1 × 5 €	5
2 × 1 € + 1 × 2 € + 1 × 5 €	4
2 × 2 € + 1 × 5 €	3

Cette méthode permettra à coup sûr de trouver la solution optimale du problème.
Mais le nombre de possibilités est très important (essayez de trouver toutes les répartitions possibles pour une somme de 42 € par exemple) donc utiliser ce type d'algorithme est très coûteux à la fois en terme de temps de calcul et d'espace mémoire.

Il faut donc trouver un moyen plus « efficace » de raisonner.

Retour à l'exemple

Dans le cas du rendu de 9 euros en monnaie, il est facile, pour un humain, de déterminer « de tête » cette façon optimale de faire, à savoir une pièce de 5 euros et deux pièces de 2 euros.

Mais comment programmer un automate pour qu'il y parvienne ?