Chương trình C++ tìm số Fibonacci chẵn thứ N

Mô tả bài toán

Cho N, tìm số Fibonacci chẵn thứ N (F₀=0, F₁=1, F₂=1, F₃=2...).

Ví dụ

N=4 → Output: 144 (dãy chẵn: 0,2,8,34,144...).

Giải thuật

Mỗi số Fibonacci thứ 3 là chẵn. Dãy số chẵn thỏa E_n = 4E_n-1 + E_n-2 (E₀=0, E₁=2). Dùng đệ quy hoặc DP.

Mã nguồn C++

#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