亚线性时间内的第 n 个斐波那契数

绝對不後悔。 2024-08-13 18:08:32

这是我的递归版本，递归 log(n) 次。我认为以递归形式最容易阅读：

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

它之所以有效，是因为您可以使用 fib(n-1),fib(n) 计算 fib(n),fib(n-1) -2) 如果 n 为奇数且 n 为偶数，则可以使用 fib(n/2),fib 计算 fib(n),fib(n-1) （n/2-1）。

基本情况和奇数情况很简单。要导出偶数情况，请从 a、b、c 作为连续的斐波那契值（例如 8、5、3）开始，并将它们写入矩阵中，其中 a = b+c。注意：

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

从中，我们看到前三个斐波那契数的矩阵乘以任意三个连续斐波那契数的矩阵，等于下一个。所以我们知道：

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

所以：

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

简化右侧会导致偶数情况。

Here's my recursive version that recurses log(n) times. I think that it's easiest to read in the recursive form:

def my_fib(x):
  if x < 2:
    return x
  else:
    return my_fib_helper(x)[0]

def my_fib_helper(x):
  if x == 1:
    return (1, 0)
  if x % 2 == 1:
    (p,q) = my_fib_helper(x-1)
    return (p+q,p)
  else:
    (p,q) = my_fib_helper(x/2)
    return (p*p+2*p*q,p*p+q*q)

It works because you can compute fib(n),fib(n-1) using fib(n-1),fib(n-2) if n is odd and if n is even, you can compute fib(n),fib(n-1) using fib(n/2),fib(n/2-1).

The base case and the odd case are simple. To derive the even case, start with a,b,c as consecutive fibonacci values (eg, 8,5,3) and write them in a matrix, with a = b+c. Notice:

[1 1] * [a b]  =  [a+b a]
[1 0]   [b c]     [a   b]

From that, we see that a matrix of the first three fibonacci numbers, times a matrix of any three consecutive fibonacci numbers, equals the next. So we know that:

      n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

So:

      2n                        2
[1 1]    =  [fib(n+1) fib(n)  ]
[1 0]       [fib(n)   fib(n-1)]

Simplifying the right hand side leads to the even case.

回复收藏 0 原文

好倦 2024-08-13 18:08:32

使用 R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765

using R

l1 <- (1+sqrt(5))/2
l2 <- (1-sqrt(5))/2

P <- matrix(c(0,1,1,0),nrow=2) #permutation matrix
S <- matrix(c(l1,1,l2,1),nrow=2)
L <- matrix(c(l1,0,0,l2),nrow=2)
C <- c(-1/(l2-l1),1/(l2-l1))

k<-20 ; (S %*% L^k %*% C)[2]
[1] 6765

回复收藏 0 原文

沉溺在你眼里的海 2024-08-13 18:08:32

定点运算不准确。 Jason 的 C# 代码对于 n = 71（308061521170130 而不是 308061521170129）及以上给出了错误答案。

要获得正确答案，请使用计算代数系统。 Sympy 就是这样一个 Python 库。 http://live.sympy.org/ 有一个交互式控制台。复制并粘贴此函数

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

然后计算

>>> f(10)
55

>>> f(71)
308061521170129

您可能想尝试检查 phi。

Fixed point arithmetic is inaccurate. Jason's C# code gives incorrect answer for n = 71 (308061521170130 instead of 308061521170129) and beyond.

For correct answer, use a computational algebra system. Sympy is such a library for Python. There's an interactive console at http://live.sympy.org/ . Copy and paste this function

phi = (1 + sqrt(5)) / 2
def f(n):
    return floor(phi**n / sqrt(5) + 1/2)

Then calculate

>>> f(10)
55

>>> f(71)
308061521170129

You might like to try inspecting phi.

回复收藏 0 原文

抚笙 2024-08-13 18:08:32

这是一个单行代码，它使用大小为 O(n) 的整数，在 O(log n) 算术运算中计算 F(n)：

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

使用大小为 O(n) 的整数是合理的，因为这与答案的大小相当。

为了理解这一点，让 phi 为黄金比例（x^2=x+1 的最大解），F(n) 为第 n 个斐波那契数，其中 F(0)=0，F(1)=F (2)=1

现在，phi^n = F(n-1) + F(n)phi。

归纳证明：phi^1 = 0 + 1*phi = F(0) + F(1)phi。如果 phi^n =
F(n-1) + F(n)phi，则 phi^(n+1) = F(n-1)phi + F(n)phi^2 = F(n-1)phi +
F(n)(phi+1) = F(n) + (F(n)+F(n-1))phi = F(n) + F(n+1)phi。此计算中唯一棘手的步骤是将 phi^2 替换为 (1+phi)，这是因为 phi 是黄金比例。

此外，(a+b*phi) 形式的数字（其中 a、b 是整数）在乘法下也是封闭的。

证明： (p0+p1*phi)(q0+q1*phi) = p0q0 + (p0q1+q1p0)phi + p1q1*phi^2 =
p0q0 + (p0q1+q1p0)phi + p1q1*(phi+1) = (p0q0+p1q1) +
(p0q1+q1p0+p1q1)*phi。

使用这种表示形式，可以通过平方求幂在 O(log n) 整数运算中计算 phi^n。结果将是 F(n-1)+F(n)phi，从中可以读出第 n 个斐波那契数。

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

请注意，此代码的大部分是标准的乘方求幂函数。

为了得到这个答案的第一行，我们可以注意到，用足够大的整数 X 来表示 phi，可以执行 (a+b*phi)(c+d* phi) 作为整数运算(a+bX)(c+dX) modulo (X^2-X-1)。然后，pow 函数可以替换为标准 Python pow 函数（该函数方便地包含第三个参数 z，用于计算对 取模的结果） z 所选择的X 是2<。

Here's a one-liner that computes F(n), using integers of size O(n), in O(log n) arithmetic operations:

for i in range(1, 50):
    print(i, pow(2<<i, i, (4<<2*i)-(2<<i)-1)//(2<<i))

Using integers of size O(n) is reasonable, since that's comparable to size of the answer.

To understand this, let phi be the golden ratio (the largest solution to x^2=x+1) and F(n) be the n'th Fibonacci number, where F(0)=0, F(1)=F(2)=1

Now, phi^n = F(n-1) + F(n)phi.

Proof by induction: phi^1 = 0 + 1*phi = F(0) + F(1)phi. And if phi^n =
F(n-1) + F(n)phi, then phi^(n+1) = F(n-1)phi + F(n)phi^2 = F(n-1)phi +
F(n)(phi+1) = F(n) + (F(n)+F(n-1))phi = F(n) + F(n+1)phi. The only tricky step in this calculation is the one that replaces phi^2 by (1+phi), which follows because phi is the golden ratio.

Also numbers of the form (a+b*phi), where a, b are integers are closed under multiplication.

Proof: (p0+p1*phi)(q0+q1*phi) = p0q0 + (p0q1+q1p0)phi + p1q1*phi^2 =
p0q0 + (p0q1+q1p0)phi + p1q1*(phi+1) = (p0q0+p1q1) +
(p0q1+q1p0+p1q1)*phi.

Using this representation, one can compute phi^n in O(log n) integer operations using exponentiation by squaring. The result will be F(n-1)+F(n)phi, from which one can read off the n'th Fibonacci number.

def mul(p, q):
    return p[0]*q[0]+p[1]*q[1], p[0]*q[1]+p[1]*q[0]+p[1]*q[1]

def pow(p, n):
    r=1,0
    while n:
        if n&1: r=mul(r, p)
        p=mul(p, p)
        n=n>>1
    return r

for i in range(1, 50):
    print(i, pow((0, 1), i)[1])

Note that the majority of this code is a standard exponentiation-by-squaring function.

To get to the one-liner that starts this answer, one can note that representing phi by a large enough integer X, one can perform (a+b*phi)(c+d*phi) as the integer operation (a+bX)(c+dX) modulo (X^2-X-1). Then the pow function can be replaced by the standard Python pow function (which conveniently includes a third argument z which calculates the result modulo z. The X chosen is 2<<i.

回复收藏 0 原文

爱的十字路口 2024-08-13 18:08:32

除了通过数学方法进行微调之外，最好的最佳解决方案之一（我认为）是使用字典以避免重复计算。

import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

我们从简单的字典（斐波那契数列的前两个值）开始，并不断将斐波那契值添加到字典中。

前 100000 个斐波那契值大约需要 0.7 秒（Intel Xeon CPU E5-2680 @ 2.70 GHz、16 GB RAM、Windows 10-64 位操作系统）

Apart from fine-tuning by mathematical approaches, one of the best optimum solution (I believe) is using a dictionary in order to avoid repetitive calculations.

import time

_dict = {1:1, 2:1}

def F(n, _dict):
    if n in _dict.keys():
        return _dict[n]
    else:
        result = F(n-1, _dict) + F(n-2, _dict)
        _dict.update({n:result})
        return result

start = time.time()

for n in range(1,100000):
    result = F(n, _dict) 

finish = time.time()

print(str(finish - start))

We start with trivial dictionary (first two values of Fibonacci sequence) and constantly adding Fibonacci values to the dictionary.

It took about 0.7 seconds for the first 100000 Fibonacci values (Intel Xeon CPU E5-2680 @ 2.70 GHz, 16 GB RAM, Windows 10-64 bit OS)

回复收藏 0 原文

你对谁都笑 2024-08-13 18:08:32

请参阅分而治之算法此处

链接有这个问题的一些其他答案中提到的矩阵求幂的伪代码。

回复收藏 0 原文

情深缘浅 2024-08-13 18:08:32

您可以使用奇怪的平方根方程来获得确切的答案。原因是 $\sqrt(5)$ 最后掉了，你只需要用你自己的乘法格式来跟踪系数。

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55

You can use the weird square rooty equation to get an exact answer. The reason is that the $\sqrt(5)$ falls out at the end, you just have to keep track of the coefficients with your own multiplication format.

def rootiply(a1,b1,a2,b2,c):
    ''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b'''
    return a1*a2 + b1*b2*c, a1*b2 + a2*b1

def rootipower(a,b,c,n):
    ''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format'''
    ar,br = 1,0
    while n != 0:
        if n%2:
            ar,br = rootiply(ar,br,a,b,c)
        a,b = rootiply(a,b,a,b,c)
        n /= 2
    return ar,br

def fib(k):
    ''' the kth fibonacci number'''
    a1,b1 = rootipower(1,1,5,k)
    a2,b2 = rootipower(1,-1,5,k)
    a = a1-a2
    b = b1-b2
    a,b = rootiply(0,1,a,b,5)
    # b should be 0!
    assert b == 0
    return a/2**k/5

if __name__ == "__main__":
    assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
    assert fib(10)==55

回复收藏 0 原文

无人接听 2024-08-13 18:08:32

我遇到过一些以高效时间复杂度计算斐波那契的方法，以下是其中一些 -

方法 1 - 动态规划
现在这里的子结构是众所周知的，因此我将直接跳转到解决方案 -

static int fib(int n) 
{ 
int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
int i; 

f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
}

上述空间优化版本可以按如下方式完成 -

static int fib(int n) 
 { 
    int a = 0, b = 1, c; 
    if (n == 0) 
        return a; 
    for (int i = 2; i <= n; i++) 
    { 
        c = a + b; 
        a = b; 
        b = c; 
    } 
    return b; 
}

方法 2- （使用矩阵的幂 {{1,1},{ 1,0}} )

这是一个 O(n)，它依赖于这样一个事实：如果我们将矩阵 M = {{1,1},{1,0}} 与其自身相乘 n 次（换句话说，计算 power(M, n ))，然后我们得到第 (n+1) 个斐波那契数作为结果矩阵中行和列 (0, 0) 的元素。该解决方案的时间复杂度为 O(n)。

矩阵表示给出了以下斐波那契数的闭合表达式：
fibonaccimatrix

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

/*multiplies 2 matrices F and M of size 2*2, and 
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/*function that calculates F[][] raise to the power n and puts the 
result in F[][]*/
static void power(int F[][], int n) 
{ 
int i; 
int M[][] = new int[][]{{1,1},{1,0}}; 

// n - 1 times multiply the matrix to {{1,0},{0,1}} 
for (i = 2; i <= n; i++) 
    multiply(F, M); 
}

这可以优化以 O(Logn) 时间复杂度工作。我们可以在前面的方法中进行递归乘法来得到power(M,n)。

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

static void multiply(int F[][], int M[][]) 
{ 
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

static void power(int F[][], int n) 
{ 
if( n == 0 || n == 1) 
  return; 
int M[][] = new int[][]{{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
   multiply(F, M); 
}

方法 3（O(log n) 时间）
下面是一个更有趣的递归公式，可用于在 O(log n) 时间内找到第 n 个斐波那契数。

如果 n 是偶数，则 k = n/2：
F(n) = [2*F(k-1) + F(k)]*F(k)

如果 n 是奇数，则 k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)
这个公式是如何运作的？
由上述矩阵方程可以推导出该公式。
fibonaccimatrix

两边取行列式，我们得到
(-1)n = Fn+1Fn-1 – Fn2
此外，由于对于任何方阵 A，AnAm = An+m，因此可以导出以下恒等式（它们是从矩阵乘积的两个不同系数获得的）

FmFn + Fm-1Fn-1 = Fm+n-1

通过将 n = n+1,

FmFn+1 + Fm-1Fn = Fm+n

将 m = n

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (来源：Wiki）

要获得要证明的公式，我们只需执行以下操作
如果 n 是偶数，我们可以设 k = n/2
如果 n 是奇数，我们可以将 k = (n+1)/2

public static int fib(int n) 
{ 

    if (n == 0) 
        return 0; 

    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    // If fib(n) is already computed 
    if (f[n] != 0) 
        return f[n]; 

    int k = (n & 1) == 1? (n + 1) / 2 
                        : n / 2; 

    // Applyting above formula [See value 
    // n&1 is 1 if n is odd, else 0. 
    f[n] = (n & 1) == 1? (fib(k) * fib(k) +  
                    fib(k - 1) * fib(k - 1)) 
                   : (2 * fib(k - 1) + fib(k))  
                   * fib(k); 

    return f[n]; 
}

方法 4 - 使用公式
在这个方法中，我们直接实现斐波那契数列第n项的公式。时间 O(1) 空间 O(1)
Fn = {[(√5 + 1)/2] ^ n} / √5

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n)  
                    / Math.sqrt(5)); 
}

参考：http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

I have come across some of the methods for calculating Fibonacci with efficient time complexity following are some of them -

Method 1 - Dynamic Programming
Now here the substructure is commonly known hence I'll straightly Jump to the solution -

static int fib(int n) 
{ 
int f[] = new int[n+2]; // 1 extra to handle case, n = 0 
int i; 

f[0] = 0; 
f[1] = 1; 

for (i = 2; i <= n; i++) 
{ 
    f[i] = f[i-1] + f[i-2]; 
} 

return f[n]; 
}

A space-optimized version of above can be done as follows -

static int fib(int n) 
 { 
    int a = 0, b = 1, c; 
    if (n == 0) 
        return a; 
    for (int i = 2; i <= n; i++) 
    { 
        c = a + b; 
        a = b; 
        b = c; 
    } 
    return b; 
}

Method 2- ( Using power of the matrix {{1,1},{1,0}} )

This an O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix. This solution would have O(n) time.

The matrix representation gives the following closed expression for the Fibonacci numbers:
fibonaccimatrix

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

/*multiplies 2 matrices F and M of size 2*2, and 
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][]) 
{ 
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

/*function that calculates F[][] raise to the power n and puts the 
result in F[][]*/
static void power(int F[][], int n) 
{ 
int i; 
int M[][] = new int[][]{{1,1},{1,0}}; 

// n - 1 times multiply the matrix to {{1,0},{0,1}} 
for (i = 2; i <= n; i++) 
    multiply(F, M); 
}

This can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the previous method.

static int fib(int n) 
{ 
int F[][] = new int[][]{{1,1},{1,0}}; 
if (n == 0) 
    return 0; 
power(F, n-1); 

return F[0][0]; 
} 

static void multiply(int F[][], int M[][]) 
{ 
int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0]; 
int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1]; 
int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0]; 
int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1]; 

F[0][0] = x; 
F[0][1] = y; 
F[1][0] = z; 
F[1][1] = w; 
} 

static void power(int F[][], int n) 
{ 
if( n == 0 || n == 1) 
  return; 
int M[][] = new int[][]{{1,1},{1,0}}; 

power(F, n/2); 
multiply(F, F); 

if (n%2 != 0) 
   multiply(F, M); 
}

Method 3 (O(log n) Time)
Below is one more interesting recurrence formula that can be used to find nth Fibonacci Number in O(log n) time.

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)
How does this formula work?
The formula can be derived from the above matrix equation.
fibonaccimatrix

Taking determinant on both sides, we get
(-1)n = Fn+1Fn-1 – Fn2
Moreover, since AnAm = An+m for any square matrix A, the following identities can be derived (they are obtained from two different coefficients of the matrix product)

FmFn + Fm-1Fn-1 = Fm+n-1

By putting n = n+1,

FmFn+1 + Fm-1Fn = Fm+n

Putting m = n

F2n-1 = Fn2 + Fn-12

F2n = (Fn-1 + Fn+1)Fn = (2Fn-1 + Fn)Fn (Source: Wiki)

To get the formula to be proved, we simply need to do the following
If n is even, we can put k = n/2
If n is odd, we can put k = (n+1)/2

public static int fib(int n) 
{ 

    if (n == 0) 
        return 0; 

    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    // If fib(n) is already computed 
    if (f[n] != 0) 
        return f[n]; 

    int k = (n & 1) == 1? (n + 1) / 2 
                        : n / 2; 

    // Applyting above formula [See value 
    // n&1 is 1 if n is odd, else 0. 
    f[n] = (n & 1) == 1? (fib(k) * fib(k) +  
                    fib(k - 1) * fib(k - 1)) 
                   : (2 * fib(k - 1) + fib(k))  
                   * fib(k); 

    return f[n]; 
}

Method 4 - Using a formula
In this method, we directly implement the formula for the nth term in the Fibonacci series. Time O(1) Space O(1)
Fn = {[(√5 + 1)/2] ^ n} / √5

static int fib(int n) { 
double phi = (1 + Math.sqrt(5)) / 2; 
return (int) Math.round(Math.pow(phi, n)  
                    / Math.sqrt(5)); 
}

Reference: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

回复收藏 0 原文

辞旧 2024-08-13 18:08:32

我们首先应该注意到，斐波那契数 (F(n)) 随着 n 增长得非常快，并且不能用 64 位来表示 n 大于 93。因此，计算此类 n 的程序需要使用额外的机制来运算这些大数。现在，仅考虑（大量）操作的计数，顺序计算它们的算法将需要线性数量的操作。

我们可以从以下关于斐波那契数列的恒等式中受益：（

F(2m) = 2*F(m)*F(m+1) − (F(m))^2

F(2m+1) = (F(m))^2 + (F(m+1))^2

像 A^2 这样的符号表示 A 的平方）。

因此，如果我们知道 F(m) 和 F(m+1)，我们就可以直接计算 F(2m) 和 F(2m+1)。

考虑n 的二进制表示。请注意，从 x = 1 开始，我们可以通过迭代加倍并可能向 x 加 1 来得到 x = n。这可以通过迭代 n 的位并检查它是 0 还是 1 来完成。

这个想法是，我们可以保持 F(x) 与x。在每次这样的迭代中，当我们将 x 加倍并可能在 x 上加 1 时，我们还可以使用以下方法计算 F(x) 的新值： F(x) 和 F(x+1) 的早期值，具有上述方程。

由于迭代次数将以 n 为对数，因此总（大量）操作也以 n 为对数。

We should first note that Fibonacci numbers (F(n)) grow very fast with n and cannot be represented in 64-bits for n larger than 93. So a program for computing them for such n needs to use additional mechanisms to operate on these large numbers. Now, considering only the count of (large-number) operations, the algorithm to sequentially compute them will require linear number of operations.

We can benefit from the below identity about Fibonacci numbers:

F(2m) = 2*F(m)*F(m+1) − (F(m))^2

F(2m+1) = (F(m))^2 + (F(m+1))^2

(a symbol like A^2 denotes square of A).

So, if we know F(m) and F(m+1), we can directly compute F(2m) and F(2m+1).

Consider the binary representation of n. Observe that starting with x = 1, we can make x = n by iteratively doubling and possibly adding 1 to x. This can be done by iterating over the bits of n, and checking if it is 0 or 1.

The idea is that, we can maintain F(x) in sync with x. In each such iteration, as we double x and possibly add 1 to x, we can also compute the new value of F(x) using the earlier value of F(x) and F(x+1), with above equations.

Since the number of iterations will be logarithmic in n, the total (large-number) operations are also logarithmic in n.

回复收藏 0 原文

梦境 2024-08-13 18:08:32

c++14 示例实现：

uint64_t fib(unsigned n) {
    static struct FIB_NUMBERS {
        uint64_t numbers[100] {0, 1};
        unsigned max_n = 2;
        constexpr FIB_NUMBERS() {
            for (; max_n<100; ++max_n) {
                numbers[max_n] = numbers[max_n-1] + numbers[max_n-2];
                if (numbers[max_n] < numbers[max_n-1]) {
                    // overflow
                    numbers[max_n--] = 0;
                    break;
                }
            }
        }
    } fib;

    if (n <= fib.max_n)
        return fib.numbers[n];
    return 0;
}

编译器将生成所有 fib 数字，直到 n = 93
运行时只是一个查找。
要检测调用者的溢出：

auto res = fib(n);
if (res==0 && n>0) overflow_msg();

c++14 sample implementation:

uint64_t fib(unsigned n) {
    static struct FIB_NUMBERS {
        uint64_t numbers[100] {0, 1};
        unsigned max_n = 2;
        constexpr FIB_NUMBERS() {
            for (; max_n<100; ++max_n) {
                numbers[max_n] = numbers[max_n-1] + numbers[max_n-2];
                if (numbers[max_n] < numbers[max_n-1]) {
                    // overflow
                    numbers[max_n--] = 0;
                    break;
                }
            }
        }
    } fib;

    if (n <= fib.max_n)
        return fib.numbers[n];
    return 0;
}

Compiler will generate all fib numbers until n = 93
Runtime is just a lookup.
To detect overflow from the caller:

auto res = fib(n);
if (res==0 && n>0) overflow_msg();

回复收藏 0 原文

听风吹 2024-08-13 18:08:31

对于矩阵

M = [1 1] 
    [1 0]

遵循 Pillsy 对矩阵求幂的参考，这样

fib(n) = Mⁿ_1,2

使用重复乘法求矩阵幂的效率不是很高。

矩阵求幂的两种方法是分而治之，在 O(ln n) 步中产生 Mⁿ，或者特征值分解是恒定时间的，但由于浮点精度有限，可能会引入误差。

如果您想要一个大于浮点实现精度的精确值，则必须使用基于以下关系的 O ( ln n ) 方法：

Mⁿ = (M^n/2)² if n even
   = M·M^n-1 if n is odd

M 上的特征值分解找到两个矩阵 U 和 Λ 使得 Λ 是对角线并且

 M  = U Λ U^-1 
 Mⁿ = ( U Λ U^-1) ⁿ
    = U Λ U^-1 U Λ U^-1 U Λ U^-1 ... n times
    = U Λ Λ Λ ... U^-1 
    = U Λ ⁿ U^-1

Raising a the diagonal matrix Λ to the nth power is a simple matter of raising each element in Λ to the nth, so this gives an O(1) method of raising M to the nth power. However, the values in Λ are not likely to be integers, so some error will occur.

将 2x2 矩阵的 Λ 定义为

Λ = [ λ₁ 0 ]
  = [ 0 λ₂ ]

要找到每个 λ，我们

 |M - λI| = 0

求解它给出的

 |M - λI| = -λ ( 1 - λ ) - 1

λ² - λ - 1 = 0

使用二次公式

λ    = ( -b ± √ ( b² - 4ac ) ) / 2a
     = ( 1 ± √5 ) / 2
 { λ₁, λ₂ } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2

结果如果您已阅读 Jason 的答案，您可以看到这会发生什么去。

求解特征向量 X₁ 和 X₂：

if X₁ = [ X_1,1, X_1,2 ]

 M.X_{1 1} = λ₁X₁

 X_1,1 + X_1,2 = λ₁ X_1,1
 X_1,1      = λ₁ X_1,2

=>
 X₁ = [ Φ,   1 ]
 X₂ = [ 1-Φ, 1 ]

这些向量给出 U：

U = [ X_1,1, X_2,2 ]
    [ X_1,1, X_2,2 ]

  = [ Φ,   1-Φ ]
    [ 1,   1   ]

使用 U^-1 反转 U

A   = [  a   b ]
      [  c   d ]
=>
A^-1 = ( 1 / |A| )  [  d  -b ]
                   [ -c   a ]

由健全性检查给出

U^-1 = ( 1 / ( Φ - ( 1 - Φ ) )  [  1  Φ-1 ]
                               [ -1   Φ  ]
U^-1 = ( √5 )^-1  [  1  Φ-1 ]
               [ -1   Φ  ]

：

UΛU^-1 = ( √5 )^-1 [ Φ   1-Φ ] . [ Φ   0 ] . [ 1  Φ-1 ] 
                     [ 1   1  ]   [ 0  1-Φ ]   [ -1   Φ ]

let Ψ = 1-Φ, the other eigenvalue

as Φ is a root of λ²-λ-1=0 
so  -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 1

UΛU^-1 = ( √5 )^-1 [ Φ   Ψ ] . [ Φ   0 ] . [  1  -Ψ ] 
                 [ 1   1 ]   [ 0   Ψ ]   [ -1   Φ ]

       = ( √5 )^-1 [ Φ   Ψ ] . [ Φ   -ΨΦ ] 
                 [ 1   1 ]   [ -Ψ  ΨΦ ]

       = ( √5 )^-1 [ Φ   Ψ ] . [ Φ    1 ] 
                 [ 1   1 ]   [ -Ψ  -1 ]

       = ( √5 )^-1 [ Φ²-Ψ²  Φ-Ψ ] 
                  [ Φ-Ψ      0 ]

       = [ Φ+Ψ   1 ]    
         [ 1     0 ]

       = [ 1     1 ] 
         [ 1     0 ]

       = M

因此健全性检查成立。

现在我们已经拥有了计算 Mⁿ_1,2 所需的一切：

Mⁿ = UΛⁿU^-1
   = ( √5 )^-1 [ Φ   Ψ ] . [ Φⁿ  0 ] . [  1  -Ψ ] 
              [ 1   1 ]   [ 0   Ψⁿ ]   [ -1   Φ ]

   = ( √5 )^-1 [ Φ   Ψ ] . [  Φⁿ  -ΨΦⁿ ] 
              [ 1   1 ]   [ -Ψⁿ   ΨⁿΦ ]

   = ( √5 )^-1 [ Φ   Ψ ] . [  Φⁿ   Φ^n-1 ] 
              [ 1   1 ]   [ -Ψⁿ  -Ψ^n-1 ] as ΨΦ = -1

   = ( √5 )^-1 [ Φⁿ⁺¹-Ψⁿ⁺¹      Φⁿ-Ψⁿ ]
              [ Φⁿ-Ψⁿ      Φ^n-1-Ψ^n-1 ]

所以

 fib(n) = Mⁿ_1,2
        = ( Φⁿ - (1-Φ)ⁿ ) / √5

这与其他地方给出的公式一致。

您可以从递归关系中推导出它，但在工程计算和仿真中，计算大型矩阵的特征值和特征向量是一项重要的活动，因为它给出了方程组的稳定性和谐波，并允许有效地将矩阵提升为高幂。

Following from Pillsy's reference to matrix exponentiation, such that for the matrix

M = [1 1] 
    [1 0]

then

fib(n) = Mⁿ_1,2

Raising matrices to powers using repeated multiplication is not very efficient.

Two approaches to matrix exponentiation are divide and conquer which yields Mⁿ in O(ln n) steps, or eigenvalue decomposition which is constant time, but may introduce errors due to limited floating point precision.

If you want an exact value greater than the precision of your floating point implementation, you have to use the O ( ln n ) approach based on this relation:

Mⁿ = (M^n/2)² if n even
   = M·M^n-1 if n is odd

The eigenvalue decomposition on M finds two matrices U and Λ such that Λ is diagonal and

 M  = U Λ U^-1 
 Mⁿ = ( U Λ U^-1) ⁿ
    = U Λ U^-1 U Λ U^-1 U Λ U^-1 ... n times
    = U Λ Λ Λ ... U^-1 
    = U Λ ⁿ U^-1

Raising a the diagonal matrix Λ to the nth power is a simple matter of raising each element in Λ to the nth, so this gives an O(1) method of raising M to the nth power. However, the values in Λ are not likely to be integers, so some error will occur.

Defining Λ for our 2x2 matrix as

Λ = [ λ₁ 0 ]
  = [ 0 λ₂ ]

To find each λ, we solve

 |M - λI| = 0

which gives

 |M - λI| = -λ ( 1 - λ ) - 1

λ² - λ - 1 = 0

using the quadratic formula

λ    = ( -b ± √ ( b² - 4ac ) ) / 2a
     = ( 1 ± √5 ) / 2
 { λ₁, λ₂ } = { Φ, 1-Φ } where Φ = ( 1 + √5 ) / 2

If you've read Jason's answer, you can see where this is going to go.

Solving for the eigenvectors X₁ and X₂:

if X₁ = [ X_1,1, X_1,2 ]

 M.X_{1 1} = λ₁X₁

 X_1,1 + X_1,2 = λ₁ X_1,1
 X_1,1      = λ₁ X_1,2

=>
 X₁ = [ Φ,   1 ]
 X₂ = [ 1-Φ, 1 ]

These vectors give U:

U = [ X_1,1, X_2,2 ]
    [ X_1,1, X_2,2 ]

  = [ Φ,   1-Φ ]
    [ 1,   1   ]

Inverting U using

A   = [  a   b ]
      [  c   d ]
=>
A^-1 = ( 1 / |A| )  [  d  -b ]
                   [ -c   a ]

so U^-1 is given by

U^-1 = ( 1 / ( Φ - ( 1 - Φ ) )  [  1  Φ-1 ]
                               [ -1   Φ  ]
U^-1 = ( √5 )^-1  [  1  Φ-1 ]
               [ -1   Φ  ]

Sanity check:

UΛU^-1 = ( √5 )^-1 [ Φ   1-Φ ] . [ Φ   0 ] . [ 1  Φ-1 ] 
                     [ 1   1  ]   [ 0  1-Φ ]   [ -1   Φ ]

let Ψ = 1-Φ, the other eigenvalue

as Φ is a root of λ²-λ-1=0 
so  -ΨΦ = Φ²-Φ = 1
and Ψ+Φ = 1

UΛU^-1 = ( √5 )^-1 [ Φ   Ψ ] . [ Φ   0 ] . [  1  -Ψ ] 
                 [ 1   1 ]   [ 0   Ψ ]   [ -1   Φ ]

       = ( √5 )^-1 [ Φ   Ψ ] . [ Φ   -ΨΦ ] 
                 [ 1   1 ]   [ -Ψ  ΨΦ ]

       = ( √5 )^-1 [ Φ   Ψ ] . [ Φ    1 ] 
                 [ 1   1 ]   [ -Ψ  -1 ]

       = ( √5 )^-1 [ Φ²-Ψ²  Φ-Ψ ] 
                  [ Φ-Ψ      0 ]

       = [ Φ+Ψ   1 ]    
         [ 1     0 ]

       = [ 1     1 ] 
         [ 1     0 ]

       = M

So the sanity check holds.

Now we have everything we need to calculate Mⁿ_1,2:

Mⁿ = UΛⁿU^-1
   = ( √5 )^-1 [ Φ   Ψ ] . [ Φⁿ  0 ] . [  1  -Ψ ] 
              [ 1   1 ]   [ 0   Ψⁿ ]   [ -1   Φ ]

   = ( √5 )^-1 [ Φ   Ψ ] . [  Φⁿ  -ΨΦⁿ ] 
              [ 1   1 ]   [ -Ψⁿ   ΨⁿΦ ]

   = ( √5 )^-1 [ Φ   Ψ ] . [  Φⁿ   Φ^n-1 ] 
              [ 1   1 ]   [ -Ψⁿ  -Ψ^n-1 ] as ΨΦ = -1

   = ( √5 )^-1 [ Φⁿ⁺¹-Ψⁿ⁺¹      Φⁿ-Ψⁿ ]
              [ Φⁿ-Ψⁿ      Φ^n-1-Ψ^n-1 ]

so

 fib(n) = Mⁿ_1,2
        = ( Φⁿ - (1-Φ)ⁿ ) / √5

Which agrees with the formula given elsewhere.

You can derive it from a recurrance relation, but in engineering computing and simulation calculating the eigenvalues and eigenvectors of large matrices is an important activity, as it gives stability and harmonics of systems of equations, as well as allowing raising matrices to high powers efficiently.

回复收藏 0 原文

生死何惧 2024-08-13 18:08:31

给出

f(n) = Floor(phi^n / sqrt(5) + 1/2)

第 n 个斐波那契数由下式

phi = (1 + sqrt(5)) / 2

：假设原始数学运算 (+、-、* 和/) 是 O(1) 您可以使用此结果来计算 n第 Fibonacci 数 O(log n)< /code> 时间（O(log n) 因为公式中需要求幂）。

在 C# 中：

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}

The nth Fibonacci number is given by

f(n) = Floor(phi^n / sqrt(5) + 1/2)

where

phi = (1 + sqrt(5)) / 2

Assuming that the primitive mathematical operations (+, -, * and /) are O(1) you can use this result to compute the nth Fibonacci number in O(log n) time (O(log n) because of the exponentiation in the formula).

In C#:

static double inverseSqrt5 = 1 / Math.Sqrt(5);
static double phi = (1 + Math.Sqrt(5)) / 2;
/* should use 
   const double inverseSqrt5 = 0.44721359549995793928183473374626
   const double phi = 1.6180339887498948482045868343656
*/

static int Fibonacci(int n) {
    return (int)Math.Floor(Math.Pow(phi, n) * inverseSqrt5 + 0.5);
}

回复收藏 0 原文

记忆消瘦 2024-08-13 18:08:31

如果您想要确切的数字（这是一个“bignum”，而不是 int/float），那么恐怕

这是不可能的！

如上所述，斐波那契数列的公式为：

fib n = 下限 (phiⁿ/√5 + ¹/₂)

fib n ~= phiⁿ/√5

fib n 是多少位数字？

numDigits (fib n) = log (fib n) = log (phiⁿ/√5) = log phiⁿ - log √5 = n * log phi - 记录√5

numDigits (fib n) = n * const + const

这是O（n）

因为请求的结果是 O em>(n)，不能在O(n)时间内计算出来。

如果您只想要答案的低位数字，则可以使用矩阵求幂方法在亚线性时间内进行计算。

回复收藏 0 原文

池予 2024-08-13 18:08:31

SICP 练习之一是关于这个的，其中描述了答案 here.

在命令式风格中，程序看起来像这样

Function Fib(count)
    a ← 1
    b ← 0
    p ← 0
    q ← 1

    While count > 0 Do
        If Even(count) Then
             p ← p² + q²
             q ← 2pq + q²
             count ← count ÷ 2
        Else
             a ← bq + aq + ap
             b ← bp + aq
             count ← count - 1
        End If
    End While

    Return b
End Function

One of the exercises in SICP is about this, which has the answer described here.

In the imperative style, the program would look something like

Function Fib(count)
    a ← 1
    b ← 0
    p ← 0
    q ← 1

    While count > 0 Do
        If Even(count) Then
             p ← p² + q²
             q ← 2pq + q²
             count ← count ÷ 2
        Else
             a ← bq + aq + ap
             b ← bp + aq
             count ← count - 1
        End If
    End While

    Return b
End Function

回复收藏 0 原文

花伊自在美 2024-08-13 18:08:31

您也可以通过对整数矩阵求幂来完成此操作。如果您有矩阵，

    / 1  1 \
M = |      |
    \ 1  0 /

则 (M^n)[1, 2] 将等于第 n 斐波那契数，如果 [] 是矩阵下标，^ 是矩阵求幂。对于固定大小的矩阵，可以以与实数相同的方式在 O(log n) 时间内完成对正积分幂的求幂。

编辑：当然，根据您想要的答案类型，您也许可以使用恒定时间算法。与其他公式所示一样，第 n 个斐波那契数随 n 呈指数增长。即使使用 64 位无符号整数，您也只需要一个 94 项的查找表即可覆盖整个范围。

第二次编辑：首先使用特征分解进行矩阵指数与下面的 JDunkerly 解决方案完全相同。该矩阵的特征值是 (1 + sqrt(5))/2 和 (1 - sqrt(5))/2。

You can do it by exponentiating a matrix of integers as well. If you have the matrix

    / 1  1 \
M = |      |
    \ 1  0 /

then (M^n)[1, 2] is going to be equal to the nth Fibonacci number, if [] is a matrix subscript and ^ is matrix exponentiation. For a fixed-size matrix, exponentiation to an positive integral power can be done in O(log n) time in the same way as with real numbers.

EDIT: Of course, depending on the type of answer you want, you may be able to get away with a constant-time algorithm. Like the other formulas show, the nth Fibonacci number grows exponentially with n. Even with 64-bit unsigned integers, you'll only need a 94-entry lookup table in order to cover the entire range.

SECOND EDIT: Doing the matrix exponential with an eigendecomposition first is exactly equivalent to JDunkerly's solution below. The eigenvalues of this matrix are the (1 + sqrt(5))/2 and (1 - sqrt(5))/2.

回复收藏 0 原文

jJeQQOZ5 2024-08-13 18:08:31

维基百科有一个封闭式解决方案
http://en.wikipedia.org/wiki/Fibonacci_number

或者在 c# 中：

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }

Wikipedia has a closed form solution
http://en.wikipedia.org/wiki/Fibonacci_number

Or in c#:

    public static int Fibonacci(int N)
    {
        double sqrt5 = Math.Sqrt(5);
        double phi = (1 + sqrt5) / 2.0;
        double fn = (Math.Pow(phi, N) - Math.Pow(1 - phi, N)) / sqrt5;
        return (int)fn;
    }

回复收藏 0 原文

欢你一世 2024-08-13 18:08:31

对于非常大的函数，这个递归函数是有效的。它使用以下方程：

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

您需要一个可以处理大整数的库。我使用 https://mattmccutchen.net/bigint/ 中的 BigInteger 库。

从一系列斐波那契数开始。使用fibs[0]=0、fibs[1]=1、fibs[2]=1、fibs[3]=2、fibs[4]=3等。在这个例子中，我使用前501个数组（数0）。您可以在此处找到前 500 个非零斐波那契数：http://home.hiwaay.net /~jalison/Fib500.html。需要进行一些编辑才能将其设置为正确的格式，但这并不难。

然后你可以使用这个函数（在 C 语言中）找到任何斐波那契数：

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

我已经测试了第 25,000 个斐波那契数等。

For really big ones, this recursive function works. It uses the following equations:

F(2n-1) = F(n-1)^2 + F(n)^2
F(2n) = (2*F(n-1) + F(n)) * F(n)

You need a library that lets you work with big integers. I use the BigInteger library from https://mattmccutchen.net/bigint/.

Start with an array of of fibonacci numbers. Use fibs[0]=0, fibs[1]=1, fibs[2]=1, fibs[3]=2, fibs[4]=3, etc. In this example, I use an array of the first 501 (counting 0). You can find the first 500 non-zero Fibonacci numbers here: http://home.hiwaay.net/~jalison/Fib500.html. It takes a little editing to put it in the right format, but that is not too hard.

Then you can find any Fibonacci number using this function (in C):

BigUnsigned GetFib(int numfib)
{
int n;
BigUnsigned x, y, fib;  

if (numfib < 501) // Just get the Fibonacci number from the fibs array
    {
       fib=(stringToBigUnsigned(fibs[numfib]));
    }
else if (numfib%2) // numfib is odd
    {
       n=(numfib+1)/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=((x*x)+(y*y));
    }
else // numfib is even
    {
       n=numfib/2;
       x=GetFib(n-1);
       y=GetFib(n);
       fib=(((big2*x)+y)*y);
   }
return(fib);
}

I've tested this for the 25,000th Fibonacci number and the like.

回复收藏 0 原文

亚线性时间内的第 n 个斐波那契数

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（17）

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

亚线性时间内的第 n 个斐波那契数

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（17）

关于作者

相关话题

热门标签

推荐作者

1CH1MKgiKxn9p

ゞ记忆︶ㄣ

JackDx

信远

yaoduoduo1995

霞映澄塘

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。