← 完整题目索引

PROJECT EULER · #0101

最优多项式

Optimum Polynomial

仅题目 · 已解决原题 ↗

如果我们看到序列的前一项 k 项,则不可能确定地说出下一项的值,因为有无数个多项式函数可以对序列进行建模。

作为一个例子,让我们考虑立方体数字的序列。这是由生成函数定义的,
un=n3: 1,8,27,64,125,216,

假设我们只给出了这个序列的前两项。按照"简单就是最好"的原则,我们应该假设线性关系并预测下一项为 15(公差 7)。即使我们看到前三项,根据同样的简单原则,也应该假设存在二次关系。

我们将 OP(k,n) 定义为序列第一个 k 项的最佳多项式生成函数的第 nth 项。应该清楚的是,OP(k,n) 将准确生成 nk 的序列项,并且第一个错误项 (FIT) 可能会是 OP(k,k+1);在这种情况下,我们将其称为坏OP (BOP)。

作为基础,如果我们只给出序列的第一项,那么假设恒定性是最明智的;即,对于 n2OP(1,n)=u1

因此,我们获得三次序列的以下 OP

OP(1,n)=1 1,1,1,1,
OP(2,n)=7n6 1,8,15,
OP(3,n)=6n211n+6      1,8,27,58,
OP(4,n)=n3 1,8,27,64,125,

显然 k4 不存在 BOP。

通过考虑 BOP 生成的 FIT 总和(如上面的 red 所示),我们得到 1+15+58=74

考虑以下十次多项式生成函数: un=1n+n2n3+n4n5+n6n7+n8n9+n10.

求国际收支平衡表的 FIT 总和。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。