Реализация ряда Фибоначчи с использованием жадного подхода? - PullRequest
Новая
       55

Реализация ряда Фибоначчи с использованием жадного подхода?

0 голосов
/ 18 октября 2018

Я реализовал ряд Фибоначчи с помощью рекурсии: 

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]

Я хочу реализовать это с использованием жадного подхода.Я не могу думать об этом в жадных выражениях.Пожалуйста, предоставьте жадный подход к этой проблеме.

1 Ответ

0 голосов
/ 18 октября 2018

Я не понял, что вы хотели сказать, сказав слово «жадный».Но есть следующие способы:

Пример 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. Использование памятки в качестве декоратора 

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)
...