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ść

Informatyka

Kurs: Informatyka > Rozdział 1

Lekcja 6: Algorytmy rekurencyjne
Informatyka
Informatyka
Algorytmy
Algorytmy rekurencyjne
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie

Silnia rekurencyjna

Google Classroom
Dla dodatnich wartości n, możemy zapisać n!, jak już robiliśmy wcześniej, jako iloczyn liczb zaczynając od n i idąc w dół aż do 1: n! = n⋅(n−1)⋯2⋅1. Ale zauważ, że (n−1)⋯2⋅1 to po prostu inny sposób zapisania (n−1)!, więc możemy napisać, że n!=n⋅(n−1)!. Widziałeś, co przed chwilą zrobiliśmy? Napisaliśmy n! jako iloczyn, w którym jednym z czynników jest (n−1)!. Powiedzieliśmy, że możesz obliczyć n! poprzez obliczenie (n−1)! a następnie pomnożenie wyniku otrzymanego z (n−1)! przez n. Możesz obliczyć silnię z n najpierw obliczając wartość silni z n−1. Powiedzieliśmy zatem, że obliczenie (n−1)! jest podproblemem który rozwiązujemy aby obliczyć n!
Spójrzmy na przykład: obliczyć 5!
  • Możesz obliczyć 5! jako 5⋅4!.
  • Teraz musisz rozwiązać podproblem obliczenia 4!, który możesz policzyć jako 4⋅3!
  • Teraz musisz rozwiązać podproblem obliczenia 3!, które wynosi 3⋅2!.
  • Teraz 2!, które jest równe 2⋅1!.
  • Teraz musisz obliczyć 1!. Mógłbyś powiedzieć, że 1! jest równe 1, ponieważ jest to iloczyn wszystkich liczb całkowitych od 1 do 1. Lub możesz zastosować regułę, że 1!=1⋅0!. Zróbmy to przez zastosowanie formuły.
  • Zdefiniowaliśmy 0! jako równe 1.
  • Teraz możesz policzyć 1!=1⋅0!=1.
  • Mając obliczone 1!=1, możesz policzyć 2!=2⋅1!=2.
  • Mając obliczone 2!=2, możesz policzyć 3!=3⋅2!=6.
  • Mając obliczone 3!=6, możesz policzyć 4!=4⋅3!=24.
  • W końcu, mając obliczone 4!=24, możesz zakończyć przez obliczenie 5!=5⋅4!=120.
Poznaliśmy zatem inny sposób myślenia o tym jak można policzyć wartość n!dla nieujemnych liczb całkowitych n:
  • Jeśli n=0, to z definicji n!=1.
  • W przeciwnym przypadku n musi być dodatnie. Rozwiąż podproblem obliczenia (n−1)!, pomnóż wynik przez n i ogłoś, że n! równa się wynikowi tego mnożenia.
Kiedy w ten sposób obliczamy n!, odwołujemy się do pierwszego przypadku, w którym natychmiast znamy odpowiedź, czyli przypadku bazowego, a następnie wywołujemy drugi przypadek, w którym liczymy tą samą funkcję, ale przy użyciu innych wartości, czyli przypadek rekurencyjny.
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?

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