C++でSternの二原子分子シリーズからn番目の要素を検索します

ここでは、SternのDiatomicシリーズの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