Programowanie silni w Javie

Opublikowano w grupie Poland
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;// nasza liczba pozwalająca nam zademonstrować, jak przy użyciu klasy Factorial obliczana jest silnia w języku Java
  for(i=1;i<=number;i++){
      fact=fact*i;
  }
  System.out.println("Silnia liczby "+number+" to: "+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; // znajdowanie silni liczby za pomocą pętli
  }
  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:
  1. 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.
  2. Logika, której wymaga sytuacja oraz wywołanie rekurencji, ale z inną wartością wejściową.
Znalezienie silni w Javie jest doskonałym przykładem zastosowania tego algorytmu:
public static int getFactorial(int f) { // deklaracja metody do znajdowania silni rekurencyjnie w Javie
  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) { // znajdowanie silni liczby za pomocą 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. Programowanie silni w Javie - 1

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.Programowanie silni w Javie - 2

Zwykłe rozwiązanie

public static BigInteger getFactorial(int f) { // znajdowanie silni liczby za pomocą 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.
Komentarze
  • Popularne
  • Najnowsze
  • Najstarsze
Musisz się zalogować, aby dodać komentarz
Ta strona nie ma jeszcze żadnych komentarzy