Complete the sequence generated by a polynomial - GeeksforGeeks
Given a sequence with some of its term, we need to calculate next K term of this sequence. It is given that sequence is generated by some polynomial, however complex that polynomial can be. Notice polynomial is an expression of the following form:
P(x) = a0 + a1 x +a2 x^2 + a3 x^3 …….. + an x^n
We can solve this problem using a technique called difference of differences method, which is derivable from lagrange polynomial.
The technique is simple, we take the difference between the consecutive terms, if difference are equal then we stop and build up next term of the sequence otherwise we again take the difference between these differences until they become constant.
In below code same technique is implemented, first we loop until we get a constant difference keeping first number of each difference sequence in a separate vector for rebuilding the sequence again. Then we add K instance of same constant difference to our array for generating new K term of sequence and we follow same procedure in reverse order to rebuild the sequence.
Read full article from Complete the sequence generated by a polynomial - GeeksforGeeks
Given a sequence with some of its term, we need to calculate next K term of this sequence. It is given that sequence is generated by some polynomial, however complex that polynomial can be. Notice polynomial is an expression of the following form:
P(x) = a0 + a1 x +a2 x^2 + a3 x^3 …….. + an x^n
The given sequence can always be described by a number of polynomials, among these polynomial we need to find polynomial with lowest degree and generate next terms using this polynomial only.
The technique is simple, we take the difference between the consecutive terms, if difference are equal then we stop and build up next term of the sequence otherwise we again take the difference between these differences until they become constant.
In below code same technique is implemented, first we loop until we get a constant difference keeping first number of each difference sequence in a separate vector for rebuilding the sequence again. Then we add K instance of same constant difference to our array for generating new K term of sequence and we follow same procedure in reverse order to rebuild the sequence.
void
nextTermsInSequence(
int
sequence[],
int
N,
int
terms)
{
int
diff[N + terms];
// first copy the sequence itself into diff array
for
(
int
i = 0; i < N; i++)
diff[i] = sequence[i];
bool
more =
false
;
vector<
int
> first;
int
len = N;
// loop untill one difference remains or all
// difference become constant
while
(len > 1)
{
// keeping the first term of sequence for
// later rebuilding
first.push_back(diff[0]);
len--;
// converting the difference to difference
// of differences
for
(
int
i = 0; i < len; i++)
diff[i] = diff[i + 1] - diff[i];
// checking if all difference values are
// same or not
int
i;
for
(i = 1; i < len; i++)
if
(diff[i] != diff[i - 1])
break
;
// If some difference values were not same
if
(i != len)
break
;
}
int
iteration = N - len;
// padding terms instance of constant difference
// at the end of array
for
(
int
i = len; i < len + terms; i++)
diff[i] = diff[i - 1];
len += terms;
// iterating to get actual sequence back
for
(
int
i = 0; i < iteration; i++)
{
len++;
// shifting all difference by one place
for
(
int
j = len - 1; j > 0; j--)
diff[j] = diff[j - 1];
// copying actual first element
diff[0] = first[first.size() - i - 1];
// converting difference of differences to
// difference array
for
(
int
j = 1; j < len; j++)
diff[j] = diff[j - 1] + diff[j];
}
// printing the result
for
(
int
i = 0; i < len; i++)
cout << diff[i] <<
" "
;
cout << endl;
}