查找序列中下一个数字的算法

Question

自从我开始编程以来，这一直是我很好奇的事情。但似乎太复杂了，我什至无法尝试。

我很想看到一个解决方案。

1, 2, 3, 4, 5    // returns 6 (n + 1)
10, 20, 30, 40, 50   //returns 60 (n + 10)
10, 17, 31, 59, 115  //returns 227 ((n * 2) - 3)

Answer 1

你想做的是多项式插值。有很多方法(参见 http://en.wikipedia.org/wiki/Polynomial_interpolation )，但您必须在多项式的次数上有一个上限 U 并且至少有 U + 1 个值。

如果您有顺序值，则有一个简单的算法。

给定一个序列 x1, x2, x3, ...，令 Delta(x) 为差值序列 x2 - x1, x3 - x2, x4 - x3, ...。如果您有 n 次多项式的连续值，则 Delta 的第 n 次迭代是一个常数序列。

例如多项式n^3:

1, 8, 27, 64, 125, 216, ...
7, 19, 37, 61, 91, ...
12, 18, 24, 30, ...
6, 6, 6, ...

要获得下一个值，请再填充 6，然后向后计算。

6, 6, 6, 6 = 6, ...
12, 18, 24, 30, 36 = 30 + 6, ...
7, 19, 37, 61, 91, 127 = 91 + 36, ...
1, 8, 27, 64, 125, 216, 343 = 216 + 127, ...

上述值的数量限制确保您的序列在执行差分时永远不会变空。