Podział liczby - algorytm

[Bugmenot]

Liczbę naturalną C można przedstawić jako sumę parami różnych liczb naturalnych. Na przykład jeśli C = 6, to możemy C przedstawić na cztery sposoby:
1 + 2 + 3
1 + 5
2 + 4
6

Skonstruuj algorytm wyczerpujący z nawrotami, generujący wszystkie podziały podanej liczby naturalnej C.

Proszę o pomoc!

[mcbob]

Myślę że to się da sprowadzić do jakiejś prostej rekurencji. Nie mam teraz czasu więc pomyśl sam, jak nie wpadniesz na rozwiązanie to jutro wieczorem ci napiszę.

[sonicwork]

musisz napisać pętlę której warunkiem zakończenia będzie dojście dzielnika do zera, a w pętli sprawdzaj wielokrotnie czy liczba a potem reszta z dzielenia może być podzielona kolejno od liczby C-1 w dół unikając powtórzeń np dajmy C=25:
-sprawdź 24 wynik=1
-sprawdź 23 wynik=0
...
-sprawdź 1, wynik=1
-jeśli reszta=0 wyświetl rezultat: 24+1
-sprawdź 23, wynik=1
-sprawdź 22, wynik=0
...
-sprawdź 2, wynik=1
-sprawdź 1, wynik=0
-jeśli reszta=0 wyświetl rezultat: 23+2
...

ten algorytm ma jeden minus nie rozbija liczb składowych na mniejsze znajdzie 20+5 ale nie 20+3+2 więc aby uzyskać wszystkie możliwości trzeba po każdej dodanej liczbie zastosować identyczny algorytm(różnica taka że rozbija na liczby mniejsze od poprzedniej w równaniu), dla 10+9+6 ma to działać tak:
-rezultat 10+9+6
-rozbijanie sumy wszystkiego po 1 liczbie czyli 9+6=15
10+9+6 (powtórka, odrzuć)
10+8+7
10+7+6+2
10+6+5+4
...
-rozbijanie sumy wszystkiego po 2 liczbie (dla każdego równania)
itd ...


algorytm nie jest chyba zbyt wydajny ale jest późno i takie coś mi wpadło do głowy,
możesz jeszcze składać liczby z jak mniejszych powiększając je aż dojdziesz do C to będzie wydajniejsze i łatwiejsze więc sam sobie powinieneś poradzić

[argv]

Algorytm znajdziesz na ważniaku, różni się jedynie kolejnością (tam jest nierosnąca)
Poniżej masz wersje niemalejącą. Jeśli czegoś nie rozumiesz, czytaj ważniaka tak długo aż zrozumiesz

Kod: Zaznacz cały

 /* tutaj przechowujemy podzial */ /* globalna, aby nie przekazywac w te i nazad */int ciag[100]; void dalej(int poz, int pozostalo){    if(pozostalo == 0) {        for(int i = 1; i <= poz-1; i++) {            cout << ciag[i] << " ";        }        cout << endl;    }    else {        for(int k = ciag[poz-1]; k <= pozostalo; k++) {            ciag[poz] = k;            dalej(poz+1, pozostalo - k);        }    }}void podzialy(int n){    ciag[0] = 1;        dalej(1, n);  } 

[mcbob]

Tak jak mówiłem, prosta rekurencja z warunkiem stopu i jedną pętlą w środku. Kiedyś to pisałem, ale jak jest na wazniaku to nie ma sensu odkrywać koła na nowo.