У меня есть список размера n, который содержит n последовательных элементов арифметической прогрессии, которые расположены не по порядку. Я изменил менее половины элементов в этом списке на какое-то случайное целое число. Как из этого нового списка найти разность начальной арифметической прогрессии?
Я много думал об этом, но кроме грубой силы ничего другого придумать не смог :(
Спасибо, что подумали об этом :)
Невозможно решить это вообще и быть на 100% уверенным в правильности своего ответа. Допустим, исходный список представляет собой следующую арифметическую прогрессию (не по порядку):
1 3 2 4
Измените менее половины элементов случайным образом... скажем, например, что мы изменили 2 на 5:
1 3 5 4
Если мы сможем сначала выяснить, какие числа нам нужно изменить, чтобы получить правильную перетасованную арифметическую последовательность, то мы сможем легко решить проблему, указанную в вопросе. Однако мы видим, что существует несколько возможных ответов в зависимости от того, какой номер мы решим изменить:
Невозможно узнать, какая из этих возможных последовательностей является исходной последовательностью, поэтому вы не можете быть уверены, в чем заключалась исходная разница.
1 3 5 7 неверно? Вы не знаете, какой была исходная последовательность (нет доступа к 1 3 2 4), поэтому, насколько вам известно, она может быть правильной. Кроме того, почему нужно смотреть только на первые три элемента? Если вы посмотрите на все из них, нет никаких причин, по которым вы не можете придумать и 1 2 3 4. Я бы сказал, что есть несколько возможных ответов, а не то, что это невозможно.
- person IVlad; 28.01.2011
Поскольку детерминированного решения проблемы не существует (как заявил @Mark Byers), вы можете попробовать вероятностный подход.
Трудно получить исходную прогрессию, но ее скорость можно легко получить, сравнив различия между элементами. Отличие от исходных будет кратно скорости.
Предположим, вы берете 2 элемента из списка (вероятность того, что они оба принадлежат исходной последовательности, равна 1/4) и вычисляете разницу. Эта разница с вероятностью 1/4 будет кратна курсу. Разложите его на простые множители и посчитайте их (например, 12 = 2^^2 * 3 добавит 2 к счетчику 2 и увеличит счетчик 3).
После многих таких итераций (выглядит как хорошая задача для вероятностных методов, таких как Монте-Карло), вы может анализировать счетчики.
Если простой множитель принадлежит ставке, его счетчик будет не менее num_iteartions/4 (или num_iterations/2, если он встречается дважды).
Основная проблема заключается в том, что небольшие факторы будут иметь большую вероятность при случайном вводе (например, разница между двумя случайными числами будет с вероятностью 50% делиться на 2). Таким образом, вам придется это компенсировать: поскольку 3/4 ваших различий были случайными, вам придется учитывать, что (3/8)*num_iterations счетчика 2 следует игнорировать. Поскольку это также относится ко всем степеням двойки, самый простой способ - предварительно сгенерировать «маску белого шума», взяв различия только между случайными числами.
РЕДАКТИРОВАТЬ: давайте продолжим этот подход. Учтите, что вы создаете эту «маску белого шума» (назовем ее спектр) для случайных чисел и считаете, что это спектр по основанию 1, поскольку их наименьший «наибольший общий множитель» равен 1. Вычислив его для разностей арифметической последовательности вы получите спектр с основанием R, где R — скорость, и он будет эквивалентен смещенной версии спектра с основанием 1. Итак, вам нужно найти такое значение R, что
your_spectrum ~= spectrum(1)*3/4 + spectrum(R)*1/4
Вы также можете проверить наибольшее число R, чтобы по крайней мере половина элементов была равна по модулю R.
