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, '');

}