Gegeven een waarde n, vind je de n-de even Fibonacci-getal .
Voorbeelden:
Invoer n = 3
Uitvoer 34
Uitleg De eerste 3 even Fibonacci-getallen zijn 0 2 8 34 144 en de derde is 34.Invoer n = 4
Uitvoer 144
Uitleg De eerste 4 even Fibonacci-getallen zijn 0 2 8 34 144 en de 4e is 144.
[Naïeve aanpak] Controleer elk Fibonacci-getal één voor één
Wij alle Fibonacci-getallen genereren en controleer elk nummer één voor één of het ooit is of niet
[Efficiënte aanpak] Met behulp van directe formule - O(n) tijd en O(1) ruimte
De even getalreeks van Fibonacci is 0 2 8 34 144 610 2584. Uit deze reeks kunnen we een idee krijgen dat elk derde getal in de rij is even en de reeks volgt de recursieve formule.
Herhaling voor de even Fibonacci-reeks is:
Eefn = 4fn-1 + Efn-2
Hoe werkt bovenstaande formule?
Laten we eens kijken naar de originele Fibonacci-formule en deze schrijven in de vorm van Fn-3 en Fn-6 vanwege het feit dat elk derde Fibonacci-getal even is.
Fn = Fn-1 + Fn-2 [Beide termen uitbreiden]
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4 [Eerste term uitbreiden]
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4 [Eén Fn-4 uitbreiden]
= 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Fn-4 en Fn-5 gecombineerd]
= 4Fn-3 + Fn-6
Omdat elk derde Fibonacci-getal even is, dus als Fn dat is
zelfs dan is Fn-3 even en Fn-6 is ook even. Laat Fn zijn
x-de even element en markeer het als EFx.
hoe je een methode in Java aanroeptAls Fn EFx is, dan is Fn-3 het vorige even getal, d.w.z. EFx-1
en Fn-6 is een voorloper van EFx-1, dat wil zeggen EFx-2
Dus Fn = 4Fn-3 + Fn-6
wat betekent
EFx = 4EFx-1 + EFx-2
Hieronder ziet u een eenvoudige implementatie van het idee
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);
Uitvoer
8