Décomposition d'un nombre en somme d'éléments tous décroissants

Question

Je recherche à écrire un petit programme utilisant la récursivité au mieux.
Le but est de trouver pour un nombre N les n-uplets dont la somme des éléments est N, deplus les éléments sont par ordre décroissant)
ex pour N=4
(4,0,0,0)-(3,1,0,0)-(2,2,0,0)-(2,1,1,0),(1,1,1,1)
pour n=5
(5,0,0,0,0)-(4,1,0,0,0)-(3,2,0,0,0)-(3,1,1,0,0)-(2,2,1,0,0)-(2,1,1,1,0) et (1,1,1,1,1)

Remarque pour les chimistes : cela permet de trouver l'ensemble des polymères d'un alcane...

mes sources de travail sont pour le moment :
http://www.vbfrance.com/code.aspx?ID=20376
http://www.vbfrance.com/code.aspx?ID=20350

mais j'obtiens plusieurs fois la même décomposition...

Une idée quelqu'un ????

Vb Lover · Answer

Je n'ai pas le moyen de tester ce code, mais ça devrait rendre qqch :


private sub Decompose(byval Somme as integer, byval NTermes as integer, byval Max as integer, byval Resultat as string)
dim i as integer

if Somme=0 then
print Resultat;
' ajout des 0 à la fin
for i=1 to NTermes
print ",0";
next
print
elseif NTermes = 1 then
print Resultat & "," & cstr(Somme)
else
for i=Somme to Max step -1
Decompose Somme-i,NTermes-1,Somme-i,Resultat & "," & cstr(i)
next
end if

end sub


il suffit d'appeler, par exemple pour N=3 :

Decompose 3,3,1,""

après, tu peux améliorer pour l'affichage des virgules, parenthèses, ...

Vb Lover

Vb Lover · Answer

voilà, j'ai pu tester mon code. Donc celui-ci marche, et affiche "tout joli" !  8-) 


Private Sub Decompose(ByVal S As Integer, ByVal Max As Integer, ByVal N As Integer, ByVal Resultat As String)
Dim i As Integer, iMax As Integer
Dim Temp As String

    If S = 0 Then
        Temp = Resultat
        For i = 1 To N
            Temp = Temp & ",0"
        Next
    ElseIf N = 1 Then
        Temp = Resultat & "," & CStr(S)
    Else
        If Resultat = "" Then
            Temp = "("
        Else
            Temp = ","
        End If
        iMax = S
        If iMax > Max Then iMax = Max
        For i = iMax To 1 Step -1
            Decompose S - i, i, N - 1, Resultat & Temp & CStr(i)
        Next
        Exit Sub
    End If

    Print Temp & ")"
    
End Sub


il suffit d'appeler

Decompose N,N,N,""

VB Lover

Décomposition d'un nombre en somme d'éléments tous décroissants

2 réponses

Discussions similaires