Java dasturlashda faktorial

Bugun biz faktoriallar haqida gaplashamiz. Bu dasturchi bilishi va shu bilan birga u bilan ishlay olishi kerak bo'lgan eng asosiy funksiyalardan biridir. Shunday qilib, keling, boshlaylik. n ning faktoriali 1 dan n gacha bo'lgan barcha natural sonlarning ko'paytmasi (ko'paytirish) qiymati bo'lib, u n bilan belgilanadi! U qanday ko'rinishga ega:

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

Va yana bir kichik qoida, 0 uchun:

!0  = 1

Agar biz, masalan, 6 faktorial farqni olishni xohlasak! va 4!:

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

Keling, bu Java-da qanday ko'rinishini ko'rib chiqamiz va faktorialni hisoblashning bir necha usullarini tushunamiz.

Oddiy yechim

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

Hech qanday murakkab narsa yo'q: biz olingan raqamni bizning davrimizning o'lchami sifatida ishlatamiz, unda biz f ga yetguncha barcha oldingi raqamlarga ko'paytiramiz. Va asosiysi:

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

Biz tekshiramiz va kerakli natijani olamiz: 696.

Rekursiv yechim

Rekursiya o'z-o'zidan usulni chaqirish orqali ba'zi mantiqiy ishlarni amalga oshiradi. Bu usul rekursiv deb ataladi. Odatda u ikki qismdan iborat:

1. usuldan chiqish sharti, unga erishgandan so'ng usul o'zini chaqirishni to'xtatib, qiymatlarni oshirishni boshlashi kerak. Aks holda, biz o'z-o'zidan usulni chaqirishdan cheksiz tsiklga ega bo'lamiz va natijada StackOverflowError .

2. ma'lum bir vaziyatda zarur bo'lgan ba'zi ishlov berish (mantiqiy) + o'zini chaqirish, lekin boshqa kiruvchi qiymat bilan.

Bugungi rekursiya uchun ideal misolimiz faktorialni topishdir:

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

Rekursiyadan 1 ga yetganda chiqish shartini qo'yamiz. Agar argument 1 bo'lmasa, u holda joriy qiymatni ushbu usulga keyingi chaqiruv natijasiga ko'paytiramiz (bu erda biz joriy qiymatni -1 yuboramiz).

Stream yordamida yechim

Oqim funksiyasini bilmaganlar yoki xotirasini yangilamoqchi bo'lganlar uchun buni o'qish foydali bo'ladi .

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

Bu erda biz IntStream maxsus sinfidan foydalanamiz, bu int qiymatlaridan oqim bilan ishlashda qo'shimcha imkoniyatlar beradi. Bunday oqimni yaratish uchun biz uning statik usuli diapazonidan foydalanamiz, u 1 qadam bilan 2 dan f gacha bo'lgan qiymatlarni yaratadi. Keyin biz barcha qiymatlarni kamaytirish usuli yordamida birlashtiramiz, ya'ni biz unda qandayligini ko'rsatamiz. biz ularni birlashtirmoqchimiz. Nihoyat, getAsInt terminal usuli yordamida olingan qiymatni olamiz.

BigInteger-dan foydalanish

Java-da BigInteger klassi ko'pincha raqamlarni, ayniqsa BIG raqamlarini boshqarish uchun ishlatiladi . Axir, agar biz int dan foydalansak, unda ma'lumotlarni yo'qotmasdan olishimiz mumkin bo'lgan maksimal faktorial 31, uzoq vaqt davomida - 39. Lekin agar bizga 100 faktorial kerak bo'lsa-chi? Oldingi echimlarni ko'rib chiqaylik, lekin BigInteger-dan foydalanamiz.

Oddiy yechim

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

Hisoblash algoritmi asosan bir xil, lekin bu erda biz BigInteger imkoniyatlaridan foydalanamiz: BigInteger.ONE - boshlang'ich qiymatni 1 ga o'rnatish uchun. ko'paytirish - oldingi faktorial qiymat va joriy raqam o'rtasida ko'paytirish.

Rekursiv yechim

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

Yechimning umumiy mantig'i o'zgarmaydi, faqat BigInteger bilan ishlashning ba'zi usullari qo'shiladi.

Stream bilan yechim

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

Aslida hamma narsa bir xil, lekin BigInteger bilan. Oqimda endi biz mapToObj usuliga egamiz, uning yordamida biz int qiymatlarini BigInteger ga aylantiramiz, keyin ularni ko'paytirish yordamida birga ko'paytiramiz (yaxshi, biz qo'shdik get ob'ektni Ixtiyoriy o'ramdan olish ) . Agar biz ushbu uchta usuldan birini 100 argument bilan ishlatsak, bizda to'lib-toshgan bo'lmaydi va biz quyidagilarni olamiz:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000