On considère qu'une somme doit comporter au moins un terme et que l'ordre des termes ne compte pas. Ainsi :
il y a \(3\) façons d'écrire \(3\) comme une somme :
\(3 = 3\),
\(3 = 2 + 1\) ;
\(3 = 1 + 1 + 1\) ;
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.
Indice 2
Il est recommandé de construire une fonction auxiliairenb_k_sommes qui prend en paramètres deux entiers n et k et 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 :
n<k ne donne aucune somme ;
k==1 donne une unique somme.
Indice 3
Pour dénombrer nb_k_sommes(n, k), on fera deux cas :
Les sommes dont le plus petit terme est 1. Combien ont-elles 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 enlever 1 à 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.
Par exemple, parmi les sommes de \(10\) termes égales à \(50\), il y a :
des sommes de \(9\) termes valant toutes \(49\) auxquelles on ajoute \(1\) ;
des sommes de \(10\) termes valant toutes \(40\) auxquelles on ajoute \(10\) fois \(1\).
On en déduit : nb_k_sommes(50,10)=nb_k_sommes(49,9)+nb_k_sommes(40,10).
Indice 4
Il faudra utiliser de la mémoïsation pour que le code soit assez rapide.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)