задачка

[avva]

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

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

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

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

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

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

Comments

[snorapp.livejournal.com]

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

[snorapp.livejournal.com]

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

[torquelimach.livejournal.com]

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

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

[avva.livejournal.com]

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

[alexeybobkov]

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

[avva.livejournal.com]

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

[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]

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

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

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

[avva.livejournal.com]

Нет :)

[gianthare.livejournal.com]

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

[avva.livejournal.com]

Нет, см. апдейт.

[cmm.livejournal.com]

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

[avva.livejournal.com]

См. апдейт.

[jerom.livejournal.com]

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

[avva.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 - меняем значения местами
Т.е. пробегаем снизу вверх и обратно. Уверен, что есть и другие способы.

[avva.livejournal.com]

Это не работает - у вас неявное предположение слишком хороших раскладок исходных чисел.

[avva.livejournal.com]

У вас слишком оптимистичное представление о самом неприятном случае :)

[angerona.livejournal.com]

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

[avva.livejournal.com]

нет (см. апдейт).

[bealex.livejournal.com]

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

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

[avva.livejournal.com]

Очень пожалуйста :)

[malaya-zemlya.livejournal.com]

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

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

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

[avva.livejournal.com]

Послушай, твое второе решение не может работать из-за принципов, которые ты верно изложил в своем первом решении. Разве нет?

Конкретно если, то последняя часть второго решения несколько кавалеристски описана, и мне не вполне понятно, как это сработает.

[nenujomojo.livejournal.com]

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

[avva.livejournal.com]

Нет.

[grur.livejournal.com]

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

[avva.livejournal.com]

Какой это на 5! перестановках есть полный порядок, по которому ты делаешь бинарный поиск? :)

Это школьная олимпиадная задача про взвешивания

[(Anonymous)]

И решать ее проще именно в терминах есть весы и 5 гирек разных по весу. Задача простая, IMHO.

Re: Это школьная олимпиадная задача про взвешивания

[avva.livejournal.com]

Верно, я не знал о варианте с весами, но явно можно так сформулировать.

[strangeraven.livejournal.com]

Для начала: 5 чисел могут лечь в ряд 5! = 120 вариантами.
7 взвешиваний рассекают 2^7 = 128 вариантов
Должны успеть.

Тактика решения подобных задач: каждое рассечение вариантов как можно ровней, чтобы после рассечения множества вариантов не делились на "удачное" и "неудачное". Идеально, если рассечение бьет множество симметрично. Тогда не надо рассматривать различные исходы.

Поехали:

A, B, C, D, E

1. A ? B
A < B

2. C ? D
A < B
C < D

3. B ? D
A   <   B
      < 
C < D

4.a. D ? E

A   <   B
      <
C < D
E <

5.a. C ? E

        A < B
          <
C < E < D

далее A за два сравнения доставляем в ряд C,E,D,B

4.b. D ? E

    A < B
      <
C < D < E

5.b. B ? E

        A <
C < D < E < B

или
    A <
C < D < B < E

в любом случае доставляем A за два сравнения

[avva.livejournal.com]

Ага, верно.

[deni-ok.livejournal.com]

Выбираем две пары 1 и 2. Упорядочиваем каждую за 2 сравнения: m1<M1, m2<M2.
Сравниваем M1 и M2 (3ье сравнение). Без ограничения общности можно считать, что M2 больше:

m1 < M1
     ^
m2 < M2

Сравниваем теперь оставшееся ещё неиспользованным пятое число (x) с M1. Возможны 2 варианта:
(1)

m1 < M1 < x
     ^
m2 < M2

(2)

     x
     ^
m1 < M1
     ^
m2 < M2

Легко видеть, что оставшихся трех сравнений достаточно, чтобы сделать эти частичные порядки полными.

[avva.livejournal.com]

Все верно (хотя "легко видеть" наверное не всем :))

[nenujomojo.livejournal.com]

отсоротровать 3 числа (3 сравнения), оставшиеся 2 (одно). сравнить минимум из двух с максимумом трех (одно). если больше - все. если меньше - сравнить максимум двух с минимумо трех (одно). если меньше - все. если больше - сравнить два со средним их трех (два).

[avva.livejournal.com]

Нет, увы, так в худшем случае не сработает.

[dfayruzov.livejournal.com]

Разделим 5 чисел на группы:
A,B - группа1, C, D - группа 2, Е - группа 3

Далее, предположим, что "победитель" группы - который больше. Тогда максимум можно выбрать за 4 сравнения:
А,B -> Win1
-> Win3
C,D -> Win2
-> Win4
E

И вот здесь вопрос: могу ли я проверить, что Win4 "is" Win3?

[avva.livejournal.com]

простите, но ваш метод я кажется совсем не понял :)

[talash.livejournal.com]

i understand that swapping places etc is allowed?

[avva.livejournal.com]

Ага.

[azot.livejournal.com]

AB, DE, BD, BC, CD , AB, DE.

[avva.livejournal.com]

Нет, это не сработает в худшем случае.

[(Anonymous)]

Метод вставки

[(Anonymous)]

Метод вставки дает 9, сорри