Xpoint
   [напомнить пароль]

Сортировка массива в последовательность без повторов

Метки: [без меток]
2009-05-01 13:11:09 [обр] Николай Бельцов(0/52)[досье]

Со вчерашнего вечера бьюсь над следующей задачкой.
И чего-то совсем НИКАК :-((

Объясню на пальцах суть задачи.
Высыпаем из кошелька всю имеющуюся в нём мелочь.
Надо разложить ВСЕ монетки на столе в одну линию ТАК, чтобы две монеты одного достоинства не лежали рядом.
Понятно, что когда-то эта задача решается, а когда-то - нет (если, например, из всего четырёх монеток три - одинаковые).

Так вот, прошу ваших соображений в следующих вопросах:

  1. Как В ОБЩЕМ ВИДЕ, проанализировав горсть мелочи (разложив монетки в кучки по достоинству и пересчитав количество в каждой кучке) сделать вывод - МОЖНО ЛИ разложить их так, чтобы не было двух подряд лежащих одинаковых монеток или НЕЛЬЗЯ это сделать?
  1. А если МОЖНО их разложить, то каков АЛГОРИТМ этого действия?

PS. В реале исходными являются массивы, а не горсти монет.
И с довольно большим количеством элементов, среди которых ВСЕГДА есть значительное количество повторяющихся элементов, причём повторяются разные элементы произвольное число раз (т.е. крайние случаи - нет элементов, нет повторов - можно не рассматривать).

PS2. Ссылка на существующее решение этой (или похожей, но где можно "поймать" алгоритм) задачи на любом языке программирования приветствуется (кроме ассемблера, разумеется).

спустя 21 час [обр] Саша75[досье]
По моему задача решается следующим образом.
Заносим все в один массив с элементами типа значение монеты (ключ) -> количество таких монет. Это чтобы было удобнее работать с ними в дальнейшем.
Если в одном из элементов массива оказывается больше монет чем суммарно во всех остальных+1, то задача нерешаема.
В противном случае:
  1. Выкладываем монету из элемента массива в котором больше всего монет.
  2. Выкладываем монету из элемента массива в котором больше всего монет, но не из того элемента из которого было выложено на предыдущем шаге.
  3. Пока не опустел весь массив goto 2
спустя 6 дней [обр] Николай Бельцов(0/52)[досье]
Саша75[досье]Спасибо.
Powered by POEM™ Engine Copyright © 2002-2005