Funkcja silnia

Jako pierwszy przykład rekurencji, zobaczmy jak obliczyć silnię. Silnię z liczby $n$n zapiszemy jako $n!$n, !. Jest to iloczyn liczb całkowitych od 1 do $n$n. Na przykład, 5! równa się $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5$1, dot, 2, dot, 3, dot, 4, dot, 5, czyli 120. (Uwaga: Kiedykolwiek piszemy o silni, wszystkie wykrzykniki odnoszą się do silni, a nie do kładzenia nacisku na coś w tekście.)

Pewnie zastanawiasz się, po co kładziemy nacisk na silnię. Jest ona bardzo przydatna, gdy próbujemy policzyć ile jest różnych ustawień dla obiektów, albo na ile różnych sposobów możemy połączyć te obiekty. Na przykład, ile jest różnych możliwości ułożenia $n$n-obiektów? Dla pierwszego obiektu mamy $n$n możliwości. Dla każdej z $n$n możliwości, pozostaje nam $n-1$n, minus, 1 możliwości dla drugiego obiektu, w takim razie mamy $n \cdot (n-1)$n, dot, left parenthesis, n, minus, 1, right parenthesis dla pierwszych dwóch obiektów w kolejności. Teraz, na każdą z tych dwóch pierwszych możliwości, mamy $n-2$n, minus, 2 możliwości na trzeci obiekt, to nam daje $n \cdot (n-1) \cdot (n-2)$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis możliwości na pierwsze trzy obiekty w kolejności. I tak dalej, dopóki nie dotrzemy do ostatnich dwóch obiektów, aż pozostanie nam tylko jeden obiekt. Ogółem, mamy $n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, dot, left parenthesis, n, minus, 2, right parenthesis, \@cdots, 2, dot, 1 sposobów na ułożenie $n$n obiektów. Ten iloczyn to po prostu $n!$n, ! ($n$n silnia), ale iloczyn ten zapisany jest od $n$n aż do 1, a nie od 1 do $n$n.

Kolejnym zastosowaniem silni jest obliczanie ile mamy możliwości wyboru obiektów spośród zbioru obiektów. Na przykład, załóżmy, że wybierasz się na wycieczkę i musisz zdecydować, które koszulki masz ze sobą zabrać. Powiedzmy, że posiadasz $n$n-koszulek, ale masz miejsce tylko na $k$k z nich. Na ile różnych sposobów możesz wybrać $k$k-koszulek ze zbioru $n$n-koszulek? Odpowiedź (której nie będziemy starali się tutaj uzasadniać) okazuje się być następująca $n! / (k! \cdot (n-k)!)$n, !, slash, left parenthesis, k, !, dot, left parenthesis, n, minus, k, right parenthesis, !, right parenthesis. Z tego wynika, że silnia może być naprawdę bardzo przydatna. Możesz dowiedzieć się więcej o permutacjach i kombinacjach tutaj, ale nie potrzebujesz tego do realizacji algorytmu silni.

Funkcja silnia zdefiniowana jest dla wszystkich dodatnich liczb całkowitych, oraz 0. Jaką wartość powinna mieć 0! ? Jest to iloczyn wszystkich liczb całkowitych większych lub równych 1, a mniejszych lub równych 0. Ale nie ma takich liczb całkowitych. Dlatego definiujemy 0! , aby równało się elementowi neutralnemu mnożenia, który wynosi 1. (Definiując 0! =1 udaje nam się ładnie zazębić formułę wyboru $k$k obiektów z $n$n obiektów. Zakładając, że chcemy wiedzieć ile jest możliwości wyboru $n$n obiektów spośród $n$n obiektów. To proste, ponieważ jest tylko jeden sposób: wybierz wszystkie $n$n obiektów. Więc teraz już wiemy, że używając naszego wzoru, $n! / (n! \cdot (n-n)!)$n, !, slash, left parenthesis, n, !, dot, left parenthesis, n, minus, n, right parenthesis, !, right parenthesis powinno wynosić 1. Ale $(n-n)!$left parenthesis, n, minus, n, right parenthesis, ! wynosi 0!, więc teraz wiemy, że $n! / (n! \cdot 0!)$n, !, slash, left parenthesis, n, !, dot, 0, !, right parenthesis powinno wynosić 1. Kiedy zredukujemy $n!$n, ! w liczniku i mianowniku, zobaczymy, że $1/(0!)$1, slash, left parenthesis, 0, !, right parenthesis powinno wynieść 1, i tak jest, ponieważ 0! równa się 1.)

Więc teraz już wiemy co oznacza $n!$n, !. Wynosi ona 1, kiedy $n=0$n, equals, 0, i wynosi $1 \cdot 2 \cdots (n-1) \cdot n$1, dot, 2, \@cdots, left parenthesis, n, minus, 1, right parenthesis, dot, n kiedy $n$n jest dodatnie.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.