Фибоначчи до 4 миллионов

Условие цикла неверное, должно быть примерно так:

while True:
    Fibonacci1 = Fibonacci1 + Fibonacci2
    if Fibonacci1 % 2 == 0:
        if a + Fibonacci1 > 4000000:
            break
        a = a + Fibonacci1
    Fibonacci2 = Fibonacci1 + Fibonacci2
    if Fibonacci2 % 2 == 0:
        if a + Fibonacci2 > 4000000:
            break
        a = a + Fibonacci2

Есть пара проблем с вашим кодом:

• Вы выполняете цикл четыре миллиона раз, а не до тех пор, пока условие не станет истинным.
• Вы повторяете код в теле цикла.

Большинство людей, когда они начинают изучать Python, изучают только императивное программирование. Это неудивительно, поскольку Python — императивный язык. Но Python также в определенной степени поддерживает функциональное программирование, и для такого рода упражнений подход функционального программирования, на мой взгляд, более информативен.

Сначала определите генератор, который генерирует все числа Фибоначчи:

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

Чтобы использовать этот генератор, мы можем импортировать несколько полезных функций из itertools. Чтобы напечатать первые несколько чисел, используйте islice:

from itertools import ifilter, islice, takewhile

for x in islice(fib(), 5):
    print x

1
1
2
3
5

Чтобы найти только четные числа, мы можем использовать ifilter для создания нового генератор:

def is_even(x):
    return x % 2 == 0

evenfibs = ifilter(is_even, fib())

for x in islice(evenfibs, 5):
    print x

2
8
34
144
610

Чтобы получить числа из генератора, пока число не превысит четыре миллиона, используйте takewhile :

for x in takewhile(lambda x: x < 4000000, evenfibs):
    print x

Для решения задачи можно использовать сумму:

sum(list(takewhile(lambda x: x < 4000000, evenfibs)))

Надеюсь, это показывает, что подход функционального программирования не сложен и является более элегантным способом решения определенных типов задач.

Вы уверены, что i хотите быть меньше 4 миллионов?

Возможно, вам будет интересно узнать об он-лайн энциклопедии целочисленных последовательностей!

Вы можете искать информацию по имени или по последовательности.

Если вы ищете 0,2,8,34 или «Четное число Фибоначчи», вы будете перенаправлены на последовательность A014445

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

def evenfib():
    """ Generates the even fibonacci numbers """
    a, b = 2, 0
    while True:
        a, b = b, a+4*b
        yield a  

В настоящее время вы суммируете все первые 2 миллиона четных чисел Фибоначчи.

Но это не задача. Вы должны просуммировать все четные числа Фибоначчи, которые меньше 4 миллионов.

ПРИМЕЧАНИЕ. Это было сильно изменено для решения фактического вопроса.

Вот альтернативный (и очень быстрый, но непроверенный метод). Он зависит от нескольких свойств:

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

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

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

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

n = (n/3)*3

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

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

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

sum_even = 4613732

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

Я не совсем понимаю ваш алгоритм, но кажется, что у smerriman есть смысл, 4000000 порядковых номеров Фибоначчи наверняка вырастут выше 4M. Я предполагаю, что более быстрым подходом будет создание последовательности до 4M, а затем добавление четных.

Есть и другие приемы, которые делают это более эффективным, чем простое вычисление полного списка чисел Фибоначчи и последующее суммирование четных чисел в списке.

Если бы я пытался решить эту проблему, я бы составил список четных чисел Фибоначчи. Есть ли какие-нибудь интересные особенности этого списка? Можете ли вы убедить себя, что эта закономерность в целом верна?

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

Конечно, все это отнимет у вас больше времени, чем просто кодирование решения методом грубой силы, но цель проекта Euler — найти красивое решение, а не решение методом грубой силы. В конце концов, если вы узнали что-то о математике, о вычислениях, вы выиграли.

Да ладно, оптимальный способ вычислить последовательность Фибоначчи — использовать 2 приема:

ОТРЕДАКТИРОВАНО, извините за предыдущую ошибку

1:

N =|2 0 0|
   |1 0 0|
   |0 0 0|

M =|3 2 1|
   |2 1 0|
   |0 0 1|

Матрица N*M^(n/3) имеет сумму первых n чисел Фибоначчи (отфильтровано только до четных) является верхним правым элементом.

2:

Вы можете использовать http://en.wikipedia.org/wiki/Exponentiation_by_squaring, поскольку умножение матриц кольцо.

Таким образом, вы можете решить нашу задачу за O(log n)