ภาพรวมปัญหา
หาพจน์ที่ N ของอนุกรม: 7, 15, 32, 67, 138, 281, ...
ตัวอย่าง
อินพุต
N = 6
เอาต์พุต
281
วิธีแก้ปัญหา
สังเกตรูปแบบ Recurrence:
T(1) = 7 T(n) = 2·T(n-1) + (n-1)
โค้ดตัวอย่าง
#include <iostream>
using namespace std;
int findNthTerm(int n) {
if (n == 1) return 7;
int termN = 7;
for (int i = 2; i <= n; i++)
termN = 2 * termN + (i - 1);
return termN;
}
int main() {
int n = 12;
cout << "The series is 7, 15, 32, 67...\n";
cout << n << "th term of the series is " << findNthTerm(n);
return 0;
}
เอาต์พุต
The series is 7, 15, 32, 67... 12th term of the series is 18419
สรุป
Recurrence แบบ Linear Non-homogeneous คำนวณได้ด้วย Loop O(N) หรือหาสูตรปิดได้ด้วย Generating Function
