C++ में स्टर्न के डायटॉमिक सीरीज का n-वां एलिमेंट ढूंढें

यहां हम देखेंगे कि स्टर्न के डायटॉमिक सीरीज में nवां पद कैसे ढूंढें। श्रृंखला है 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... इसे फस्क फंक्शन के नाम से भी जाना जाता है। इस श्रृंखला को इस प्रकार परिभाषित किया जा सकता है -

p(n) = p(n/2) जब n सम है

p(n) = p((n-1)/2) + p((n+1)/2) जब n विषम है

p(0) = 0 और p(1) = 1

यहां हम गणनाओं की संख्या कम करने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। p(0) और p(1) के लिए बेस केस सहेजने के बाद, हम इंडेक्स i = 2 से n तक इटरेट करेंगे, और p(i) की गणना करेंगे

उदाहरण

#include 
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