Tìm số hạng thứ N của dãy 1, 2, 11, 12, 21... trong C++

Cho dãy: 1, 2, 11, 12, 21, 22, 111, 112... (chỉ chứa chữ số 1 và 2). Tìm số hạng thứ N.

Đệ quy

• N=1 → 1; N=2 → 2.
• N chẵn: T(N) = T(N/2 - 1)*10 + 2.
• N lẻ: T(N) = T(N/2)*10 + 1.

Mã nguồn C++

#include <iostream>
using namespace std;

int findNTerm(int N) {
    if (N == 1) return 1;
    if (N == 2) return 2;
    if (N % 2 == 0) return findNTerm(N/2 - 1) * 10 + 2;
    else return findNTerm(N/2) * 10 + 1;
}

int main() {
    int N = 12;
    cout << N << "Th term of the series is " << findNTerm(N); // 212
    return 0;
}

Đầu ra

12Th term of the series is 212