用于检测递归的算法

Question

我正在尝试实现一种方法，该方法将给出一个长度为k的整数序列。根据给定值，该方法将检测是否可以使用具有整数系数的线性递推公式生成序列的值。

1. 如果不可能，则会给出一个错误。
2. 如果可能，该方法将返回一个大小为s<=k的整数系数数组C，其中s尽可能小。

对于斐波那契数列，给定输入{0,1,1,2,3,5,13}，该方法将返回{1,1}。

对于Tribonacci数列，给定至少3个值的输入序列，该方法将返回{1,1,1}。

对于已知递推关系f(n)=f(n−1)+f(n−2)−3*f(n−5)+4*f(n−10)，任何少于10个值的输入序列都会返回一个错误，但是给定至少10个连续值的序列，该方法将返回{1,1,0,0,−3,0,0,0,0,4}，对应于递推的系数（数组中第i个位置的零表示不需要f(n−i)的值）。

显然，递推不是提前知道的，这只是为了简单起见，我提供了已知递推的示例。但是该方法需要自行检测它。

这是否可行？是否有任何已知的算法？我尝试在Java中编写了一些程序，但实际上它不过是一种暴力方法，检测所有可能的递推公式并没有什么帮助...如果可能的话，我很想看到高效尝试这个问题的代码示例或任何指导方向。

编辑

搜索后，我偶然发现了“Berlekamp-Massey算法”，它似乎与此主题有关。

- MC From Scratch

---

检测公式的精确算法是不可能的（在我看来）。想象一下一个简单的公式 f(n)=af(n-1)+bf(n-2), a,b 为整数。在这种情况下，如何进行变化以适应 a,b？接下来，如果放弃这个尝试并向初始函数添加一个部分 cf(n-3)。输入参数的数量非常重要，如果没有限制，算法可能会非常低效。我的观点是，您的问题对于数学理论来说很好，但作为此处的主题，它不太实用（关键是算法，与数学相关，而不是任何语言中的任何实现）。 - Traian GEICU

进一步观察所给答案，似乎可以检测线性递归。因此，在生成方程系统之后应计算 a、b、etc。 - Traian GEICU

Answer 1

给定一个特定的s，对于第一个s后的每个序列元素，您将获得一个线性方程（具有s个未知数）。

例如，如果 s=2 而序列是 1，1，2，3，5，8，则有未知数a、b和方程式1a+1b = 2，1a+2b =3，2a+3b =5 等。你可以尝试使用任何解决线性方程的方法来解决这些问题--例如高斯消元法。如果 s 很小，则您的某些方程需要是先前方程的线性组合，但高斯消元法会为您找到它们。在这个例子中，2a+3b=5 是 1a+1b=2 和 1a+2b=3 的一个线性组合（只需将它们相加即可）。

因此，您可以尝试 s=1，s=2，s=3 等，直到找到解决方案。

- Paul Hankin