![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
juan_gandhiХрестоматийную задачку ни одна собака решить не может: Отсортируйте пять элементов, используя не более семи сравнений.
juan_gandhijuan_gandhi
Page Summary
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Active Entries
Style Credit
- Style: Neutral Good for Practicality by timeasmymeasure
Expand Cut Tags
No cut tags
no subject
Date: 2008-07-17 02:33 am (UTC)no subject
Date: 2008-07-17 02:57 am (UTC)no subject
Date: 2008-07-17 06:43 pm (UTC)PS: но за подсказку спасибо, я помню была на топкодере похожая задачка только нужно было написать программу, которая найдет не кратчайшую последовательсть сравнений, а наиболее дешевую.
no subject
Date: 2008-07-17 07:07 pm (UTC)Что количество перестановок 5 элементов равно 5! = 120 < 27, т.е. что нас не накалывают?
Или что начинать поиск можно не на множестве размером 120, а хотя бы в 4 раза меньше, поэтому не нужно ни писать программу, генерирующую перестановки, ни мучиться особенно с cut-n-paste?
Потому что дальше - дело техники. Так, что там мы еще с чем не сравнивали? grep это дело | wc; Сколько строчек получилось? Если отличается от половины исходного, пробуем еще. Если нет - записываем, что с чем сравнивали, на бумажке и сохраняем результат в следующий файл.
no subject
Date: 2008-07-17 08:14 pm (UTC)Если про не знаешь, то кажется, что все просто.
Следующее, в общем-то тоже несложное наблюдение заключается в том, что элементы для сравнения нужно выбирать так, чтобы они эту дихотомию обеспечивали. Тут, наверное, большинство догадаются.
Третья (это даже не наблюдение), а не заморочка, на которой многие тоже могут заткнуться, заключается в том, что в задаче нужно тупо построить decision tree и не пытаться придумать что-нибудь красивое и закономерное.
Если перемножить все эти факторы, то получается довольно нетривиальная задача.