Discussion :

[Tidus159]

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.

[Jedai]

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 Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï

[Tidus159]

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.

[Jedai]

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) !

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ï

[Tidus159]

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

@+,
Tid.