xmoonlight
@xmoonlight
https://sitecoder.blogspot.com

Как быстро найти зависимость элементов в последовательном ряду?

Примеры.
Дан ряд: 1,2,3,4,5
-------
Начальный элемент (значение): 1
Явно видно, что каждый следующий элемент больше предыдущего на 1-цу.

Сложнее: 1,4,2,5,3,6,4
------
Начальный элемент (значение): 1
Следующий чётный больше на 3, чем предыдущий; нечётный - меньше на 2, чем предыдущий.

Вот как именно (алгоритм) можно выявлять имеющуюся зависимость (при её наличии) элементов одного произвольного ряда?
  • Вопрос задан
  • 191 просмотр
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Если зависимость может быть любая (например, числа фиббоначи) - то никак. Можно поискать последовательность на oeis.org

Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

Сначала от массива чисел перейдите к массиву приращений.

Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы