Find nth element of Stern’s Diatomic Series in C++
In this article, we will learn how to find the nth element of Stern’s Diatomic Series in C++.
Stern’s Diatomic Series is a sequence 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5 …. which emerges in the Calkin-Wilf tree. It is in some cases otherwise called the fusc function.
In mathematical notation, the nth term can be given by recurrence equation
s(n) = s(n/2) for n even
s(n) = s((n-1)/2)+ s((n+1)/2) for n odd
where s(0) = 0, s(1) = 1
Stern’s Diatomic Series in C++
We are going to solve this problem using dynamic programming.
1. Create a dynamic array of size n+1. Initialize the dp[0] to 0 and do[1] to 1.
2. Iterate the array for range (2, n)
- If n is even then set dp[i] = dp[i/2].
- Else set dp[i] = dp[(i-1)/2]+dp[(i+1)/2]
3. Finally, return dp[n].
#include <bits/stdc++.h> using namespace std; int Sterns_Diatomic_Series(int n){ int dp[n+1]; dp[0] = 0; dp[1] = 1; for(int i=2;i<=n;i++){ if (i%2 == 0) dp[i] = dp[i/2]; else dp[i] = dp[(i-1)/2]+dp[(i+1)/2]; } return dp[n]; } int main(){ int n; cout<<"Enter the n value: "; cin>>n; cout<<"The nth element of Sterns Diatomic Series is "<<Sterns_Diatomic_Series(n); return 0; }
Output
Enter the n value: 20 The nth element of Sterns Diatomic Series is 3 Enter the n value: 15 The nth element of Sterns Diatomic Series is 4
Also, read
Leave a Reply