完成由多项式生成的序列-yiteyi-C++库

给定一个序列及其部分项，我们需要计算该序列的下一个K项。给出了序列是由某个多项式生成的，无论该多项式有多复杂。请注意，多项式是以下形式的表达式： P（x）=a0+a1x+a2x^2+a3x^3一个x^n 给定的序列总是可以用一系列多项式来描述，在这些多项式中我们需要找到次数最低的多项式，并仅使用该多项式生成下一项。

null

例如：

If given sequence is 1, 2, 3, 4, 5 then its next term will be 6, 7, 8, etcand this correspond to a trivial polynomial.If given sequence is 1, 4, 7, 10 then its next term will be 13, 16, etc.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们可以使用一种叫做差分法的技术来解决这个问题，这种方法可以从拉格朗日多项式 .

这个技巧很简单，我们取连续项之间的差，如果差相等，那么我们停止并建立序列的下一项，否则我们再次取这些差之间的差，直到它们变为常数。下面的图表用一个例子解释了这项技术，给定的序列是8，11，16，23，我们假设找到这个序列的下三项。

generate-polynomial

在下面的代码中，实现了相同的技术，首先我们循环，直到我们得到一个常数差，将每个差序列的第一个数保持在一个单独的向量中，以便再次重建序列。然后，我们向数组中添加相同常差的K个实例，以生成新的序列K项，并按照相同的步骤以相反的顺序重建序列。

请参阅下面的代码以更好地理解。

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(                                     ""                                     );                       
                         }                       
           
                         // 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>                       

输出：

8 11 16 23 30 37 44

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章