فاکتوریل در برنامه نویسی جاوا

امروز در مورد فاکتوریل صحبت خواهیم کرد. این یکی از اساسی ترین توابعی است که یک برنامه نویس باید بداند و در عین حال بتواند با آن کار کند. پس بیایید شروع کنیم. فاکتوریل n مقدار حاصل ضرب (ضرب) تمام اعداد طبیعی از 1 تا n است که با n نشان داده می شود! به نظر می رسد:

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

و یک قانون کوچک دیگر، برای 0:

!0  = 1

اگر بخواهیم مثلاً تفاضل فاکتوریل 6 را بگیریم! و 4!:

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

بیایید نگاهی به این بیندازیم که این در جاوا چگونه به نظر می‌رسد و روش‌های مختلفی را برای محاسبه فاکتوریل درک می‌کنیم.

راه حل معمول

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

هیچ چیز پیچیده ای نیست: ما از عدد دریافتی به عنوان اندازه چرخه خود استفاده می کنیم، که در آن در تمام اعداد قبلی ضرب می کنیم تا به f برسیم. و در اصل:

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

بررسی می کنیم و نتیجه دلخواه را می گیریم: 696.

راه حل بازگشتی

بازگشت، انجام برخی منطق با فراخوانی یک متد روی خود است. این روش بازگشتی نامیده می شود. به طور معمول از دو بخش تشکیل شده است:

1. شرایط خروج از روش، با رسیدن به آن متد باید خود را فراخوانی نکند و شروع به ارسال مقادیر به بالا کند. در غیر این صورت، یک حلقه بی نهایت از فراخوانی یک متد روی خودش و در نتیجه یک خطای StackOverflow دریافت می کنیم .

2. مقداری پردازش (منطق) لازم در یک موقعیت معین + فراخوانی خود، اما با مقدار ورودی متفاوت.

مثال ایده آل ما برای بازگشت امروز، یافتن فاکتوریل است:

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

ما شرط خروج از بازگشت را با رسیدن به 1 قرار می دهیم. اگر آرگومان 1 نباشد، مقدار فعلی را در نتیجه فراخوانی بعدی به این متد (جایی که مقدار فعلی -1 را ارسال می کنیم) ضرب می کنیم.

راه حل با استریم

برای کسانی که عملکرد جریان را نمی دانند یا برای کسانی که می خواهند حافظه خود را تازه کنند، خواندن این مطلب مفید خواهد بود .

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

در اینجا ما از یک کلاس ویژه IntStream استفاده می کنیم که قابلیت های اضافی را هنگام کار با جریان از مقادیر int فراهم می کند. برای ایجاد چنین جریانی از روش استاتیک آن rangeClosed استفاده می کنیم که مقادیری از 2 تا f را با گام 1 ایجاد می کند. در مرحله بعد، همه مقادیر را با استفاده از روش کاهش ترکیب می کنیم، یعنی در آن نشان می دهیم که چگونه ما می خواهیم آنها را ترکیب کنیم. در نهایت با استفاده از روش ترمینال getAsInt مقدار حاصل را بدست می آوریم.

با استفاده از BigInteger

در جاوا، کلاس BigInteger اغلب برای مدیریت اعداد، به خصوص اعداد BIG استفاده می شود . به هر حال، اگر از int استفاده کنیم، حداکثر فاکتوریل که می توانیم بدون از دست دادن داده بگیریم 31 است، برای مدت طولانی - 39. اما اگر به فاکتوریل 100 نیاز داشته باشیم چه؟ بیایید به راه حل های قبلی نگاه کنیم، اما با استفاده از BigInteger.

راه حل معمول

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

الگوریتم شمارش اساساً یکسان است، اما در اینجا ما از قابلیت های BigInteger استفاده می کنیم: BigInteger.ONE - برای تنظیم مقدار شروع به 1. ضرب - ضرب بین مقدار فاکتوریل قبلی و عدد فعلی.

راه حل بازگشتی

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

منطق کلی راه حل تغییر نمی کند، به جز اینکه روش هایی برای کار با BigInteger اضافه می شود.

راه حل با استریم

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

اساساً همه چیز یکسان است، اما با BigInteger. در استریم اکنون متد mapToObj را داریم که با آن مقادیر int را به BigInteger تبدیل می کنیم تا متعاقباً آنها را با استفاده از multiply در یکدیگر ضرب کنیم (خوب، برای گرفتن یک شی از Optional wrapper ) get را اضافه کردیم. اگر هر یک از این سه متد را با آرگومان 100 اجرا کنیم، سرریز نخواهیم داشت و به دست خواهیم آورد:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000