โปรแกรม C++ หาองค์ประกอบที่ n-th ของชุด Stern's Diatomic Series

ที่นี่เราจะดูวิธีหาพจน์ที่ n ในชุด Stern's Diatomic series ชุดนี้เป็น 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... นี่ยังเรียกว่า fusc function ชุดนี้สามารถนิยามได้ดังนี้:

p(n) = p(n/2) เมื่อ n เป็นเลขคู่

p(n) = p((n-1)/2) + p((n+1)/2) เมื่อ n เป็นเลขคี่

p(0) = 0 และ p(1) = 1

ที่นี่เราจะใช้แนวคิด Dynamic Programming เพื่อลดจำนวนการคำนวณ หลังจากบันทึกกรณีฐานสำหรับ p(0) และ p(1) เราจะวนลูปจากดัชนี i = 2 ถึง n และคำนวณ p(i)

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

#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