פקטורי בתכנות ג'אווה

היום נדבר על פקטוריאלים. זוהי אחת הפונקציות הבסיסיות ביותר שמתכנת צריך לדעת, ובמקביל להיות מסוגל לעבוד איתה. אז בואו נתחיל. הפקטוריאלי של 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).

פתרון עם Stream

למי שלא מכיר את פונקציונליות הזרם או למי שרוצה לרענן את הזיכרון, יהיה שימושי לקרוא את זה .

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. לאחר מכן, אנו משלבים את כל הערכים בשיטת ה-reduce, כלומר, אנו מראים בה כיצד אנחנו רוצים לשלב ביניהם. לבסוף, אנו מקבלים את הערך המתקבל באמצעות שיטת המסוף 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.

פתרון עם 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();
  }
}

בעצם הכל זהה, אבל עם BigInteger. בזרם יש לנו כעת את שיטת mapToObj, שבאמצעותה אנו ממירים ערכי int ל-BigInteger על מנת להכפיל אותם יחד באמצעות כפל (טוב, הוספנו get to take a object מהעטיפה האופציונלית ) . אם נריץ אחת משלוש השיטות הללו עם ארגומנט 100, אז לא תהיה לנו הצפה ונקבל:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000