Strona główna » Algorytmy » Artykuły » Symbol Newtona
( )nk
 

Symbol Newtona

https://mattomatti.com/a0024

Wstęp

Symbol Newtona to funkcja dwóch argumentów całkowitych nieujemnych. Najpowszechniej używany jest wzór:

Istnieje również wzór rekurencyjny:

Symbol Newtona jest wykorzystywany najczęściej podczas różnego rodzaju zadań kombinatorycznych. Powyższe wzory nie zawsze są najbardziej efektywną metodą wyliczania żądanej wartości. W dalszej części artykułu zostaną przedstawione trzy metody.

Implementacja

Wzór z silnią

Wykorzystanie silni do obliczenia symbolu Newtona jest bardzo wygodne ze względu na bardzo dużo składników, które się redukują. Jednak efektywność takiego kodu jest bardzo trudno zoptymalizować i bardzo szybko może się okazać, że zmienna przekroczyła zakres zmiennej. Warto zauważyć, że zaletą takiego algorytmu jest liniowa zależność obliczeń od kodu.

Poniżej został zamieszczony niezoptymalizowany kod liczący symbol Newtona z definicji:

  1. int symbolNewtona(int n, int k) {
  2.   int s = 1;
  3.   for (int i = 2; i <= n; i++)
  4.     s *= i;
  5.   for (int i = 2; i <= k; i++)
  6.     s /= i;
  7.   for (int i = 2; i <= n - k; i++)
  8.     s /= i;
  9.   return s;
  10. }

(2.) Ustal wynik na neutralny element mnożenia 1. (3. - 4.) Oblicz licznik, a następnie podziel (5. - 8.) przez wszystkie elementy z mianownika. Na koniec (9.) zwróć wynik.

Rekurencja

Problem z przekraczeniem zakresu wartości typu zmiennej jest zastosowanie rekurencji. Dzięki temu przechowywana wartość będzie mniejsza, równa wartości wynikowej. Nie jest to jednak rozwiązanie idealne, ponieważ w trakcie wykonywania rekurencji niektóre wartości są obliczane więcej niż jeden raz.

Oznaczmy dwumian Newtona przez symbol F. Przykładowo wartość F(4, 2) będzie obliczona jako suma:

F(4, 2) = F(3, 1) + F(3, 2) =
  F(2, 0) + F(2, 1) + F(2, 1) + F(2, 2) =
  F(2, 0) + F(1, 0) + F(1, 1) + F(1, 0) + F(1, 1) + F(2, 2)

Jak można zauważyć niektóre wartości są wyliczane więcej niż jeden raz. W przypadku większych wartości n i k powtarzających się czynników jest znacznie więcej.

Kod realizujący wyliczanie symbolu Newtona przy wykorzystaniu rekurencji wygląda następująco:

  1. int symbolNewtona(int n, int k) {
  2.   if (k == n || k == 0)
  3.     return 1;
  4.   return symbolNewtona(n-1, k-1) + symbolNewtona(n-1, k);
  5. }

Trójkąt Pascala

Symbolem Newtona można obliczyć współczynnik stojący w rozwinięciu wyrażenia (a + b)n na k-tej pozycji. Zapisując wszystkie wartości dla każdego n otrzymuje się trójkąt Pascala. Trzecia metoda wyznaczania wartości symbolu Newtona polega na wyliczeniu n wierszy i zwróceniu k-tej wartości z ostatniego, wyliczonego wiersza.

Chociaż z perspektywy analizy program działa oszczędniej niż rozwiązanie rekurencyjne, bo znowu nie zostanie przekroczona wartość wynikowa w trakcie obliczeń, ale te same wartości nie są wyliczane po kilka razy. Niestety złożoność obliczeniowa jest kwadratowa O(n2).

Poniżej został przedstawiony kod realizujący zadanie:

  1. int symbolNewtona(int n, int k) {
  2.   int* tab = new int[n + 1];
  3.   tab[0] = 1;
  4.   tab[1] = 0;
  5.   for (int i = 1; i < n; i++) {
  6.     for (int j = i; j > 0; j--) {
  7.       tab[j] = tab[j] + tab[j - 1];
  8.     }
  9.     tab[i + 1] = 0;
  10.   }
  11.   int wynik = tab[k];
  12.   delete tab;
  13.   return wynik;
  14. }

(2.) Zaalokuj miejsce w pamięci o długości ostatniego wiersza oraz jednego miejsca wolnego. (3.) Wpisz wartość z pierwszego wiersza i zakończ listę (4.) wartością 0. (5.) Wylicz kolejne wiersze: (6. - 8.) za każdym razem sumując odpowiednie wartości i (9.) stawiając na koniec 0. Wartość 0 pomaga tutaj uprościć kod, ponieważ nie trzeba rozpatrywać oddzielnie przepisywania ostatniej wartości listy. Bez zerowania sumowane byłyby "śmieci" z pamięci komputera, więc ostateczny wynik nie byłby poprawny. Na koniec (11.) należy pobrać odpowiednią wartość, (12.) zdealokować tablice i (13.) zwrócić wynik.

Testowanie funkcji

Poniższa funkcja main() wczytuje od użytkownika wartości n i k, a następnie wypisuje wynik symbolu Newtona .

  1. int main() {
  2.   int n, k;
  3.   cout << "Podaj n: ";
  4.   cin >> n;
  5.   cout << "Podaj k: ";
  6.   cin >> k;
  7.   cout << "/ " << n << " \\ = " << symbolNewtona(n, k);
  8.   cout << "\n\\ " << k << " /\n";
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz zoptymalizowany kod wykorzystujący wzór z silnią do obliczenia symbolu Newtona. Przetestuj napisaną funkcję.