java - 检测递归的算法

Question

我正在尝试实现一种方法，该方法将获得第一个 k 的数组。序列的整数值。根据给定的值，该方法将检测是否可以使用整数系数的线性递归生成序列的值。

1. 如果不可能，则会给出错误。
2. 如果可能，该方法将返回一个数组 C生成序列所需的整数系数，大小为 s <= k , 与 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 的输入序列values 会返回错误，但给定的序列至少为 10连续值，该方法将返回 {1,1,0,0,-3,0,0,0,0,4} ，对应于递归系数(数组第 i 位置中的零表示不需要 f(n - i) 值)。

显然，事先并不知道重复情况，只是为了简单起见，我给出了已知重复情况的示例。但该方法需要自行检测。

这能做到吗？这有什么已知的算法吗？我尝试用 Java 编写一些东西，但实际上它只不过是一种蛮力，检测 ALL 可能的重复，这不是很有帮助......我很乐意看到有效尝试的代码示例，如果它是可能的或任何正确方向的点。

编辑

经过一些搜索，我偶然发现了“Berlekamp–Massey algorithm”，它似乎与这个主题有关。

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 等等，直到找到解决方案。