Trong bài toán này, chúng ta được cung cấp một giá trị nguyên N. Nhiệm vụ của chúng ta là tìm Số Fibonacci Chẵn thứ N .
Chuỗi Fibonacci tạo ra số tiếp theo bằng cách thêm hai số trước đó. Chuỗi Fibonacci bắt đầu từ hai số - F0 &F1. Các giá trị ban đầu của F0 &F1 có thể được lấy tương ứng là 0, 1 hoặc 1, 1.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 4 Output : 144
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng thực tế là mọi số thứ ba trong dãy fibonacci đều là số chẵn và dãy số chẵn cũng tuân theo công thức đệ quy.
Công thức đệ quy cho dãy Fibonacci chẵn là -
Ef (n) =4Ef (n-1) + Ef (n-2) trong đó Ef (0) =0 và Ef (1) =2
Chúng ta biết rằng mọi số fibonacci thứ ba đều là số chẵn, do đó f (n-3) và f (n-6) đều là số chẵn. Vì vậy, chúng ta sẽ coi f (n) là phần tử thứ k và được ký hiệu là Ef (k). Nếu f (n) là Ef (k), thì f (n-3) là số chẵn trước đó được ký hiệu là Ef (k-1) và do đó f (n-6) là số trước của Ef (k-1) mà là Ef (k-2).
Do đó f (n) =4f (n-3) + f (n-6)
Hoặc, Ef (k) =4Ef (k-1) + Ef (k-2).
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
5th even fibonacci number is 610