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

多项式插值 . 有许多方法(参见 http://en.wikipedia.org/wiki/Polynomial_interpolation

如果你有顺序值,那么有一个简单的算法。

给定一个序列x1,x2,x3,…,让δ(x)为差序列x2-x1,x3-x2,x4-x3。如果有n次多项式的连续值,那么Delta的第n次迭代是一个常量序列。

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, ...

对上述值数量的限制可确保在执行差异时序列不会变为空。

抱歉让你失望了,但这不太可能(一般来说),因为任何给定的序列都有无穷多个 k

你可以看看这个 Everything2 Lagrange polynomial .

形式上,部分序列没有唯一的下一个值。通常理解的问题可以清楚地表述为:

假设所展示的部分序列刚好足以约束某些生成规则,推导出最简单的可能规则并展示生成的下一个值。

这本书 Numerical Recipes 有一页又一页真正实用的算法来做这类事情。很值得一读!

>>> seq1 = [1, 2, 3, 4, 5]
>>> seq2 = [10, 20, 30, 40, 50]
>>> def next(seq):
...   m = (seq[1] - seq[0])/(1-0)
...   b = seq[0] - m * 0
...   return m*len(seq) + b
>>> next(seq1)
6
>>> next(seq2)
60

第三种情况需要求解非线性函数。

你可以试着用 extrapolation

这种数字序列通常是“智力测试”的一部分,这让我想到这样一种算法是某种通过(至少是部分)测试的东西 Turing Test ,这是很难做到的。

例如,在第三个示例中:

10 17 31 59 115

17和10之间的差值为7,31和17之间的差值为14,59和31之间的差值为28,115和59之间的差值为56。

所以你注意到它变成元素i+1=i+(7*2^n)。

所以17=10+(7*2^0)

和31=17+(7*2^1)

等等。。。

你有 f(n+1) = a*f(n) + b ,问题就在于 a b .

给定序列中至少三个项,你就可以这样做(你需要三个,因为你有三个未知数——起点, ,和 B ). 例如,假设你有 f(0) f(1) 和 f(2) .

我们可以解方程:

f(1) = a*f(0) + b
f(2) = a*f(1) + b

解决方法是:

a = (f(2)-f(1))/(f(1)-f(0))
b = f(1) - f(0)*(f(2)-f(1))/(f(1)-f(0))

(你要单独解决 f(0) = f(1) 以避免被零除。)

一旦你有 B

我们还可以编写一个更通用的过程,在给定的情况下运行 任何 序列中的三个点(例如第4、第7、第23或其他点)。这只是一个简单的例子。

不过,我们必须再次对解决方案的形式做出一些假设。在这个例子中,假设它是线性的。例如,我们可以把它看作是一个更一般的多项式,但是在这种情况下,您需要更多的序列项来找到解决方案,这取决于多项式的次数。

另见道格拉斯·霍夫施塔特《流动的概念和创造性的类比:思维基本机制的计算机模型》一书中的“寻找序列从何而来”一章

http://portal.acm.org/citation.cfm?id=218753.218755&coll=GUIDE&dl=GUIDE&CFID=80584820&CFTOKEN=18842417