주어진 값 n에서 n번째 짝수를 찾습니다. 피보나치 수 .
예:
입력 n = 3
산출 34
설명 처음 3개의 짝수 피보나치 수는 0 2 8 34 144이고 세 번째는 34입니다.입력 n = 4
산출 144
설명 처음 4개의 짝수 피보나치 수는 0 2 8 34 144이고 4번째는 144입니다.
[순진한 접근 방식] 모든 피보나치 수를 하나씩 확인
우리 모든 피보나치 수 생성 그런 적이 있는지 없는지 모든 숫자를 하나씩 확인하세요.
[효율적인 접근 방식] 직접 공식 사용 - O(n) 시간과 O(1) 공간
짝수 피보나치 수열은 0 2 8 34 144 610 2584입니다.... 이 수열에서 우리는 다음과 같은 아이디어를 얻을 수 있습니다. 순서대로 세 번째 숫자는 모두 짝수입니다. 그리고 그 순서는 다음 재귀 공식을 따릅니다.
짝수 피보나치 수열의 반복은 다음과 같습니다.
Eefn = 4fn-1 + Efn-2
위 공식은 어떻게 작동하나요?
세 번째 피보나치 수는 모두 짝수이기 때문에 원본 피보나치 공식을 살펴보고 Fn-3 및 Fn-6 형식으로 작성해 보겠습니다.
Fn = Fn-1 + Fn-2 [두 용어 확장]
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4 [첫 번째 항 확장]
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4 [Fn-4를 1개 확장]
= 3Fn-3 + Fn-4 + Fn-5 + Fn-6 [Fn-4와 Fn-5 결합]
= 4Fn-3 + Fn-6
세 번째 피보나치 수는 모두 짝수이므로 Fn이
그럼에도 불구하고 Fn-3은 짝수이고 Fn-6도 짝수입니다. Fn을 이라고 하자
x번째 짝수 요소를 삭제하고 EFx로 표시합니다.
DFA 오토마타 예Fn이 EFx이면 Fn-3은 이전 짝수입니다. 즉, EFx-1입니다.
Fn-6은 EFx-1보다 이전입니다. 즉, EFx-2입니다.
따라서 Fn = 4Fn-3 + Fn-6
즉
EFx = 4EFx-1 + EFx-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