GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Compter des combinaisons ======

Supposons que j'ai deux dés à 6 faces, que je les lance et que je fasse le total.

Intuitivement, on devine que le score 7 est plus probable que le score 12. En effet, pour obtenir 12, le seul moyen est de faire un double 6 tandis que l'on aura un score de 7 avec 2 et 5 ou encore avec 4 et 3.

Ainsi on peut compter qu'avec deux dés à 6 faces, on pourra obtenir 12 d'une seule façon alors qu'il y a 6 façons de faire 7. Ce résultat pourrait être utilisé en probabilité : on dirait qu'il y a 6 fois plus de chances d'obtenir 7 que d'obtenir 12.

Dans ce TD, l'objectif est d'écrire une fonction qui
  * reçoit ''n'', le nombre de dés, au moins 1,
  * reçoit ''s'', le score visé, au moins 0,
  * reçoit ''f'', le nombre de faces par dé, au moins 2 (les numéros sur les faces vont de 1 à ''f'')
  * renvoie le nombre de façons d'obtenir ''s'' en sommant ''n'' dés de ''f'' faces.

Je vous propose quelques approches. Seules la dernière est efficace pour de grandes valeurs de ''n''.

===== Exhaustif =====

Première approche, on liste toutes les combinaisons possibles et on compte celles qui produisent le score désiré.

<code lang-none>
FONCTION comptage
ENTRÉES: n, s, f
DÉBUT
    initialiser compteur à 0
    POUR CHAQUE combinaison possible, FAIRE
        calculer la somme pour cette combinaison
        SI la somme est égale à s ALORS
            ajouter 1 à compteur
        FIN
    FIN
    RENVOYER compteur
FIN
</code>

Le problème de cette solution est que le nombre de combinaisons augmente exponentiellement. Avec des dés à 6 faces, pour 2 dés, il y a $6^2 = 36$ combinaisons. Avec 3 dés, c'est $6^3 = 216$ ; avec 5 dés, c'est $6^5 = 7\,776$, avec 10 dés c'est $6^{10} = 60\,466\,176$ et avec 20 dés c'est $6^{20} = 3\,656\,158\,440\,062\,976$...

===== Récursif =====

Supposons que je veuille obtenir 40 avec 10 dés à 6 faces.

  * Je pourrais faire 39 avec les 9 premiers dés et 1 avec le 10e,
  * ou bien 38 avec les 9 premiers et 2 avec le 10e,
  * ...
  * ou bien 34 avec les 8 premiers et 6 avec le 10e.

Le nombre de combinaison donnant 40 avec 10 dés à 6 faces sera donc le nombre de combinaisons donnant 39 avec 9 dés plus le nombre de combinaisons donnant 38 avec 9 dés, plus ... le nombre de combinaisons donnant 34 avec 9 dés.

On généraliser la formule ainsi :

$$nombre(n, s, f) = nombre(n-1, s-1, f) + nombre(n-1, s-2, f) + \cdots + nombre(n-1, s-f, f) = \sum_{i = 1}^f nombre(n-1, s - i, f)$$

Mais si $f > s$ on aura parfois $s - i < 0$ ce qui pourrait être ennuyeux. On convient donc que $nombre(n, s, f) = 0$ si $s < 0$, ce qui est tout à fait naturel.

De même, on calcule le cas pour $n$ en utilisant le cas $n-1$. Comme dans une récurrence, il faut un cas de base. Ce cas de base sera le cas $n = 0$. On dira que $nombre(0,0,f) = 1$ (c'est à dire 1 si $n$ et $s$ valent 0) et 0 sinon.

<code lang-none>
FONCTION comptage
ENTRÉES: n, s, f
DÉBUT
    SI s < 0 ALORS
        RENVOYER 0
    FIN
    SI n est 0 ALORS
        SI s est 0 ALORS
            RENVOYER 1
        SINON
            RENVOYER 0
        FIN
    FIN
    initialiser somme à 0
    POUR i ALLANT DE 1 à f, FAIRE
        calculer comptage avec n-1, s-i et f
        et ajouter le résultat à somme
    FIN
    RENVOYER somme
FIN
</code>

Ce cas est plus simple d'un certain point de vue : on n'a pas le soucis de générer les différentes combinaisons. Mais comme souvent avec la récursivité, la simplicité apparente cache des problèmes.

Ici, le gros problème est que l'on va refaire inutilement beaucoup de calculs. Prenez l'exemple $n = 3$ et $s = 10$ par exemple et essayez de suivre la récurrence, vous verrez que la fonction ''comptage'' est appelée plusieurs fois avec les mêmes arguments. Ce problème grandit exponentiellement et rend la méthode impraticable très rapidement.

===== Approche dynamique =====

L'approche [[nsi:terminales:dynamique:programmation_dynamique|dynamique]] consiste à reprendre la récursivité mais en sauvegardant les résultats de calculs de façon à ne pas répéter inutilement toujours les mêmes calculs.

On pourrait ainsi proposer cette méthode presque identique à la précédente mais avec une mémoire en plus :


<code lang-none>
memoire = dictionnaire vide

FONCTION comptage
ENTRÉES: n, s, f
DÉBUT
    SI s < 0 ALORS
        RENVOYER 0
    FIN
    SI n est 0 ALORS
        SI s est 0 ALORS
            RENVOYER 1
        SINON
            RENVOYER 0
        FIN
    FIN
    SI (n, s, f) présent dans memoire ALORS
        RENVOYER memoire pour (n, s, f)
    FIN
    initialiser somme à 0
    POUR i ALLANT DE 1 à f, FAIRE
        calculer comptage avec n-1, s-i et f
        et ajouter le résultat à somme
    FIN
    écrire somme dans memoire, avec la clé (n, s, f)
    RENVOYER somme
FIN
</code>

Vous voyez que le dictionnaire permet de sauvegarder des résultats antérieurs.

Une telle approche est très séduisante. Mais elle nécessite une structure compliquée : le dictionnaire. Certains langages n'en disposent pas et on peut préférer une autre approche plus proche de ce qui est proposé dans la programmation dynamique.

Cette méthode passe par la création d'un tableau ''tab'' à deux dimensions tel que ''%%tab[i][j]%%'' contienne le nombre de combinaisons avec ''i'' dés pour obtenir le score ''j''. Donc la valeur cherchée est ''%%tab[n][s]%%''.

On sait que ''%%tab[0][j]%%'' vaut ''1'' si ''j == 0'' et ''0'' sinon. La première ligne du tableau est donc connue. L'algorithme consiste à remplir les lignes l'une après l'autre.

<code lang-none>
FONCTION comptage
ENTRÉES: n, s, f
DÉBUT
    créer un tableau de n + 1 lignes et s + 1 colonnes plein de 0
    mettre 1 en [0][0]
    POUR CHAQUE ligne de 1 à n FAIRE
        POUR CHAQUE colonne de 1 à s FAIRE
            cumuler les valeurs allant de [ligne-1][colonne - f] jusqu'à [ligne-1][colonne-1], compris
            écrire le cumul en [ligne][colonne]
        FIN
    FIN
    RENVOYER la valeur en [n][s]
</code>

<WRAP box>
===== À faire =====

Faire l'implémentation et testez.

Pour les terminales, dans le cadre de la programmation dynamique, vous préférerez bien sûr la dernière approche mais il serait intéressant de faire des comparatifs de performances.
</WRAP>