Головоломки: способы решения
от Ксакеп
Задачи-головоломки являются очень спорной темой, многие компании запрещают использовать их на собеседованиях. Если вам досталась головоломка, то наверняка она интересная и наверняка её можно решить логически. Корни большинства головоломок лежат в математике или информатике. Давайте рассмотрим основные подходы к решению головоломок.
Правила и шаблоны
В большинстве случаев попробуйте найти и записать правила или шаблоны, которые помогут вам решить задачу. Да-да, именно записать — это поможет запомнить их и использовать при решении задачи. Давайте посмотрим простой пример.
У вас две веревки и каждая из них горит ровно один час. Как их можно использовать, чтобы определить, что прошло 15 минут? Более того, плотность веревок не является константой, поэтому необязательно, что половина веревки будет гореть ровно полчаса. Совет: остановитесь и попытайтесь решить задачу самостоятельно. В крайнем случае, прочитайте этот раздел медленно и вдумчиво. Каждый абзац будет приближать вас к решению.
Балансировка худшего случая
Большинство головоломок относятся к задачам минимизации, когда требуется уменьшить количество действий или выполнить что-либо определенное количество раз. Можно попробовать «сбалансировать» худший случай. Таким образом, если решение приведет к смещению худшего случая, можно выполнить балансировку худшего случая. Рассмотрим конкретный пример. Задача о «девяти шарах» — классика собеседования.
У вас есть 9 шаров — восемь имеют одинаковый вес, а один более тяжелый. Вы можете воспользоваться весами, позволяющими узнать, какой шар тяжелее. Требуется найти тяжелый шар за два взвешивания.
Алгоритмический подход
Если вы не можете сразу найти решение, попробуйте использовать один из методов алгоритмизации. Головоломки — это те же задачи алгоритмизации, из которых убраны технические нюансы. Думайте, упрощайте, обобщайте, сопоставляйте с шаблоном, используйте базовый случай — всё это может пригодиться.
Список задач
Интересные задачи и решения к ним можно найти здесь: Головоломки: задачи и разбор.
Правила и шаблоны
В большинстве случаев попробуйте найти и записать правила или шаблоны, которые помогут вам решить задачу. Да-да, именно записать — это поможет запомнить их и использовать при решении задачи. Давайте посмотрим простой пример.
У вас две веревки и каждая из них горит ровно один час. Как их можно использовать, чтобы определить, что прошло 15 минут? Более того, плотность веревок не является константой, поэтому необязательно, что половина веревки будет гореть ровно полчаса. Совет: остановитесь и попытайтесь решить задачу самостоятельно. В крайнем случае, прочитайте этот раздел медленно и вдумчиво. Каждый абзац будет приближать вас к решению.
Открыть спойлер
Балансировка худшего случая
Большинство головоломок относятся к задачам минимизации, когда требуется уменьшить количество действий или выполнить что-либо определенное количество раз. Можно попробовать «сбалансировать» худший случай. Таким образом, если решение приведет к смещению худшего случая, можно выполнить балансировку худшего случая. Рассмотрим конкретный пример. Задача о «девяти шарах» — классика собеседования.
У вас есть 9 шаров — восемь имеют одинаковый вес, а один более тяжелый. Вы можете воспользоваться весами, позволяющими узнать, какой шар тяжелее. Требуется найти тяжелый шар за два взвешивания.
Открыть спойлер
Алгоритмический подход
Если вы не можете сразу найти решение, попробуйте использовать один из методов алгоритмизации. Головоломки — это те же задачи алгоритмизации, из которых убраны технические нюансы. Думайте, упрощайте, обобщайте, сопоставляйте с шаблоном, используйте базовый случай — всё это может пригодиться.
Список задач
Интересные задачи и решения к ним можно найти здесь: Головоломки: задачи и разбор.
