HTML+CSS+JavaScript

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

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

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

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

2. А если МОЖНО их разложить, то каков АЛГОРИТМ этого действия?

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

PS2. Разумеется, в заголовке я оБшибся, а исправить его здесь нельзя - читать надо как "Сортировка МАССИВА"

Рискну нарваться на Ваш любезный комплимент =) По-моему или тут все очень просто или очень сложно (тогда я просто не понял "заковырку" этой задачи).

1. Количество самых больших по значению элементов должно быть с каким-то другим значением парным

2. Сортировать элементы "по кругу" до конца ("12341231212")

ща попробую на на том же примере цифр от 1 до 9 разобраться и отпишусь... \/

Попробую на кошках цифрах
Есть следующие горсти

111 222 33333 44 55555 66

Сортируем: 123456 123456 1235 35 35 нет повторов. Тут все верно? Пар нет?
Теперь

111 22 33 444 5

Результат: 12345 1234 14 нет повторов
Еще

1 22 333 4444 55555

Результат: 12345 2345 345 45 5 есть повтор!
Мои рассуждения идут по верному пути ли нет? )

Спасибо за участие!

Вы ищете алгоритм сортировки, а мне ПЕРВЫМ делом надо решить задачу - МОЖНО или НЕЛЬЗЯ разложить без повторов, причём В ОБЩЕМ ВИДЕ?
Т.е. имея на входе известное: (элемент х количество повторов) 1 х 5, 2 х 3, 3 х 3, 4 х 1, 5 х 8, 6 х 1 и т.д. СРАЗУ сказать - ПОЛУЧИТСЯ или НЕ ПОЛУЧИТСЯ.

И вот если ПОЛУЧИТСЯ - то тогда будем решать - КАК ИМЕННО?
Хотя, мей би, вы и правы - может, надо решать и в обратном порядке - сначала получить алгоритм, а потом из него вывести условие реализации.

Один критерий (получится/не получится) я выявил: если количество повторов одного элемента будет на 2 меньше, чем количество всех остальных элементов, то разложить НЕЛЬЗЯ.
Но единственный ли это критерий невозможности - я пока "не допёр" :-)
Пример:

Имеем 1111112234 (т.е. ШЕСТЬ единиц и в сумме ЧЕТЫРЕ другие цифры) - разложить нельзя.

да не ищу я алгоритм сортировки, просто пример такой =)

>если количество повторов одного элемента будет на 2 меньше, чем количество всех остальных элементов, то разложить НЕЛЬЗЯ.
вот! это ж примерно вытекает из моего
>1. Количество самых больших по значению элементов должно быть с каким-то другим значением парным
Я тут правда неудачно выразился.
Я Вам для чего эти 3 примера-то и привел и именно ТАК ("отсортировал") - типа в подтверждение моей "теоремы" ). Пока вроде все сходятся, я пытаюсь методом перебора выявить слобое место )

Вот смотрите, у Вас 5 единиц. Именно единиц больше всех. Так вот у Вас должно быть еще каких-то других цифр тоже 5, иначе разложить НЕЛЬЗЯ.

ПОСМОТРИТЕ ВСЕ примеры. Внимательно. Тогда может поймете к чему я клоню )

Единиц у меня уже ШЕСТЬ - пока вы писали, я исправил:-)
(Ввел повтор двойки, дабы привести к общему виду - не просто ДРУГИЕ цифры, а в том числе ПОВТОРЯЮЩИЕСЯ другие)


>у Вас 5 единиц. Именно единиц больше всех. Так вот у Вас должно быть еще каких-то других цифр тоже 5, иначе разложить НЕЛЬЗЯ.

Утверждение неверное.
ПЯТЬ единиц и ЧЕТЫРЕ другие цифры вполне себе раскладываются:

121314151

Это вы с ЗАМКНУТОЙ цепью перепутали - типа танковой/тракторной гусеницы - там действительно надо одинаковое число траков и пальцев. А у меня в задаче не цепь, а разорванная линия, коя может начинаться и заканчиваться одинаковыми элементами.

хм.. да, с упорядочиванием не пойдет тогда и теория моя тогда "лагает"

а придеться, наверное, Вам все равно плясать от алгоритма.
Потому что вот еще

11111 2 3 4 5 66

Если расположить так, то НЕЛЬЗЯ: 12131415166
А так МОЖНО: 12613141516
=)

Так что однозначно, вполне вероятно, сказать не получится

Всё, проблему решил.
Критерий невозможности разложения - единственный (выше я озвучивал по поводу максимально повторяющегося символа: количество повторов такого символа не должно быть больше количества оставшихся более, чем на на единицу).
В принципе, могу дать этому строгое мат.доказательство.

Алгоритм разложения для крайних условий (т.е. когда число максимально повторяющегося символа равно или на единицу больше/меньше количества всех остальных символов) ЕДИНСТВЕННЫЙ - ставим максимальноповторяющийся символ на НЕЧЁТНЫЕ места, а прочие символы (в любом порядке, можно даже рамдомно) - на ЧЁТНЫЕ.
Соответственно, этот же алгоритм можно распространить и на "некрайние" условия: из ряда цифр количества повторов символов

N = 1 + 1 + ... + 1 + 1 + 2 + 2 + ... + 2 + 2 + 3 + 3 + ... + 3 + 3 + ... + m + m + ... + m + m     -------------------   -------------------   -------------------         -------------------      уникальные  эл-ты    2-ды повторяющиеся    3-ды повторяющиеся          повторяющиеся m раз

надо набрать сумму, приблизительно равную половине общего количества и поставить их на НЕЧЁТНЫЕ места, а оставшиеся - на ЧЁТНЫЕ. И если что-то из неупотреблённых символов ещё останется - "сунуть" их опять же методом "через одно место" хоть с начала строки, хоть с конца, хоть с середины.

ну что ж, поздравляю Вас с решением проблемы! Я несколько недальновидным опять оказался )

t1... tn - типы объектов в порядке уменьшения количества..
num(t1)...num(tn) - количество объектов каждого типа.
Условие расклада:
num(t1) <= 1 + sum(num(t2)...num(tn))
По-моему, так.

Да, так.

Спасибо.

Я для сортировки русских строк, с буквой Ё, использовал JS библиотеку, функция получилась невероятно простой, но скорость слабенькая. У тебя большие массивы, этот способ не пойдёт. Даже не пробуй. Да и работает только в осле. Меня тогда устроило, я и не стал голову морочить.
Если не послушаешься и решишь попробовать, могу скинуть функцию, она задуманна под приём массива.


Может, что и даст тебе эта статья. Где взял не знаю, когда тоже.

<html><head>

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
<title>Методы сортировки.</title>
<meta content="text/html; charset=windows-1251" http-equiv="Content-Type">
<style type="text/css"><!--
body { font-weight:600; }
pre { font-weight: bold; color:maroon;}
--></style>
</head><body>

<table cellpadding=6><tr><td colspan="3" class="Normal" valign="top">

<b>Сортировка массива методом пузырька</b> - медленная, но если скорость не главное, можно применить и его. Алгоритм очень прост - если два соседних элемента расположены не по порядку, то меняем их местами. Так повторяем до тех пор, пока в очередном проходе не сделаем ни одного обмена, т.е. массив будет упорядоченным. Ниже текст процедуры, реализующей алгоритм сортировки методом пузырька (Arr - массив для сортировки с начальным индексом 0, n - размерность массива)
<pre>
procedure SortPuz (var Arr : array of Integer; n : Integer);
var
i : Integer;
Temp : Integer;
Flag : Boolean;
begin
repeat
Flag := False;
for i := 0 to n - 1 do
if Arr [i] &gt; Arr [i + 1] then begin
Temp := Arr [i];
Arr [i] := Arr [i + 1];
Arr [i + 1] := Temp;
Flag := True;
end;
until Flag = False;
end;
</pre>
<b><font >Сортировка методом нахождения минимального элемента</font></b><br>
Ещё один вариант сортировки, более быстрый, чем метод пузырька. Заключается он в следующем: при каждом просмотре массива находим минимальный элемент и меняем местами его с первым на первом проходе, со вторым - на втором и т.д. Не забудьте только, что первый элемент массива должен иметь индекс 0.
<pre>
procedure SortMin (var Arr : array of Integer; n : Integer);
var
i, j : Integer;
Min, Pos, Temp : Integer;
begin
for i := 0 to n - 1 do begin
Min := Arr [i];
Pos := i;
for j := i + 1 to n do
if Arr [j] &lt; Min then begin
Min := Arr [j];
Pos := j;
end;
Temp := Arr [i];
Arr [i] := Arr [Pos];
Arr [Pos] := Temp;
end;
end;
</pre>
<b><font >Сортировка массива вставками</font></b><br>
Более быстрый и оптимальный метод сортировки - сортировка вставками. Суть её в том, что на n-ном шаге мы имеем упорядоченную часть массива из n элементов, и следующий элемент встаёт на подходящее ему место. Имейте в виду - первый индекс массива - 0.
<pre>
procedure SortInsert (var Arr : array of Integer; n : Integer);
var
i, j, Temp : Integer;
begin
for i := 1 to n do begin
Temp := Arr [i];
j := i - 1;
while Temp &lt; Arr [j] do begin
Arr [j + 1] := Arr [j];
Dec (j);
if j &lt; 0 then
Break;
end;
Arr [j + 1] := Temp;
end;
end;
</pre>
<b><font >Поиск перебором</font></b><br>
Чтобы найти какие-то данные в неупорядоченном массиве, применяется алгоритм простого перебора элементов. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве и искомое число. Если число не найдено, возвращается -1.
<pre>
function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;
var
i : Integer;
begin
Result := -1;
for i := 1 to n do
if Arr [i] = v then begin
Result := i;
Exit;
end;
end;
</pre>
<b><font >Бинарный поиск</font></b><br>
При поиске в упорядоченном массиве можно применить гораздо более быстрый метод поиска - бинарный. Суть его в следующем: В начале переменная Up указывает на самый маленький элемент массива (Up := 0), Down - на самый большой (Down := n, где n - верхний индекс массива), а Mid - на средний. Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.
<pre>
function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;
var
Up, Down, Mid : Integer;
Found : Boolean;
begin
Up := 0; Down := n;
Found := False; Result := -1;
repeat
Mid := Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found := True
else
if v &lt; Arr [Mid] then
Down := Mid - 1
else
Up := Mid + 1;
until (Up &gt; Down) or Found;
if Found then
Result := Mid;
end;
</pre>

</td></tr></table></body></html>



Удачи!