Dzisiaj porozmawiamy o silni i najczęstszych sposobach jej znajdowania. Jest to jedna z najbardziej podstawowych funkcji, którą programista Java musi znać i umiejętnie wykorzystywać. Okej, zaczynajmy.
Silnia liczby n, oznaczonej jako n!, jest wartością iloczynu (mnożenia) wszystkich liczb naturalnych od 1 do n.
Oto, jak to wygląda (odświeżmy sobie wiedzę z matematyki):
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
5! = 1 * 2 * 3 * 4 * 5 = 120
Jest jeszcze jedna mała zasada dla 0:
!0 = 1
Jeśli chcemy obliczyć różnicę między 6! i 4!:
6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696
Zobaczmy, jak by to wyglądało po zaimplementowaniu w programowaniu. Zbadamy kilka sposobów wykonywania obliczeń silni w Javie.Zwykłe rozwiązanie w programie do liczenia silni w Javie
Oto prosty program silni wykorzystujący pętlę:
class FactorialExample{
public static void main(String args[]){
int i,fact=1;
int number=7;// our number to do the necessary calculations in class Factorial
for(i=1;i<=number;i++){
fact=fact*i;
}
System.out.println("Factorial of "+number+" is: "+fact);
}
}
Nasze wyniki w konsoli będą wyglądać następująco:
Silnia liczby 7 to: 5040
I jeszcze jeden przykład, aby to wszystko wyjaśnić:
public static int getFactorial(int f) {
int result = 1;
for (int i = 1; i <= f; i++) {
result = result * i; // finding factorial of number using loops
}
return result;
}
Nic trudnego: przekazaną liczbę wykorzystujemy jako rozmiar naszej pętli, w której mnożymy przez wszystkie poprzednie liczby, aż dojdziemy do f. Oraz poniższy kod w metodzie main:
System.out.println(getFactorial(6) - getFactorial(4));
Testując kod, widzimy, że otrzymujemy pożądany wynik: 696.Rozwiązanie rekurencyjne
Rekurencja (rekursja) ma miejsce, gdy metoda wywołuje samą siebie. Taka metoda nazywana jest metodą rekurencyjną. Z reguły składa się z dwóch części:- Warunek kończący - gdy warunek kończący jest spełniony, metoda powinna przestać wywoływać samą siebie i zacząć przekazywać wartości w górę. W wypadku jeśli nie ma warunku kończącego, to będziemy mieli nieskończoną pętlę, w której metoda będzie wywoływała się wielokrotnie, aż do momentu, gdy otrzymamy StackOverflowError.
- Logika, której wymaga sytuacja oraz wywołanie rekurencji, ale z inną wartością wejściową.
public static int getFactorial(int f) { // finding factorial of number using recursive solution
if (f <= 1) {
return 1;
}
else {
return f * getFactorial(f - 1);
}
}
Nasz warunek kończący rekurencję będzie miał miejsce, gdy osiągniemy 1. Jeżeli parametr nie jest równy 1, to mnożymy wartość bieżącą przez wynik kolejnego rekurencyjnego wywołania metody (do której przekazujemy wartość bieżącą minus 1)Rozwiązanie z wykorzystaniem Java Stream
Każdy, kto nie jest zaznajomiony z funkcjonalnością Stream w Javie lub każdy, kto chciałby odświeżyć swoją pamięć, skorzysta czytając o tym tutaj.
public static int getFactorial(int f) { // finding factorial of number using Stream
if (f <= 1) {
return 1;
}
else {
return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
}
}
Używamy tutaj specjalnej klasy IntStream, która daje nam dodatkowe możliwości podczas pracy ze strumieniem wartości int. Aby stworzyć taki strumień, używamy jego statycznej metody rangeClosed, która generuje wartości od 2 do f, rosnące o 1. Następnie używamy metody reduce, aby połączyć wszystkie wartości. Dokładniej, pokazujemy jej, jak chcemy połączyć wartości. Na koniec otrzymujemy wartość wynikową za pomocą metody końcowej getAsInt.
Korzystanie z BigInteger
W Javie klasa BigInteger jest często używana do obsługi liczb, zwłaszcza DUŻYCH (ang. big) liczb. Rzeczywiście, jeśli użyjemy int, to maksymalna silnia jaką możemy obsłużyć bez utraty danych, wynosi 31. Dla typu danych long maksymalna silnia wynosi 39. Ale co jeśli potrzebujemy silni 100? Dostosujmy poprzednie rozwiązania do BigInteger.Zwykłe rozwiązanie
public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
BigInteger result = BigInteger.ONE;
for (int i = 1; i <= f; i++)
result = result.multiply(BigInteger.valueOf(i));
return result;
}
Algorytm jest w zasadzie taki sam, ale tutaj wykorzystujemy funkcjonalność BigInteger: BigInteger.ONE to wartość początkowa 1, a multiply() służy do pomnożenia poprzedniej wartości silni i bieżącej liczby.Rozwiązanie rekurencyjne
public static BigInteger getFactorial(int f) {
if (f <= 1) {
return BigInteger.valueOf(1);
}
else {
return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
}
}
Ogólna logika rozwiązania nie ulega zmianie, poza tym, że dodano kilka metod do pracy z BigInteger.Rozwiązanie z wykorzystaniem Java Stream
public static BigInteger getFactorial(int f) {
if (f < 2) {
return BigInteger.valueOf(1);
}
else {
return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
}
}
Zasadniczo wszystko jest takie samo, ale korzystamy z BigInteger. Klasa Stream daje nam metodę mapToObj, której używamy do konwersji wartości int na BigInteger, aby następnie pomnożyć je przez siebie za pomocą metody multiply (a get() zostało dodane, aby uzyskać obiekt z wrappera Optional).
Jeśli uruchomimy którąkolwiek z tych trzech metod z argumentem 100, to unikniemy przepełnienia stosu i otrzymamy poprawny wynik:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Ten artykuł przeczytasz także po angielsku. |
---|
See this article in English for another opportunity to see factorials in action in Java. |
GO TO FULL VERSION