Étant donné une valeur n, trouver le nième pair Nombre de Fibonacci .
Exemples :
Saisir n = 3
Sortir 34
Explication Les 3 premiers nombres pairs de Fibonacci sont 0 2 8 34 144, le 3ème étant 34.Saisir n = 4
Sortir 144
Explication Les 4 premiers nombres pairs de Fibonacci sont 0 2 8 34 144, le 4ème étant 144.
[Approche naïve] Vérifiez chaque numéro de Fibonacci un par un
Nous générer tous les nombres de Fibonacci et vérifie chaque numéro un par un si c'est le cas ou non
[Approche efficace] Utilisation d'une formule directe - temps O(n) et espace O(1)
La séquence de nombres pairs de Fibonacci est 0 2 8 34 144 610 2584.... À partir de cette séquence, nous pouvons avoir l'idée que un nombre sur trois dans une séquence est pair et la séquence suit la formule récursive.
La récurrence pour la séquence paire de Fibonacci est :
Eefn = 4fn-1 + Efn-2
Comment fonctionne la formule ci-dessus ?
Jetons un coup d'œil à la formule de Fibonacci originale et écrivons-la sous la forme Fn-3 et Fn-6 car un nombre de Fibonacci sur trois est pair.
Fn = Fn-1 + Fn-2 [Développer les deux termes]
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4 [Premier terme en expansion]
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4 [Extension d'un Fn-4]
= 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Combinant Fn-4 et Fn-5]
= 4Fn-3 + Fn-6
Puisque un nombre de Fibonacci sur trois est pair, donc si Fn est
même alors, Fn-3 est pair et Fn-6 est également pair. Soit Fn
xième élément pair et marquez-le comme EFx.
transition d'opacité CSSSi Fn est EFx alors Fn-3 est le nombre pair précédent, c'est-à-dire EFx-1
et Fn-6 est précédent de EFx-1, c'est-à-dire EFx-2
Donc Fn = 4Fn-3 + Fn-6
ce qui veut dire
EFx = 4EFx-1 + EFx-2
Vous trouverez ci-dessous une mise en œuvre simple de l'idée
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);
Sortir
8