Nombre de partitions d'un entier⚓︎
On dira qu'une somme doit comporter au moins un terme, et que l'ordre ne compte pas, ainsi
- Il y a \(3\) façons d'écrire \(3\) comme une somme.
- \(3 = 1 + 2\)
- \(3 = 1 + 1 + 1\)
- \(3 = 3\)
- Il y a \(7\) façons d'écrire \(5\) comme une somme.
- \(5 = 5\)
- \(5 = 4 + 1\)
- \(5 = 3 + 2\)
- \(5 = 3 + 1 + 1\)
- \(5 = 2 + 2 + 1\)
- \(5 = 2 + 1 + 1 + 1\)
- \(5 = 1 + 1 + 1 + 1 + 1\)
Écrire une fonction nb_sommes
qui prend un paramètre entier 0 < n <= 42
et qui renvoie le nombre de façons d'écrire n
comme une somme, sans compter l'ordre.
Exemples
>>> nb_sommes(3)
3
>>> nb_sommes(5)
7
Indice 1
- Toujours commencer par dénombrer à la main les premiers cas.
- Bien ranger les cas ; faire des figures.
- Ajouter dès que possible des tests, avant d'écrire la fonction.
Indice 2
Il est recommandé de construire une fonction auxiliaire telle que nb_k_sommes(n, k)
renvoie le nombre de façons d'écrire n
comme une somme de k
termes.
Ainsi, nb_sommes(n)
sera la somme pour k
allant de 1
à n
de nb_k_sommes(n, k)
.
On remarquera que
k > n
ne donne aucune sommek == 1
donne une unique somme
On ajoutera des tests à cette fonction !
Indice 3
Pour dénombrer nb_k_sommes(n, k)
, on fera deux cas :
- Les sommes dont le plus petit terme est
1
. Combien de termes restants, et pour quelle somme ? Un calcul récursif est alors possible. - Les sommes dont tous les termes sont supérieurs à
1
. On pourra enlever1
à chaque terme, ce qui donne une somme égale à ??? en ??? parties. Et réciproquement. Ce qui permet de dénombrer ce cas de manière récursive également.
def nbpy-undsommes(n):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undsommes(3) == 3bksl-nlassert nbpy-undsommes(5) == 7bksl-nlbksl-nlNone
A
Z