Podział Liczb

Definicja

Każdą liczbę naturalną n można wyrazić jako różne sumy liczb naturalnych. Dwa zbiory składników sumy są takie same jeśli różnią się jedynie kolejnością sumowania.

Przykład

Najbardziej trywialnym przypadkiem jest n = 1, którą można wyrazić jedynie jako 1 = 1. Kolejną liczbę n = 2 można zapisać ponownie jako 2 = 2, ale też 2 = 1 + 1. Istnieją dwa różne sposoby zapisu liczby 2, więc istnieje podział tej liczby na 2 sposoby.

Bardziej złożonym przypadkiem jest n = 5, którą moża zapisać na 7 różnych sposobów:

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

W podanym przykładzie warto zauważyć, że zapis 5 = 4 + 1 to jest to samo co 5 = 1 + 4 i oba przypadki to jeden i ten sam podział liczby 5 zgodnie z definicją.

Ciąg liczb

Wyliczając podział liczby dla każdej kolejnej liczby naturalnej można otrzymać następujący ciąg:
1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ..

Implementacja

Wstęp

Problemem, który może się pojawić w trakcie projektowania algorytmu wyznaczającego podział liczby może się okazać wybieranie tylko unikalnych zestawów. Istnieje na to jednak prosta rada. Należy ustalić, że każdy kolejny składnik jest nie większy niż poprzedni. Następnie przy użyciu rekurencji można wyznaczyć ile jest podziałów liczby n.

Ile podziałów?

Przykładowy rekurencyjny algorytm znajdowania liczby podziałów liczby. Funkcja przyjmuje dwa argumenty: n - wartość liczby jeszcze niezsumowana oraz l - wartość ostatnio dodanego składnika.

1. int szukajPodzialu(int n, int l) {
2.   if (n == 0)
3.     return 1;
4.   int licznik = 0;
5.   for (int i = 1; i <= l; i++)
6.     if (n >= i)
7.       licznik += szukajPodzialu(n - i, i);
8.   return licznik;
9. }

(2.) Jeśli n wyniosło 0 to znaczy, że został znaleziony podział liczby i (3.) należy zwrócić 1. W przeciwnym wypadku n jest większe od 0, więc należy poszukać dalszych rozkładów aktualnej wartości n. (4.) Deklarujemy licznik, który zliczy ile zostało dalej znalezionych rozkładów. (5.) W pętli dla każdej możliwej wartości składnika (6.) o ile składnik nie przewyższa n (7.) ustal jaki składnik został dodany i wywołaj szukajPodzialu() z nowymi wartościami argumentów. Warunek (6.) jest bardzo ważny, ponieważ gwarantuje, że n nigdy nie będzie ujemne. Na koniec (8.) wystarczy zwrócić wartość licznik.

Potem wystarczy dopisać jeszcze funkcję podzialn(), która dla podanego argumentu n będzie umiała wywołać szukajPodzialu() z odpowiednimi argumentami. Rzecz jasna podczas rozpoczecia rekurencji należy wskazać, że zmniejszana jest wartość n i ostatnio dodanym składnikiem było n, aby pierwszy elementem podziału liczby mogła być dowolna liczba naturalna pomiędzy 1, a n włącznie.

1. int podzialn(int n) {
2.   return szukajPodzialu(n, n);
3. }

Testowanie funkcji

Poniższa funkcja main() wypisze liczbę podziałów dla pierwszych dziesięciu liczb naturalnych.

1. int main() {
2.   for (int i = 1; i <= 10; i++)
3.     cout << podzialn(i) << endl;
4.   system("pause");
5.   return 0;
6. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz algorytm, który sprawdzi ile jest różnych podziałów liczby w których każda liczba występuje nie więcej niż jeden raz.

Przykładowo dla liczby n = 4 wynikiem ma być 2, ponieważ warunek spełniają tylko podziały 4 = 4, 4 = 3 + 1. Warunku nie spełniają wszystkie pozostałe podziały: 4 = 2 + 2, 4 = 2 + 1 + 1, 4 = 1 + 1 + 1 + 1.

• Kod źródłowy Zadanie 1