Назовем равномерным набор натуральных чисел, в котором чередуются четные и нечетные числа: четное-нечетное-четное-нечетное... или нечетное-четное-нечетное... Задан набор из 2N натуральных чисел, из которых ровно N чисел четных и N чисел нечетных. Нужно определить, за какое МИНИМАЛЬНОЕ количество перестановок его можно сделать равно мерным. Перестановкой считаем обмен местами двух эл-тов. Есть ли какие то формулы для этого?
надо написать программу для расчета. программу напишу я сам, вопрос как рассчитать минимальное кол-во перестановок? даже человеку, вручную, трудно сказать какое минимальное.. есть ли какие то формулы для этого?
Рассмотрим порядок чёт-нечет-чёт-нечет…
Считаем, сколько чётных не на своих местах (=a).
И сколько нечётных не на своих местах (=b).
Если a≠b, у нас нет N чётных и N нечётных — выводим «неверный набор данных».
А если равны, то для порядка чёт-нечет нужны a замен. Для противоположного — N-a.
Вот и получается ответ min(a, N−a).
>А если равны, то для порядка чёт-нечет нужны a замен. Для противоположного — N-a.
>Вот и получается ответ min(a, N−a).
то есть сначала определяем с чего начинается последовательность, с четного или нет, правильно?
Нет, не нужно.
Если есть N чётных и N нечётных, и в порядке «чёт-нечет» не на местах a тех и других, то в порядке «нечёт-чёт» те, которые были на месте, становятся не на месте, и наоборот — то есть, не на месте N−a.
блин чего то не доходит до меня этот момент.. А если равны, то для порядка чёт-нечет нужны a замен. Для противоположного — N-a.
Вот и получается ответ min(a, N−a).
можете сказать по шагам именно этот момент, порядок чет-нечет это при вводе или когда? как определить порядок у нас чет-нечет или наоборот?
Вот у нас есть массив ч н ч ч н н, N=3.
В порядке ч-н не на своих местах стоят 1 чётное и 1 нечётное (4 и 5). Их и поменяем.
В порядке н-ч не на местах 2 чётных и 2 нечётных (1…3 и 6). Поменяем, например, 1-2 и 3-6.
1+2 =, как ни странно, 3.
Так что не важно, какой из этих двух порядков брать за основу. Результат будет один и тот же.
Простой
Простой
Простой
