Проблема

Примечание. Эта задача была взята из серии еженедельных задач, предлагаемых Coursera Data Structures and Algorithms Specialization. Таким образом, и проблему, и решение гораздо легче понять в контексте проблем недели. Если вы хотите сначала понять их (что настоятельно рекомендуется), сначала перейдите туда.

Описание:даны два целых неотрицательных числа 𝑚 и 𝑛, где 𝑚 ≤ 𝑛, найдите последнюю цифру суммы Fₘ+Fₘ₊₁ + · · · + Fₙгде Fₙобозначает n-е число Фибоначчи.

Входные данные: два неотрицательных целых числа 𝑚 и 𝑛, разделенные пробелом.

Ограничения:0 ≤ 𝑚 ≤ 𝑛 ≤ 10¹⁴

Вывод:последняя цифра Fₘ+Fₘ₊₁ + · · · + Fₙ

Образец:

INPUT
3 7
OUTPUT
1

F₃ + F₄ + F₅ + F₆ + F₇ = 31

Решение

В нашем решении будет использоваться период Пизано: период, с которым повторяется последовательность чисел Фибоначчи, взятых по модулю m. Это означает, что последние цифры наших чисел Фибоначчи можно просто найти, найдя период Пизано с модулем m10.

В поисках периода Пизано

Во-первых, нам нужно будет найти длину периода Пизано, чтобы заполнить массив элементами периода. Здесь мы будем использовать тот факт, что период Пизано всегда начинается с 01. Мы также можем воспользоваться этим фактом:

F(n) mod m = (F(n-2) mod m + F(n-1) mod m) mod m

Таким образом, мы можем определить функцию get_period_length(m) для возврата длины периода по модулю m.

def get_period_length(m):
   # instantiate prev and curr to be the first two Fibonacci numbers
   prev, curr = 0, 1
   # keep finding new elements of the period until we find 01 again
   for i in range(2, m * m + 1):
      prev, curr = curr, (prev + curr) % m
      if prev == 0 and curr == 1:
         return i - 1
   # default return if for some reason we don't find 01
   return 0

Теперь мы можем определить функцию get_pisano_period(m) , где m — модуль, который мы будем брать. В нашем случае, поскольку мы ищем только последнюю цифру, мы будем использовать только m , равное 10. Однако теоретически вы можете получить период Пизано для любого модуля, который вам нужен.

def get_pisano_period(m):
   # get length of period
   length = get_period_length(m)
   # instantiate a list of length 'length' beginning with 0 & 1
   period = [0] * length
   period[0] = 0
   period[1] = 1
   # fill in the entirety of the period
   for i in range(2, length):
      period[i] = (period[i-1] + period[i-2]) % n
   
   return period

Нахождение частичной суммы

Теперь о сути проблемы. Мы можем начать с определения функции fibonacci_partial_sum(m, n), которая принимает первое и последнее числа Фибоначчи, которые будут частью нашей частичной суммы. Мы можем автоматически вернуть n, если n меньше 2, и мы уже знаем, что нам понадобится период Пизано, поэтому мы можем получить и его.

def fibonacci_partial_sum(m, n):
   # if n < 2, automatically return n
   if n < 2:
      return n
   # get the Pisano period of modulus m = 10
   period = get_pisano_period(10)
   length = len(period)

Эту часть было труднее всего решить, но я смог разбить шаги на следующие:

  1. Найдите индекс m в периоде Пизано, чтобы получить последнюю цифру m-го числа Фибоначчи. Установите его равным переменнойlast , которая будет нашим окончательным результатом.
  2. Впереди два случая:
  3. Если n не входит в набор элементов между m и концом периода, перейдите от m к концу периода и добавьте их значения к last, чтобы «сбросить» период Пизано. Таким образом, мы сможем обращаться к m как к «полной» сумме, а не как к «частичной».
  4. Обычно мы находим количество периодов между m и n и суммируем все элементы периода, чтобы нам не приходилось повторять от m до n, чтобы непрерывно складывать цифры периода Пизано. Мы могли бы просто умножить num_periods и last_digit_of_period_sum и прибавить к last . Затем мы просто сможем выполнить цикл в последний раз, пока не нажмем n. Однако есть тонкий трюк — сумма периода Пизано по модулю 10 равна 280, где его последняя цифра равна 0. Это означает, что мы можем все пропустить и перейти сразу к счету от первого до n_index периода Пизано. Таким образом, нашим шагом 3 было бы просто найти индекс n в пределах периода Пизано. Затем мы подсчитывали и добавляли элементы от первого индекса к n_index периода Пизано в переменную last.
  5. Во втором случае, если n находится в наборе элементов между m и концом периода, то мы можем просто считать от индекса m до индекса n и добавьте цифры к last .

Наш псевдокод будет выглядеть примерно так:

n_index = n % length
m_index = m % length
last = 0
m_to_end = length - m_index
if m + m_to_end < n:
   for i from m_index to end of period:
      last = (last + period[i]) % 10
   for i from 0 to n_index:
      last = (last + period[i]) % 10
else:
   for i from m_index to n_index:
      last = (last + period[i]) % 10
return last

Чтобы лучше проиллюстрировать значение переменных, мы рассмотрим пример.

Example 1: m=3, n=7
Pisano period of modulus 10: [0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1]
BOLD = m_index = the last digit of Fibonacci number m
ITALICIZED = m_to_end = set of numbers between m and end of period

Эквивалентный код Python показан ниже.

    n_index = n % length
    m_index = m % length
    last = 0
    m_to_end = length - m_index
    
    if m + m_to_end < n:
        for i in range(m_index, length):
            last = (last + period[i]) % 10
        for i in range(0, n_index + 1):
            last = (last + period[i]) % 10
    else:
        for i in range(m_index, n_index + 1):
            last = (last + period[i]) % 10
    return last

Вывод

Вот окончательная программа целиком: