F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F 0 = 0, F 1 = 1, F n = F n - 1 + F n - 2 ;
n ≥ 0, n ∈ Z
השגת מספרי פיבונאצ'י ראשונים ב-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 בסדרת פיבונאצ'י. ככלל, זה רק מקל על המשימה, כי אתה יכול להתאים בקלות פתרונות קודמים לכך. ובכן, מה לגבי פתרון הבעיה באמצעות רקורסיה?-
עבור 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. למעשה, אנו, כמו בפתרונות קודמים, צריכים להגדיר את שני הראשונים אלמנטים.
-
היישום עבור 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 .
GO TO FULL VERSION