Моя проблема заключается в следующем: у меня большая последовательность чисел. Я знаю, что после некоторого момента он становится периодическим, то есть в начале последовательности есть k чисел, а затем еще m чисел, которые повторяются для остальной части последовательности. В качестве примера, чтобы сделать это более понятным, последовательность может выглядеть следующим образом: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...], где k равно 5 и m равно 4, а повторяющийся блок равен [2, 1, 1, 3]. Как ясно из этого примера, у меня могут быть повторяющиеся биты внутри большего блока, так что это не помогает просто искать первые экземпляры повторения.

Однако я не знаю, что такое k или m - моя цель - взять последовательность [a_1, a_2, ..., a_n] в качестве входных данных и вывести последовательность [a_1, ..., a_k, [a_ (k) +1), ..., a_ (k + m)]] - в основном усекает более длинную последовательность, перечисляя большую ее часть как повторяющийся блок.

Есть ли эффективный способ решить эту проблему? Кроме того, вероятно, сложнее, но более идеально в вычислительном отношении - возможно ли это сделать, когда я генерирую соответствующую последовательность, так что мне нужно генерировать минимальное количество? Я рассмотрел другие похожие вопросы на этом сайте, но все они, похоже, имеют дело с последовательностями без начального неповторяющегося бита и часто без необходимости беспокоиться о внутреннем повторении.

Если это поможет / будет полезно, я также могу понять, почему я смотрю на это и для чего я буду его использовать.

Спасибо!

РЕДАКТИРОВАТЬ: Во-первых, я должен был упомянуть, что я не знаю, заканчивается ли входная последовательность точно в конце повторяющегося блока.

Реальная проблема, над которой я пытаюсь работать, - это написание красивого выражения в замкнутой форме для продолжения разложений дробей (CFE) квадратичных иррациональных чисел (фактически, отрицательных CFE). Очень просто сгенерировать частичные коэффициенты * для этих ДОВСЕ с любой степенью точности - однако в какой-то момент хвост ДОВСЕ для квадратичного иррационального становится повторяющимся блоком. Мне нужно работать с частными частными в этом повторяющемся блоке.

Мои нынешние мысли таковы: возможно, я смогу адаптировать некоторые предложенные алгоритмы, которые работают с правами на работу с одной из этих последовательностей. В качестве альтернативы, возможно, есть что-то в доказательстве того, почему квадратичные иррациональные числа являются периодическими, что поможет мне понять, почему они начинают повторяться, что поможет мне придумать несколько простых критериев для проверки.

* Если я пишу продолжение расширения дроби как [a_0, a_1, ...], я называю a_i частными частными.

Некоторая справочная информация может быть найдена здесь для заинтересованных:http://en.wikipedia.org/wiki/Periodic_continued_fraction