Dada una sucesión con parte de su término, necesitamos calcular el siguiente término K de esta sucesión. Se da que la secuencia es generada por algún polinomio, por complejo que sea ese polinomio. Observe que el polinomio es una expresión de la siguiente forma:
P(x) = a0 + a1 x +a2 x^2 + a3 x^3 …….. + an x^n
La secuencia dada siempre se puede describir mediante varios polinomios , entre estos polinomios necesitamos encontrar el polinomio con el grado más bajo y generar los siguientes términos usando solo este polinomio.
Ejemplos:
If given sequence is 1, 2, 3, 4, 5 then its next term will be 6, 7, 8, etc and this correspond to a trivial polynomial. If given sequence is 1, 4, 7, 10 then its next term will be 13, 16, etc.
Podemos resolver este problema utilizando una técnica llamada método de diferencia de diferencias, que se deriva del polinomio de Lagrange .
La técnica es simple, tomamos la diferencia entre los términos consecutivos, si la diferencia es igual, nos detenemos y construimos el siguiente término de la secuencia; de lo contrario, nuevamente tomamos la diferencia entre estas diferencias hasta que se vuelven constantes.
La técnica se explica en el siguiente diagrama con un ejemplo, la secuencia dada es 8, 11, 16, 23 y se supone que debemos encontrar los siguientes 3 términos de esta secuencia.
A continuación, se implementa la misma técnica de código, primero hacemos un bucle hasta que obtenemos una diferencia constante manteniendo el primer número de cada secuencia de diferencia en un vector separado para reconstruir la secuencia nuevamente. Luego agregamos la instancia K de la misma diferencia constante a nuestra array para generar un nuevo término K de secuencia y seguimos el mismo procedimiento en orden inverso para reconstruir la secuencia.
Consulte el siguiente código para una mejor comprensión.
C++
// C++ code to generate next terms of a given polynomial
// sequence
#include <bits/stdc++.h>
using namespace std;
// method to print next terms term of 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 until 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;
}
// Driver code to test above method
int main()
{
int sequence[] = {8, 11, 16, 23};
int N = sizeof(sequence) / sizeof(int);
int terms = 3;
nextTermsInSequence(sequence, N, terms);
return 0;
}
Java
// Java code to generate next terms
// of a given polynomial sequence
import java.util.*;
class GFG{
// Method to print next terms term of sequence
static void nextTermsInSequence(int []sequence,
int N, int terms)
{
int []diff = new int[N + terms];
// First copy the sequence itself
// into diff array
for(int i = 0; i < N; i++)
diff[i] = sequence[i];
//bool more = false;
ArrayList<Object> first = new ArrayList<Object>();
int len = N;
// Loop until one difference remains
// or all difference become constant
while (len > 1)
{
// Keeping the first term of
// sequence for later rebuilding
first.add(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 j;
for(j = 1; j < len; j++)
if (diff[j] != diff[j - 1])
break;
// If some difference values
// were not same
if (j != 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] = (int)first.get(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++)
{
System.out.print(diff[i] + " ");
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int []sequence = { 8, 11, 16, 23 };
int N = sequence.length;
int terms = 3;
nextTermsInSequence(sequence, N, terms);
}
}
// This code is contributed by pratham76
Python3
# Python3 code to generate next terms # of a given polynomial sequence # Method to print next terms term of sequence def nextTermsInSequence(sequence, N, terms): diff = [0] * (N + terms) # First copy the sequence itself # into diff array for i in range(N): diff[i] = sequence[i] more = False first = [] length = N # Loop until one difference remains # or all difference become constant while (length > 1): # Keeping the first term of sequence # for later rebuilding first.append(diff[0]) length -= 1 # Converting the difference to difference # of differences for i in range(length): diff[i] = diff[i + 1] - diff[i] # Checking if all difference values are # same or not for i in range(1, length): if (diff[i] != diff[i - 1]): break # If some difference values # were not same if (i != length): break iteration = N - length # Padding terms instance of constant # difference at the end of array for i in range(length, length + terms): diff[i] = diff[i - 1] length += terms # Iterating to get actual sequence back for i in range(iteration): length += 1 # Shifting all difference by one place for j in range(length - 1, -1, -1): diff[j] = diff[j - 1] # Copying actual first element diff[0] = first[len(first) - i - 1] # Converting difference of differences to # difference array for j in range(1, length): diff[j] = diff[j - 1] + diff[j] # Printing the result for i in range(length): print(diff[i], end = " ") print () # Driver code if __name__ == "__main__": sequence = [ 8, 11, 16, 23 ] N = len(sequence) terms = 3 nextTermsInSequence(sequence, N, terms) # This code is contributed by chitranayal
C#
// C# code to generate next terms
// of a given polynomial sequence
using System;
using System.Collections;
class GFG{
// Method to print next terms term of sequence
static void nextTermsInSequence(int []sequence,
int N, int terms)
{
int []diff = new int[N + terms];
// First copy the sequence itself
// into diff array
for(int i = 0; i < N; i++)
diff[i] = sequence[i];
//bool more = false;
ArrayList first = new ArrayList();
int len = N;
// Loop until one difference remains
// or all difference become constant
while (len > 1)
{
// Keeping the first term of
// sequence for later rebuilding
first.Add(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 j;
for(j = 1; j < len; j++)
if (diff[j] != diff[j - 1])
break;
// If some difference values
// were not same
if (j != 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] = (int)first[first.Count - 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++)
{
Console.Write(diff[i] + " ");
}
Console.Write("\n");
}
// Driver Code
public static void Main(string[] args)
{
int []sequence = { 8, 11, 16, 23 };
int N = sequence.Length;
int terms = 3;
nextTermsInSequence(sequence, N, terms);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript code to generate next terms
// of a given polynomial sequence
// Method to print next terms term of sequence
function nextTermsInSequence(sequence, N,terms)
{
let diff = new Array(N + terms);
// First copy the sequence itself
// into diff array
for(let i = 0; i < N; i++)
diff[i] = sequence[i];
//bool more = false;
let first=[];
let len = N;
// Loop until one difference remains
// or all difference become constant
while (len > 1)
{
// Keeping the first term of
// sequence for later rebuilding
first.push(diff[0]);
len--;
// Converting the difference to
// difference of differences
for(let i = 0; i < len; i++)
diff[i] = diff[i + 1] - diff[i];
// Checking if all difference values
// are same or not
let j;
for(j = 1; j < len; j++)
if (diff[j] != diff[j - 1])
break;
// If some difference values
// were not same
if (j != len)
break;
}
let iteration = N - len;
// Padding terms instance of constant
// difference at the end of array
for(let i = len; i < len + terms; i++)
diff[i] = diff[i - 1];
len += terms;
// Iterating to get actual sequence back
for(let i = 0; i < iteration; i++)
{
len++;
// Shifting all difference by one place
for(let j = len - 1; j > 0; j--)
diff[j] = diff[j - 1];
// Copying actual first element
diff[0] = first[first.length - i - 1];
// Converting difference of differences
// to difference array
for(let j = 1; j < len; j++)
diff[j] = diff[j - 1] + diff[j];
}
// Printing the result
for(let i = 0; i < len; i++)
{
document.write(diff[i] + " ");
}
document.write("<br>");
}
// Driver Code
let sequence=[8, 11, 16, 23];
let N = sequence.length;
let terms = 3;
nextTermsInSequence(sequence, N, terms);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8 11 16 23 30 37 44
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA