algorithm - 获取修改后的斐波那契数列的第 N 位

Question

在今天的一次采访中，我得到了这个序列，这是一种修改后的斐波那契：

1, 1, 2, 4, 6, 13, 19, 42, 61, 135, ...,

我被要求编写一个函数来返回n位置的数字。

所以，如果 n = 4，函数应该返回 4，n = 6 返回 13，以此类推。

我相信你已经注意到了，不同之处在于偶数项等于前 4 项，而奇数项等于前 2 项。

如果您使用递归，这不是问题。这就是我所做的，但这不是我想要的方法。

斐波那契计算是这样的（在 PHP 中）：

$n = 17;
$phi = (1 + sqrt(5)) / 2;
$u = (pow($phi, $n) - pow(1 - $phi, $n)) / sqrt(5);

$u在这种情况下是 1597。

但是，我不知道如何使用像这样的斐波那契数列的修改版本来解决它。

score 1 · Accepted Answer

如果我对您的理解正确，您希望有效地计算 [ie in O( log(n) )] 序列定义为：

a[2n + 5] = a[2n + 4] + a[2n + 3] + a[2n + 2] + a[2n + 1]
a[2n + 2] = a[2n + 1] + a[2n]

让我们定义两个新序列。第一个对应偶数位置的a值，第二个对应偶数位置的值：

b[n] = a[2n]
c[n] = a[2n + 1]

现在我们有：

c[n] = b[n] + c[n - 1] + b[n - 1] + c[n - 2]
b[n] = c[n - 1] + b[n - 1]

从我们得到的第一个方程中减去第二个方程（经过一些变换）：

b[n] = ( c[n] - c[n-1] ) /2

接下来将此公式代入第一个方程以获得c的公式：

c[n] = 2 c[n-1] + c[n-2]

请注意，此等式仅涉及c中的元素。因此，现在可以使用此处描述的技术计算c的元素。通过进一步变换方程，您也可以有效地计算b。

score 0 · Accepted Answer

与由具有恒定系数的线性递归定义的每个序列一样，斐波那契数具有封闭形式的解。

但是，我不知道如何为这个特定序列创建一个封闭的形式表达式。

我可以补充的是，您无需递归即可求解斐波那契或任何类似序列，例如：

因此，您可以使用循环而不是堆栈来解决问题。

2 回答 2