Silnia

Silnia

Definicja

Silnia w matematyce operuje na zbiorze liczb naturalnych i oznacza iloczyn wszystkich liczb nie większych od n. Oznaczana jest poprzez wykrzyknik ! tj. n!. Funkcję tę można zapisać przy pomocy wzoru rekurencyjnego:

Przykład

Przykładowo zapis 5! oznacza 5 · 4 · 3 · 2 · 1 = 120.

Implementacja

Najprostsza implementacja silni w C++ polega na wykorzystaniu rekurencji. Wtedy potrzebny jest w funkcji zaledwie jeden warunek i dwie instrukcje zwracające odpowiednią wartość:

1. long long silnia(int n) {
2.   if (n == 0) {
3.     return 1;
4.   } else {
5.     return n * silnia(n - 1);
6.   }
7. }

(1.) Dla podanego argumentu n zwróć n!. Ze względu na fakt, że wartości silni bardzo szybko są duże to do przechowywania wartości używany jest typ zmiennej long long. (2.) Sprawdź warunek i jeśli n to 0 to (3.) zwróć jeden. (4.) W przeciwnym wypadku (5.) rekurencyjnie pobierz kolejne czynniki.

Rozwiązanie rekurencyjne jest eleganckie. Można je skrócić do zaledwie jednej linijki używając skróconej instrukcji if. Należy jednak pamiętać, że przy każdym wywołaniu jest tworzona kopia zmiennej n. Oznacza to, że do obliczenia n! zostanie utworzonych n kopii zmiennej co niepotrzebnie zwiększa zapotrzebowanie programu na pamięć komputera. W tym przypadku lepszym pomysłem jest rozwiązanie iteracyjne:

1. long long silnia_iter(int n) {
2.   long long w = n;
3.   while (--n) {
4.     w *= n;
5.   }
6.   return w;
7. }

(2.) Zadeklaruj zmienną wynikową i przypisz jej wartość n. (3. - 5.) Następnie pomnóż w przez każdą liczbę z zakresu [1, n - 1]. (6.) Zwróć wynik w.

Podwójna silnia

Definicja

Podwójna silnia, oznaczana jako n!!, oznacza, że z zakresu [1, n] mnożone są tylko liczby o tej samej parzystości co n. Dla podwójnej silni wzór rekurencyjny jest nieco inny:

Przykład

W tym przypadku 5!! = 5 · 3 · 1 = 15, a w przypadku n parzystego np. n = 6: 6!! = 6 · 4 · 2 = 48.

Uwaga: nie należy mylić n!! z (n!)!. Te dwa, choć podobne zapisy znaczą co innego. W pierwszym przypadku mamy do czynienia z silnią podwójną tj. 3!! = 3 · 1, ale w drugiej jest to silnia silni czyli (3!)! = (3 · 2 · 1)! = 6! = 6 · 5 · 4 · 3 · 2 · 1 = 720.

Implementacja

Rekurencyjna wersja wzoru nie powinna stanowić problemu - wystarczy tylko dodać odpowiedni warunek i zmienić zasadę wyznaczania następnego czynniku:

1. long long silniapodwojna(int n) {
2.   if (n == 0 || n == 1) {
3.     return 1;
4.   } else {
5.     return n * silniapodwojna(n - 2);
6.   }
7. }

Tak samo jak w przypadku wersji rekurencyjnej w iteracyjnej też nie trzeba dużo zmieniać. Warto jednak zauważyć, że zamiast sprawdzać dwóch warunków czy n = 0 lub n = 1 to wystarczy sprawdzić czy n > 1. Ten drobny szczegół pozwoli na łatwiejsze opracowanie kodu dla ogólnego wzoru silni.

1. long long silniapodwojna_iter(int n) {
2.   long long w = 1;
3.   while (n > 1) {
4.     w *= n;
5.     n -= 2;
6.   }
7.   return w;
8. }

Wzór ogólny silni

Definicja

Silnia posiada wzór ogólny, którego przypadkami jest n! i n!!. Zapis

należy czytać jako:

Rekurencyjny wzór ogólny silni wygląda następująco:

Implementacja

W przypadku pisania kodu dla ogólnego wzoru silni funkcja silnia() powinna przyjmować dwa argumenty n - liczba, której silnia jest obliczana oraz k - rząd silni. Rekurencyjna wersja będzie wyglądać wtedy następująco:

1. long long silnia(int n, int k = 1) {
2.   if (n < k) {
3.     return 1;
4.   } else {
5.     return n * silnia(n - k, k);
6.   }
7. }

Testowanie funkcji

W celu przetestowania dowolnej funkcji można skorzystać z poniższego fragmentu kodu. Nalezy pamiętać, aby odpowiednio zmienić nazwę wywoływanej funkcji.

1. int main () {
2.   int n, k;
3.   cin >> n >> k;
4.   cout << silnia(n, k) << endl;
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Silnia
• Kod źródłowy Podwójna silnia
• Kod źródłowy Wzór Ogólny

Zadania

Zadanie 1

Napisz program, który wczyta od użytkownika dwie liczby całkowite n i k. Następnie program powinien obliczyć silnię rzędu k liczby n. Algorytm nie może wykorzystywać rekurencji.

• Kod źródłowy Implementacja