в серии из n элементов арифметической прогрессии элементы [n / 2] изменены. Найти разницу в начальной арифметической прогрессии - PullRequest
Новая
       4

в серии из n элементов арифметической прогрессии элементы [n / 2] изменены. Найти разницу в начальной арифметической прогрессии

2 голосов
/ 28 января 2011

У меня есть список размера n, который содержит n последовательных членов арифметической последовательности, которые не в порядке.Я изменил менее половины элементов в этом списке со случайным целым числом.Из этого нового списка, как я могу найти разницу в начальной арифметической прогрессии?

Я много думал об этом, но, кроме грубой силы, я не смог придумать ничего другого: (

Спасибо, что подумали об этом:)

Ответы [ 2 ]

3 голосов
/ 28 января 2011

В общем, решить эту проблему невозможно и быть на 100% уверенным в правильности вашего ответа. Допустим, что начальный список имеет следующую арифметическую прогрессию (не по порядку):

1 3 2 4

Произведите случайное изменение менее половины элементов ... скажем, например, что мы изменили 2 на 5:

1 3 5 4

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

  • 6 , 3, 5, 4 (разница составляет 1)
  • 1, 3, 2 , 4 (разница составляет 1)
  • 1, 3, 5, 7 (разница составляет 2)

Нет способа узнать, какая из этих возможных последовательностей является исходной последовательностью, поэтому вы не можете быть уверены, каково было исходное отличие.

1 голос
/ 28 января 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. Путем вычисления ее дляВ отличие от арифметической последовательности, вы получите спектр base-R, где R - скорость, и она будет эквивалентна сдвинутой версии спектра base-1.Таким образом, вы должны найти значение R так, чтобы 

your_spectrum ~= spectrum(1)*3/4 + spectrum(R)*1/4

Вы также могли проверить наибольшее число R, чтобы по крайней мере половина элементов была равна по модулю R.

...