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

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

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]

首先，我们创建一个新的枚举器，然后将a和b分配给起始值（分别为2和1）。

为了生成序列，我们使用一个循环，它将延迟地将值生成给yielder（y）。

在这里，我们推入a，然后我们将a分配给bs值，将bs值分配给a b并行以避免在添加ab之前覆盖a。

Answer 2

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

因此，请考虑以下几行：

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

也就是说：

>

把那个较短序列的最后两个成员加起来。。。

。。。并将总和附加到较短的序列中。。。

。。。结果就是这个序列，就是你要求的序列。

这基本上就是它的全部！唯一的问题是没有地方可以开始。我们假设对于长度4的seq，我们已经解决了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求解，我刚刚告诉了你如何做到这一点。以此类推，对于你想给我的任何长度。