Silnia w programowaniu w Javie

Dziś porozmawiamy o silniach. To jedna z najbardziej podstawowych funkcji, którą programista musi znać, a jednocześnie umieć z nią pracować. Więc zacznijmy. Silnia n jest wartością iloczynu (mnożenia) wszystkich liczb naturalnych od 1 do n, co oznacza się jako n! Jak to wygląda:

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

I jeszcze jedna mała zasada dla 0:

!0  = 1

Jeśli chcemy na przykład uzyskać różnicę silni 6! i 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

Przyjrzyjmy się, jak to by wyglądało w Javie i poznajmy kilka sposobów obliczania silni.

Zwykłe rozwiązanie

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Nic skomplikowanego: otrzymaną liczbę wykorzystujemy jako wielkość naszego cyklu, w którym mnożymy przez wszystkie poprzednie liczby, aż dotrzemy do f. I w głównej:

System.out.println(getFactorial(6) - getFactorial(4));

Sprawdzamy i uzyskujemy pożądany wynik: 696.

Rozwiązanie rekurencyjne

Rekurencja wykonuje pewną logikę, wywołując metodę na sobie. Ta metoda nazywa się rekurencyjną. Zwykle składa się z dwóch części:

1. warunek wyjścia metody, po osiągnięciu którego metoda powinna przestać się wywoływać i zacząć przekazywać wartości. W przeciwnym razie wywołanie metody na niej samej spowoduje nieskończoną pętlę i w rezultacie wygeneruje błąd StackOverflowError .

2. pewne przetwarzanie (logika) niezbędne w danej sytuacji + wywołanie samego siebie, ale z inną wartością przychodzącą.

Naszym idealnym przykładem dzisiejszej rekurencji jest znalezienie silni:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Warunek wyjścia z rekurencji stawiamy w momencie, gdy osiągnie ona wartość 1. Jeżeli argumentem nie jest 1, to aktualną wartość mnożymy przez wynik kolejnego wywołania tej metody (gdzie wysyłamy aktualną wartość -1).

Rozwiązanie ze strumieniem

Dla tych, którzy nie znają funkcjonalności streamu lub chcą odświeżyć sobie pamięć, przydatna będzie lektura .

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Tutaj używamy specjalnej klasy IntStream, która zapewnia dodatkowe możliwości podczas pracy ze strumieniem z wartości int. Do stworzenia takiego strumienia wykorzystujemy jego statyczną metodę rangeClosed, która tworzy wartości od 2 do f włącznie z krokiem 1. Następnie łączymy wszystkie wartości metodą redukcji, czyli pokazujemy w niej jak chcemy je połączyć. Na koniec uzyskaną wartość otrzymujemy za pomocą metody terminalowej getAsInt.

Używanie BigIntegera

W Javie klasa BigInteger jest często używana do obsługi liczb, zwłaszcza liczb BIG . W końcu, jeśli użyjemy int, to maksymalna silnia, którą możemy przyjąć bez utraty danych, wynosi 31, a długo - 39. Ale co, jeśli potrzebujemy silni równej 100? Przyjrzyjmy się poprzednim rozwiązaniom, ale używając BigInteger.

Zwykłe rozwiązanie

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

Algorytm zliczania jest zasadniczo taki sam, ale tutaj wykorzystujemy możliwości BigInteger: BigInteger.ONE - aby ustawić wartość początkową na 1. multiply - mnożenie pomiędzy poprzednią wartością silni i aktualną liczbą.

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, z wyjątkiem dodania niektórych metod pracy z BigInteger.

Rozwiązanie ze strumieniem

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 z BigInteger. W strumieniu mamy teraz metodę mapToObj, za pomocą której konwertujemy wartości int na BigInteger, aby później je pomnożyć za pomocą metody multiply (no cóż, dodaliśmy get, aby pobrać obiekt z opakowania Opcjonalne ). Jeśli uruchomimy którąkolwiek z tych trzech metod z argumentem 100, to nie będziemy mieli przepełnienia i otrzymamy:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000