Bei einem gegebenen Wert n finden Sie die n-te gerade Zahl Fibonacci-Zahl .
Beispiele:
Eingang n = 3
Ausgabe 34
Erläuterung Die ersten drei geraden Fibonacci-Zahlen sind 0 2 8 34 144, die dritte ist 34.Eingang n = 4
Ausgabe 144
Erläuterung Die ersten 4 geraden Fibonacci-Zahlen sind 0 2 8 34 144, wobei die vierte 144 ist.
[Naiver Ansatz] Überprüfen Sie jede Fibonacci-Zahl einzeln
Wir Generieren Sie alle Fibonacci-Zahlen und überprüfen Sie jede Zahl einzeln, ob es jemals so ist oder nicht
[Effizienter Ansatz] Verwendung der direkten Formel – O(n)-Zeit und O(1)-Raum
Die geradzahlige Fibonacci-Folge ist 0 2 8 34 144 610 2584.... Aus dieser Folge können wir uns eine Vorstellung davon machen Jede dritte Zahl in Folge ist gerade und die Sequenz folgt der folgenden rekursiven Formel.
Die Wiederholung für eine gerade Fibonacci-Folge ist:
Eefn = 4fn-1 + Efn-2
Wie funktioniert die obige Formel?
Schauen wir uns die ursprüngliche Fibonacci-Formel an und schreiben sie in der Form Fn-3 und Fn-6, da jede dritte Fibonacci-Zahl gerade ist.
Fn = Fn-1 + Fn-2 [Erweiterung beider Begriffe]
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4 [Erweiterter erster Term]
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4 [Erweitern eines Fn-4]
= 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Kombination von Fn-4 und Fn-5]
= 4Fn-3 + Fn-6
Da jede dritte Fibonacci-Zahl gerade ist, also wenn Fn ist
selbst dann ist Fn-3 gerade und Fn-6 ist auch gerade. Sei Fn
x-tes gerades Element und markieren Sie es als EFx.
Unterschied zwischen Eis und SchneeWenn Fn EFx ist, dann ist Fn-3 die vorherige gerade Zahl, d. h. EFx-1
und Fn-6 ist vor EFx-1, d. h. EFx-2
Also Fn = 4Fn-3 + Fn-6
was bedeutet
EFx = 4EFx-1 + EFx-2
Nachfolgend finden Sie eine einfache Umsetzung der 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);
Ausgabe
8