Очень часто в практических задачах возникает необходимость искать цикл в некоторых последовательностях значений. Одним из таких подходов, решающих эту задачу, является алгоритм черепахи и зайца. Так, можно найти ему применение в криптографии для поиска коллизий в хэш-функциях, в определении насколько «случайны» генераторы случайных значений и даже в факторизации чисел. Однако прежде, чем перейти к описанию алгоритма, формализуем задачу, которую он решает.
Условия задачи
Пусть у нас есть некоторая функция f, которая сопоставляет некоторому элементу из множества S элемент из этого же множества. Каждое применение этой функции к элементу будем называть итерацией. Таким образом, если выписать ряд, построенный на применении f к некоторому x_0 из множества S, мы получим следующую запись:
Это можно изобразить на конкретных значениях более наглядно в виде функционального графа:
Таким образом, задачей является нахождение такого индекса i, с которого начинается зацикливание последовательности, и соответственно длины этого цикла.
Решение
Идейно алгоритм черепахи и зайца основывается на том факте, что если x_i находится в цикле, то значения x_i и x_2i равны. Следовательно, логично было бы завести два указателя. Первый будем двигать на одну позицию (черепаха), а второй на две позиции (заяц).
Впоследствии, когда значения этих двух указателей начнут совпадать - просто один из указателей перевести в начало и двигать их с одинаковой скоростью - на одну позицию, пока значения двух указателей снова не совпадут. Так мы найдем с какой итерации будет начинаться цикл.
Теперь, когда известен элемент, с которого начинается цикл, не составит труда найти длину цикла, применяя «влоб» f к этому элементу, пока мы не получим его снова.
Собственно, ответом будет mu - номер итерации, с которой начинается цикл и lam - длина цикла. При этом мы сделали это за O(lam + mu).
Итоги
Таким образом, был рассмотрен достаточно интересный и фундаментальный алгоритм, который во многом актуален и по сегодняшний день. В дальнейшем мы разберем, как этот результат используется для эффективной факторизации целых чисел за O(n^(1/4)).
Читайте также
- Отзыв на книгу М. Лонэ «Большой роман о математике»
- Тезисы о математических началах человека
- Оценка вероятности делимости чисел