@Primer

Проект Эйлера. Задача №2. Как решить правильно?

Не судите строго пожалуйста, я начинающий в этой в сфере.
Пытался написать сам код, но как то не очень получается. пытался искать в инете, но там команды, которые я не очень понимаю (и как то их пояснения я тоже не очень понял). Если вам не очень трудно, то я вас прошу объяснить детально этот код:5e60f962704af092407593.png

Задача звучит так:
Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих.
Начиная с 1 и 2, первые 10 элементов будут
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона.
  • Вопрос задан
  • 225 просмотров
Решения вопроса 1
trapwalker
@trapwalker
Программист, энтузиаст
ВНИМАНИЕ! Это неправильное решение!
Это сумма четных по счету элементов ряда фиббоначчи.
a = 1
b = 2
s = b
while b < 4*10**6:
    a = a + b
    b = a + b
    s += b

print(s)

А если четные (по значению) элементы складывать, то нужно так:
s, a, b = 0, 1, 2
while b < 4*10**6:
    if b % 2 == 0:
        s += b
    a, b = b, a + b   

print(s)

А ваше решение из вопроса неэффективно. Оно сначала строит список из всех элементов ряда, не превышающих заданного. Потом фильтрует их по четности, благо лениво и не требуется лишней памяти. Ну и суммирует фильтрат. Итого у этого алгоритма O(2*N) сложность по памяти и по столько же по операциям.
Предложенный выше алгоритм -- O(1) по памяти и O(N) по операциям.

И на старуху бывает проруха. Ага. невнимательность.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
FoxCloud
@FoxCloud
Хостинг и облачные сервисы
a, b = 1, 1
total = 0
while a <= 4000000:
if a % 2 == 0:
total += a
a, b = b, a+b # the real formula for Fibonacci sequence
print total
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы