куда катится программирующее человечество...

[juan_gandhi]

Хрестоматийную задачку ни одна собака решить не может: Отсортируйте пять элементов, используя не более семи сравнений.

Comments

[gmz.livejournal.com]

Не читают хрестоматий?
А практического смысла задача сейчас не имеет, если не иметь в виду тренировку мозгов.

[spamsink.livejournal.com]

Не скажи. Если сравнение дорогое, то лучше так, чем insertion sort.

[os80.livejournal.com]

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

[malaya-zemlya.livejournal.com]

merge sort всего на 1 сравнение хуже оптимального (а то не всегда), зато гораздо понятнее.

[panikowsky.livejournal.com]

ну подождите, avva закомментировал правильные ответы до завтра.

[ivan-gandhi.livejournal.com]

Да без разницы; уже столько народу поналезло с глупостями, что ужас, ужас, ужас.

[panikowsky.livejournal.com]

C'est dévaluation du profession...

Не говори гоп

[spamsink.livejournal.com]

Сколько собак решило эту олимпиадную задачку по математике для 7-8 классов, мы узнаем завтра, когда откроют комментарии.

Тем более что с грепом и wc можно особенно глаза не трудить выискиваючи.

Re: Не говори гоп

[ivan-gandhi.livejournal.com]

Стр. 183 известно какой книжки.

Re: Не говори гоп

[spamsink.livejournal.com]

CLR, что ль? Там это разве что как упражнение.

Re: Не говори гоп

[6pack.livejournal.com]

Что за книжка?

[poluzhivago.livejournal.com]

По-моему, действительно детская задача на перебор вариантов. Никакой изюминки, кроме достаточно очевидного посыла, что начинать сравнивать надо не линейно, а по парам и потом вводить 5-е число.

[ionial.livejournal.com]

указанное решение не верное.
сравнили 1<2, 3<4
теперь, сравнив 1:3 и переставив, что бы получить
1<3 мы можем получить вариант:
1<2
1<3
но отношение 3<4 пропадает. для его поддержания нужно
еще одно сравнение.
пример
8,9,3,4,7
1 - 8<9
2 - 3 < 4
3 - 1:3 + swap получаем 3,9,8,4
условие 3<4 не выполняется.

[ionial.livejournal.com]

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

[poluzhivago.livejournal.com]

А я как дурак, сидел и никак не мог понять, что же Вам не понравилось в том решении?
:)))
хотя записано оно действительно небрежно.

[angerona.livejournal.com]

В том-то и дело, что хрестоматии вспоминать легко, а вот самим мозгами подумать, вряд ли результаты впечатлающие будут.

[spamsink.livejournal.com]

Да там и мозгами думать не надо, если текстовый редактор под рукой.

[itman.livejournal.com]

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

[faceted-jacinth.livejournal.com]

Я, может, туплю где-то.
Набросал программку на питоне, которая умудряется таки перебрать все варианты меньше чем за секунду если ей чуть-чуть помочь (задать явно порядок между первым и вторым числом). И результаты она вполне правдоподобные выводит если попросить за 8 сравнений отсортировать.

А для семи сравнений она утверждает, что решения нет.
При этом я точно знаю, что 5! < 2**7.

Как так? У меня в программе глюк? Или там где-то информация неприятно округляется и из-за этого её не хватает?

[ionial.livejournal.com]

таки глюк.
решение есть и оно очень простое...

[itman.livejournal.com]

Это смотря что называть простым решением. Я бы не назвал decision tree (с подробным описанием того, что и где мы сравниваем) глубины 5 таким уж простым решением.

[raa.livejournal.com]

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

[fenikso.livejournal.com]

>лыжник проехал 1 километр и поймал ртом 20 снежинок.
>оцените дальность видимости
хорошая формулировка, напомнила задачу "почему в тумане всё выглядит одинаково" украинского ТЮФа какого-то там года :)

[itman.livejournal.com]

Это не программистская задачка, это задачка математическая.

[selfmade.livejournal.com]

Решил. Хрестоматию не читал, что имеется в виду?