Faktorial dalam Pengaturcaraan Java

Hari ini kita akan bercakap tentang faktorial. Ini adalah salah satu fungsi paling asas yang perlu diketahui oleh pengaturcara, dan pada masa yang sama dapat bekerja dengannya. Jadi mari kita mulakan. Faktorial n ialah nilai hasil darab semua nombor asli dari 1 hingga n, yang dilambangkan sebagai n! Bagaimana rupanya:

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

Dan satu lagi peraturan kecil, untuk 0:

!0  = 1

Jika kita mahu, sebagai contoh, untuk mendapatkan perbezaan faktorial 6! dan 4!:

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

Mari kita lihat bagaimana ini akan kelihatan di Jawa dan fahami beberapa cara di mana faktorial boleh dikira.

Penyelesaian biasa

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

Tiada apa-apa yang rumit: kami menggunakan nombor yang diterima sebagai saiz kitaran kami, di mana kami mendarab dengan semua nombor sebelumnya sehingga kami mencapai f. Dan secara utama:

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

Kami menyemak dan mendapatkan hasil yang diingini: 696.

Penyelesaian rekursif

Rekursi melakukan beberapa logik dengan memanggil kaedah pada dirinya sendiri. Kaedah ini dipanggil rekursif. Biasanya ia terdiri daripada dua bahagian:

1. keadaan keluar kaedah, apabila mencapai kaedah yang sepatutnya berhenti memanggil dirinya sendiri dan mula menghantar nilai. Jika tidak, kita akan mendapat gelung tak terhingga daripada memanggil kaedah pada dirinya sendiri dan, sebagai hasilnya, StackOverflowError .

2. beberapa pemprosesan (logik) yang diperlukan dalam situasi tertentu + memanggil dirinya sendiri, tetapi dengan nilai masuk yang berbeza.

Contoh ideal kami untuk rekursi hari ini ialah mencari faktorial:

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

Kami menetapkan syarat untuk keluar dari rekursi apabila ia mencapai 1. Jika hujahnya bukan 1, maka kami darabkan nilai semasa dengan hasil panggilan seterusnya kepada kaedah ini (di mana kami menghantar nilai semasa -1).

Penyelesaian dengan Strim

Bagi mereka yang tidak mengetahui fungsi strim atau bagi mereka yang ingin menyegarkan ingatan mereka, adalah berguna untuk membaca ini .

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

Di sini kami menggunakan IntStream kelas khas, yang menyediakan keupayaan tambahan apabila bekerja dengan aliran daripada nilai int. Untuk mencipta aliran sedemikian, kami menggunakan julat kaedah statiknyaClosed, yang mencipta nilai daripada 2 hingga f termasuk dengan langkah 1. Seterusnya, kami menggabungkan semua nilai menggunakan kaedah pengurangan, iaitu, kami menunjukkan di dalamnya bagaimana kami mahu menggabungkan mereka. Akhir sekali, kami mendapat nilai yang terhasil menggunakan kaedah terminal getAsInt.

Menggunakan BigInteger

Di Java, kelas BigInteger sering digunakan untuk mengendalikan nombor, terutamanya nombor BIG . Lagipun, jika kita menggunakan int, maka faktorial maksimum yang boleh kita ambil tanpa kehilangan data ialah 31, untuk jangka panjang - 39. Tetapi bagaimana jika kita memerlukan faktorial 100? Mari kita lihat penyelesaian sebelumnya, tetapi menggunakan BigInteger.

Penyelesaian biasa

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

Algoritma pengiraan pada asasnya adalah sama, tetapi di sini kita menggunakan keupayaan BigInteger: BigInteger.ONE - untuk menetapkan nilai permulaan kepada 1. darab - pendaraban antara nilai faktor sebelumnya dan nombor semasa.

Penyelesaian rekursif

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

Logik umum penyelesaian tidak berubah, kecuali beberapa kaedah untuk bekerja dengan BigInteger ditambah.

Penyelesaian dengan Strim

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

Pada asasnya semuanya adalah sama, tetapi dengan BigInteger. Dalam aliran kita kini mempunyai kaedah mapToObj, yang dengannya kita menukar nilai int kepada BigInteger untuk kemudiannya mendarabkannya bersama-sama menggunakan darab (baik, kita tambah dapat mengambil objek dari pembalut Pilihan ). Jika kita menjalankan mana-mana daripada tiga kaedah ini dengan hujah 100, maka kita tidak akan mempunyai limpahan dan kita akan mendapat:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000