Java proqramlaşdırmasında faktorial

Bu gün faktoriallar haqqında danışacağıq. Bu, proqramçının bilməli olduğu və eyni zamanda onunla işləməyi bacarmalı olduğu ən əsas funksiyalardan biridir. Beləliklə, başlayaq. N faktorialı n kimi işarələnən 1-dən n-ə qədər bütün natural ədədlərin hasilinin (vurmasının) qiymətidir! Nə kimi görünür:

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

Və daha bir kiçik qayda, 0 üçün:

!0  = 1

İstəsək, məsələn, faktor fərqi 6 almaq! və 4!:

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

Bunun Java-da necə göründüyünə nəzər salaq və faktorialın hesablanmasının bir neçə üsulunu anlayaq.

Adi həll

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

Mürəkkəb bir şey yoxdur: alınan nömrəni dövrümüzün ölçüsü kimi istifadə edirik, burada f-ə çatana qədər bütün əvvəlki nömrələrə çarpırıq. Və əsas olaraq:

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

Yoxlayırıq və istədiyiniz nəticəni alırıq: 696.

Rekursiv həll

Rekursiya öz üzərində bir metodu çağıraraq bəzi məntiq edir. Bu üsul rekursiv adlanır. Tipik olaraq iki hissədən ibarətdir:

1. metoddan çıxış şərti, ona çatdıqdan sonra metod özünü çağırmağı dayandırmalı və dəyərləri yuxarı ötürməyə başlamalıdır. Əks halda, öz üzərində metodu çağırmaqla sonsuz döngə əldə edəcəyik və nəticədə StackOverflowError .

2. müəyyən bir vəziyyətdə lazım olan bəzi emal (məntiq) + özünü çağırır, lakin fərqli bir daxil olan dəyərlə.

Bu gün rekursiya üçün ideal nümunəmiz faktorial tapmaqdır:

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

1-ə çatdıqda rekursiyadan çıxmaq şərtini qoyuruq.Arqument 1 deyilsə, o zaman cari dəyəri bu metoda növbəti çağırışın nəticəsi ilə vururuq (burada cari dəyəri -1 göndəririk).

Stream ilə həll

Axın funksiyasını bilməyənlər və ya yaddaşını yeniləmək istəyənlər üçün bunu oxumaq faydalı olacaq .

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

Burada biz int dəyərlərindən axınla işləyərkən əlavə imkanlar təmin edən xüsusi IntStream sinfindən istifadə edirik. Belə bir axın yaratmaq üçün 1 addımı ilə 2-dən f daxil olmaqla dəyərləri yaradan rangeClosed statik metodundan istifadə edirik. Sonra, azaltma metodundan istifadə edərək bütün dəyərləri birləşdiririk, yəni necə onları birləşdirmək istəyirik. Nəhayət, getAsInt terminal metodundan istifadə edərək nəticədə alınan dəyəri əldə edirik.

BigInteger istifadə

Java-da BigInteger sinfi çox vaxt nömrələri, xüsusən də BIG olanları idarə etmək üçün istifadə olunur . Axı biz int-dən istifadə etsək, onda verilənləri itirmədən götürə biləcəyimiz maksimum faktorial 31-dir, uzun müddətə - 39. Bəs bizə 100 faktorial lazımdırsa necə? Əvvəlki həlləri nəzərdən keçirək, lakin BigInteger istifadə edərək.

Adi həll

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

Hesablama alqoritmi mahiyyətcə eynidir, lakin burada biz BigInteger-in imkanlarından istifadə edirik: BigInteger.ONE - başlanğıc dəyərini 1-ə təyin etmək üçün. çarpma - əvvəlki faktorial qiymətlə cari ədəd arasında vurma.

Rekursiv həll

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

BigInteger ilə işləmək üçün bəzi üsulların əlavə edilməsi istisna olmaqla, həllin ümumi məntiqi dəyişmir.

Stream ilə həll

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

Əslində hər şey eynidir, lakin BigInteger ilə. Axında indi mapToObj metodumuz var, onun köməyi ilə int dəyərlərini BigInteger-ə çevirərək onları çarpma üsulu ilə bir-birinə vururuq (yaxşı, biz Könüllü paketdən obyekt götürmək üçün get əlavə etdik ) . Bu üç üsuldan hər hansı birini 100 arqumenti ilə işlətsək, daşqın olmayacaq və biz əldə edəcəyik:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000