3

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

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。

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

4

2 回答 2

1

如果我对您的理解正确,您希望有效地计算 [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

于 2013-10-10T10:12:06.790 回答
0

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

http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

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

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

http://forum.codecall.net/topic/41540-fibonacci-with-no-recursion-for-fun/

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

于 2012-06-01T23:03:26.273 回答