תוכנית Java עבור פקטורי

היום נדבר על פקטוריאליים ועל הדרכים הנפוצות ביותר למצוא פקטוריאליים. זוהי אחת הפונקציות הבסיסיות ביותר שמתכנת צריך גם לדעת וגם להיות מסוגל לעבוד איתן. ובכן, בואו נתחיל. הפקטוריאלי של המספר n, המסומן כ-n!, הוא הערך של המכפלה (הכפלה) של כל המספרים הטבעיים מ-1 עד n. כך זה נראה (בואו נרענן את הידע שלכם במתמטיקה): ויש עוד כלל קטן אחד עבור 0: אם אנחנו רוצים לחשב את ההפרש בין 6! ו-4!: בוא נראה איך זה ייראה כשמיושם בתכנות. נחקור כמה דרכים כיצד לבצע חישובים של פקטורי ב-Java.

פתרון רגיל בתוכנית פקטוריאלית

להלן תוכנית פקטורי פשוטה המשתמשת בלולאה:

class FactorialExample{
 public static void main(String args[]){
  int i,fact=1;
  int number=7;// our number to do the necessary calculations in class Factorial
  for(i=1;i<=number;i++){
      fact=fact*i;
  }
  System.out.println("Factorial of "+number+" is: "+fact);
 }
}

הפלט שלנו בקונסולה יהיה: ועוד דוגמה אחת לסדר הדברים:

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i; // finding factorial of number using loops
  }
  return result;
}

אין כאן שום דבר קשה: אנו משתמשים במספר שעבר כגודל הלולאה שלנו, שבה נכפיל בכל המספרים הקודמים עד שנגיע ל-f. ובעיקר:

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

בבדיקת הקוד אנו רואים שאנו מקבלים את התוצאה הרצויה: 696.

פתרון רקורסיבי

רקורסיה מתרחשת כאשר שיטה קוראת לעצמה. שיטה כזו נקראת שיטה רקורסיבית. ככלל, הוא מורכב משני חלקים:

1. תנאי מסיים - כאשר התנאי המסיים מתקיים, השיטה צריכה להפסיק לקרוא לעצמה ולהתחיל להעביר ערכים למעלה. אחרי הכל, אם אין תנאי מסיים, אז תהיה לנו לולאה אינסופית, כאשר השיטה קוראת לעצמה שוב ושוב עד שנקבל StackOverflowError .
2. לא משנה מה ההיגיון שהמצב דורש פלוס קריאה רקורסיבית, אבל עם ערך קלט שונה.

מציאת הפקטורי ב-Java היא דוגמה מושלמת למועד השימוש ברקורסיה:

public static int getFactorial(int f) { // finding factorial of number using recursive solution
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

תנאי סיום הרקורסיה שלנו יהיה כשנגיע ל-1. אם הפרמטר אינו 1, נכפיל את הערך הנוכחי בתוצאה של הקריאה הרקורסיבית הבאה למתודה (אליה נעביר את הערך הנוכחי מינוס 1).

פתרון עם זרם

מי שלא מכיר את פונקציונליות ה-Stream של Java, או כל מי שרוצה לרענן את הזיכרון שלו, ירוויח מקריאה על כאן .

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

כאן אנו משתמשים במחלקה המיוחדת IntStream , שנותנת לנו יכולות נוספות בעבודה עם זרם ערכי int. כדי ליצור זרם כזה, אנו משתמשים בשיטת rangeClosed הסטטית שלו , המייצרת ערכים מ-2 עד f, כולל, במרווחים של 1. לאחר מכן, אנו משתמשים בשיטת reduce כדי לשלב את כל הערכים. ליתר דיוק, אנו מראים כיצד אנו רוצים לשלב בין הערכים. לבסוף, אנו מקבלים את הערך המתקבל באמצעות שיטת המסוף getAsInt .

שימוש ב-BigInteger

ב-Java, המחלקה BigInteger משמשת לעתים קרובות לטיפול במספרים, במיוחד במספרים BIG. ואכן, אם אנו משתמשים ב-int , אז הפקטוריאל המקסימלי שנוכל להתמודד איתו ללא אובדן נתונים הוא 31. עבור סוג הנתונים הארוך , הפקטוריאל המקסימלי הוא 39. אבל מה אם אנחנו צריכים את הפקטוראלי של 100? בואו נתאים את הפתרונות הקודמים ל-BigInteger.

פתרון רגיל

public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

האלגוריתם בעצם זהה, אבל כאן אנו משתמשים ביכולות של BigInteger: BigInteger.ONE הוא הערך ההתחלתי 1, ו- multiply() משמש להכפלת הערך הפקטוריאלי הקודם והמספר הנוכחי.

פתרון רקורסיבי

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. המחלקה Stream נותנת לנו את שיטת mapToObj , שבה אנו משתמשים כדי להמיר ערכי int ל-BigInteger על מנת להכפיל אותם עם עצמם באמצעות שיטת multiply (ו- get() נוספה כדי לקבל אובייקט מהעטיפה Optional ). אם נריץ אחת משלוש השיטות הללו עם ארגומנט של 100, אז נמנע מגלישה של מחסנית ונקבל את התוצאה הנכונה: