欧拉计划问题 25 的非暴力解决方案

Question

欧拉计划问题 25:

斐波那契数列由递推关系定义：

F_n = F_n−1 + F_n−2，其中 F_{1 = 1} 且 F₂ = 1。因此前 12 项 将是 F₁ = 1、F₂ = 1、F₃ = 2、F₄ = 3、F₅ = 5、F₆ = 8、F₇ = 13 , F₈ = 21、F₉ = 34、F₁₀ = 55、F₁₁ = 89、F₁₂ = 144

第 12 项 F₁₂，是第一个包含三位数的项。

斐波那契数列中包含 1000 的第一项是什么 数字？

我用 Python 做了一个强力解决方案，但这需要很长时间。谁能建议一个非暴力解决方案？

def Fibonacci(NthTerm):
    if NthTerm == 1 or NthTerm == 2:
        return 1 # Challenge defines 1st and 2nd term as == 1
    else:  # recursive definition of Fib term
        return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)

FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary range
    FibValue = str(Fibonacci(Term)) # Convert integer to string for len()
    if len(FibValue) == 1000:
        FirstTerm = Term
        break # Stop there
    else:
        continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."

Answer 1

您可以编写一个以线性时间运行并具有恒定内存占用的斐波那契函数，您不需要一个列表来保存它们。 这是一个递归版本（但是，如果 n 足够大，它只会stackoverflow）

def fib(a, b, n):
    if n == 1:
        return a
    else: 
        return fib(a+b, a, n-1)


print fib(1, 0, 10) # prints 55

此函数仅调用自身一次（导致大约 N 次调用参数 N），而您的解决方案调用自身两次（大约 2^N 次调用参数 N）。

这是一个永远不会堆栈溢出并使用循环而不是递归的版本：

def fib(n):
    a = 1
    b = 0
    while n > 1:
        a, b = a+b, a
        n = n - 1
    return a

print fib(100000)

而且速度足够快：

$ time python fibo.py 
3364476487643178326662161200510754331030214846068006390656476...

real    0m0.869s

但是调用

fib

直到得到足够大的结果并不完美：系列的第一个数字会被多次计算。 您可以计算下一个斐波那契数并在同一循环中检查其大小：

a = 1
b = 0
n = 1
while len(str(a)) != 1000:
    a, b = a+b, a
    n = n + 1
print "%d has 1000 digits, n = %d" % (a, n)

Answer 2

为什么没有人为此使用发电机？这是一个蛮力解决方案，但速度非常快：

def fibo():
    a = 0
    b = 1
    while True:
        yield b
        a,b = b,a+b

这给出了一个计算斐波那契数列的生成器。例如

f = fibo()
[next(f) for i in range(10)]

产生

[1,1,2,3,5,8,13,21,34,55]

使用这个，我们可以像这样解决问题：

f = enumerate(fibo())
x = 0
while len(str(x)) < 1000:
    i,x = next(f)

print("The %d-th term has %d digits"%(i+1,len(str(x))))

这会产生输出

The 4782-th term has 1000 digits

生成器计算序列并生成 1 乘 1 的项，并且该解决方案几乎立即运行。

Answer 3

只需对代码进行一点点更改，就可以对两件事进行大量优化。这两件事是：

• 您使用另外两个斐波那契数来计算每个斐波那契数，从而导致指数复杂性（即使您只计算单个但高的斐波那契数，其复杂性也会爆炸）。

• 您不记得任何先前计算的斐波那契数来计算循环中的下一个数。

只需记住所有计算的斐波那契数作为

Fibonacci

中的私有实现细节，您就可以摆脱这两个性能问题。您可以通过使用一个简单的动态数组来完成此操作，如果之前未缓存结果，则将结果添加到该数组中。

伪代码（我不会Python，但这可以很容易实现）：

def Fibonacci(NthTerm):
    if (cache contains NthTerm)
        return cache[NthTerm]
    else
        FibValue = Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)
        cache[NthTerm] = FibValue
        return FibValue

这将导致非常有限的递归，因为只有当您已经知道（并缓存）第 (N-1) 个数字时，您才能计算第 N 个斐波那契数。

即使您需要任何斐波那契数（用于将来的问题），这种优化也有效，但在这种特殊情况下，我们知道我们只需要记住最后两个数字，因为我们永远不会再要求旧数字。因此，您不需要整个数字列表，而只需要两个数字，您可以在主循环中的每个步骤中“循环遍历”它们。类似的东西

f1, f2 = f2, f1 + f2

在循环和初始化中

f1, f2 = 1, 1

本质上会取代你的函数

Fibonacci

及其性能问题，但它限制了你的使用场景。

Answer 4

您可以尝试对binet公式使用牛顿近似法。这个想法是在图上找到一条切线，并使用该线的 x 截距来近似图的零值。

Answer 5

不用每次都递归计算每个项，而是创建一个项数组，然后可以通过添加 terms[-1] 和 terms[-2] 来计算项

Answer 6

这是恒定空间和线性时间下的 Java 版本：

    static int q24(){
    int index = 3;
    BigInteger fn_2 = new BigInteger("1");
    BigInteger fn_1 = new BigInteger("1");
    BigInteger fn   = fn_1.add(fn_2);
    while(fn.toString().length()<1000){
        fn_2 = fn_1;
        fn_1 = fn;
        fn = fn_2.add(fn_1);
        index++;
    }       
    return index;
}

Answer 7

你可以使用记忆：

m={}

def fub(n):
     if n not in m:
        if n <= 2 :
           m[n] =  1
        else:
           m[n] =  fub(n-1) + fub(n-2)

     return m[n]

i=1
while len(str(fub(i))) != 1000:
   i+=1
print(i)

Answer 8

如果您使用 Kotlin，这是一个非常简单的解决方案。

import java.math.BigInteger
val bound: BigInteger = BigInteger.TEN.pow(999)
var index = 2
var fib = BigInteger.ONE
var prevFib = BigInteger.ONE
while (fib < bound) {
    prevFib = fib.also { fib += prevFib }
    index++
}
println(index)

Answer 9

进一步优化：检查长度不是通过字符串长度，而是通过与具有所需位数的最小整数进行比较。 1000 和 4000 位的基准：

n=1000
fibo_int 4782  0.00062 seconds
fibo_str 4782  0.03403 seconds

n=4000
fibo_int 19137  0.01066 seconds
fibo_str 19137  1.86070 seconds

代码：

from time import perf_counter as time

def fibo_int(n):
    a = b = i = 1
    goal = 10**(n-1)
    while a < goal:
        a, b, i = b, a+b, i+1
    return i

def fibo_str(n):
    a = b = i = 1
    while len(str(a)) < n:
        a, b, i = b, a+b, i+1
    return i

funcs = fibo_int, fibo_str

for n in 1000, 4000:
    print(f'{n=}')
    for f in funcs:
        t0 = time()
        print(f.__name__, f(n), f' {time() - t0:.5f} seconds')
    print()

在线尝试！

Answer 10

为什么不这样呢：

fib_list = [1, 1]
index = 2

while len(str(fib_list[-1])) < 1000:
    fib_list.append(fib_list[-1] + fib_list[-2])
    fib_list.pop(-3)
    index += 1

print(index)