Podział liczby m na n elementów

[Platyna]

Mam nadzieję, że to odpowiedni dział na ten temat :P

Ma może ktoś jakiś pomysł jak można szybko i zgrabnie wyliczyć ile istnieje podziałów danej liczby m na n elementów?

Podział liczby to taki ciąg liczb a1,a2,a3...an że a1+a2+a3+...+an=m i a1<a2<a3<...<an?

Potrzebne mi to do jednego zadanka z kółka i nie mogę wykombinować :P

 

EDIT: W sumie chyba to się bardziej nadaje do C, C++. Może ktoś przenieść? :)

[TeoTN]

#include iostream;
using namespace std;
int main()
{
int liczba, n, m=0;
cin >> liczba;
if m<liczba;
{
for (n=2; n<liczba; n++)
{
if (liczba mod n == 0)
{
if (!m<liczba)
{
cout << n;
m+=n;
}
}
}
}
return 0;
}

 

Chyba w ten sposób, ale nie jestem pewien, czy o to chodziło, ani czy poprawnie kodowo, bo w C++ już dawno nie pisałem ^^

[Platyna]

Chyba źle mnie zrozumiałeś. Nie mam pojęcia co robi ten kod, ale na pewno nie to o co mi chodziło :P

Ale już sobie sam poradziłem. Zrobiłem to w ten sposób że mam tablice 3 wymiarową t[m+1][n+1][m+1] przechowującą ile istnieje podziałów liczby m (pierwszy wymiar) na n elementów (2 wymiar) których pierwszym składnikiem jest x (3 wymiar). I wiadomo od razu ile jest podziałów każdej liczby na 1 element wiec część tablicy możemy od razu uzupełnić. A pozostałe komórki tablicy sobie uzupełniamy wiedząc, że podziałów liczby m na n elementów zaczynających się od x jest tyle ile podziałów liczby m-x na n-1 elementów zaczynających się od x, x+1, x+2...(m-x)/(n-1)

czyli:

for(int i=x;i<=(m-x)/(n-1))

t[m][n][x]+=t[m-x][n-1]

 

I mając tą tablicę idzie wyszukać k-ty podział liczby m na n elementów o co właśnie w zadaniu chodziło :P