Как оптимизировать алгоритм подсчёта суммы чётных чисел Фибоначчи?

Question

[Александр Дорофеев]

Есть задание:

Каждый новый элемент последовательности Фибоначчи получается сложением предыдущих двух. Начиная с 1 и 2, получаем первые 10 элементов: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Найдите сумму всех четных элементов последовательности Фибоначчи, порядковый номер которых меньше A и верните из функции сумму всех ее цифр.

Пример: A = 10
Ряд Фибоначчи: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Четные элементы: 2, 8, 34
Их сумма: 44, а сумма всех ее чисел - 8.

Вот мой код.Использую алгоритм с мемоизацией:

# function that find sum of digits at number
def sum_of_digits(n):
    r = 0
    while n:
        r, n = r + n % 10, n // 10
    return r


# function that find sum of even numbers in fibonacci sequence
def solution(A):
    total_sum = 0
    a = 1
    b = 1
    for i in range(0, A):
        if a % 2 == 0:
            total_sum += a
        temporary = a
        a = b
        b += temporary
    return sum_of_digits(total_sum)

Код успешно проходит все тесты, однако выходит за рамки рекомендуемого времени
выполнения.В связи с этим вопрос: как оптимизировать данный алгоритм или подобрать более
оптимальный?
Задание взято отсюда.

P.s На Python пишу впервые в жизни, так что простите , если нарушил Code Conventions:)

Comments

[Lynn «Кофеман»]

Не виду мемоизации

[Lynn «Кофеман»]

Там реально требуется тридцать тысяч чисел?

[Александр Дорофеев]

Да

Answer 1

[uvelichitel]

Слегка можно оптимизировать

def solution(A):
    total_sum = 0
    a = 1
    b = 1
    for i in range(0, A - A % 3):           
        temporary = a
        a = b
        b += temporary
    total_sum = b // 2
    return sum_of_digits(total_sum)

Comments

[Александр Дорофеев]

Спасибо!

[alaz1987]

uvelichitel A - A % 3 - это какая-то рекуррентная формула подсчета четных чисел Фиббоначи?

Answer 2

[To4a89]

Тоже вот наткнулся на это задание решил, но оказался не быстрее чем у uvelichitel, потом оптимизировал Ваш код, убрав модуль с медленным while.
Получилось вот так

def solution(A):
    total_sum = 0 
    a = 1
    b = 1
    for i in range(0, A - A % 3):           
        temporary = a
        a = b
        b += temporary
    total_sum = b // 2
    return sum([int(i) for i in str(total_sum)]) # Считает сумму цифр в числе total_sum

Answer 3

[Oxoron]

Навскидку, числа Фибоначчи идут в периоде (нечет-нечет-чет).
При этом четный член равен сумме предыдущих нечетных.
3+5 = 8
13 + 21 = 34
55 + 89 = 144

То есть, четное число - это полусумма своей тройки.
Так что берем искомую последовательность, добавляем при необходимости один-два члена (чтоб получить полную тройку). Сумма первых 2k+1 чисел равна 2*F_{2k+1}. Сумма первых 2k чисел равна F_{2k+2}.

Так что ищем сумму, отнимаем 1 и 2, отнимаем добавленные слагаемые, делим на два, получаем ответ.

Формулу быстрого поиска энного числа Фибоначчи ищем на википедии.
В результате при любых больших n поиск будет занимать почти одинаковое время.

Answer 4

[alaz1987]

Еще одно решение, помедленнее, чем у uvelichitel, но рабочее и в лимит 4 сек. укладывается. Как показала практика, самая медленная операция в этом алгоритме - это остаток от деления на больших числах. Побитовые сдвиги помогли ускорить алгоритм в 2 раза.

def solution(A):
	r = s = 0
	x = y = 1
	i = 2

	while i < A:
		y = x + y
		x = y - x

		n = y >> 1
		n = n << 1

		if n == y: # is even?
			s += y

		i += 1

	r = sum(map(int, str(s)))
	return r