이 문제에서 정수 값 N이 주어집니다. 우리의 임무는 N번째 짝수 피보나치 수를 찾는 것입니다. .
피보나치 수열은 두 개의 이전 숫자를 더하여 후속 숫자를 생성합니다. 피보나치 수열은 F0과 F1의 두 숫자로 시작합니다. F0 및 F1의 초기 값은 각각 0, 1 또는 1, 1을 취할 수 있습니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
Input : N = 4 Output : 144
솔루션 접근 방식
이 문제에 대한 간단한 해결책은 피보나치 수열의 모든 세 번째 숫자가 짝수이고 짝수의 시퀀스도 재귀 공식을 따른다는 사실을 사용하는 것입니다.
짝수 피보나치 수열에 대한 재귀 공식은 -
Ef(n)=4Ef(n-1) + Ef(n-2) 여기서 Ef(0)=0 및 Ef(1)=2
모든 세 번째 피보나치 수는 짝수이므로 f(n-3)과 f(n-6)은 모두 짝수입니다. 따라서 f(n)을 k번째 요소로 간주하고 Ef(k)로 표시합니다. f(n)이 Ef(k)이면 f(n-3)은 Ef(k-1)로 표시되는 이전 짝수이므로 f(n-6)은 Ef(k-2)입니다.
따라서 f(n)=4f(n-3)+f(n-6)
또는, Ef(k)=4Ef(k-1) + Ef(k-2).
예시
솔루션의 작동을 설명하는 프로그램,
#include<iostream>
using namespace std;
int findNthEvenFiboNum(int n){
if (n < 1)
return n;
if (n == 1)
return 2;
return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n- 2));
}
int main (){
int n = 5;
cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n);
return 0;
} 출력
5th even fibonacci number is 610