algorytm generowania wszystkich m-częściowych kompozycji

[karol32]

Witam ,
Mam prośbę....czy możecie rzucić okiem na rozwiązanie tego zadania ...chciał bym się upewnić czy jest w 100% dobrze rozwiązane...lub zaproponujcie jakieś zmiany .z góry dzięki
Treść zadania

Kompozycją m-częściową liczby całkowitej dodatniej n nazywamy uporządkowany ciąg m liczb całkowitych dodatnich, których suma wynosi n. Na przykład mamy sześć 3-częściowych kompozycji liczby 5: (1,1,3), (1,2,2), (1,3,1), (2,2,1), (3,1,1), (2,1,2).
Podaj algorytm generowania wszystkich m-częściowych kompozycji liczby n.

Kod: Zaznacz cały

KOMPOZYCJA (A, n, m, K=1)
If n>0
   then if K<m
      then for i <- 1 to n-(m-k)
         do A[K] =i
            KOMPOZYCJA (A, n-i, m, k+1)
      else
         A[K] =n
         Write (A)

[pfauel]

Sprawdziłem algorytm dla dwóch przykładów i w obu wynik wygląda prawidłowo, także jeśli Tobie też wynik wychodzi prawidłowy to myślę, że można założyć, że jest ok.
Tylko jedną uwagę mam: jeżeli będziesz to przenosił na jakiś język programowania to uważaj na ten array A. Na przykład w Javie array jest referencją - nie jest przekazywana kopia - także w dokładnie takiej postaci, jak jest w twoim pseudokodzie ten algorytm nie zadziała.
Jeśli masz komuś pokazywać ten pseudokod, to właściwie nie wiem, czy można założyć, że przy przekazywaniu tablicy, jako parametru, przekazywana jest kopia. Myślę, że powinieneś jakoś to przynajmniej zaznaczyć.
pozdrawiam

[adam27u]

Cześć,
Jestem w takiej sytuacji że też potrzebuje wykonać to zadanie ale nie bardzo rozumiem jak działa algorytm napisany przez Karola.
Będę bardzo wdzięczny jeżeli ktoś wytłumaczy mi linia po linii jak to działa.

Z góry dziękuję

[OShon]

Jeśli ktoś jest ciekawy jak taką pętlę zrealizować w VBA to oto rozwiązanie:

Kod: Zaznacz cały

Sub test()
    Debug.Print rozklad(5)
    '(1,1,3),(1,2,2),(1,3,1),(2,1,2),(2,2,1),(3,1,1)
    Debug.Print rozklad(6)
    '(1,1,4),(1,2,3),(1,3,2),(1,4,1),(2,1,3),(2,2,2),(2,3,1),(3,1,2),(3,2,1),(4,1,1)
End Sub

Function rozklad(wartosc&) As String
Dim x&, y&, z&, o$
For x = 1 To wartosc
    For y = 1 To wartosc
        For z = 1 To wartosc
            If x + y + z = wartosc Then _
            o = o & "(" & x & "," & y & "," & z & "),"
        Next z
    Next y
Next x
rozklad = Mid(o, 1, Len(o) - 1)
End Function