On considรจre ici qu'une somme peut comporter un terme ou plus, que l'ordre des termes ne compte pas, de plus, les termes doivent รชtre des entiers strictement positifs. Ainsi :
il y a faรงons d'รฉcrire comme une somme :
,
;
;
il y a faรงons d'รฉcrire comme une somme :
;
;
;
;
;
;
.
Exercice
Coder une fonction nb_sommes qui prend un paramรจtre entier strictement positif n et qui renvoie le nombre de faรงons d'รฉcrire n comme une somme, sans compter l'ordre.
Contraintes
Modules math et functools interdits
Code source limitรฉ ร 2000 caractรจres
Indice
Toujours commencer par dรฉnombrer ร la main les premiers cas.
Bien ranger les cas, par catรฉgorie ; faire des figures.
Trouver une formule ร partir des cas bien rangรฉs.
Aide
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.
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 termes รฉgales ร , il y a :
des sommes de termes valant toutes auxquelles on adjoint ;
des sommes de termes valant toutes auxquelles on ajoute fois (ร chaque terme).
On en dรฉduit : nb_k_sommes(50,10)=nb_k_sommes(49,9)+nb_k_sommes(40,10).
Il faudra utiliser de la mรฉmoรฏsation pour que le code soit assez rapide.
# Tests(insensible ร la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)