ภาพรวมปัญหา
อนุกรมใช้หลัก 4 และ 7 เท่านั้น: 4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, ...
หาตัวที่ N
ตัวอย่าง
อินพุต
N = 4
เอาต์พุต
47
วิธีแก้ปัญหา
สร้างอาร์เรย์ series[1...N]:
- series[1] = 4
- series[2] = 7
- i คี่: series[i] = series[i/2] × 10 + 4
- i คู่: series[i] = series[i/2 - 1] × 10 + 7
โค้ดตัวอย่าง
#include <iostream>
#include <vector>
using namespace std;
int findNthSeriesElement(int N) {
vector<int> series(N + 1);
series[1] = 4;
series[2] = 7;
for (int i = 3; i <= N; i++) {
if (i % 2 != 0)
series[i] = series[i / 2] * 10 + 4;
else
series[i] = series[(i / 2) - 1] * 10 + 7;
}
return series[N];
}
int main() {
int N = 9;
cout << "The " << N << "th element of the array is " << findNthSeriesElement(N);
return 0;
}
เอาต์พุต
The 9th element of the array is 474
สรุป
ใช้ Dynamic Programming สร้างค่าจากค่าก่อนหน้า คล้าย Binary Tree แต่มัป 0→4, 1→7
