แฟกทอเรียลในการเขียนโปรแกรม Java

วันนี้เราจะพูดถึงแฟกทอเรียล นี่เป็นหนึ่งในฟังก์ชันพื้นฐานที่สุดที่โปรแกรมเมอร์จำเป็นต้องรู้ และในขณะเดียวกันก็สามารถทำงานได้ มาเริ่มกันเลย แฟกทอเรียลของ 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

มาดูกันว่าสิ่งนี้จะเป็นอย่างไรใน Java และทำความเข้าใจหลายวิธีในการคำนวณแฟคทอเรียล

วิธีแก้ปัญหาตามปกติ

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. เงื่อนไขทางออกของเมธอด เมื่อถึงซึ่งเมธอดควรหยุดเรียกตัวเองและเริ่มส่งค่าขึ้น มิฉะนั้น เราจะได้ลูปไม่สิ้นสุดจากการเรียกเมธอดด้วยตัวมันเอง และด้วยเหตุนี้จึงเกิดStackOverflowError

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

ใน Java คลาส 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 เพื่อนำไปคูณเข้าด้วยกันในภายหลังโดยใช้การคูณ (เราเพิ่ม get เพื่อรับวัตถุจาก Optional wrapper ) หากเราใช้วิธีใดวิธีหนึ่งในสามวิธีนี้ด้วยอาร์กิวเมนต์ 100 เราจะไม่มีโอเวอร์โฟลว์และเราจะได้รับ:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000