C++ में स्टर्न की द्विपरमाणुक श्रेणी से n-वें तत्व का पता लगाएं

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

𝑝(𝑛)=$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