Java programmirleme zawody

Bu gün faktorlar barada gürleşeris. Bu, programmistiň bilmeli we şol bir wagtyň özünde onuň bilen işlemegi başarmaly iň esasy funksiýalardan biridir. Geliň, başlalyň. N faktory, n hökmünde görkezilen 1-den n-a çenli ähli tebigy sanlaryň önüminiň (köpeldilmeginiň) bahasydyr! Görnüşi:

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

Forene bir kiçijik düzgün, 0 üçin:

!0  = 1

Mysal üçin, faktoriki tapawudy 6 almak islesek! we 4 !:

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

Java-da munuň nähili boljakdygyna göz aýlalyň we faktory hasaplamagyň birnäçe usulyna düşüneliň.

Adaty çözgüt

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

Hiç hili çylşyrymly zat ýok: alnan belgini aýlawymyzyň ululygy hökmünde ulanýarys, onda f-e ýetýänçä öňki sanlar bilen köpelýäris. Esasy ýagdaýda:

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

Islenýän netijäni barlaýarys we alýarys: 696.

Gaýtalanýan çözgüt

Gaýtalanma usuly özüne çagyryp, käbir logika edýär. Bu usula gaýtalanýan diýilýär. Adatça iki bölekden ybarat:

1. usul çykyş şerti, usulyň özüni çagyrmagy bes etmeli we bahalary ýokarlandyryp başlamaly. Otherwiseogsam, bir usuly çagyrmakdan we netijede StackOverflowError- dan çäksiz aýlaw alarys .

2. belli bir ýagdaýda gaýtadan işlemek (logika) + özüni çagyrýar, ýöne başga gelýän bahasy bilen.

Häzirki wagtda gaýtalanmak üçin iň gowy mysalymyz faktory tapmak:

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

Gaýtalanma 1-e ýetende çykmagyň şertini kesgitledik, eger argument 1 bolmasa, häzirki bahany şu usula indiki jaňyň netijesi bilen köpeldýäris (häzirki bahany -1 iberýäris).

Akym bilen çözgüt

Akymyň işleýşini bilmeýänler ýa-da ýadyny täzelemek isleýänler üçin muny okamak peýdaly bolar .

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

Bu ýerde int bahalardan akym bilen işleýän wagtymyz goşmaça mümkinçilikleri berýän ýörite IntStream synpyny ulanýarys. Şeýle akym döretmek üçin, 1-nji ädim bilen 2-den f-a çenli bahalary döredýän statiki usul diapazonyny ulanýarys. Soňra, azaltmak usuly bilen ähli bahalary birleşdirýäris, ýagny nädip görkezýändigimizi görkezýäris birleşdirmek isleýäris. Netijede, getAsInt terminaly usuly bilen alnan bahany alýarys.

BigInteger ulanmak

Java-da BigInteger synpy köplenç sanlary, esasanam BIG sanlary dolandyrmak üçin ulanylýar . Galyberse-de, int ulansak, maglumatlary ýitirmän alyp biljek iň ýokary faktorymyz 31, uzyn - 39. 100öne 100 faktor gerek bolsa näme etmeli? Öňki çözgütlere seredeliň, ýöne BigInteger ulanyp.

Adaty çözgüt

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

Hasaplaýyş algoritmi aslynda birmeňzeş, ýöne bu ýerde BigInteger: BigInteger.ONE - başlangyç bahasyny 1-e bellemek üçin ulanýarys - öňki faktor bahasy bilen häzirki san arasynda köpeltmek - köpeltmek.

Gaýtalanýan çözgüt

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

BigInteger bilen işlemek üçin käbir usullaryň goşulandan başga çözgüdiň umumy logikasy üýtgemeýär.

Akym bilen çözgüt

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

Aslynda hemme zat birmeňzeş, ýöne BigInteger bilen. Akymda indi mapToObj usuly bar, bu usul bilen int bahalaryny BigInteger-e öwürýäris, soň bolsa köpeltmek arkaly bilelikde köpeltmek üçin (gowy, islege görä örtükden bir zat almagy goşduk ). Bu üç usulyň haýsydyr birini 100 argument bilen işledýän bolsak, onda artykmaç bolmaz we alarys:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000