الرقم N الزوجي فيبوناتشي

نظرا لقيمة n العثور على n'th حتى رقم فيبوناتشي .

أمثلة :

مدخل ن = 3
الإخراج 34
توضيح أول 3 أرقام فيبوناتشي هي 0 2 8 34 144 والثالث هو 34.

مدخل ن = 4
الإخراج 144
توضيح أول 4 أرقام فيبوناتشي هي 0 2 8 34 144 والرابع هو 144.

[نهج ساذج] تحقق من كل رقم فيبوناتشي واحدًا تلو الآخر

نحن توليد كافة أرقام فيبوناتشي وتحقق من كل رقم واحدًا تلو الآخر إذا كان موجودًا أم لا

[نهج فعال] استخدام الصيغة المباشرة - وقت O(n) ومساحة O(1).

تسلسل فيبوناتشي للأرقام الزوجية هو 0 2 8 34 144 610 2584.... من هذا التسلسل يمكننا الحصول على فكرة ذلك كل رقم ثالث في التسلسل زوجي ويتبع التسلسل الصيغة العودية التالية.

التكرار لتسلسل فيبوناتشي الزوجي هو:
إفن = 4fn-1 + إفن-2

كيف تعمل الصيغة المذكورة أعلاه؟
دعونا نلقي نظرة على صيغة فيبوناتشي الأصلية ونكتبها على شكل Fn-3 وFn-6 نظرًا لحقيقة أن كل رقم فيبوناتشي ثالث هو زوجي.

Fn = Fn-1 + Fn-2 [توسيع كلا المصطلحين]
= الجبهة الوطنية-2 + الجبهة الوطنية-3 + الجبهة الوطنية-3 + الجبهة الوطنية-4
= Fn-2 + 2Fn-3 + Fn-4 [توسيع الحد الأول]
= الجبهة الوطنية-3 + الجبهة الوطنية-4 + 2 الجبهة الوطنية-3 + الجبهة الوطنية-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 زوجي أيضًا. دع الجبهة الوطنية تكون
العنصر الزوجي العاشر ووضع علامة عليه كـ EFx.
سلاسل جافا concat
إذا كانت Fn هي EFx، فإن Fn-3 هو الرقم الزوجي السابق، أي EFx-1
و Fn-6 سابق لـ EFx-1، أي EFx-2
إذن Fn = 4Fn-3 + Fn-6
وهو ما يعني
EFx = 4EFx-1 + EFx-2

فيما يلي تنفيذ بسيط للفكرة

C++

#include    using namespace std; // Optimized function to calculate the nth // even Fibonacci number int nthEvenFibonacci(int n) {    // Base case: the first even Fibonacci number is 2  if (n == 1) return 2;  // Start with the first two even Fibonacci numbers  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; } int main() {  int n = 2;   int result = nthEvenFibonacci(n);   cout << result << endl;   return 0; }

Java

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);   } }

Python

# 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  } }

JavaScript

// 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);

الإخراج