Factorial sa Java Programming

Ngayon ay pag-uusapan natin ang tungkol sa mga factorial. Ito ay isa sa mga pinakapangunahing function na kailangang malaman ng isang programmer, at sa parehong oras ay magagawang magtrabaho kasama nito. Kaya simulan na natin. Ang factorial ng n ay ang halaga ng produkto (multiplikasyon) ng lahat ng natural na numero mula 1 hanggang n, na tinutukoy bilang n! Ano ang hitsura nito:

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

At isa pang maliit na panuntunan, para sa 0:

!0  = 1

Kung gusto natin, halimbawa, makuha ang factorial difference 6! at 4!:

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

Tingnan natin kung ano ang magiging hitsura nito sa Java at unawain ang ilang paraan kung saan maaaring kalkulahin ang factorial.

Ang karaniwang solusyon

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

Walang kumplikado: ginagamit namin ang natanggap na numero bilang sukat ng aming cycle, kung saan kami ay nag-multiply sa lahat ng naunang numero hanggang sa maabot namin ang f. At sa pangunahing:

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

Sinusuri namin at makuha ang nais na resulta: 696.

Recursive na solusyon

Ang recursion ay gumagawa ng ilang lohika sa pamamagitan ng pagtawag ng isang pamamaraan sa sarili nito. Ang pamamaraang ito ay tinatawag na recursive. Karaniwang binubuo ito ng dalawang bahagi:

1. kondisyon ng paglabas ng pamamaraan, kapag naabot kung saan dapat ihinto ng pamamaraan ang pagtawag sa sarili nito at simulan ang pagpasa ng mga halaga. Kung hindi, makakakuha tayo ng walang katapusang loop mula sa pagtawag sa isang paraan sa sarili nito at, bilang resulta, isang StackOverflowError .

2. ilang pagproseso (lohika) na kinakailangan sa isang naibigay na sitwasyon + pagtawag sa sarili nito, ngunit may ibang papasok na halaga.

Ang aming perpektong halimbawa para sa recursion ngayon ay ang paghahanap ng factorial:

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

Itinakda namin ang kundisyon para sa pag-alis sa recursion kapag umabot sa 1. Kung ang argumento ay hindi 1, pagkatapos ay i-multiply namin ang kasalukuyang halaga sa resulta ng susunod na tawag sa paraang ito (kung saan ipinapadala namin ang kasalukuyang halaga -1).

Solusyon sa Stream

Para sa mga hindi alam ang paggana ng stream o para sa mga gustong i-refresh ang kanilang memorya, magiging kapaki-pakinabang na basahin ito .

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

Dito gumagamit kami ng isang espesyal na klase ng IntStream, na nagbibigay ng mga karagdagang kakayahan kapag nagtatrabaho sa stream mula sa mga halaga ng int. Upang lumikha ng ganoong stream, ginagamit namin ang static na hanay ng pamamaraan nitoSarado, na lumilikha ng mga halaga mula 2 hanggang f kasama na may isang hakbang na 1. Susunod, pinagsama namin ang lahat ng mga halaga gamit ang paraan ng pagbabawas, ibig sabihin, ipinapakita namin dito kung paano gusto namin silang pagsamahin. Sa wakas, nakukuha namin ang resultang halaga gamit ang getAsInt terminal method.

Gamit ang BigInteger

Sa Java, ang klase ng BigInteger ay kadalasang ginagamit upang pangasiwaan ang mga numero, lalo na ang BIG na mga numero . Pagkatapos ng lahat, kung gagamit tayo ng int, kung gayon ang pinakamataas na factorial na maaari nating kunin nang hindi nawawala ang data ay 31, sa mahabang panahon - 39. Ngunit paano kung kailangan natin ng factorial na 100? Tingnan natin ang mga nakaraang solusyon, ngunit gamit ang BigInteger.

Ang karaniwang solusyon

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;
}

Ang algorithm ng pagbibilang ay mahalagang pareho, ngunit dito ginagamit namin ang mga kakayahan ng BigInteger: BigInteger.ONE - upang itakda ang panimulang halaga sa 1. multiply - multiplikasyon sa pagitan ng dating factorial value at kasalukuyang numero.

Recursive na solusyon

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

Ang pangkalahatang lohika ng solusyon ay hindi nagbabago, maliban na ang ilang mga pamamaraan para sa pagtatrabaho sa BigInteger ay idinagdag.

Solusyon sa 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();
  }
}

Sa pangkalahatan, ang lahat ay pareho, ngunit sa BigInteger. Sa stream, mayroon na kaming paraan ng mapToObj, kung saan iko-convert namin ang mga int value sa BigInteger upang pagkatapos ay i-multiply ang mga ito gamit ang multiply (well, idinagdag namin na kumuha ng isang bagay mula sa Opsyonal na wrapper ). Kung patakbuhin natin ang alinman sa tatlong pamamaraang ito na may argumento 100, hindi tayo magkakaroon ng overflow at makakakuha tayo ng:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000