Faktorial dalam Pemrograman Java

Hari ini kita akan berbicara tentang faktorial. Ini adalah salah satu fungsi paling dasar yang perlu diketahui oleh seorang programmer, dan pada saat yang sama dapat bekerja dengannya. Jadi mari kita mulai. Faktorial dari n adalah nilai hasil kali (perkalian) semua bilangan asli dari 1 sampai n, yang dilambangkan dengan n! Seperti apa 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 aturan kecil, untuk 0:

!0  = 1

Jika kita ingin, misalnya, mendapatkan selisih faktorial 6! dan 4!:

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

Mari kita lihat seperti apa hal ini di Java dan memahami beberapa cara penghitungan faktorial.

Solusi yang biasa

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

Tidak ada yang rumit: kita menggunakan angka yang diterima sebagai ukuran siklus kita, di mana kita mengalikan dengan semua angka sebelumnya hingga mencapai f. Dan yang utama:

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

Kami memeriksa dan mendapatkan hasil yang diinginkan: 696.

Solusi rekursif

Rekursi melakukan logika dengan memanggil suatu metode pada dirinya sendiri. Metode ini disebut rekursif. Biasanya terdiri dari dua bagian:

1. kondisi keluar metode, setelah mencapainya metode harus berhenti memanggil dirinya sendiri dan mulai meneruskan nilai ke atas. Jika tidak, kita akan mendapatkan loop tak terbatas dari pemanggilan metode itu sendiri dan, sebagai hasilnya, StackOverflowError .

2. beberapa pemrosesan (logika) yang diperlukan dalam situasi tertentu + pemanggilan dirinya sendiri, tetapi dengan nilai masuk yang berbeda.

Contoh ideal kita untuk rekursi saat ini adalah mencari faktorial:

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

Kami menetapkan kondisi untuk keluar dari rekursi ketika mencapai 1. Jika argumennya bukan 1, maka kami mengalikan nilai saat ini dengan hasil panggilan berikutnya ke metode ini (di mana kami mengirimkan nilai saat ini -1).

Solusi dengan Stream

Bagi yang belum mengetahui fungsi streaming atau bagi yang ingin menyegarkan ingatan, ada baiknya 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 kita menggunakan kelas khusus IntStream, yang memberikan kemampuan tambahan saat bekerja dengan aliran dari nilai int. Untuk membuat aliran seperti itu, kami menggunakan metode statis rangeClosed, yang menciptakan nilai dari 2 hingga f inklusif dengan langkah 1. Selanjutnya, kami menggabungkan semua nilai menggunakan metode pengurangan, yaitu, kami menunjukkan di dalamnya caranya kami ingin menggabungkannya. Terakhir, kita mendapatkan nilai yang dihasilkan menggunakan metode terminal getAsInt.

Menggunakan BigInteger

Di Java, kelas BigInteger sering digunakan untuk menangani bilangan, khususnya bilangan BESAR . Toh kalau kita pakai int, maka faktorial maksimal yang bisa kita ambil tanpa kehilangan data adalah 31, panjang - 39. Tapi bagaimana jika kita membutuhkan faktorial 100? Mari kita lihat solusi sebelumnya, tetapi menggunakan BigInteger.

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

Algoritme penghitungan pada dasarnya sama, tetapi di sini kita menggunakan kemampuan BigInteger: BigInteger.ONE - untuk menetapkan nilai awal menjadi 1. perkalian - perkalian antara nilai faktorial sebelumnya dan bilangan saat ini.

Solusi rekursif

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

Logika umum dari solusi tidak berubah, kecuali beberapa metode untuk bekerja dengan BigInteger ditambahkan.

Solusi dengan Stream

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 dasarnya semuanya sama, tetapi dengan BigInteger. Di aliran kita sekarang memiliki metode mapToObj, yang dengannya kita mengonversi nilai int menjadi BigInteger untuk selanjutnya mengalikannya menggunakan perkalian (yah, kita menambahkan get untuk mengambil objek dari pembungkus Opsional ). Jika kita menjalankan salah satu dari tiga metode ini dengan argumen 100, maka kita tidak akan mengalami overflow dan kita akan mendapatkan:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000