制作fibo fas

Question

我需要写一个代码来给出一个数字并打印出F[数字]，这个代码很漂亮慢点。有吗更快代码的想法？你知道吗

 while True:
      n=input()
      if n=='END' or n=='end':
         break
      class Fibonacci:
            def fibo(self, n):
                if int(n) == 0:
                   return 0
                elif int(n) == 1:
                   return 1
                else:
                  return self.fibo(int(n)-1) + self.fibo(int(n)-2)
      f=Fibonacci()
      print(f.fibo(n))

Answer 1

可以使用functools memoize使它存储以前的值，这样它就不必递归调用fibonacci函数。他们列举的例子就是斐波那契

Answer 2

您可以使用dict来记忆函数：

class Fibonacci:
    memo = {}
    def fibo(self, n):
        if n in self.memo:
            return self.memo[n]
        if int(n) == 0:
            value = 0
        elif int(n) == 1:
            value = 1
        else:
            value = self.fibo(int(n) - 1) + self.fibo(int(n) - 2)
        self.memo[n] = value
        return value

Answer 3

我在这篇文章中写了一些关于更快的斐波那契，也许其中一个对你有用？https://sloperium.github.io/calculating-the-last-digits-of-large-fibonacci-numbers.html

不管怎样。你的代码非常慢，因为你得到指数运行时间调用相同的子树一遍又一遍。你知道吗

您可以尝试线性解决方案：

def fib3(n):
    if n == 0:
        return 0
    f1 = 0
    f2 = 1

    for i in range(n-1):
        f1,f2 = f2, f1+f2
    return f2