Ruby中的Lucas序列

Question

Lucas序列是一个数字序列。该序列的第一个数字是2。Lucas序列的第二个数字是1。为了生成该序列的下一个数字，我们将前两个数字相加。例如，序列的前六个数字是: 2，1，3，4，7，11，...

编写一个lucasSequence方法，它接受一个表示长度的数字作为参数。该方法应该返回一个数组，该数组包含Lucas序列，直到给定的长度。递归地解决这个问题。

def lucas_sequence(length)
    return [] if length == 0
    return [2] if length == 1
    return [2, 1] if length == 2

    seq = lucas_sequence(length - 1)
    next_el = seq[-1] + seq[-2]
    seq << next_el
    seq
end

p lucas_sequence(0)   # => []
p lucas_sequence(1)   # => [2]    
p lucas_sequence(2)   # => [2, 1]
p lucas_sequence(3)   # => [2, 1, 3]
p lucas_sequence(6)   # => [2, 1, 3, 4, 7, 11]
p lucas_sequence(8)   # => [2, 1, 3, 4, 7, 11, 18, 29]

**我很难理解这背后的递归逻辑。有人能解释一下计算机是如何解决这个问题的吗？计算机是否读取长度，然后从2,1开始累加，直到长度达到长度？如果是，如何持续倒计时？**

Answer 1

递归是数学归纳法的编程等价物。给定一个系列，假设该系列的前一个成员的问题已经解决，并提供生成该成员的规则。

因此，仅考虑以下几行：

def lucas_sequence(length)
    seq = lucas_sequence(length - 1) # <1>
    next_el = seq[-1] + seq[-2] # <2>
    seq << next_el # <3>
    seq # <4>
end

上面写着：

你想知道某一长度的序列(length)。好的，首先告诉我前面的卢卡斯序列，比这个短一个单位的序列(length-1)。(这就是递归：lucas_sequence方法本身调用lucas_sequence方法，但长度值减少了。)

1. 将较短序列的最后两个成员相加...

1. ...and将和追加到较短的序列...

1. ...and结果是这个序列，就是您要求的序列。

这基本上就是它的全部！唯一的问题是没有起点。我们假设对于长度为4的序列，我们已经解决了3，这是通过假设我们已经解决了2而得到的，我们是通过假设我们已经解决了1来获得的。但是我们实际上还没有解决任何这些问题！

因此，我们从支持最退化的案例开始：

return [] if length == 0
return [2] if length == 1
return [2, 1] if length == 2

现在，如果长度为0、1或2，问题就解决了，因为我们只需直接给出这些答案。好的，如果长度是3，我们参考2来求解，这是已知的。好的，如果长度是4，我们参考3来求解，我刚刚告诉过你怎么做。好的，如果长度是5，我们参考4来求解，我刚刚告诉过你怎么做。以此类推，无论你愿意给我多少时间。

Answer 2

所以它本质上是一个修正的斐波那契数列。解决大多数结构化序列的最佳方法是使用Enumerator，例如

lucas = Enumerator.new do |y|
  a,b = 2,1
  loop do
    y << a
    a, b = b, a + b
  end
end

然后

lucas.first(10)
#=> [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

首先，我们创建一个新的Enumerator，然后将a和b分配给您的起始值(分别为2和1)。

为了生成序列，我们使用了一个循环，该循环将懒惰地将这些值返回给获得者(y)。

在这里，我们推入a，然后并行地将a赋给b的值，将b的值赋给a + b，以避免在添加a + b之前覆盖a。