Блог им. OriginaL → Немой стражник
Хочу поделиться с вами интересной задачкой на сообразительность. Вот она:
Вы стоите на развилке двух дорог, одна из дорог ведет к дому (но вы не знаете какая). К счастью, на развилке стоит стражник, который либо правдивец (говорит только правду), либо лжец (всегда лжёт). К сожалению, стражник немой. Но, к счастью, не глухой и понимает вас. Стражник, говоря «да» и «нет», произносит их как «ыыыы» и «уууу». Однако, что из них означает «да», а что «нет» — неизвестно. Других звуков стражник не произносит, да и вдобавок не может указать нужное направление. Ко всему прочему он не понимает длинные вопросы более 15 слов. Какой вопрос нужно задать стражнику, чтобы узнать, какая дорога выведет вас к родному дому? Вопрос можно задать только один и только такой, на который стражник знает ответ.
Вы стоите на развилке двух дорог, одна из дорог ведет к дому (но вы не знаете какая). К счастью, на развилке стоит стражник, который либо правдивец (говорит только правду), либо лжец (всегда лжёт). К сожалению, стражник немой. Но, к счастью, не глухой и понимает вас. Стражник, говоря «да» и «нет», произносит их как «ыыыы» и «уууу». Однако, что из них означает «да», а что «нет» — неизвестно. Других звуков стражник не произносит, да и вдобавок не может указать нужное направление. Ко всему прочему он не понимает длинные вопросы более 15 слов. Какой вопрос нужно задать стражнику, чтобы узнать, какая дорога выведет вас к родному дому? Вопрос можно задать только один и только такой, на который стражник знает ответ.
Алгоритмы → Алгоритм m-мерной пирамиды
Данный метод является логическим завершением сортировки с помощью пирамиды, который был предложен Вильямсоном в 1964 г. Сложность предложенного алгоритма в худшем случае равна $$ O(N \cdot log _{a} N),$$ где N — размер массива, a — особый параметр, который позволяет «настраивать» работу алгоритма. Проще говоря, данный метод является самым быстрым для сортировки неупорядоченных данных.
Читать дальше
Читать дальше