5.1. Задачи о числах Фибоначчи

Числа Фибоначчи

Прежде чем начать, коротко напомним, что числа Фибоначчи — числовой ряд, при котором каждое последующее число равно сумме двух предыдущих.

Такие числа определяются рекурсивно:

Это приводит к следующему рекурсивному алгоритму:

Fibonacci(n):
     if n <= 1:
        return n
     else:
        return Fibonacci(n−2)+Fibonacci(n−1)

Рассмотрим совсем простую задачу.

• Входные данные: Целое число .
• Выходные данные: .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
3	2

Пример 2

Ввод	Вывод
10	55

Решение 1: Рекурсивный алгоритм

Ниже мы описываем простую реализацию рекурсивного псевдокода для Python. В неё входит инструкция по обнаружению багов, которая выводит то, что вычисляется в данный момент. Мы пробуем вычислить с помощью этого кода.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        print(f'Computing F{n} recursively...')
        return fibonacci(n - 2) + fibonacci(n - 1)


print(fibonacci(7))

Computing F7 recursively...
Computing F5 recursively...
Computing F3 recursively...
Computing F2 recursively...
Computing F4 recursively...
Computing F2 recursively...
Computing F3 recursively...
Computing F2 recursively...
Computing F6 recursively...
Computing F4 recursively...
Computing F2 recursively...
Computing F3 recursively...
Computing F2 recursively...
Computing F5 recursively...
Computing F3 recursively...
Computing F2 recursively...
Computing F4 recursively...
Computing F2 recursively...
Computing F3 recursively...
Computing F2 recursively...
13

Как видите, код даёт нам верный результат (), но многие вычисления повторяются. Если вы решите вычислить с помощью этого кода, то Солнце потухнет раньше, чем компьютер выдаст вам результат.

💡 Остановитесь и подумайте:
Как вычислить вручную?

Решение 2: Итерационный алгоритм

Скорее всего вы бы взяли лист бумаги и написали что-то вроде:

Вполне разумно попросить компьютер вычислить таким же итерационным способом:

Fibonacci(n):
    if n <= 1:
        return n
    allocate an array F[0..n]
    F[0] = 0
    F[1] = 1
    for i from 2 to n:
        F[i] = F[i − 2] + F[i − 1]
    return F[n]

Приблизительное количество операций, необходимых алгоритму, — . Этот алгоритм хорошо работает на практике.

💡 Остановитесь и подумайте:
Можно ли обойтись без хранения всего массива?

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

Fibonacci(n):
    if n <= 1:
        return n
    previous = 0
    current = 1
    for iter in range(n-1):
        oldPrevious = previous
        previous = current
        current = oldPevious + previous
    return current

Решение 3: Запоминание

Рекурсивный алгоритм требует так много времени, потому что он повторяет множество одинаковых вычислений: например Fibonacci(7) вызывает Fibonacci(3) пять раз. Не проще ли сохранить , как только это значение вычислено, и при необходимости использовать сохранённое значение вместо того, чтобы вычислять его с нуля? Такой простой подход называется мемоизация: при вычислении чего-либо сохраните это в структуре данных, чтобы избежать повторных вычислений в будущем.

Давайте добавим мемоизацию в рекурсивный алгоритм, чтобы сделать его практичнее.

table — некоторый ассоциативный контейнер (в table[i]  будем сохранять F[i])

Fibonacci(n):
    if table[n] ещё не вычисляли:
        if n <= 1:
            table[n] = n
        else:
            table[n] = Fibonacci(n−2)+Fibonacci(n−1)
    return table[n]

По сравнению с изначальным рекурсивным алгоритмом этот сделает максимум «серьёзных» рекурсивных вызовов: для каждого первый вызов Fibonacci(i) вычисляет , сохраняя в ; затем все дальнейшие вызовы Fibonacci(i) становятся просто поиском по таблице.

Последняя цифра числа Фибоначчи

• Формат ввода: Целое число .
• Формат вывода: Последняя цифра .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
3	2

Пример 2

Ввод	Вывод
139	1

Пример 3

Ввод	Вывод
91239	6

Предупреждение: будьте аккуратны с целочисленным переполнением. Значение превосходит диапазон стандартных целочисленных типов, а количество цифр в более , но последняя точно 6.

Решение: Взять каждое промежуточное звено по модулю 10

Для решения этой задачи мы вычислим и просто выведем последнюю цифру последовательности:

FibonacciLastDigit(n):
    if n <= 1:
        return n
    F[0..n] — массив для промежуточных значений
    F[0] = 0
    F[1] = 1
    for i from 2 to n:
        F[i] = F[i − 1] + F[i − 2]
    return F[n] mod 10

Обратите внимание, что числа Фибоначчи растут очень быстро. Например,

Таким образом, если вы используете типы C++ int32 или int64 для хранения , вы быстро придёте к целочисленному переполнению. Если вы используете числа произвольной точности, например, BigInteger в Java или встроенные целые числа в Python, то вы заметите, что цикл проходит намного медленнее при повышающемся числе итераций.

💡 Остановитесь и подумайте:
Последняя цифра в — и последняя цифра в — . Какова последняя цифра в ?

Несложно увидеть, что последняя цифра в равна , и она полностью определена последними цифрами в и . Это подсказывает нам, как сделать алгоритм практичнее: вместо вычисления и использования последней цифры можно взять каждое промежуточное звено по модулю 10.

Главный посыл этой задачи: когда вам нужно вычислить результат последовательности арифметических операций по модулю , берите результат каждой операции по модулю . Так можно гарантировать, что числа, с которыми вы работаете, будут маленькими (они уместятся в стандартный тип языка программирования, который вы предпочитаете) и что арифметические операции с ними будут выполняться быстро.

FibonacciLastDigit(n):
    if n <= 1:
        return n
    F[0..n] — массив для промежуточных значений
    F[0] = 0
    F[1] = 1
    for i from 2 to n:
        F[i] = (F[i − 1] + F[i − 2]) mod 10
    return F[n]

Огромное число Фибоначчи

• Формат ввода: Целые числа и .
• Формат вывода: .
• Ограничения: , .
• Примеры

Пример 1

Ввод	Вывод
1 239	1

Пример 2

Ввод	Вывод
115 1000	885

Пример 3

Ввод	Вывод
2816213588 239	151

Предупреждение:

• .
• .
• содержит миллионы цифр, но .

Решение 1: Период Пизано

В этой задаче может быть настолько большим, что алгоритму потребуется слишком много времени, чтобы пройти через все числа Фибоначчи для от до . Чтобы понять, как решить эту задачу, не проходя через все числа , взгляните на таблицу ниже:

💡 Остановитесь и подумайте:
Вы могли заметить в таблице необычные свойства в последних двух рядах.

Обе эти последовательности — периодические! Период для — . Его длина — . Для период будет , и его длина — .

В итоге, чтобы вычислить, например, , нам понадобится найти остальную часть при делении на . Так как , мы можем заключить, что .

Оказывается, что для любого целого числа последовательность будет периодической. Период всегда начинается с . Он называется период Пизано (Фибоначчи также называют Пизано).

✒️ Упражнение:
Каким будет период ?

✒️ Упражнение:
Докажите, что для каждого числа последовательность будет периодической.

✒️ Упражнение:
Докажите, что период последовательности не превышает
.

Таблица ниже демонстрирует, что последовательность — периодическая. Последние цифры повторяются по периоду Пизано длиной . Другими словами:

Например:

Чтобы доказать, что последние цифры чисел Фибоначчи периодические, обратите внимание на пары остатков по модулю , следующих друг за другом чисел Фибоначчи:

Каждую из колонок таблицы можно вычислить на основе предыдущей колонки

как
.
По такой же логике колонка перед колонкой

будет
.
Следовательно, для любой колонки в таблице выше можно однозначно определить соседей слева и справа. А значит, из любой позиции можно заполнить всю таблицу.

Поскольку остатков по модулю только , есть только возможных пар остатков, то есть максимум возможных колонок. Таким образом, некоторые колонки в таблице повторяются и будут это делать до бесконечности.

✒️ Упражнение:
Докажите, что первая повторяющаяся колонка таблицы для будет

💡 Остановитесь и подумайте:
Почему период Пизано для будет , а не — число всевозможных пар остатков по модулю ?

Это наводит нас на следующий простой псевдокод, который рассчитывает период Пизано для произвольного остатка по модулю .

PisanoPeriod(m):
    current = 0
    next = 1
    period = 0
    while True:
        oldNext = next
        next = (current + next) mod m
        current = oldNext
        period = period + 1
        if current = 0 and next = 1:
            return period

Объединяя изложенные идеи, получаем приемлемое по скорости работы решение.

Решение 2: Быстрое возведение матрицы в степень

Ещё один способ вычислить — обратить внимание на то, что уравнения

могут быть представлены как умножение матрицы —

— и вектора
:

Следовательно:

Поэтому — просто элемент справа вверху -й степени матрицы
.

💡 Остановитесь и подумайте:
Примитивный способ вычислить потребует умножений матриц. Получится ли у вас сделать это, ограничившись умножениями матрицы?

Мы продемонстрируем быстрое возведение в степень с помощью целых чисел вместо матриц. Имея целое число , можно было бы примитивно вычислить , используя умножение 8 раз. Однако есть и более быстрый способ вычислить , используя умножение лишь 4 раза:

В целом, при чётном вычисление потребует выполнить умножение лишь еще один раз по сравнению с , так как . Если — нечетное, то вычисление потребует выполнить умножение лишь ещё два раза — по сравнению с , так как .

FastIntegerExponentiation(x, n):
    if n = 0:
        return 1
    if n % 2 == 0: # чётное значение
        y = FastIntegerExponentiation(x, n/2)
        return y * y 
    else: # нечётное значение
        y = FastIntegerExponentiation(x, (n−1)/2)
        return y * y * x 

Поскольку каждый рекурсивный вызов FastIntegerExponentiation приводит к двум операциям умножения целых чисел и разделяет пополам, он выполнит максимум операций умножения.

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

FastMatrixExponentiation(D, n, m):
    if n = 0:
        return [[1, 0], [0, 1]] # единичная 2×2 матрица
     if n % 2 == 0: # чётное значение
        Y = FastMatrixExponentiation(D, n/2, m)
        return Multiply2x2Matrices(Y, Y, m)
     else:
        Y = FastMatrixExponentiation(D, (n−1)/2, m)
        Y2 = Multiply2x2Matrices(Y, Y, m)
        return Multiply2x2Matrices(Y2, D, m)

Multiply2x2Matrices(A, B, m):
	  C[1][1] = (A[1][1]*B[1][1] + A[1][2]*B[2][1]) mod m
	  C[1][2] = (A[1][1]*B[1][2] + A[1][2]*B[2][2]) mod m
	  C[2][1] = (A[2][1]*B[1][1] + A[2][2]*B[2][1]) mod m
	  C[2][2] = (A[2][1]*B[1][2] + A[2][2]*B[2][2]) mod m
	  return C

Наконец, вычисление нужного значения выглядит следующим образом:

FibonacciModuloM(n, m):
	M = [[0, 1], [1, 1]]
	P = FastMatrixExponentiation(M, n, m)
	return P[0][1]

Последняя цифра суммы чисел Фибоначчи

• Формат ввода: Целое число .
• Формат вывода: .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
3	4

Пример 2

Ввод	Вывод
100	5

Подсказка. Раз исчерпывающий поиск будет слишком медленным для этой задачи, попробуйте придумать формулу для . Для лучшего понимания поиграйте с маленькими значениями . Затем используйте решение для предыдущей задачи.

Решение

В таблице ниже указаны первые одиннадцать чисел Фибоначчи и первые одиннадцать чисел .

💡 Остановитесь и подумайте:
Можете заметить сходства между последовательностями и ?

Похоже, что . Давайте докажем это по индукции. Это условие определённо выполняется для первого шага (), так как . Для шага с индукцией предположим, что утверждение верно для , и докажем его для :

Ещё один способ прийти к формуле — сложить равенства.

Так как элементы в правых частях взаимоуничтожаются, то сумма всех элементов справа — , а сумма всех элементов слева будет ,

Так задача сводится к тому, чтобы найти последнюю цифру в . Благодаря предыдущей задаче мы знаем, как можно быстро это сделать: исходя из того, что период Пизано по модулю равен , мы имеем

Последняя цифра частичной суммы чисел Фибоначчи

• Формат ввода: Целые числа и .
• Формат вывода: .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
3 7	1

Пример 2

Ввод	Вывод
10 10	5

Решение

Сумма частичной суммы чисел Фибоначчи равна разнице между двумя частичными суммами:

Более обобщённо,

Благодаря предыдущей задаче мы знаем, как быстро вычислять префиксные, то есть первые элементы последовательности, суммы.

Последняя цифра суммы квадратов чисел Фибоначчи

• Формат ввода: Целое число .
• Формат вывода: .
• Ограничения: .
• Примеры

Пример 1

Ввод	Вывод
7	3

Пример 2

Ввод	Вывод
73	1

Пример 3

Ввод	Вывод
1234567890	0

• .
• .

Подсказка. Раз алгоритм исчерпывающего поиска будет слишком медленным для этой задачи ( может доходить до ), нам нужно найти простую формулу для . Рисунок выше представляет сумму как площадь прямоугольника с вертикальным ребром и горизонтальным ребром .

Решение

Рисунок выше подсказывает, что для каждого неотрицательного целого числа

Мы докажем это по индукции. Для двух первых случаев и получается:

Для шага с индукцией предположим, что . Так,

В итоге остаётся вычислить последние цифры и .