4

Нужно посчитать сумму четных чисел Фибоначчи, которые не превышают 4 миллиона. Увидел закономерность, что начиная с числа 2(первого парного числа Фибоначчи) парным является каждое 3 число. 2 3 5 8 13 21 34 и т.д. Сделал такое решение, но интересно, есть ли еще более быстрое и красивое решение?

import math
def fib(number): 
    fn=0
    phi = (1 + math.sqrt(5)) / 2
    fn = (1 / math.sqrt(5)) * (phi**number - (math.cos(math.pi * number)) / phi**number)
    print(math.trunc(fn)),
    return math.trunc(fn)

currentFib = 0
i=1
sum=0

while currentFib<4*10**6:
    currentFib = fib(i*3)
    i+=1
    sum+=currentFib
print("\n" + str(sum))

5
  • phi и часть fn можно рассчитать заранее
    – vp_arth
    20 окт 2020 в 23:32
  • 1
    у тебя кстати ошибка... проверка на выход из цикла должна быть после вычисления очередного числа...
    – Fat-Zer
    21 окт 2020 в 0:48
  • @Fat-Zer, действительно, спасибо. У себя починил)
    – vp_arth
    21 окт 2020 в 1:47
  • Здесь ещё больше формул. 21 окт 2020 в 2:44
  • Поскольку вам нужен перебор чисел, а не одно конкретное число - думаю, что суммирование будет не хуже плавающей точки и возведений в степень... Но лучше вообще без вычисления ряда - так как сумма F[3*i] от 1 до n равна (F[3*n + 2] - 1)/2.
    – Harry
    21 окт 2020 в 4:48

2 ответа 2

5

т.к. ответ задачи не зависит ни от каких входных параметров, то самым быстрым способом будет:

print(4613732)

В случае если обобщать задачу на «найти сумму чётных чисел Фибоначчи, которые не превышают N» то можно сделать как-то так:

from math import log, sqrt, trunc

def sum_phib_even(N):
  if (N<8): 
    return 2 
  phi = (1 + sqrt(5)) / 2

  n = trunc( log(N*sqrt(5), phi) )
  if (n%3 == 2 and fib(n+1) <= N):
    n = n+1
  n //= 3
  return (fib(n*3+2) - 1) / 2

Объяснения/обоснования

Для малых N результат может быть некорректен, поэтому сразу отметаем этот случай:

  if (N<8): return 2

Найти n для числа Fn ≤ N можно так:

n = trunc( log(N*sqrt(5), phi) )

Но если N само является числом Фибоначчи (в частности чётным), то эта проверка может вернуть n на единицу меньше, поэтому нужна дополнительная проверка:

  if (n%3 == 2 && fib(n+1) <= N):
    n = n+1

Чётные числа Фибоначчи имеют вид F3n, поэтому:

n //= 3;

Далее, из того что

  • Σ(Fn) = Fn+2 - 1

не сложно вывести, что

  • Σ(F3n) = (F3n+2 - 1) / 2

, т.е. итоговая сумма вычисляется как:

(fib(n*3+2)-1)/2;

Замечания

  • т.к. всё это использует арифметику с плавающей точкой, то всё это будет работать пока хватает точности мантисы т.е. примерно для чисел до 2^50.
  • Большое количество арифметики с плавающей точкой при вычислении определённого числа Фибоначчи по обобщённой версии формулы Бине — тоже довольно тяжёлая штука, так что на практике его имеет смысл заменить чем-то динамическим.
0

Если понаблюдать за последовательностью, можно попробовать изобразить нечто такое:

def solve(N):
    sum_ = 0
    even, next_ = 0, 1

    while even <= N:
        sum_ += even
        next_, even = (
            3 * next_ + 2 * even,
            2 * next_ + even,
        )

    return sum_

Или даже так:

def solve2(N):
    sum_ = 0 
    a, b = 0, 2

    while b <= N:
        sum_ += b
        a, b = b, a+4*b

    return sum_
assert solve(4e6) == 4613732
assert solve2(4e6) == 4613732

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.