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

Есть задача "Требуется найти последнюю цифру n-го числа Фибоначчи." по адресу http://acmp.ru/?main=task& >

Мое решение такое ( не знаю насколько этично выкладывать код решения в паблик )

Результат: Время выполнения 0,858 Память 772 Кб

Есть идеи по повышению производительности?

4 ответа 4

Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.

Что такое период Пизано понятно из таблицы для π(4):

То есть π(4) = 6, а именно: остатки от деления чисел Фибоначчи на 4 повторяются с периодом 6.

Как это применить для решения задачи подумайте сами.

Очевидные простые улучшения:

  1. Можно заменить взятие остатка на сравнение с 10 и вычитание 10 (т. к. результат гарантированно меньше 20). По идее, операция деления более тяжёлая.
  2. Можно подсчитать lookup-таблицу (a, b) -> c , она по идее небольшая. Но вряд ли двойной lookup будет существенно быстрее пары сложений/вычитаний.
  3. Алгоритмическое улучшение: поскольку следующий член последовательности зависит лишь от двух предыдущих, то последовательность обязательно зациклится. Причём поскольку всего пар цифр не более 100, длина цикла не более 100. Найдите заранее длину цикла (отдельной программой), теперь число n можно брать по модулю длины цикла.
  4. Комбинируя 2 и 3, можно подсчитать заранее ответы для n от 0 до 99, и согласно 3 этого достаточно. Итого решение за O(1).
Читайте также  Размер изображения на рабочий стол

В степень бинарным возведением, беря ее элементы по модулю 10, можно решать эту задачу за O(logN).

Даже можно не ограничиваться модулем 10.

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

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

Похожие

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2019 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2019.12.20.35703

Есть задача "Требуется найти последнюю цифру n-го числа Фибоначчи." по адресу http://acmp.ru/?main=task& >

Мое решение такое ( не знаю насколько этично выкладывать код решения в паблик )

Результат: Время выполнения 0,858 Память 772 Кб

Есть идеи по повышению производительности?

4 ответа 4

Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.

Читайте также  Приложение для ответа на звонок андроид

Что такое период Пизано понятно из таблицы для π(4):

То есть π(4) = 6, а именно: остатки от деления чисел Фибоначчи на 4 повторяются с периодом 6.

Как это применить для решения задачи подумайте сами.

Очевидные простые улучшения:

  1. Можно заменить взятие остатка на сравнение с 10 и вычитание 10 (т. к. результат гарантированно меньше 20). По идее, операция деления более тяжёлая.
  2. Можно подсчитать lookup-таблицу (a, b) -> c , она по идее небольшая. Но вряд ли двойной lookup будет существенно быстрее пары сложений/вычитаний.
  3. Алгоритмическое улучшение: поскольку следующий член последовательности зависит лишь от двух предыдущих, то последовательность обязательно зациклится. Причём поскольку всего пар цифр не более 100, длина цикла не более 100. Найдите заранее длину цикла (отдельной программой), теперь число n можно брать по модулю длины цикла.
  4. Комбинируя 2 и 3, можно подсчитать заранее ответы для n от 0 до 99, и согласно 3 этого достаточно. Итого решение за O(1).

В степень бинарным возведением, беря ее элементы по модулю 10, можно решать эту задачу за O(logN).

Даже можно не ограничиваться модулем 10.

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

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

Похожие

Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.

дизайн сайта / логотип © 2019 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2019.12.20.35703

Задача на программирование. Дано число n (1≤n≤107), необходимо найти последнюю цифру n-го числа Фибоначчи.

Как мы помним, числа Фибоначчи растут очень быстро, поэтому при их вычислении нужно быть аккуратным с переполнением. В данной задаче, впрочем, этой проблемы можно избежать, поскольку нас интересует только последняя цифра числа Фибоначчи: если 0≤a,b≤9 —последние цифры чисел Fi и Fi+1 соответственно, то (a+b)mod10 — последняя цифра числа Fi+2.

Читайте также  Проверить айфон по серийному номеру на официальном

Далее код моего решения:

Но этот код не принимают и выдают ошибку:

Я так понял, я всё-таки переполнил память. Помогите, пожалуйста, как этого избежать?

Ссылка на основную публикацию
Adblock
detector