Nombre de facon d'écrire une somme : récursivité complexe

Bonjour,

dans le cadre d'un TP, je dois réaliser ce sujet :
Ecrire une fonction nbsum qui prend comme argument un nombre n et qui renvoie le nombre de façons d'écrire une somme égale à n (on comptera une seule fois les commutations).


Ayant beaucoup de mal avec la récursivité, et après plusieurs tentatives je m'adresse à vous.

Je crois que je dois utiliser un arbre pour réaliser la fonction qui m'enregistrer chaque solution pour ne la prendre en compte qu'une seule fois...

Bref je suis dans le flou !

Pourriez vous m'aider a trouver un algorithme permettant de réaliser cette fonction, et m'expliquer les différentes étapes ?


Merci par avance.
Cordialement,
Tid.

Il s'agit d'un problème bien connu : les partitions d'un entier.
Tu as toutes les solutions que tu veux dans plusieurs langages dans ce sujet.

Néanmoins s'il s'agit juste de compter le nombre de possibilités, cette page pourrait être plus appropriée.

Une solution que j'avais trouvé sans fouiller dans la littérature consacrée au sujet (en fait toutes mes solution dans ce sujet me sont propres, je n'ai pas fait de recherche au préalable) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

module Main where import Data.Array import System   countsums n = a!(n,n) where a = array ((0,0),(n,n)) $ ((0,0),1) : countList countList = [( (k,l), foldl (\c x -> c + (a!(k-x, min (k-x) x))) 0 [1..l]) | k<-[1..n], l<-[1..k]]   main = print . countsums . read . (!!0) =<< getArgs

---

Moins de 10s pour n=1000, mais je suis relativement sûr qu'on peut faire mieux, particulièrement en utilisant la relation découverte par Euler.

EDIT : C'est en effet relativement meilleur... Cette version mets 4 centièmes de seconde pour n=1000 et seulement 1.5s pour n=10000 :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

module Main where import Data.Array import System   {- (k+1)(3k+3-1)/2 = (k)(3k-1)+3k-1+3(k+1)/2 = k(3k-1) + (6k +2)/2 = f(k) + 3k+1 (k-1)(3k-1) - 3(k-1)/2 = k(3k-1) - (3k-1) - 3 (k-1) /2 = f(k)- 3k + 2 -}   posPents = scanl (\n k -> n + 3*k + 1) 1 [1..] negPents = scanl (\n k -> n + 3*k + 2) 2 [1..]   genPents = interleave posPents negPents where interleave (x:xs) ys = x : interleave ys xs   nbsums n = a ! n where a = listArray (0,n) $ 1 : map p [1..] p n = sum $ zipWith (*) (double $ iterate negate 1) (map (a!) $ takeWhile (>=0) $ map (n-) genPents) double (x:xs) = x : x : double xs   main = print . nbsums . read . (!!0) =<< getArgs

---

--
Jedaï

Re,

merci pour cette réponse très complète.
Je ne recherche pas vraiment pour l'instant à programmer de façon à gagner du temps/ de l'espace système mais ta remarque est intéressante !

Je vais travailler la dessus, je reviendrai ici si j 'ai un petit soucis ;-) car je dois programmer ceci en C et je ne comprends pas immédiatement ce que signifie ton code. Quel langage est-ce ?

@+,
Tid.

Citation:

---

Envoyé par Tidus159

Quel langage est-ce ?

---

C'est du Haskell, un langage fonctionnel pur à évaluation paresseuse... Plus éloigné du C ça n'existe pas (à peine une exagération) ! :mouarf:

Néanmoins je te suggèrerais de partir simplement de la formule d'Euler, en utilisant un tableau pour stocker les résultats intermédiaires de façon à ne pas avoir à recalculer les mêmes valeurs. Tu devrais pouvoir faire nettement plus rapide que ma solution avec un minimum d'effort.

--
Jedaï

édité après lecture du lien wikipédia...

@+,
Tid.