בהינתן ערך n מצא את ה-n' זוגי מספר פיבונאצ'י .
דוגמאות:
קֶלֶט n = 3
תְפוּקָה 34
הֶסבֵּר 3 המספרים הזוגיים הראשונים של פיבונאצ'י הם 0 2 8 34 144 כאשר השלישי הוא 34.קֶלֶט n = 4
תְפוּקָה 144
הֶסבֵּר 4 המספרים הזוגיים הראשונים של פיבונאצ'י הם 0 2 8 34 144 כאשר הרביעי הוא 144.
[גישה נאיבית] בדוק כל פיבונאצ'י מספר אחד אחד
אָנוּ ליצור את כל מספרי פיבונאצ'י ולבדוק כל מספר אחד אחד אם זה אי פעם או לא
[גישה יעילה] שימוש בנוסחה ישירה - זמן O(n) ומרחב O(1).
רצף המספר הזוגי של פיבונאצ'י הוא 0 2 8 34 144 610 2584.... מרצף זה נוכל לקבל מושג כל מספר שלישי ברצף הוא זוגי והרצף עוקב אחר נוסחה רקורסיבית.
הישנות עבור רצף אבן פיבונאצ'י היא:
Eefn = 4fn-1 + Efn-2
איך עובדת הנוסחה לעיל?
הבה נסתכל על נוסחת פיבונאצ'י המקורית ונכתוב אותה בצורה של Fn-3 ו-Fn-6 בגלל העובדה שכל מספר פיבונאצי שלישי הוא זוגי.
Fn = Fn-1 + Fn-2 [הרחבת שני המונחים]
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4 [מונח ראשון מתרחב]
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4 [הרחבת Fn-4 אחד]
= 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [סירוק Fn-4 ו-Fn-5]
= 4Fn-3 + Fn-6
מכיוון שכל מספר פיבונאצ'י שלישי הוא זוגי אז אם Fn הוא
גם אז Fn-3 הוא זוגי ו-Fn-6 הוא גם זוגי. תן ל-Fn להיות
אלמנט זוגי וסמן אותו כ-EFx.
ל-java יש את הבאאם Fn הוא EFx אז Fn-3 הוא המספר הזוגי הקודם כלומר EFx-1
ו-Fn-6 הוא הקודם של EFx-1 כלומר EFx-2
אז Fn = 4Fn-3 + Fn-6
כלומר
EFx = 4EFx-1 + EFx-2
להלן יישום פשוט של הרעיון
C++#include
public class GfG { // Function to calculate the nth even Fibonacci // number using dynamic programming public static int nthEvenFibonacci(int n) { // Base case: the first even // Fibonacci number is 2 if (n == 1) return 2; // Start with the first two Fibonacci // numbers (even ones) int prev = 0; // F(0) int curr = 2; // F(3) // We need to find the nth even Fibonacci number for (int i = 2; i <= n; i++) { // Next even Fibonacci number is 4 // times the previous even Fibonacci // number plus the one before that int nextEvenFib = 4 * curr + prev; prev = curr; curr = nextEvenFib; } return curr; } public static void main(String[] args) { int n = 2; int result = nthEvenFibonacci(n); System.out.println(result); } }
# Function to calculate the nth even # Fibonacci number using dynamic programming def nthEvenFibonacci(n): # Base case: the first even Fibonacci number is 2 if n == 1: return 2 # Start with the first two Fibonacci numbers (even ones) prev = 0 # F(0) curr = 2 # F(3) # We need to find the nth even Fibonacci number for i in range(2 n + 1): # Next even Fibonacci number is 4 times the # previous even Fibonacci number plus the # one before that next_even_fib = 4 * curr + prev prev = curr curr = next_even_fib return curr # Driver code if __name__ == '__main__': n = 2 # Setting n to 2 result = nthEvenFibonacci(n) print(result)
using System; class GfG { // Function to calculate the nth even Fibonacci // number using dynamic programming public int NthEvenFibonacci(int n) { // Base case: the first even Fibonacci number is 2 if (n == 1) return 2; // Start with the first two Fibonacci numbers (even ones) int prev = 0; // F(0) int curr = 2; // F(3) // We need to find the nth even Fibonacci number for (int i = 2; i <= n; i++) { // Next even Fibonacci number is 4 times the // previous even Fibonacci number plus the // one before that int nextEvenFib = 4 * curr + prev; prev = curr; curr = nextEvenFib; } return curr; } static void Main() { GfG gfg = new GfG(); int n = 2; int result = gfg.NthEvenFibonacci(n); Console.WriteLine(result); // Output: The nth even Fibonacci number } }
// Function to calculate the nth even Fibonacci number using dynamic programming function nthEvenFibonacci(n) { // Base case: the first even Fibonacci number is 2 if (n === 1) return 2; // Start with the first two Fibonacci numbers (even ones) let prev = 0; // F(0) let curr = 2; // F(3) // We need to find the nth even Fibonacci number for (let i = 2; i <= n; i++) { // Next even Fibonacci number is 4 times // the previous even Fibonacci number plus // the one before that let nextEvenFib = 4 * curr + prev; prev = curr; curr = nextEvenFib; } return curr; } // Example usage: const n = 2; // Setting n to 2 const result = nthEvenFibonacci(n); console.log(result);
תְפוּקָה
8