使用贪婪方法实现斐波那契数列？

Question

我已经使用递归实现了斐波那契数列：

def fibonacci(n): 
    if n==0: 
        return 0
    elif n==1: 
        return 1
    else: 
        return fibonacci(n-1) + fibonacci(n-2)

我也用动态规划实现过：

def fibonacci(n): 
    result = [0, 1]

    if n > 1:
        for i in range(2, n+1):
            result.append(result[i-1] + result[i-2])
    return result[n]

我想用贪婪的方法来实现它。我无法用贪婪的术语来思考它。请为这个问题提供一个贪心的方法。

Answer 1

'greedy'我没听懂你想表达的意思。但这些是方法：

示例 1：使用循环技术

 def fib(n):
     a,b = 1,1
     for i in range(n-1):
      a,b = b,a+b
     return a
    print fib(5)

示例 2：使用递归

def fibR(n):
 if n==1 or n==2:
  return 1
 return fibR(n-1)+fibR(n-2)
print fibR(5)

示例 3：使用生成器

a,b = 0,1
def fibI():
 global a,b
 while True:
  a,b = b, a+b
  yield a
f=fibI()
f.next()
f.next()
f.next()
f.next()
print f.next()

示例 4：使用记忆

def memoize(fn, arg):
 memo = {}
 if arg not in memo:
  memo[arg] = fn(arg)
  return memo[arg]

fib() 如示例 1 中所写。

fibm = memoize(fib,5)
print fibm

示例 5：使用 memoization 作为装饰器

class Memoize:
 def __init__(self, fn):
  self.fn = fn
  self.memo = {}
 def __call__(self, arg):
  if arg not in self.memo:
   self.memo[arg] = self.fn(arg)
   return self.memo[arg]

@Memoize
def fib(n):
 a,b = 1,1
 for i in range(n-1):
  a,b = b,a+b
 return a
print fib(5)

使用贪婪方法实现斐波那契数列？

Implementing fibonacci series using greedy approach?

python

algorithm

dynamic-programming

fibonacci

greedy

示例 1：使用循环技术

示例 2：使用递归

示例 3：使用生成器

示例 4：使用记忆

fib() 如示例 1 中所写。

示例 5：使用 memoization 作为装饰器