Tìm phần tử thứ n của dãy Stern's Diatomic C++

Tìm số hạng thứ n trong dãy Stern's Diatomic. Dãy: 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4... Còn gọi là hàm fusc. Định nghĩa:

p(n) = p(n/2) khi n chẵn

p(n) = p((n-1)/2) + p((n+1)/2) khi n lẻ

p(0)=0 và p(1)=1

Dùng quy hoạch động để giảm tính toán. Lưu cơ sở p(0), p(1), lặp i=2 đến n tính p(i).

Ví dụ mã nguồn

#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; }

Kết quả

3 rd term is: 2 15 th term is: 4 20 th term is: 3