Программа Python для поиска ряда Фибоначчи. Более питонский путь

Question

Есть еще одна тема для обсуждения серии Фибо в Python. Это для того, чтобы настроить код на более питонический. Как написать последовательность Фибоначчи на Python

Я влюблен в эту программу, которую я написал для решения Project Euler Q2. Я недавно пишу код на Python и радуюсь каждый раз, когда делаю это Pythonic way! Можете ли вы предложить лучший Pythonic способ сделать это?

Проект Euler Q2 . Найдите сумму всех четных членов в последовательности Фибоначчи, которые не превышают четырех миллионов.

fib=[]
def fibo(a=-1,b=1,upto=4000000):
    if a+b>=upto:
        return
    else:
        a,b=b,a+b
        fib.append(b)
        fibo(a,b)

fibo()
even=[i for i in fib if not i%2]
print sum(even)

Answer 1

Использование генераторов - это Pythonic способ генерирования длинных последовательностей при сохранении памяти:

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

import itertools
upto_4000000 = itertools.takewhile(lambda x: x <= 4000000, fibonacci())
print(sum(x for x in upto_4000000 if x % 2 == 0))

Answer 2

Сначала я бы сделал fibo () в качестве генератора:

def fibo(a=-1,b=1,upto=4000000):
    while a+b<upto:
        a,b = b,a+b
        yield b

Тогда я бы также выбрал для равномерности генератор, а не понимание списка.

print sum(i for i in fibo() if not i%2)

Answer 3

С одной стороны, я бы предложил суммировать термины по мере их вычисления, а не сохранять их в массиве и впоследствии суммировать массив, поскольку вам не нужно ничего делать с отдельными терминами, кроме сложения их. (Это просто хороший вычислительный смысл на любом языке)

Answer 4

Я бы использовал генератор Фибоначчи, как в @ constantin 'answer , но выражения генератора могли бы быть заменены простым циклом for:

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

sum_ = 0
for f in fibonacci():
    if f > 4000000:
       break
    if f % 2 == 0:
       sum_ += f

print sum_

Answer 5

Я бы внес следующие изменения:

• Использовать итерацию вместо рекурсии
• Просто сохраняйте промежуточный итог вместо того, чтобы хранить список всех чисел Фибоначчи, а затем находите сумму четных за последним

Кроме этого, это разумно Pythonic.

def even_fib_sum(limit):
    a,b,sum = 0,1,0
    while a <= limit:
        if a%2 == 0:
            sum += a
        a,b = b,a+b
    return sum

print(even_fib_sum(4000000))

Answer 6

Вот альтернативный прямой метод Он опирается на несколько свойств:

1. Каждое число Фибоначчи можно вычислить непосредственно как пол (pow (phi, n) + 0,5) (см. Расчет по округлению в http://en.wikipedia.org/wiki/Fibonacci_number). И наоборот, индекс наибольшего числа Фибоначчи, меньшего, чем i, определяется этажом (log (i * sqrt (5)) / log (phi))
2. Сумма первых N чисел Фибоначчи - это N + 2-е число Фибоначчи минус 1 (см. Вторую идентичность на той же странице википедии)
3. Четные числа Фибоначчи - это каждое третье число. (Посмотрите на последовательность мод 2 и результат тривиален)
4. Сумма четных чисел Фибоначчи равна половине суммы нечетных чисел Фибоначчи до одной и той же точки в последовательности.

Точка 4 видна из этого:

Sum of first 3N fibonacci numbers
   =(F(1) + F(2))+ F(3) +(F(4) + F(5))+ F(6) + ... +(F(3N-2) + F(3N-1))+ F(3N) 
   =     F(3)    + F(3) +     F(6)    + F(6) + ... +       F(3N)       + F(3N)
   = 2( F(3) + F(6) + ... + F(3N) )
   = 2 ( Sum of odd fibonacci numbers up to F(3N) )

Итак, переведите наше максимальное значение в 4000000, рассчитайте индекс наибольшего числа Фибоначчи меньше чем это.

int n = floor(log(4000000*sqrt(5))/log(phi));  // ( = 33) 

33 делится на 3, поэтому это четное число Фибоначчи, в противном случае нам нужно было бы настроить n следующим образом.

n = (n/3)*3;

Сумма всех чисел Фибоначчи до этого момента, если дана

sum = floor( pow( phi, n+2 ) + 0.5 ) - 1; // ( = 9227464 )

Сумма всех четных чисел составляет половину от этого:

sum_even = sum/2; // ( = 4613732 )

Приятно то, что это алгоритм O (1) (или O (log (N)), если вы включили стоимость pow / log), и он работает на удвоениях ... так что мы можем вычислить сумму для очень большие значения.

ПРИМЕЧАНИЕ. Я отредактировал и переместил этот ответ из закрытого дубликата этого вопроса. Фибоначчи до 4 миллионов

Answer 7

def main():
    a = 1
    b = 2
    num = 2

    while b < 4000000:
        a, b = b, a+b
        num += b if b % 2 == 0 else 0

    print num

if __name__ == '__main__':
    main()

Answer 8

print ("Fibonacci Series\n")

a  = input ("Enter a nth Term: ")

b = 0 

x = 0

y = 1

print x,("\n"), y

while b <=a-2:

  b = b+1

  z = x + y

  print z

  x = y

  y = z

Answer 9

В Python 3, по крайней мере, если вы дадите генератор функции sum, он будет лениво оценивать его, поэтому нет необходимости заново изобретать колесо.

Это то, что @Constantin сделал и правильно.

Протестировано путем сравнения использования памяти с использованием генераторов:

sum(range(9999999))

по сравнению с не так:

sum(list(range(9999999)))

Тот, у которого есть генератор, также не вызывает исключений памяти с более высокими числами.