4

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

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

#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    int a=1, b=1, c=a+b, n;
    cin >> n;
    if (n <= 1)
        c = 1;
    else
        for (int i = 2; i <= n; i++){
            c = (a + b) % 10;
            a = b;
            b = c;
        }
    cout << c % 10;
    return 0;
}

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

Согласно таблице на странице http://acmp.ru/index.asp?main=bstatus&id_t=623&lang=CPP за счет небольшого увеличения расхода памяти как то умудряются вложиться в 1-2 секунды. С одной стороны может быть мне подсунули входное число 1000, а другим 10.

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

4
  • Очевидные оптимизации самой задачи вроде уже применены. Скорее всего, сэкономить можно на IO.
    – user181100
    2 ноя 2015 в 19:19
  • 1
    Чем плохо использование формулы для n-го члена рекуррентного отношения, задающего числа Фибоначчи? На бумаге выводится минут за 7, и программируется легко. ideone.com/WTXmX5
    – typemoon
    2 ноя 2015 в 19:25
  • Перепиши на асме habrahabr.ru/post/252647 2 ноя 2015 в 19:26
  • @typemoon: Хм. Тысячный член последовательности требует всего тысячу итераций со сложением, так что это не много. А вот при возведении в тысячную степень можно вылезти за пределы double.
    – VladD
    2 ноя 2015 в 19:33

4 ответа 4

9

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

  1. Можно заменить взятие остатка на сравнение с 10 и вычитание 10 (т. к. результат гарантированно меньше 20). По идее, операция деления более тяжёлая.
  2. Можно подсчитать lookup-таблицу (a, b) -> c, она по идее небольшая. Но вряд ли двойной lookup будет существенно быстрее пары сложений/вычитаний.
  3. Алгоритмическое улучшение: поскольку следующий член последовательности зависит лишь от двух предыдущих, то последовательность обязательно зациклится. Причём поскольку всего пар цифр не более 100, длина цикла не более 100. Найдите заранее длину цикла (отдельной программой), теперь число n можно брать по модулю длины цикла.
  4. Комбинируя 2 и 3, можно подсчитать заранее ответы для n от 0 до 99, и согласно 3 этого достаточно. Итого решение за O(1).
4
  • 1
    По поводу п.п. 3,4 аплодирую 2 ноя 2015 в 19:45
  • @tutankhamun: Спасибо! (покраснел)
    – VladD
    2 ноя 2015 в 19:46
  • 1
    @VladD вот оно, настоящее программирование. По поводу п.3 остаётся добавить - длина цикла не более 100, можно уже не считать настоящую, достаточно мало. 2 ноя 2015 в 20:56
  • @LapshinDmitry: Угу, вы правы. В принципе 100 итераций, просто ждать, когда повторится (0, 1).
    – VladD
    2 ноя 2015 в 21:03
8

Цитата из википедии

Период чисел Фибоначчи по модулю натурального числа 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):

n          | 1  2  3  4  5  6 | 7  8  9 ...
F(n)       | 0  1  1  2  3  5 | 8 13 21 ...
F(n) mod 4 | 0  1  1  2  3  1 | 0  1  1 ...

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

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

1

Возводя матрицу

1 1
1 0

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

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

0

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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