หาพจน์ที่ N ของอนุกรม 3, 5, 33, 35, 53, 55... ใน C++

หาพจน์ที่ N ของอนุกรม: 3, 5, 33, 35, 53, 55, ... (ประกอบด้วยเลข 3 และ 5 เท่านั้น)

ตัวอย่าง: N = 6 → 55

วิธีแก้ปัญหา (DP / Recursive Construction)

สร้างอาร์เรย์ arr ขนาด n+1:

• arr[1] = 3, arr[2] = 5
• สำหรับ i = 3 ถึง n:
  • ถ้า i คี่: arr[i] = arr[i/2] × 10 + 3
  • ถ้า i คู่: arr[i] = arr[(i/2)-1] × 10 + 5

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int printNthElement(int n) {
    vector<int> arr(n + 1);
    arr[1] = 3;
    arr[2] = 5;
    for (int i = 3; i <= n; i++) {
        if (i % 2 != 0)
            arr[i] = arr[i / 2] * 10 + 3;
        else
            arr[i] = arr[(i / 2) - 1] * 10 + 5;
    }
    return arr[n];
}

int main() {
    int n = 6;
    cout << printNthElement(n);
    return 0;
}

Output

55