เราจะมาดูวิธีหาพจน์ที่ n ในอนุกรมไดอะตอมมิกของสเติร์น อนุกรมนี้เหมือนกับ 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … นี่เรียกอีกอย่างว่าฟังก์ชันฟัส ชุดนี้สามารถกำหนดเป็น −
𝑝(𝑛)=$p\lgroup\frac{n}{2}\rgroup$ 𝑤ℎ𝑒𝑛 𝑛 𝑣 𝑒𝑣𝑒𝑛
𝑝(𝑛)=$p\lgroup\frac{n-1}{2}\rgroup+p\lgroup\frac{n+1}{2}\rgroup$ 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑜𝑑𝑑
𝑝(0)=0 𝑎𝑛𝑑 𝑝(1)=1
เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกเพื่อลดจำนวนการคำนวณ หลังจากบันทึกตัวพิมพ์พื้นฐานสำหรับ p(0) และ p(1) แล้ว เราจะวนซ้ำจากดัชนี i =2 ถึง n และคำนวณ p(i)
ตัวอย่าง
#include<iostream>
using namespace std;
int findTerm(int n) {
int table[n+1];
table[0] = 0;
table[1] = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0)
table[i] = table[i / 2];
else
table[i] = table[(i - 1) / 2] + table[(i + 1) / 2];
}
return table[n];
}
int main() {
cout << 3 << " rd term is: " << findTerm(3) << endl;
cout << 15 << " th term is: " << findTerm(15) << endl;
cout << 20 << " th term is: " << findTerm(20) << endl;
} ผลลัพธ์
3 rd term is: 2 15 th term is: 4 20 th term is: 3
