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