2

Положим, что у меня имеются значения двух первых членов последовательности и формула, рекуррентно задающая все последующие члены. Количество членов не превышает 10^1000000. Как найти последнюю цифру некоторого n-го члена?

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

3
  • 2
    В общем случае — соорудите «длинное число» из нескольких обычных (подобно тому, как нормальное число составляется из цифр/битов), определите нужные арифметические операции. Или воспользуйтесь языком, в котором длинные числа встроены (например, C#, Java). Или воспользуйтесь подходящей библиотекой (например, gmp/C/C++). Смиритесь с тем, что наивное вычисление займёт десятилетия. В случае, если ваша рекуррентная последовательность поддаётся математической атаке (например, это линейная рекуррентная последовательность), проведите анализ и найдите решение не в лоб.
    – VladD
    29 янв 2014 в 12:00
  • 2
    @VladD 10^1000000 -- десятилетия? Вы оптимист, однако.
    – alexlz
    29 янв 2014 в 15:59
  • В Java есть тип BigInteger который может хранить целое неограниченной длины. А касательно рекурсии - любую рекурсию можно свести к циклу.
    – Barmaley
    30 янв 2014 в 6:28

5 ответов 5

6

В подобных случаях применяют такой подход.

Вначале доказывают, что последняя цифра числа не зависит от предыдущих - например в случае чисел Фибоначчи или если это последовательность квадратов чисел. Потом строят последовательность для первых 10-100 элементов и ищут закономерность. Например, в случае с квадратами 0, 1, 4, 9, 6, 5, 6, 9, 4, 1

Теперь, написать код уже не сложно f(n) = (0, 1, 4, 9, 6, 5, 6, 9, 4, 1)[n % 10];

В случае чисел Фибоначчи этот период составляет 60 цифр

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
3
  • Вывел 100 чисел своей последовательности, но закономерности нет. Может он для формулы f(k)=f(k-2)+3f(k-3) быть больше, чем 100?
    – MathMike
    29 янв 2014 в 13:00
  • какая то странная формула. если даже первые два элемента заданы (номер один и номер два), то вычислить третий невозможно - для этого нужен нулевой. Уточните пожалуйста формулу и приведите хотя бы 5-10 первых элементов.
    – KoVadim
    29 янв 2014 в 13:14
  • пересчитал, независимо от первых трех элементов, длина последовательности - 868. Потом она повторяется.
    – KoVadim
    29 янв 2014 в 13:46
6

Для вашей формулы (f(k)=f(k-2)+3f(k-3)) всё намного проще.

Для начала, вычисления можно делать сразу по модулю 10:

f(k) mod 10 сравнимо с f(k-2) mod 10 + 3 (f(k-3) mod 10) по модулю 10

а значит,

f(k) % 10 = (f(k-2) % 10 + 3 (f(k-3) % 10)) % 10

Перейдём к последовательности g(k) := f(k) % 10. Имеем:

g(k) = (g(k-2) + 3 * g(k-3)) % 10

Очевидно, что все члены последовательности, начиная с g(k), зависят лишь от g(k-1), g(k-2) и g(k-3). Поскольку каждая величина g(k-1), g(k-2), g(k-3) может принимать лишь 10 различных значений, за 1000 итераций тройка значений g(k-1), g(k-2), g(k-3) повторится, а значит, последовательность зациклится.

Делайте так:

  1. Определите длину цикла. Для этого прогоните 1000 итераций и найдите первый случай когда тройка (g(k-1), g(k-2), g(k-3)) впервые повторится. (Это обязательно произойдёт по принципу Дирихле.)
  2. Пусть найденная длина цикла k. Очевидно, что g(N) == g(N % k). Поскольку k < 1000, а значения g(x) для аргумента меньше 1000 подсчитаны на предыдущем шаге, результат можно посмотреть в таблице.

Вот и всё. Дерзайте!


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

9
  • я правильно понимаю, что Вы считаете, что для данной последовательности длина цикла меньше 100?
    – KoVadim
    29 янв 2014 в 13:41
  • @KoVadim: меньше или равна. --- Поскольку (0, 0) очевидно не может участвовать в последовательности, то да, строго меньше. --- Хм, хотя вы правы, на самом деле последовательность зависит от трёх членов. Сейчас поправлю.
    – VladD
    29 янв 2014 в 13:43
  • дело в том, что я нашел длину последовательности и она больше - 868.
    – KoVadim
    29 янв 2014 в 13:46
  • @KoVadim: да, уже понял, обновил ответ. Спасибо!
    – VladD
    29 янв 2014 в 13:46
  • @VladD А можно подробнее про переход к mod 10. Это возможно потому что у нас только сложение и умножение? Или по какой то другой причине?
    – IronVbif
    29 янв 2014 в 14:15
1

написал в виде ответа т.к. в каментарий банально не влезет, по сути является вариантом ответа предоставленого: @VladD с той лишь разницей что не прибегает сразу к испльзованию модулей

если позначить 3 первых члена последовательности как x1,x2,x3 получается что каждый элемент последовательности можно описать функцией:

f(j) = a*x1 + b*x2 + c*x3 (1)

где a,b,c определяют количество вхождений элементов: x1,x2,x3

учитывая что нас интересует только последняя позиция в числе можно записать формулу так:

f(x) = a*x1 + b*x2 + c*x3 = a*x1 % 10 + b*x2 % 10 + c*x3 % 10 (2)

где, для каждого из чисел a,b,c справедлива начальная формула: f(k)=f(k-2)+3f(k-3), арифметика по модулю 10 применяется для того чтоб держать множители a,b,c в пределах 10, так как: 10*x % 10 = x

пишем функцию которая в цикле считает числа a,b,c для каждого элемента последовательности, до тех пор пока не найдем период: T (3)

после того как найден период можно получить индекс элемента:

K = (10^10000) % mod T = ...

соответственно запускаем функцию (3) еще раз, для числа T: получаем конкретные значения чисел a,b,c. далее используем формулу (1) и получаем результат

p.s. програмка пишется примерно за 30-60 минут

0

К сожалению, не могу прикреплять картинки, поэтому разместил свой ответ здесь

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

-1

"Длинная арифметика" помогла бы. Хотя проблема будет, мне кажется, не в переменной счетчике, а в глубине рекурсии.

Ваш ответ

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

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