Sau đây chúng ta sẽ xem cách tìm số hạng thứ n trong loạt bài Stern’s Diatomic. Dãy số như 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4,… Đây còn được gọi là hàm fusc. Chuỗi này có thể được định nghĩa là -
𝑝 (𝑛) =$ p \ lgroup \ frac {n} {2} \ rgroup $ 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛
𝑝 (𝑛) =$ p \ lgroup \ frac {n-1} {2} \ rgroup + p \ lgroup \ frac {n + 1} {2} \ rgroup $ 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑜𝑑𝑑
𝑝 (0) =0 𝑎𝑛𝑑 𝑝 (1) =1
Ở đây chúng tôi sẽ sử dụng cách tiếp cận Lập trình động để giảm số lần tính toán. Sau khi lưu trường hợp cơ sở cho p (0) và p (1), chúng tôi sẽ lặp lại từ chỉ mục i =2 thành n và tính p (i)
Ví dụ
#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;
} Đầu ra
3 rd term is: 2 15 th term is: 4 20 th term is: 3