检测递归的算法

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值的输入序列都会返回错误，但给定一个至少包含10连续值的序列，该方法将返回{1,1,0,0,-3,0,0,0,0,4}对应于递推系数（i数组第 ' 个位置的零）表示f(n - i)不需要该值）。

显然，事先并不知道复发，只是为了简单起见，我给出了已知复发的例子。但是该方法需要自己检测它。

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

编辑

经过一番搜索，我偶然发现了“Berlekamp-Massey 算法”，它似乎与这个主题有关。

Answer 1

给定一个特定的 s，您会得到序列中第一个 s 之后的每个元素的线性方程（有 s 个未知数）。

For example, if s=2 and the sequence is 1, 1, 2, 3, 5, 8 then have unknowns a, b, and equations 1a + 1b = 2, 1a + 2b = 3, 2a + 3b = 5 and so on. You can try to solve these using any method for solving linear equations -- for example gaussian elimination. If s is small, then some of your equations need to be linear combinations of earlier ones, but gaussian elimination will find those for you. In this example, 2a+3b=5 is a linear combination of 1a+1b=2 and 1a+2b=3 (just add them up).

So you can try s=1, s=2, s=3 and so on, until you find a solution.