A numerical sequence referred to as Stern's Diatomic Series is generated by summing up the preceding two numbers. Initially, the series begins with 0 and 1, with subsequent numbers calculated by adding the last two numbers together. As an illustration:
0, 1, 1, 2, 3, 2, 3, 4, 5, 3, 4, 5, 6, 7,.. . This sequence is occasionally referred to as the fusc Function.
Approach:
We apply the rather fundamental concept of dynamic programming to uncover the resolution to this issue. Calculating series[i] can be achieved by iterating from q = 2 to num and storing the initial values of series[0] = 0, series[1] = 1. This process aligns with the definition of Stern's diatomic series. Subsequently, the final step involves returning the value of series[n]. This method is well-suited for a range of applications and examinations as it furnishes a structured approach for producing and accessing series components.
Approach to Find the n-th Element
- Initializing the Series: Initially, we are initializing a vector to store the series's elements. The vector's initial two elements, 0 and 1 , are added.
- Generating the Series: We use a loop to generate the series up to the n-th Element. We add the two elements before it to calculate each successive Element inside the loop. After that, this new Element is pushed into the vector.
- Returning the n-th Element: After the series is formed up to thacpp tutorial, we return the n-th Element's value from the vector.
Formula
The recurrence relation serves as a formal mathematical expression defining the sequence series(num) within Stern's diatomic series.
For the initial scenario,
- When num equals 0, the value at the specified position will be 0.
- In the situation where num is 1, the value at the indicated position will be 1.
For a scenario where the process is repeated multiple times:
- In the event that the number is even, the value at series[num] is determined by the value at series[num/2].
- When the number is odd, the value at series[num] is calculated based on the values at series[(num-1)/2] and series[(num+1)/2].
Algorithm:
// SET the Base case
series[0] = 0;
series[1] = 1;
//Traversing the array From the 2nd Element to the nth Element.
for (int q=2; q<=num; q++)
{
// Case-1: for even num
if (q%2 == 0)
series[q] = series[q/2];
// Case-2: for odd num
else
series[q] = series[(q-1)/2] + series[(q+1)/2];
}
return series[num];
Example:
Let's consider an illustration to demonstrate the process of locating the nth element from Stern's Diatomic Series using C++.
#include <iostream>
#include <vector>
//Function to calculate Stern's Diatomic Series' n-th Element
int TofindSDSFunction(int num)
{
std::vector<int> series(num + 1, 0);
// Set all elements of the vector series to 0 and initialize it with a size of n+1.
series[1] = 1;
// Base case for n = 1
for (int q = 2; q <= num;q++)
{
if (q % 2 == 0)
series[q] = series[q / 2];
// series[q] is equal to series[q/2] for even n.
else
series[q] = series[(q - 1) / 2] + series[(q + 1) / 2];
// For odd n, series[q] is the sum of series[(q-1)/2] and series[(q+1)/2]
}
return series[num];
}
int main()
{
int num;
std::cout << "To determine the n-th Element in Stern's Diatomic Series, enter the value of num: ";
std::cin >> num;
std::cout << "The " << num << "-th Element in Stern's Diatomic Series is: " << TofindSDSFunction(num) << std::endl;
return 0;
}
Output:
To determine the n-th Element in Stern's Diatomic Series, enter the value of num: 7
The 7-th Element in Stern's Diatomic Series is: 3
Explanation:
In this instance, the TofindSDSFunction method is established to compute the n-th term of Stern's Diatomic Series using dynamic programming. Beginning with the initial term set at 1, it sets up a series vector to hold the series elements. Successive terms are calculated in a loop based on the parity of q. Finally, the designated function calculates the n-th term and displays the outcome alongside an explanatory statement within the primary method, enabling user input for the num value.
Complexity Analysis:
The time complexity is
- O(n).
This is due to iterating through the range from 2 to n to compute each element in the sequence.
Space Complexity
- The space complexity is also O(n) .
- We use a vector of size n+1 to store the elements of the series.
- Additionally, we use a constant amount of extra space for variables like num in the main Function.
The time and space complexity scales in direct proportion to the input value n. This algorithm demonstrates effectiveness and is capable of managing substantial n values without imposing notable additional burdens.
