756 читали · 1 год назад
Алгоритм черепахи и зайца
Очень часто в практических задачах возникает необходимость искать цикл в некоторых последовательностях значений. Одним из таких подходов, решающих эту задачу, является алгоритм черепахи и зайца. Так, можно найти ему применение в криптографии для поиска коллизий в хэш-функциях, в определении насколько «случайны» генераторы случайных значений и даже в факторизации чисел. Однако прежде, чем перейти к описанию алгоритма, формализуем задачу, которую он решает. Условия задачи Пусть у нас есть некоторая функция f, которая сопоставляет некоторому элементу из множества S элемент из этого же множества...