Witam.
Dostałem do napisania algorytm co prawda w schemacie NS, ale to mniej ważne na oba rodzaje liczb Stirlinga. Wiem jak się je liczy normalnie, natomiast jak ułożyć do tego algorytm to nie mam pojęcia.
Mógłby ktoś podpowiedzieć jak się zabrać za to przynajmniej z jednym rodzajem, drugie spróbowałbym już sam.
[Algorytm] Liczby Stirlinga
-
JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
[Algorytm] Liczby Stirlinga
Spróbujmy zająć się liczbami drugiego rodzaju.
Dane wejściowe: liczby \(\displaystyle{ n}\) oraz \(\displaystyle{ k}\) naturalne (włącznie z zerem).
Najprościej będzie wykorzystać własność rekurencyjną liczb II rodzaju (stąd nasz algorytm będzie rekurencyjny:
\(\displaystyle{ \left\{\begin{matrix}n\\k\\\end{matrix}\right\}=k\left\{\begin{matrix}n - 1\\k\\\end{matrix}\right\}+\left\{\begin{matrix}n - 1\\k - 1\\\end{matrix}\right\}}\)
Należy określić również wartości podstawowe:
\(\displaystyle{ {\displaystyle \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1,\quad {\mbox{ }}\quad \left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,\quad {\mbox{ }}\quad \left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0\quad,\quad \left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1.}}\)
Określamy funkcję \(\displaystyle{ S2(n,k)}\) podanym algorytmem:
1. sprawdź, czy \(\displaystyle{ k>n}\), jeżeli tak, zwróć \(\displaystyle{ 0}\),
2. jeżeli \(\displaystyle{ k=1}\) lub \(\displaystyle{ k=n}\), zwróć \(\displaystyle{ 1}\),
3. jeżeli \(\displaystyle{ k=0}\) oraz \(\displaystyle{ n\neq 0}\), zwróć \(\displaystyle{ 0}\),
4. jeżeli \(\displaystyle{ k=0}\) oraz \(\displaystyle{ n=0}\), zwróć \(\displaystyle{ 1}\),
5. w przeciwnym razie zwróć \(\displaystyle{ k\cdot S2(n-1,k)+S2(n-1,k-1)}\).
Dane wejściowe: liczby \(\displaystyle{ n}\) oraz \(\displaystyle{ k}\) naturalne (włącznie z zerem).
Najprościej będzie wykorzystać własność rekurencyjną liczb II rodzaju (stąd nasz algorytm będzie rekurencyjny:
\(\displaystyle{ \left\{\begin{matrix}n\\k\\\end{matrix}\right\}=k\left\{\begin{matrix}n - 1\\k\\\end{matrix}\right\}+\left\{\begin{matrix}n - 1\\k - 1\\\end{matrix}\right\}}\)
Należy określić również wartości podstawowe:
\(\displaystyle{ {\displaystyle \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1,\quad {\mbox{ }}\quad \left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,\quad {\mbox{ }}\quad \left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0\quad,\quad \left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1.}}\)
Określamy funkcję \(\displaystyle{ S2(n,k)}\) podanym algorytmem:
1. sprawdź, czy \(\displaystyle{ k>n}\), jeżeli tak, zwróć \(\displaystyle{ 0}\),
2. jeżeli \(\displaystyle{ k=1}\) lub \(\displaystyle{ k=n}\), zwróć \(\displaystyle{ 1}\),
3. jeżeli \(\displaystyle{ k=0}\) oraz \(\displaystyle{ n\neq 0}\), zwróć \(\displaystyle{ 0}\),
4. jeżeli \(\displaystyle{ k=0}\) oraz \(\displaystyle{ n=0}\), zwróć \(\displaystyle{ 1}\),
5. w przeciwnym razie zwróć \(\displaystyle{ k\cdot S2(n-1,k)+S2(n-1,k-1)}\).