计算序列的第 n 个元素的脚本

Question

我正在尝试编写一些代码来计算序列的第 n 个元素。a_i = 2 * a_i-1 + 1 for i > 0, where a_0 = 1.我了解该公式的工作原理以及如何在 Python 中实现它。我只是迷失了如何找到第 n 个元素的公式。自从我服用 clac2 以来已经有一段时间了。我知道有一种方法可以找到公式，所以如果有人有任何提示，将不胜感激！我会发布一些代码，但我知道这是错误的并且不计算第 n 个元素。截至目前，我只是对每个元素进行硬编码。所以，正如我所说，一旦我知道找到第 n 个元素的公式，我就可以编写代码。

Answer 1

首先，观察a_0 = 1 = 2**(0+1) - 1.

现在，通过归纳：

a_i = 2 * a_(i-1) + 1 = 2*(2**((i-1)+1) - 1) + 1 = 2**(i+1) - 1.

这为您提供了一个封闭形式的解决方案：

>>> def a(i):

...   return 2**(i+1) - 1

...

>>> [a(i) for i in range(10)]

[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]

Answer 2

这可以通过一个非常简单的递归函数来完成：

def a(i):

    if i == 0:

        return 1

    return 2 * a(i - 1) + 1

当然，如果你需要一个类似 的列表[a(i) for i in range(1000)]，你不希望函数a(0), a(1), ..., a(n - 2), a(n - 1)为了计算a(n)all而重新计算n，所以你需要一个缓存：

import functools 

@functools.lru_cache(None)

def a(i):

    ...  # do the thing

Answer 3

您不需要直接为您提供第 n 个元素的公式。计算第一个元素，然后计算第二个元素，以此类推，直到你得到第 n 个元素。