資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究在 C++ 中查詢斯特恩雙原子序列的第 n 個元素
以下，我們將瞭解如何在斯特恩雙原子序列中找到第 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
更新於： 2019 年 12 月 19 日
101 次瀏覽
廣告