задачка

[avva]

Эта запись будет интересна в основном программистам.

Красивая задачка, которую подкинули во внутренней рассылке:

Отсортируйте пять чисел, используя не более семи сравнений.

(комментарии оставлю скрытыми до завтра)

Update: уточнение условий: складывать/умножать числа не разрешается. Вообще разрешается только сравнивать их друг с другом, а больше никакой информации о них не дано. "Сравнивать", определенности ради, означает применять операцию "<" или ">", на выбор.

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

Comments

[snorapp.livejournal.com]

кроме сравнений - любые действия?

[snorapp.livejournal.com]

математические, i mean

[avva.livejournal.com]

Нет, разрешаются только сравнения между данными числами, и более ничего.

[torquelimach.livejournal.com]

*удивленно* Простите, а что в этом такого? Вы точно уверены, что она будет интересна кому-то старше учеников средней школы?

Сортируем четыре числа, за три сравнения вставляем между ними пятое.

[alexeybobkov]

Что понимать под сравнением?
Скажем, процессорная команда cmp позволяет получить больше информации, чем простая операция "<".

[pierser.livejournal.com]

Словами сложно :) проще так:

Пусть есть массив a[5] одного из числовых типов и переменная b того же типа. тогда:

{
if ( a[0] > a[1] )
{
b = a[0];
a[0] = a[1];
a[1] = b;
}

if ( a[2] > a[3] )
{
b = a[2];
a[2] = a[3];
a[3] = b;
}

if ( a[1] > a[3] )
{
b = a[0];
a[0] = a[2];
a[2] = b;
b = a[1];
a[1] = a[3];
a[3] = b;
}

if ( a[1] > a[4] )
{
if ( a[0] > a[4] )
{
if ( a[0] > a[2] )
{
if ( a[4] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = b;
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = b;
}
else
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = a[2];
a[2] = b;
}
}
else
{
if ( a[1] >= a[2] )
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = b;
}
else
{
b = a[0];
a[0] = a[4];
a[4] = a[3];
a[3] = a[2];
a[2] = a[1];
a[1] = b;
}
}
}
else
{
if ( a[4] > a[2] )
{
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = b;
}
}
else
{
if ( a[1] >= a[2] )
{
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = b;
}
else
{
b = a[1];
a[1] = a[4];
a[4] = a[3];
a[3] = a[2];
a[2] = b;
}
}
}
}
else
{
if ( a[3] > a[4] )
{
if ( a[1] > a[2] )
{
b = a[3];
a[3] = a[4];
a[4] = b;
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = b;
}
}
else
{
if ( a[4] >= a[2] )
{
b = a[3];
a[3] = a[4];
a[4] = b;
}
else
{
b = a[2];
a[2] = a[4];
a[4] = a[3];
a[3] = b;
}
}
}
else
{
if ( a[1] > a[2] )
{
if ( a[0] > a[2] )
{
b = a[0];
a[0] = a[2];
a[2] = a[1];
a[1] = b;
}
else
{
b = a[1];
a[1] = a[2];
a[2] = b;
}
}
}
}
}

Проверить легко, если есть любой компилятор :)

[avva.livejournal.com]

А теперь посчитайте, сколько нужно сравнений для сортировки четырех чисел в худшем случае, и сложите.

[ivan-gandhi.livejournal.com]

Милай мой. Это тест на знание источников.

(Кстати, я одно время задавал эту задачку на интервью; знание источников также приветствовалось, но, к сожалению, ни один интервьюируемый его не проявил.)

[avva.livejournal.com]

Это, кажется, мелочи, но давайте определенности ради скажем, что это одна из двух операций: < или >, на выбор.

[mapux-f.livejournal.com]

эммм я не программист, но вот так работает

числа: а, б, в, г, д

а = о
а + б < в
б + в = г
г < д

[gianthare.livejournal.com]

А можно ли с ними что-нибудь еще делать, типа складывать/вычитать?

[torquelimach.livejournal.com]

Вот это глюк! Приношу извинения.

[cmm.livejournal.com]

а на количество умножений и сложений ограничения есть?

[jerom.livejournal.com]

Должно быть семь сравнений в блок-схеме или по ходу выполнения алгоритма просто должно быть выполнено не более семи?

[adventurism.livejournal.com]

Прикольная задачка, пришлось даже Excel открыть, чтобы не в голове цифры крутить :)
Пять цифр - A, B, C, D, E
1.Если A>B - меняем значения местами (A=B, B=A)
2.Если B>C - меняем значения местами
3.Если C>D - меняем значения местами
4.Если D>E - меняем значения местами
5.Если C>D - меняем значения местами
6.Если B>C - меняем значения местами
7.Если A>B - меняем значения местами
Т.е. пробегаем снизу вверх и обратно. Уверен, что есть и другие способы.

[amigofriend.livejournal.com]

А == можно? Потому что если идти сверху по битам в шестнадцатиричном (или двоичном) представлении, то > < вообще не нужны будут :)

[angerona.livejournal.com]

явно их надо складывать (попарно)? и сравнивать/перемещать пары, а потом уже сами числа, но теперь же надо еще придумать, в каком порядке и как, чтоб всегда результат давало...

[bealex.livejournal.com]

Цифровая сортировка позволяет сортировать числа с фиксированной точкой вообще без сравнений.

Но задачка интересная, да. Очень спасибо. :)

[malaya-zemlya.livejournal.com]

Я тебе по внутреннему емейлу шибко развернутый ответ послал. Там я накатал программу, которая берет множество всех перестановок из 5 чисел и делит его надвое при помощи результата одного сравнения. Сравнение выбирается так, чтоб две части были максимально близки по размеру. Потом каждая из частей тоже делится пополам итп.

А потом я прикинул и понял, что простой merge sort тоже подойдет.

Делишь числа на группу из двух и группу из трех. Сортируешь их по отдельности. (3 числа сортируется за 1 сравнение, 3 числа - за 3). Потом обе группы сливаются в одну. Это еще максимум 3 сравнения. Итого как раз 7.

[avva.livejournal.com]

Бывает :)

[nenujomojo.livejournal.com]

а логарифм чисел можно брать?

[grur.livejournal.com]

Бинарный поиск среди 5! перестановок.

[avva.livejournal.com]

К битам доступа нет, а только к операции сравнения двух чисел.

[avva.livejournal.com]

См. апдейт.

[avva.livejournal.com]

Второе.