Задача стояла такая: вводя 2 целых числа, нужно было найти все простые числа между ними. С этим быстро справился, но вторая часть задания добавляет условие: сгенерировать массив из простых чисел, найденных ранее, при условии, что среднее-арифметическое модулей разностей всех элементов массива наиболее близка к целому числу P > 1. Число Р также вводится вместе с границами диапазона. Разности считаются так: если массив, например, 7 2 2 5, то среднее арифметическое будет вычисляться так ср_арф = (|7-2|+|7-2|+|7-5|+|2-2|+|2-5|+|2-5|)/6.

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

Но и у этого метода есть недостатки - если, например, массив из двух чисел получился {5, 7}, P = 3, а доступные простые числа, это {2, 3, 5, 7}, то тогда большего числа не,т и по алгоритму будет браться все время 7, и с каждым разом среднее-арифметическое будет становиться только меньше. Если добавлять проверки на такие частные случае, то еще больше загромоздится и без того не очень хорошо читаемый код. Поэтому прошу совета у математиков, есть ли у вас какие соображения, потому что я не очень хорошо дружу с математикой, и вот этот алгоритм вывел эмпирическим путем, просто пробуя разные варианты массивов и пытаясь найти закономерность.

задан 27 Дек '14 14:26

изменен 28 Дек '14 20:52

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
0

Пусть у нас есть массив длины n. Ясно, что при сложении модулей разностей между числами самый левый отрезок встретится n - 1 раз, второй слева - 2(n - 2), третий слева - 3(n - 3), ..., самый правый снова n - 1 раз. Поэтому при постоянном положении прочих элементов массива при сдвиге элемента из левой половины вправо функция будет убывать, из правой - возрастать, при сдвиге центрального элемента (если он есть) функция будет оставаться постоянной. Поэтому можно устроить несколько троичных поисков - сначала поиск ближайшей суммы по последнему элементу, затем поиск из ближайших по предпоследнему и так далее (на каждом шаге сумму можно менять за О(1), а весь алгоритм будет работать за $%O(\log_{\Phi}^nn)$%).

ссылка

отвечен 28 Дек '14 0:47

Спасибо, попробую реализовать.

(28 Дек '14 11:22) K_ID
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×93
×13

задан
27 Дек '14 14:26

показан
520 раз

обновлен
28 Дек '14 20:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru