מה שמתכנת ג'אווה צריך לדעת על מספרי פיבונאצ'י

לעתים קרובות במהלך ראיונות, במיוחד בחברות זרות, אנשים עשויים להישאל על אלגוריתמים, ובמצב מלחיץ, לזכור משהו בטירוף זה לא תמיד קל. לכן, אתה צריך להתכונן. מלכתחילה, לפחות רענן את זיכרון האלגוריתמים הבסיסיים. היום ננתח תופעה כמו מספרי פיבונאצ'י והגרסאות הנפוצות ביותר של בעיות הקשורות אליהם. מספרי פיבונאצ'י הם רצף של מספרים טבעיים שמתחיל במספרים אפס ואחד, וכל מספר שאחריו שווה לסכום של השניים הקודמים: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈ Z

ראוי לציין שלפעמים מושמט 0, והסדרה מתחילה ב-1 1 2 3... ככלל, בתנאי הבעיה מצוין מיד באילו שני מספרים ראשונים הסדרה מתחילה (0.1 או 1.1), אז בהמשך נשקול פתרונות לשני המקרים.

השגת מספרי פיבונאצ'י ראשונים ב-Java

נניח שיש לנו משימה להשיג את n מספרי פיבונאצ'י הראשונים.

• מקרה 0.1:

  מספר מסוים n מגיע אלינו:

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  אנו יוצרים מערך בגודל n. שני האלמנטים הראשונים יהיו שווים לאפס ואחד, ואת האלמנטים הנותרים מקבלים על ידי מעבר דרך הלולאה הזו ושימוש במספרים הקודמים מהמערך.

  ואנחנו מציגים:

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  קבע int n = 10;

  ואנחנו מקבלים:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• במקרה 1.1 הפתרון למעשה אינו שונה:

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  כל מה שהיינו צריכים לשנות היה האלמנט הראשון של המערך arr[0]: מ-0 ל-1. בהתאם לכך, 10 האלמנטים הראשונים יהיו:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

מספרי פיבונאצ'י הראשונים באמצעות זרם

אבל אנחנו רוצים להראות את הרמה שלנו. אז בואו נראה איך הפתרון הזה ייראה באמצעות זרם .

• עבור 0.1:

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  שיטת האיטרציה הסטטית של המחלקה Stream מחזירה זרם מסודר אינסופי שנוצר על ידי החלת הפונקציה על המערך הראשוני arr. במקרה שלנו, הפונקציה היא להגדיר את הכלל להרכבת כל מערך חדש, בהתבסס על הקודם. כתוצאה מכך, נקבל זרם של מערכים:

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  אבל יהיה מספר אינסופי מהם, ולכן באמצעות .limit(n) נפחית את מספר האלמנטים ל-n הראשון (במקרה שלנו ל-10).

  עם זאת, אנחנו לא צריכים זרם של מערכים, אז באמצעות .map(y -> y[0]) אנחנו בוחרים את האלמנט הראשון של כל מערך ומקבלים זרם עם המספרים שאנחנו צריכים ומדפיסים אותו למסוף באמצעות forEach .

  נראה מגניב יותר, לא?

  כשהרכיבים הראשונים הם 1,1 גם הקוד הזה יהיה כמעט זהה:

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  שוב, ההבדלים הם באלמנט ההתחלתי: במקום {0, 1} הגדרנו {1, 1}

  למעשה, התוצאות יהיו זהות לאלו שבדוגמה הקודמת.

סכום מספרי פיבונאצ'י

מה אם נתבקש לקבל את הסכום של מספרי פיבונאצ'י עד האלמנט ה-n כולל? זה לא אמור לגרום לנו לקשיים. בואו ניקח פתרון עם זרם ונחליף את forEach בכמה שיטות אחרות:

• עבור 0.1:

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  באמצעות .mapToInt(Integer::intValue) אנו ממירים את הזרם שלנו ל-IntStream מספרי ומשתמשים בשיטת ה-.sum() שלו כדי לקבל את הסכום של כל האלמנטים.

• עבור מקרה עם 1,1 אלמנטים ראשוניים, במקום {0, 1} הגדרנו {1, 1}.

קבלת המספר ה-n בסדרת פיבונאצ'י

לפעמים אתה מתבקש להדפיס לא סדרה של מספרים, אלא ספציפית את המספר ה-n בסדרת פיבונאצ'י. ככלל, זה רק מקל על המשימה, כי אתה יכול להתאים בקלות פתרונות קודמים לכך. ובכן, מה לגבי פתרון הבעיה באמצעות רקורסיה?

1. עבור 0.1:

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

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

2. היישום עבור 1.1 יהיה מעט שונה:

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   במקרה זה, עלינו להגדיר רק את האלמנט הראשון כ-1, מכיוון שהאלמנט השני יהיה זהה, והתגובה של השיטה תהיה זהה.

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

עם זאת, השיטה הרקורסיבית אינה מומלצת מכיוון שבניגוד לשיטות הקודמות, אשר פועלות בזמן O(n) ליניארי, השיטה הרקורסיבית עשויה להימשך זמן רב יותר באופן משמעותי. למה? השיטה הרקורסיבית יכולה להימשך זמן רב, שכן במהלך תהליך החישוב הפונקציה תיקרא פעמים רבות מאותו ארגומנט. לדוגמה, בעת הערכת getFibonacciValue(7), הפונקציה תבצע קריאות רקורסיביות ל-getFibonacciValue(5) ול-getFibonacciValue(6), שתי הקריאות הרקורסיביות יקראו getFibonacciValue(4)), מה שיביא לקריאה לאותן פעולות מספר פעמים. בראיון אפשר להראות שיטה זו כפתרון, אך במקביל לדבר על חסרונותיה ולהציע שיטה אחרת בתמורה. כדאי גם לציין שסוג int בג'אווה מאפשר לך לאחסן מ-2147483648 עד 2147483647, כך שתוכל לחשב רק את 46 מספרי פיבונאצ'י הראשונים: אם ננסה להשיג את ה-47 הבא, תהיה הצפת ו נקבל מספר שלילי. אם נשתמש בסוג הנתונים הארוך במקום int, נוכל לחשב נכון את 91 מספרי פיבונאצ'י הראשונים. כדי לחשב את מספרי פיבונאצ'י הבאים, עליך להשתמש במחלקה BigInteger, המיישמת את ההיגיון לאחסון ופעולות אריתמטיות של מספרים גדולים באמת.