Tìm số Pell (Pell Number) bằng C++

Số Pell định nghĩa: P₀ = 0, P₁ = 1, Pₙ = 2·Pₙ₋₁ + Pₙ₋₂. Cho n, tìm Pₙ.

Cách đệ quy (Recursive)

Áp dụng công thức trực tiếp. Độ phức tạp O(N) do có memoization ngầm (thực tế là O(2^N) nếu không memo, nhưng code mẫu dùng đệ quy đơn giản).

Ví dụ

#include <iostream>
using namespace std;

int pell(int n) {
    if (n <= 2) return n;
    return 2 * pell(n - 1) + pell(n - 2);
}

int main() {
    int n = 6;
    cout << pell(n) << "\n";
    return 0;
}

Kết quả

70

Cách lặp (Iterative) — hiệu quả hơn

Duyệt từ 2 đến n, cập nhật p0, p1. Độ phức tạp O(N), không gian O(1).

Ví dụ

#include <iostream>
using namespace std;

int main() {
    int n = 6;
    int p0 = 0, p1 = 1, pn;
    if (n <= 2) { cout << n << "\n"; return 0; }
    for (int i = 2; i <= n; i++) {
        pn = 2 * p1 + p0;
        p0 = p1;
        p1 = pn;
    }
    cout << pn << "\n";
    return 0;
}

Kết quả

70

Kết luận

Đã giải quyết tìm số Pell thứ N bằng đệ quy và lặp. Cách lặp tối ưu O(N) time, O(1) space. Code C++ mẫu.