Дате вредности н пронађите парни н'-ти Фибоначијев број .
Примери:
Инпут н = 3
Излаз 34
Објашњење Прва 3 парна Фибоначијева броја су 0 2 8 34 144, а трећи је 34.Инпут н = 4
Излаз 144
Објашњење Прва 4 парна Фибоначијева броја су 0 2 8 34 144, а 4. је 144.
[Наивни приступ] Проверите сваки Фибоначијев број један по један
Ми генерише све Фибоначијеве бројеве и проверите сваки број један по један да ли је икада или није
[Ефикасан приступ] Коришћење директне формуле – О(н) време и О(1) простор
Фибоначијев низ парних бројева је 0 2 8 34 144 610 2584.... Из овог низа можемо добити идеју да сваки трећи број у низу је паран а редослед следи по рекурзивној формули.
Понављање за парни Фибоначијев низ је:
Еефн = 4фн-1 + Ефн-2
Како функционише горња формула?
Хајде да погледамо оригиналну Фибоначијеву формулу и запишемо је у облику Фн-3 и Фн-6 због чињенице да је сваки трећи Фибоначијев број паран.
Фн = Фн-1 + Фн-2 [Проширивање оба појма]
= Фн-2 + Фн-3 + Фн-3 + Фн-4
= Фн-2 + 2Фн-3 + Фн-4 [Проширивање првог термина]
= Фн-3 + Фн-4 + 2Фн-3 + Фн-4
= 3Фн-3 + 2Фн-4 [Проширивање једног Фн-4]
= 3Фн-3 + Фн-4 + Фн-5 + Фн-6 [Комбинација Фн-4 и Фн-5]
= 4Фн-3 + Фн-6
Пошто је сваки трећи Фибоначијев број паран Па ако је Фн
чак и тада је Фн-3 паран и Фн-6 је такође паран. Нека је Фн
к-ти парни елемент и означите га као ЕФк.
селенАко је Фн ЕФк онда је Фн-3 претходни паран број, тј. ЕФк-1
а Фн-6 је претходни од ЕФк-1, тј. ЕФк-2
Дакле, Фн = 4Фн-3 + Фн-6
што значи
ЕФк = 4ЕФк-1 + ЕФк-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