Escapist Marginalia

User Preferences

Interface language

Theme

Проект Эйлера #2

Чётные числа Фибоначчи.

  • project euler
  • math
Published at Last updated at

Каждый новый член последовательности Фибоначчи получается из суммы двух предыдущих. Начиная с 1 и 2, первые 10 членов последовательности будут:

1,2,3,5,8,13,21,34,55,89,...1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Найти сумму всех чётных членов последовательности, значения которых не превышают четыре миллиона.

Brute-force решение#

Для начала отбросим тонкости и попробуем решить задачу максимально просто. Так как нам нужно сумму членов последовательности, удовлетворяющих некоторому условию, то необходимо сгенерировать саму последовательность.

Пример реализации на Python#

В реализации решения с помощью Python, воспользуемся генератором. Для этого определим функцию-генератор fibonacci_sequence, единственным параметром которой будет максимальное значение члена последовательности.

Далее, уже непосредственно для решения задачи определим функцию even_fib_sum, в которой с помощью list comprehension найдём сумму всех чётных значений генератора, не привышающих максимальное значение, переданное в единственный параметр функции.

def fibonacci_sequence(limit: int) -> int:
  a, b = 0, 1
  while a < limit:
    yield a
    a, b = b, a + b

def even_fib_sum(limit: int) -> int:
  return sum([ item for item in fibonacci_sequence(limit) if item % 2 == 0 ])

Чётная последовательность Фибоначчи#

Основная проблема предыдущего решения в том, что мы генерировали все значения последовательности, хотя для решения достаточно лишь чётных по значению. Попробуем взглянуть на чётные члены последовательности:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Не забывая, что счёт индексов начинется с нуля, заметим, что все чётные элементы повторяются с постоянным интервалом, каждое третье число Фибоначчи чётное. Выходит, что можно попробовать выразить закономерность для генерации лишь чётных числе Фибоначчи, используя реккурентную формулу. Для этого необходимо выразить F(n)F(n) через F(n−3)F(n - 3) и F(n−6)F(n - 6).

Используя определение последовательности Фибоначчи:

Fn=Fn−1+Fn−2F_{n} = F_{n-1} + F_{n-2}

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

Fn=Fn−1+Fn−2=Fn−2+Fn−3+Fn−2=2×Fn−2+Fn−3=2×(Fn−3+Fn−4)+Fn−3=2×Fn−3+2×Fn−4+Fn−3=3×Fn−3+2×Fn−4=3×Fn−3+Fn−4+Fn−4=3×Fn−3+Fn−4+Fn−5+Fn−6=3×Fn−3+(Fn−4+Fn−5)+Fn−6=3×Fn−3+Fn−3+Fn−6=4×Fn−3+Fn−6egin{aligned} F_{n} &= F_{n-1} + F_{n-2}\ &= F_{n-2} + F_{n-3} + F_{n-2}\ &= 2 imes F_{n-2} + F_{n-3}\ &= 2 imes (F_{n-3} + F_{n-4}) + F_{n-3}\ &= 2 imes F_{n-3} + 2 imes F_{n-4} + F_{n-3}\ &= 3 imes F_{n-3} + 2 imes F_{n-4}\ &= 3 imes F_{n-3} + F_{n-4} + F_{n-4}\ &= 3 imes F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6}\ &= 3 imes F_{n-3} + (F_{n-4} + F_{n-5}) + F_{n-6}\ &= 3 imes F_{n-3} + F_{n-3} + F_{n-6}\ &= 4 imes F_{n-3} + F_{n-6}\ end{aligned}

Итого, мы получили реккурентное выражение исключительно для чётных элементов последовательности Фибоначчи:

Fn=4×Fn−3+Fn−6F_{n} = 4 imes F_{n-3} + F_{n-6}

Больше нет необходимости в проверке чётности значений, код становится проще и быстрее.

Пример реализации на Python#

Аналогично предыдущему решению, используем генератор для получения последовательности Фибоначчи fibonacci_sequence_even. В этот раз он будет генерировать лишь чётные значения последовательности, поэтому впишем вместо 0 и 1: 2 и 8, как первые четные элементы и используем реккурентное соотношение, полученое в разборе выше.

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

def fibonacci_sequence_even(limit: int) -> int:
  a, b = 2, 8
  while a < limit:
    yield a
    a, b = b, 4 * b + a

def even_fib_sum(limit: int) -> int:
  return sum([ item for item in fibonacci_sequence_even(limit) ])

Ссылки#

  1. Project Euler, Problem 2: Even Fibonacci numbers
  2. Числа Фибоначчи