Factorial

Q: Jaka jest złożoność czasowa obliczania silni?

Zarówno pętla, jak i rekurencja wykonują jedno mnożenie dla każdej liczby aż do n , więc ich złożoność czasowa wynosi O(n) . Pętla wymaga dodatkowej pamięci O(1) . Rekurencja zachowuje jedną ramkę stosu dla każdego wywołania aż do zwrócenia wyniku przez przypadek bazowy, więc wykorzystuje O(n) pamięci.

Q: Dlaczego 0! jest równe 1?

0! to iloczyn żadnych liczb, a iloczyn bez czynników wynosi 1 , tak samo jak suma bez składników wynosi 0 . Dzięki temu reguła n! = n × (n-1)! jest prawdziwa także dla n = 1 : 1! = 1 × 0! = 1 . Zliczanie się zgadza: istnieje dokładnie jeden sposób na uporządkowanie zera elementów.

Q: Czy rekurencja czy pętla jest lepsza do obliczania silni?

Wykonują te same mnożenia i zwracają tę samą odpowiedź. Wersja rekurencyjna przypomina definicję matematyczną, dlatego jest klasycznym pierwszym ćwiczeniem z rekurencji. Pętla korzysta ze stałej ilości pamięci i nie może doprowadzić do przepełnienia stosu wywołań, dlatego w rzeczywistym kodzie jest lepszym wyborem.

Q: Jaka jest największa silnia, która mieści się w liczbie całkowitej?

12! = 479001600 to największa silnia, która mieści się w 32-bitowej liczbie całkowitej ze znakiem. 20! = 2432902008176640000 to największa silnia dla 64-bitowej liczby całkowitej ze znakiem. Do większych wartości potrzebujesz liczb o nieograniczonym rozmiarze, takich jak int w Pythonie, BigInteger w Javie lub BigInt w JavaScript.

PoczątkującyMatematyka i symulacja Rekurencja

+10

Silnia liczby całkowitej nieujemnej n, zapisywana jako n!, to iloczyn wszystkich liczb całkowitych od 1 do n. Na przykład 4! = 1 × 2 × 3 × 4 = 24. Z definicji 0! = 1. Twoja funkcja otrzymuje n i zwraca n!.

Funkcja

factorial(n: integer) → integer

ninteger: liczba całkowita, której silnię obliczasz
Zwracainteger: iloczyn wszystkich liczb całkowitych od 1 do n, który wynosi 1, gdy n jest równe 0

Ograniczenia

0 ≤ n ≤ 12
Odpowiedź mieści się w 32-bitowej liczbie całkowitej ze znakiem: największa z nich to 12! = 479001600.

Przykłady

Wejście: n = 5
Wyjście: 120
Wyjaśnienie: Pomnóż 1 × 2 × 3 × 4 × 5. Iloczyn bieżący wynosi kolejno 1, 2, 6, 24, a na końcu 120.

Wejście: n = 0
Wyjście: 1
Wyjaśnienie: Nie ma czego mnożyć, a iloczyn bez czynników wynosi 1. Dlatego 0! = 1.

+11 ukrytych testów przy wysłaniu

Pytanie dodatkowe

100! ma 158 cyfr. Czy potrafisz policzyć, ile zer znajduje się na końcu tej liczby, nie obliczając jej?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Silnia ma dwa równoważne opisy i każdy z nich można przełożyć na kod. Jako iloczyn: n! = 1 × 2 × ... × n, co odpowiada pętli. Jako definicja rekurencyjna: 0! = 1 i n! = n × (n-1)!, co odpowiada funkcji wywołującej samą siebie. Oba sposoby wymagają około n mnożeń. Na koniec warto wybrać pętlę, ponieważ nie wymaga stosu wywołań.

Rekurencja z definicji

Intuicja

Silnia jest zdefiniowana za pomocą mniejszej silni: n! = n × (n-1)!. Jeśli wiesz już, że 4! = 24, to 5! = 5 × 24 = 120. Funkcja rekurencyjna zapisuje to zdanie w postaci kodu. Aby obliczyć factorial(n), wywołuje factorial(n-1) i mnoży wynik przez n.

Wywołania muszą mieć miejsce, w którym się zatrzymują — przypadek bazowy: factorial(0) zwraca 1 bez wywoływania czegokolwiek. Każde wywołanie zmniejsza n o jeden, więc dla wartości 5 wywołania przebiegają kolejno: 5, 4, 3, 2, 1, 0. Następnie wyniki wracają w górę łańcucha: 1, 1, 2, 6, 24, 120.

Wykonywanych jest n + 1 wywołań i n mnożeń, więc czas działania wynosi O(n). Każde wywołanie czeka na stosie, aż zakończy się wywołanie znajdujące się niżej, dlatego stos przechowuje n + 1 ramek, co wymaga O(n) pamięci. Gdy n ≤ 12, to niewiele, ale ten sam schemat dla dużych danych wejściowych powoduje przepełnienie stosu.

Algorytm

Jeśli n wynosi 0, zwróć 1. To przypadek bazowy.
W przeciwnym razie wywołaj funkcję dla n-1.
Pomnóż ten wynik przez n i zwróć go.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Mnóż w pętli

Intuicja

Rozwiń rekurencję, a otrzymasz iloczyn narastający. Zacznij od result = 1 i pomnóż go przez 2, następnie przez 3 i tak dalej aż do n. Dla n = 5 wynik kolejno wynosi 1, 2, 6, 24, 120.

Rozpoczęcie od 1 sprawdza się także dla najmniejszych danych wejściowych. Dla n = 0 i n = 1 pętla od 2 do n wykona się zero razy, a funkcja zwróci wartość początkową 1, która jest prawidłową odpowiedzią w obu przypadkach.

Pętla wykonuje n-1 mnożeń, działa w czasie O(n) i przechowuje jedną liczbę, zajmując O(1) pamięci. Nie ma stosu wywołań, który mógłby się przepełnić, dlatego rekruterzy oczekują tej wersji, gdy pokażesz już wersję rekurencyjną.

Algorytm

Ustaw result = 1.
Wykonuj pętlę dla k od 2 do n, włącznie.
Na każdym kroku pomnóż result przez k.
Zwróć result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Pułapki i przypadki brzegowe

Kod obliczający silnię jest krótki, więc błędy kryją się na jego krańcach.

Rozpoczynanie iloczynu od 0. Każde mnożenie pozostawia go na poziomie 0. Początkową wartością iloczynu jest 1.
Zatrzymywanie rekurencji tylko przy n == 1. Wywołana z argumentem 0 funkcja nigdy nie osiąga przypadku bazowego: przechodzi do -1, -2 i tak dalej, aż do przepełnienia stosu. Ustaw n == 0 jako przypadek bazowy.
Używanie pętli z warunkiem k < n zamiast k ≤ n. Pomija to ostatni czynnik i zwraca (n-1)!, więc dla 5 daje 24 zamiast 120.
Ignorowanie przepełnienia. 13! = 6227020800 nie mieści się w 32-bitowej liczbie całkowitej ze znakiem. W Javie i C# iloczyn po cichu zawija się do błędnej liczby, w C przepełnienie ze znakiem ma niezdefiniowane zachowanie, a kompilacja debugowa w Rust powoduje panikę. 64-bitowa liczba całkowita mieści wartości do 20!; dla większych potrzebujesz dużych liczb całkowitych.
W Swift zapisywanie for k in 2...n. Zakres domknięty, którego koniec jest mniejszy od początku, powoduje awarię w czasie działania, gdy n wynosi 0 lub 1.

Najczęstsze pytania4

Jaka jest złożoność czasowa obliczania silni?

Zarówno pętla, jak i rekurencja wykonują jedno mnożenie dla każdej liczby aż do n, więc ich złożoność czasowa wynosi O(n). Pętla wymaga dodatkowej pamięci O(1). Rekurencja zachowuje jedną ramkę stosu dla każdego wywołania aż do zwrócenia wyniku przez przypadek bazowy, więc wykorzystuje O(n) pamięci.

Dlaczego 0! jest równe 1?

0! to iloczyn żadnych liczb, a iloczyn bez czynników wynosi 1, tak samo jak suma bez składników wynosi 0. Dzięki temu reguła n! = n × (n-1)! jest prawdziwa także dla n = 1: 1! = 1 × 0! = 1. Zliczanie się zgadza: istnieje dokładnie jeden sposób na uporządkowanie zera elementów.

Czy rekurencja czy pętla jest lepsza do obliczania silni?

Wykonują te same mnożenia i zwracają tę samą odpowiedź. Wersja rekurencyjna przypomina definicję matematyczną, dlatego jest klasycznym pierwszym ćwiczeniem z rekurencji. Pętla korzysta ze stałej ilości pamięci i nie może doprowadzić do przepełnienia stosu wywołań, dlatego w rzeczywistym kodzie jest lepszym wyborem.

Jaka jest największa silnia, która mieści się w liczbie całkowitej?

12! = 479001600 to największa silnia, która mieści się w 32-bitowej liczbie całkowitej ze znakiem. 20! = 2432902008176640000 to największa silnia dla 64-bitowej liczby całkowitej ze znakiem. Do większych wartości potrzebujesz liczb o nieograniczonym rozmiarze, takich jak int w Pythonie, BigInteger w Javie lub BigInt w JavaScript.

Python

def factorial(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

n = 5

Oczekiwane