If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Funkcja silnia

Jako pierwszy przykład rekurencji, zobaczmy jak obliczyć silnię. Silnię z liczby n zapiszemy jako n!. Jest to iloczyn liczb całkowitych od 1 do n. Na przykład, 5! równa się 12345, 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-obiektów? Dla pierwszego obiektu mamy n możliwości. Dla każdej z n możliwości, pozostaje nam n1 możliwości dla drugiego obiektu, w takim razie mamy n(n1) dla pierwszych dwóch obiektów w kolejności. Teraz, na każdą z tych dwóch pierwszych możliwości, mamy n2 możliwości na trzeci obiekt, to nam daje n(n1)(n2) 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(n1)(n2)21 sposobów na ułożenie n obiektów. Ten iloczyn to po prostu n! (n silnia), ale iloczyn ten zapisany jest od n aż do 1, a nie od 1 do 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-koszulek, ale masz miejsce tylko na k z nich. Na ile różnych sposobów możesz wybrać k-koszulek ze zbioru n-koszulek? Odpowiedź (której nie będziemy starali się tutaj uzasadniać) okazuje się być następująca n!/(k!(nk)!). 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 obiektów z n obiektów. Zakładając, że chcemy wiedzieć ile jest możliwości wyboru n obiektów spośród n obiektów. To proste, ponieważ jest tylko jeden sposób: wybierz wszystkie n obiektów. Więc teraz już wiemy, że używając naszego wzoru, n!/(n!(nn)!) powinno wynosić 1. Ale (nn)! wynosi 0!, więc teraz wiemy, że n!/(n!0!) powinno wynosić 1. Kiedy zredukujemy n! w liczniku i mianowniku, zobaczymy, że 1/(0!) powinno wynieść 1, i tak jest, ponieważ 0! równa się 1.)
Więc teraz już wiemy co oznacza n!. Wynosi ona 1, kiedy n=0, i wynosi 12(n1)n kiedy 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.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.