Найти период в очень большой последовательности чисел
Есть ли возможность найти длину цикла в очень большой части чисел (больше максимального значения самого большого целочисленного типа в C / C ++, скажем, 2 ^ 20), не задействуя диск для ее выполнения? Лучше всего было бы проанализировать их последовательно, поскольку они поступают со стандартного ввода, но я почти уверен, что это невозможно, и мне нужно хранить их в памяти. Но я надеюсь, что я не прав. Числовые значения являются целыми числами, они поступают из стандартного ввода.
Пример:
Ввод: (1 2 3 … (2 ^ 20 троек из 1 2 3) … 1 2 3)
Желаемый результат: 3
РЕДАКТИРОВАТЬ
давайте думать о цикле как о периоде (f (x) = f (x + t) для некоторого t) — ищем значение t
давайте предположим, что оперативной памяти слишком мало для хранения всех чисел (числа могут быть больше 2 ^ 20) и могут быть типы gmp.
Решение
Это хорошо изученная проблема, с большим количеством алгоритмов, в зависимости от того, каковы ваши ресурсы и недостатки:
http://en.wikipedia.org/wiki/Cycle_detection
Вам не нужно хранить все в памяти (всего два указателя / индекса в основных алгоритмах), но вам нужно иметь возможность обращаться к последовательности несколько раз.
Смотрите также:
Другие решения
Стандартный способ определения длины периода состоит в том, чтобы представить, что ваша последовательность представляет собой строку S над алфавитом целых чисел, а затем найти крайнюю левую позицию (больше 0), где S можно найти в строке SS (конкатенация строки S с собой). То есть если S = 'abcabc'нужно найти первую позицию i больше нуля, так что S находится в положении i в строке SS = 'abcabcabcabc', В данном случае это 3, и это длина периода.
Это может быть сделано любым алгоритмом поиска строк с линейной производительностью, и он должен прекрасно работать для 2 ^ 20 чисел на современном компьютере. Я сомневаюсь, что вы можете избежать сохранения чисел в памяти, хотя.