Uniwersytet Śląski

Wydział Informatyki i Nauki o Materiałach

Sprawozdanie na potrzeby przedmiotu 

Analiza i złożoność obliczeniowa algorytmów

Zadanie 10. Podział Liczby

Michał Daniel

Magisterskie, zaoczne, grupa F

Sosnowiec 2012

1. Treść zadania

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

a jeśli C = 10, to takimi podziałami są:

     1 + 2 + 3 + 4

     1 + 2 + 7

     1 + 3 + 6

     1 + 4 + 5

     1 + 9

     2 + 3 + 5

     2 + 8

     3 + 7

     4 + 6

     10   

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

naturalnej C.

2. Teoria

Materiały teoretyczne przedstawione poniżej nie są autorstwa Michała Daniel i pochodzą z serwisu 

dostępnego pod adresem: 

http://wazniak.mimuw.edu.pl/index.php?

title=Matematyka_dyskretna_1/Wyk%C5%82ad_6:_Permutacje_i_podzia

%C5%82y#Podzia.C5.82y

 (data dostępu 16.01.2012)

Podział liczby n na k składników to przedstawienie n w postaci sumy 

a

0

 + … + a

k−1 

= n,  

gdzie      a

0

 ≤ a

1  

≤ … ≤ a

k−1 

≤ 1. 

Liczbę podziałów n na k składników oznaczamy przez P(n,k). 

Dowód 

Dla podziału n = a

0 

+ … + a

k−1

 definiujemy 

Zauważmy, że wszystkie liczby bi są różne oraz 

A zatem podziały liczby n na k składników stoją w bijektywnej odpowiedniości z podziałami liczby 
na 

k parami różnych składników. Każdy podział

 na k parami różnych składników generuje dokładnie k! rozwiązań równania 

gdzie x

i

>0. Wiemy zaś, że to ostatnie równanie posiada co najwyżej 

rozwiązań. A zatem ciągów  bi , a tym samym podziałów n na k składników, jest co najwyżej 

⟨ ⟩

Dość skutecznym narzędziem do badania podziałów liczb naturalnych są tzw. diagramy Ferrersa. 

Diagram Ferrersa dla podziału n = a

0 

+ … + a

k−1

 składa się z k wierszy o odpowiednio a

i−1 

elementach. 

Własności diagramów Ferrersa:

1. Liczba P(n,k) jest równa liczbie podziałów liczby n (na dowolną liczbę składników) o 

największym składniku równym k.

2. Liczba P(n+k,k) jest równa liczbie podziałów n na co najwyżej k składników. 

3. Rozwiązanie

Algorytm rekurencyjny zapisany w pseudokodzie:

// ciąg – pomocnicza zmienna typu string służąca do przekazywania wyników obliczeń 

// pomiędzy wywołaniami rekurencyjnymi

Podział(n, k, ciąg)
1

if n = 0 then 

2

if paramiRóżny(ciąg)  then wyświetlPodział(ciąg)

3

return;

4

for i := min(k, n) downto 1

5

ciąg := ciąg + „ ” + i

6

Podział(n – i, i, ciąg)

Przebieg algorytmu z wyszczególnieniem rekurencji dla podziału liczby 5:

Podział(5, 5, '')

Podział(0, 5, ' 5') → 5

Podział(1, 4, ' 4')

Podział(0, 1, ' 4 1') → 4 + 1

Podział(2, 3, ' 3')

Podział(0, 2, ' 3 2') → 3 + 2

Podział(1, 1, ' 3 1')

Podział(0, 1, ' 3 1 1')

Podział(3, 2, ' 2')

Podział(1, 2, ' 2 2')

Podział(0, 1, ' 2 2 1')

Podział(2, 1, ' 2 1')

Podział(1, 1, ' 2 1 1')

Podział(0, 1, ' 2 1 1 1')

Podział(4, 1, ' 1')

Podział(3, 1, ' 1 1')

Podział(2, 1, ' 1 1 1')

Podział(1, 1, ' 1 1 1 1')

Podział(0, 1, ' 1 1 1 1 1') 

** Podział liczby na składniki parami różne

** Podział liczby, którego składniki nie są parami różne

Załącznik 1 – implementacja algorytmu w PHP

Algorytm rekurencyjny zapisany w języku PHP wraz z objaśnieniami:

// główna funkcja wyznaczająca podział liczby 
// n – liczba naturalna, której chcemy wyznaczyć podział
// max – maksymalny składnik 
// prefix – parametr pomocniczy do przekazywania wygenerowanego ciągu

function P($n, $max, $prefix) 
{
    // warunek zakończenia rekurencji – jeśli n = 0 tzn, że wyznaczyliśmy podział 
    if ($n == 0) {   
            // sprawdź czy podział jest parami różny, jeśli tak to wyświetl
    

if (pairsDifferent($prefix)) {
    echo $prefix.'<br />';
} 

            return;
    }
  
    // wyznaczamy podziały
    for ($i = min($max, $n); $i >= 1; $i--) 
    {
        P($n-$i, $i, $prefix." ".$i);
    }
}

// funkcja sprawdza czy zadany podział jest parami różny
function pairsDifferent($prefix)
{

$components = explode(' ', $prefix); // zamiana ciągu znaków w tablicę liczb całkowitych
foreach ($components as $k => $c)
{

if ($k > 0 && $c == $components[$k-1]) {

return false;

}

}
return true;

}

// prodecura uruchamiająca algorytm dla zadanej liczby naturalnej
function partition($n) 
{

P($n, $n, '');

}