?

Log in

No account? Create an account

Не хочется изобретать велосипед - Ваши рубидии уже у кобальта во ртути

(Recent Entries) (Archive) (Friends) (Profile)

Jun. 28th, 2016

07:15 pm - Не хочется изобретать велосипед

Previous Entry Share Next Entry

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

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

Например, пусть дан массив [99, 99, 99, 0, 0, 0, 100, 0, 0, 0].

Если мы возьмем подмассив, состоящий только из элемента 100, то среднее остальных элементов будет 3*99/9 = 33, а разность средних - 100-33 = 67.
Если брать в качестве подмассива группу из трех нулей, то среднее остальных равно (3*99+100)/7 = 56.714..., что хуже.
Если мы возьмем подмассив, состоящий из трех элементов, равных 99, то его среднее будет 99, среднее остальных элементов - 100/7 = 14.285..., а разность - 99-14.285... = 84.714... (максимум).

Но при увеличении количества нулей результат меняется. Пусть массив таков:
[99, 99, 99, (триста нулей), 100, (триста нулей)].

Тогда если взять подмассив [99, 99, 99], получим разность средних 99-100/601 = 98.8..., а если взять подмассив [100], получим 100-3*99/603=99.5..., и в этом случае подмассив [100] оптимален.

Tags:
(33 comments | Leave a comment)

Comments:

From:rezkiy
Date:June 29th, 2016 02:22 am (UTC)
(Link)
посчитать среднее, мин и макс за один проход. Подмассив из одного элемента в котором мин или подмассив в котором макс будут ответом.
(Reply) (Thread)
From:rezkiy
Date:June 29th, 2016 02:27 am (UTC)
(Link)
Вру. Не увидел слова 'остальных'
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 29th, 2016 02:38 am (UTC)
(Link)
Более того, подмассив, в котором содержится максимум, вовсе не обязан иметь большее среднее:

99, 99, 99, 0, 0, 0, 100, 0, 0, 0

100-3*99/9 = 67
99-100/7 = 84
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:ramlamyammambam
Date:June 29th, 2016 05:19 am (UTC)
(Link)
Разве что за N^2 пополам проходов.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 29th, 2016 05:26 am (UTC)
(Link)
Это, естественно, не очень интересно, хотя для маленьких массивов сойдёт, конечно.
Но вот даже вышеупомянутую maximum subarray problem сформулировали в 1977 году, а линейное решение придумали далеко не мгновенно, так что я не оставляю надежды.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:sab123
Date:June 29th, 2016 05:07 pm (UTC)
(Link)
Есть ли некое требование про размер этого подмассива?

Потому что иначе ответ прост:
За один проход находим среднее массива, а так же самое большое и самое маленькое число в нем (и их позиции). Смотрим, что дальше от среднего в массиве - самое большое или самое маленькое число, и соответственно выбираем его как подмассив из 1 элемента.

Чуть более интеллектуальная разновидность: запоминаем не просто самое большое и самое маленькое число, а последовательности из них, и предпочитаем самую длинную последовательность. Вуаля, линейное решение.

Вот если размер подмассива фиксирован - то сложнее.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 29th, 2016 05:34 pm (UTC)
(Link)
Уже который человек не может внимательно прочитать условие.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 30th, 2016 03:36 am (UTC)
(Link)
Я сделал апдейт с примерами.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:kcmamu
Date:June 30th, 2016 12:44 am (UTC)
(Link)
Это всё для исправления шрифта надо?
Тогда, подозреваю, более адекватная постановка была бы с поиском не максимальной разницы средних, а минимальной суммы квадратов отличий чисел от соотв. средних.

Edited at 2016-06-30 12:44 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 30th, 2016 01:16 am (UTC)
(Link)
Для него. Идея заключается в определении наиболее резкой границы между темным и светлым в окрестности пикселя (окрестность легко упорядочить по азимуту), и выполнении эрозии текущего пикселя в зависимости от угла, образуемого границей, и разницы средних интенсивностей.

Edited at 2016-06-30 01:18 am (UTC)
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:archaicos
Date:June 30th, 2016 03:09 am (UTC)
(Link)
Это пахнет проблемой Longest Common Substring, которая решается через Dynamic Programming за квадратичное время.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 30th, 2016 03:38 am (UTC)
(Link)
Не вижу связи, но судя по немонотонности решения (см. апдейт), увы, похоже, что без квадратичности не обойтись.
(Reply) (Parent) (Thread) (Expand)
From:sin_gular
Date:June 30th, 2016 08:12 pm (UTC)
(Link)
А если отсортировать сохраняя массив индексов и пройти по индесам аналогом максимального подмассива?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 30th, 2016 08:20 pm (UTC)
(Link)
И как бы оно работало на тестовом примере?
Ну будет у нас
[100, 99, 99, 99, 0, 0, 0, 0, 0, 0]
[  6,  0,  1,  2, 3, 4, 5, 7, 8, 9]
,
и дальше?
(Reply) (Parent) (Thread)
[User Picture]
From:sevabashirov
Date:July 2nd, 2016 01:43 am (UTC)
(Link)
Чем-то напоминает феномен Уилла Роджерса.
(Reply) (Thread)