Silnia liczby jest ważnym pojęciem matematycznym. Możesz go używać do wykonywania permutacji i kombinacji, pisania wyrażeń wykładniczych i logarytmicznych oraz obliczania prawdopodobieństwa.

Używasz go, aby znaleźć wiele różnych sposobów zaprojektowania aranżacji siedzenia lub wybrać koszulki na wakacje na Malediwach. Ale jak obliczyć silnię liczby?

Co to jest silnia liczby?

Silnia liczby dodatniej jest iloczynem wszystkich dodatnich liczb całkowitych mniejszych lub równych wartości samej liczby. Liczba, po której następuje wykrzyknik (!) oznacza silnię liczby. Reprezentujesz silnię liczby pięć jako 5! i obliczyć to jako:

5! = 5 * 4 * 3 * 2 * 1 = 120

Innym sposobem wizualizacji jest:

5! = 5 * 4! gdzie 4! = 4 * 3!, 3! = 3 * 2! i tak dalej, aż otrzymasz 1! = 1 * 0! czyli 1.

Użyjesz tej koncepcji do zbudowania naszego programu silniowego przy użyciu popularnej koncepcji zwanej rekurencją.

Co to jest rekurencja?

Rekurencja to proces, w którym funkcja wywołuje samą siebie. Jedną z głównych zalet tego procesu jest to, że dzieli on większy problem na mniejsze części. Dzięki temu problem jest łatwiejszy do rozwiązania.

instagram viewer

Możesz użyć rekurencji do rozwiązania odpowiednich problemów w trzech prostych krokach:

  1. Znajdź przypadek bazowy: Jeśli funkcja zawsze wywołuje samą siebie, proces będzie nieskończony. Aby temu zapobiec, zdefiniuj przypadek bazowy, który stanie się logicznym punktem zatrzymania dla Twojej funkcji. Na przykład w programie silni zatrzymaj obliczenia na zero. Staje się to podstawą problemu.
  2. Znajdź związek między problemem a podproblemami: Podziel większy problem na podproblem. Na przykład problem polega na znalezieniu silni liczby pięć. Załóżmy, że masz odpowiedź silni czterech, czyli 24. Jak uzyskasz silnię liczby pięć za pomocą 24? Mnożąc przez siebie pięć. Jest to relacja między problemem a podproblemem.
  3. Uogólnij relację z kroku 2: Teraz, gdy masz tę relację, uogólnij ją na n. Tak więc silnia liczby n jest iloczynem n i silni n-1.

Możesz użyć tej koncepcji do znajdź sumę n liczb naturalnych, obliczyć NWD, LCM, szereg Fibonacciego i sprawdzić liczby pierwsze.

Pseudokod funkcji silni wykorzystującej rekurencję

To jest jak korzystasz z rekurencji i napisz pseudokod, aby zbudować swój program w dowolnym języku. W różnych językach zmienia się składnia i wykonanie, ale logika pozostaje nienaruszona.

funkcjonowaćFakt(N)
 Jeśli n == 0 Następnie // przypadek podstawowy
Powrót1
Powrót n * Fakt połączenia (n - 1) // relacja uogólniona

Program czynnikowy w C

C był pierwszym językiem programowania wysokiego poziomu, niezależnym od platformy. Ma ścisłą składnię, uwzględnia wielkość liter i wykonuje kod z największą szybkością. Jest to proceduralny język programowania, dlatego deklarujesz dowolną funkcję na górze główny funkcjonować. Oto jak możesz zbudować program silni przy użyciu rekurencji w języku C:

W tym można znaleźć cały kod źródłowy programu silni przy użyciu rekurencji w C, Javie i Pythonie Repozytorium GitHub.

  1. Zaimportuj plik nagłówka standardowego wejścia i wyjścia, aby wyświetlić dane wyjściowe na ekranie.
    #włączać <stdio.h>
  2. Zdefiniuj funkcję fakt i weź liczbę całkowitą N jako argument.
    intfakt(int N){
  3. Zapisz przypadek bazowy funkcji, używając Jeśli instrukcja i sprawdź jej równość za pomocą ==. Jeśli n równa się zero, zwróć jeden.
     jeśli (n == 0)
    powrót1;
  4. Napisz uogólnione równanie i zwróć iloczyn N z wywołaniem funkcji podproblemu n-1.
    powrót n * fakt (n - 1);
    }
  5. Zadeklaruj główną funkcję i zainicjuj zmienną typu integer, aby przechowywać liczbę, której silnię chcesz znaleźć.
    intgłówny(){
    int liczba = 5;
  6. Wyświetl silnię liczby za pomocą printf() funkcjonować. %D jest specyfikatorem formatu dziesiętnego. Użyj każdego ze specyfikatorów formatu, aby zastąpić go liczbą, której silnię chcesz znaleźć, i uzyskaj wynik, wywołując funkcję.
     printf("Silnia %d wynosi %d", liczba, fakt (liczba));
    powrót0;
    }

Program czynnikowy w Javie

Java jest skompilowanym językiem programowania i jest niezależny od platformy. Przechowujesz cały kod wewnątrz pliku klasa a egzekucja zaczyna się od główny funkcjonować. Rozróżniana jest wielkość liter i ścisła składnia. Kod jest nieco dłuższy, ale szybszy w porównaniu do Pythona. Oto jak możesz zbudować program silni przy użyciu rekurencji w Javie:

  1. Zdefiniuj klasę główną.
    klasaGłówny{
  2. Zdefiniuj funkcję statyczną z zwracanym typem int, która przyjmuje zmienną n typu całkowitego. Zadeklarowałeś metodę statyczną, ponieważ główna metoda w Javie jest również deklarowana jako statyczna. Ponadto nie można wywołać metody niestatycznej z instancji statycznej.
    statycznyintfakt(int N){
  3. Zapisz przypadek bazowy funkcji, używając Jeśli instrukcja i sprawdź jej równość za pomocą ==. Jeśli n równa się zero, zwróć jeden.
     jeśli (n == 0)
    powrót1;
  4. Napisz uogólnione równanie i zwróć iloczyn N z wywołaniem funkcji podproblemu n-1.
    powrót n * fakt (n - 1);
     }
  5. Zadeklaruj główną funkcję w Javie. Zadeklaruj modyfikator dostępu jako publiczny, więc może być dostępny dla wszystkich innych klas i metod. Deklarujesz główną funkcję jako statyczny aby kompilator mógł go wywołać bez tworzenia instancji klasy. Zwracany typ to próżnia, i akceptuje argumenty typu Strunowy. Zapisz numer, którego silnię chcesz znaleźć.
    publicznystatycznypróżniagłówny(String[] argumenty){
    int liczba = 5;
  6. Użyj println() metoda, instancja DrukujStrumień klasa, zdefiniowana w System class, aby wyświetlić silnię liczby.
     System.out.println("silnia " + liczba + " Jest " + fakt (liczba));
     }
    }

Program czynnikowy w Pythonie

Pisanie kodu w Pythonie jest bardzo łatwe i przyjemne. Ponieważ jest to interpretowany język niezależny od platformy, nie musisz deklarować typu danych zmiennych. Unikasz także konieczności deklarowania klas i importowania bibliotek dla tak prostego programu. Plac zabaw jest gotowy do rozpoczęcia kodowania.

Składnia jest łatwiejsza, z małą długością kodu, ale wykonanie zajmuje trochę więcej czasu niż w innych językach. Oto jak możesz zbudować program silni przy użyciu rekurencji w Pythonie:

  1. Zdefiniuj fakt funkcji, który przyjmuje jako argument n.
    pokfakt(N):
  2. Zapisz przypadek bazowy funkcji, używając Jeśli instrukcja i sprawdź jej równość za pomocą ==. Jeśli n równa się zero, zwróć jeden.
     jeśli n == 0:
    powrót1
  3. Napisz uogólnione równanie i zwróć iloczyn N z wywołaniem funkcji podproblemu n-1.
    powrót n * fakt (n-1)
  4. Zapisz liczbę, której silnię chcesz znaleźć i wyświetl ją za pomocą instrukcji print.
    liczba = 5;
    wydrukować("silnia", numer, "Jest", fakt (liczba))

Istnieje wiele zastosowań rekurencji

Rekurencja jest skutecznym sposobem rozwiązywania problemów. Jest sednem sztucznej inteligencji i ma rzeczywiste zastosowania w grach logicznych, takich jak szachy czy Sudoku.

Jest to również potężna metoda sortowania struktur danych, takich jak drzewo, lub algorytmów sortowania, takich jak sortowanie szybkie i sortowanie przez scalanie. Możesz także użyć rekurencji w algorytmach wyszukiwania, takich jak wyszukiwanie binarne, wyrażeniach matematycznych, takich jak ciąg Fibonacciego i nie tylko.