从一个序列中找到模式，生成下一个元素的算法

Question

从一个序列中找到模式，生成下一个元素的算法

4

我想知道是否有可能处理一组数字，例如：

lst = [1, 1, 2, 3, 5, 8, 13, 21, 34]

并创建一个算法来找出模式： F(n) = F(n-1) + F(n-2)，然后继续添加下一个数字：

lst.append(x) # x being the next number which is 55

可能是一种可应用于任何数字列表的算法。

- Noah Cardoza

1

你所问的不是一个简单的问题，而是计算机科学中非常困难的问题。你的例子是一个简单的斐波那契数列，但并不是所有的模式都那么明显。请参见http://www.wolframalpha.com/widgets/view.jsp?id=d9976f1c2c0c972d1cee0c3647cbd194以获取一个示例。 - Selcuk

3个回答

5

我认为你试图做的事情是不可能的。主要原因是有无限数量以某些特定元素开头的序列。在这里，你想找到1, 1, 2, 3, 5, 8, 13, 21, 34后面的数字，并声称它们是55、89、144...。大多数人都同意你的说法，认为这是一个斐波那契数列。

但我会告诉你，下一个元素可以是55、91、149，而序列是ceil(e^(n-1)/2))。

实际上，我可以给你无限数量的具有相同起始元素的序列。不相信我吗？

这个怎么样：F(n) = F(n-1) + F(n-2) + F(n-9)。写一个程序，你会发现起始元素是一样的。再来一个吧：F(n) = F(n-1) + F(n-2) - 4 * F(n-9) + F(n - 17)。

你永远无法说服我或其他人，你的解决方案是正确的，我的是错误的。

- Salvador Dali

0

虽然在数学中可以定义这样的序列，假设以下值，但这需要一位聪明的数学家来进行计算。

当然，您可以编写一个具有某些“硬编码”模式检测的函数，但它可能不正确。因为那只是一个列表，下一个值很可能是12，即使上下文使其看起来像斐波那契数列。

如果您需要生成斐波那契数列，请考虑使用生成器函数：

def fib(n):
    # generate the first n Fibonacci numbers
    i = 0
    last = 0
    current = 1
    while i < n:
         yield current
         temp = current + last
         last = current
         current = temp
         i += 1

- user530873

当我运行以下代码时：fib([1, 1, 2, 3, 5, 8, 13, 21, 34])，我得到<generator object fib at 0x10ddd39b0>。这个东西该怎么处理啊？ - Noah Cardoza

如果你读了代码顶部的注释，它说它生成了前 n 个斐波那契数。不确定是否从上下文中不清楚，但 n 绝对是一个整数，而不是一个列表。你会想要像这样使用它：print(list(fib(42)))。 - user530873

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1952500 · Accepted Answer

简短的回答是：你所要求的是不可能的。

你所寻找的是一种与曲线拟合有关的算法。对于这个特殊问题，一种可能的方法是拉格朗日插值法。但需要注意的是，通常情况下，你所要求的可能没有实际解。例如，考虑简单序列：2, 4, 6, 8, 10, 12, 14，接下来的几个数字会是什么？你可能会说答案是16, 18, 20等，因为你使用方程f(n) = 2*n，其中n是项目位置（从1开始）。注意，形式为f(n) = [(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * g(n)] + 2*n的方程有无限多个。

第二项可以得到当 n = 1..7 时的正确值，而第一项只能在 n 取某些值时得到 0。因此，在第一项中，你可以选择任何有限范围的函数作为最后一个 g(n) 乘数，并从 n=8 开始获得任何想要的值。

例如，使用 g(n) = 20*n， f(n) = (n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * 20 * n + 2*n 将得到以下列表：2, 4, 6, 8, 10, 12, 14, 806416 因此，你所描述的问题是无法解决的。

然而，如果你对算法的形式进行表征（或者表征你希望使用来解决问题的函数族），你可以得到最优拟合数字的函数。例如，你可以说f(n)是一个一次多项式（线性方程），这将减少可能性并给出f(n) = 2 * n。其中一些方法在机器学习中传统地被使用，尤其是线性和逻辑回归。