Liczby Stallego "drugiego rodzaju" \(\displaystyle{ S(n,k)}\) definiujemy jako liczbę sposobów podziału n-elementowego
Np. S(4,2)=7 gdyż zbiór {1,2,3,4} można rozłożyć na dwa niepuste podzbiory następująco:
\(\displaystyle{ \{1,2,3 \} \cup \{ 4\}}\)
\(\displaystyle{ \{1,2,4 \} \cup \{ 3\}}\)
\(\displaystyle{ \{1,3,4 \} \cup \{ 2\}}\)
\(\displaystyle{ \{1,2 \} \cup \{3, 4\}}\)
\(\displaystyle{ \{2,3,4 \} \cup \{ 1\}}\)
\(\displaystyle{ \{1,3 \} \cup \{2, 4\}}\)
\(\displaystyle{ \{1,4\} \cup \{ 2,3 \}}\)
Liczba Stallego "drugiego rodzaju" spełniają związek rekurencyjny postaci
\(\displaystyle{ S(n,k)=k *S(n-1,k) +S(n-1,k-1)}\)
Przy założeniach \(\displaystyle{ S(n,1)=1}\) oraz \(\displaystyle{ S(n,n)=1}\)
a) Napisz algorytm, w którym zastosowane jest sortowanie dynamiczne wstępujące, obliczający wartość \(\displaystyle{ S(n,k)}\) dla dowolnego \(\displaystyle{ n}\) oraz \(\displaystyle{ k}\)
a) Napisz algorytm, w którym zastosowane jest sortowanie dynamiczne zstępujące, obliczający wartość \(\displaystyle{ S(n,k)}\) dla dowolnego \(\displaystyle{ n}\) oraz \(\displaystyle{ k}\)
algorytm sortowania dynamicznego
-
- Użytkownik
- Posty: 556
- Rejestracja: 15 mar 2009, o 18:13
- Płeć: Kobieta
- Podziękował: 57 razy
- Pomógł: 30 razy
algorytm sortowania dynamicznego
Mam podobny problemy, tylko się trochę różni.Piszę pierwsze zdanie, które się różni.
Liczby Stirlingo "drugiego rodzaju" S(n,k) definiujemy jako liczbę sposobów podziału zbioru n-elementowego na k niepustych podzbiorów \(\displaystyle{ \left( n \in N,1 \le k \le n \right)}\) .
Liczby Stirlingo "drugiego rodzaju" S(n,k) definiujemy jako liczbę sposobów podziału zbioru n-elementowego na k niepustych podzbiorów \(\displaystyle{ \left( n \in N,1 \le k \le n \right)}\) .