Poll-decor.ru

Пол Декор
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Самая интересная часть собеседования тестировщика: задачи на логику

Самая интересная часть собеседования тестировщика: задачи на логику

Иллюстрация - задачи на собеседование тестировщика

Собеседование на должность тестировщика ПО включает несколько этапов: интервью с HR-специалистом, с техническим экспертом, а также проверка навыков логического мышления.

Сначала вас попросят рассказать общую информацию о себе, о мотивации работы в QA и зададут базовые вопросы на понимание предметной области. Это нужно, чтобы понять уровень ваших знаний, умение применять их на практике и оценить готовность обучаться и развиваться в новой сфере.

Затем технический эксперт проверит ваши аналитические способности, задав несколько вопросов на логику. Такие задания обычно нестандартные и требуют размышления. В этот момент не нужно паниковать и молчать. Не знаете ответ наверняка? Рассуждайте вслух, даже если задача кажется очень трудной.

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

Один раз на стройке пропали кирпичи. Прораб, возмущённый тем, что кирпичи пропали без его ведома, решил выяснить кто же решился на такой дерзкий поступок. Выяснилось, что кирпичи могли украсть или монтажник Выпивайко или крановщик Наливайко или моляр Закусывайко. Прораб, с редкой фамилией Иванов, выяснил, что укравший кирпичи был левша. Каждый из трёх подозреваемых сделал по два утверждения:

Выпивайко:
Я не левша.
Я не брал кирпичи.
Наливайко:
Я левша.
Я не брал кирпичи.
Закусывайко:
Я не левша.
Левша брал кирпичи.

Прораб обнаружил, что двое из подозреваемых сказали правду и только один из подозреваемых не был левшой. Прораб Иванов конечно сразу выяснил кто украл кирпичи и в наказание послал его в магазин за различными напитками для празднования этого факта. Кому же пришлось бежать в магазин?

Кофе с молоком

image

Очень полезная задачка. Можно долго выписывать уравнения, а можно понять, что ответ очевиден. Есть два одинаковых стакана, в которые налито поровну: в один — молоко, в другой — кофе. Из первого стакана переливают ложку молока в стакан с кофе. Потом размешивают, и из второго стакана обратно в первый переливают ложку кофе с молоком. Чего теперь больше: молока в кофе или кофе в молоке?

Одинаковое содержание молока в кофе и кофе в молоке.

image

Когда центрального отопления и водогрейных колонок еще не было, воду для ванн нагревали на кухонной плите. В те времена однажды кухарка нагревала на плите воду в большой кастрюле, чтобы долить ее в ванну, где уже было некоторое количество воды комнатной температуры. Заметив это, дворецкий сказал ей: «Ты что, не понимаешь, что, чем дольше ты греешь воду на плите, тем холоднее окажется вода в ванне, когда ты вольешь туда нагретую воду?» Он был прав. Почему?

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

Интересные задачи, которые задают на собеседовании

Всего мы рассмотрим пять задач.

Комната с лампочками

Условие: Имеется закрытая комната, в которой есть три лампочки. С внешней стороны комнаты имеется три выключателя. Вам нужно узнать, какой выключатель включает каждую из лампочек. Но в комнату вы можете зайти только единожды.

Решение: С точки зрения менеджера, вы можете привлечь к решению своих сотрудников, однако необходимо решить задачу самостоятельно. Как нужно рассуждать: наша комната закрыта и снаружи лампочки не видны. При включении одной и выключении остальных мы можем узнать только об одном выключателе. Но нам нужно определиться с двумя другими. Поэтому, нужно сделать что-то, чтобы стало ясно, как лампочки и выключатели взаимосвязаны.

Вот один из самых интересных вариантов решения: состояний лампы всего два – либо «горит», либо «не горит». Состояний выключателя тоже два – либо «включен», либо «выключен». Ламп всего три. Рассуждая логически, чтобы решить задачу, нужно одну лампу выключить, вторую включить, но вот что делать с третьей – непонятно.

Выход следующий: подвести к одному из выключателей напряжение в 380 вольт – лампочка, соответственно, перегорит, и это будет заметно. Получается, что добавляется новое состояние лампы – либо «исправна», либо «не исправна». Отсюда вывод, что лампочка может теперь быть в трёх вариантах состояний – «горит», либо «не горит», «исправна, но не горит», либо вообще «неисправна». Размышляя далее, вспоминаем, что если лампа включена, то она будет нагреваться, и при выключении некоторое время ещё будет тёплой. Получаем новое состояние: лампа либо «тёплая», либо «холодная».

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

Читайте так же:
Концевые выключатели каталог размеры

Хотите научиться решать такие задачи? Сегодня курс «Когнитивистика» со скидкой 20%! Промокод — SOBES.

Котлеты на сковороде

Условие: Имеется две сковородки и три котлеты. Чтобы обжарить одну котлету с одной стороны, требуется минута. Одна сковородка вмещает лишь одну котлету. Какой минимум времени необходим, чтобы обжарить все котлеты полностью?

Решение: Итак, размышляем обычно: чтобы пожарить две котлеты с двух сторон сразу, нам понадобятся две минуты. После этого мы уберём две котлеты и начнём жарить третью. Получается, что нужно ещё две минуты. Так, понимаем, что всего нам нужно на обжарку котлет четыре минуты. Но это неверно, т.к. есть способ уложиться в три минуты.

Переходим к креативному мышлению: есть две сковороды, на которых мы можем жарить одновременно. Начиная с обжарки двух котлет, мы сразу же займём обе сковороды, и после обжарки двух котлет одна сковорода останется незадействованной. Чтобы сократить время жарки, нужно её задействовать. Но как?

Мы можем разделить весь процесс жарки на обжаривание котлет с двух сторон, и получим шесть этапов. Если мы возьмём эти шесть этапов, занимающих, в общей сложности, шесть минут, и вспомним, что у нас имеется две сковороды, то можно сделать логический вывод, что на весь процесс жарки нам может хватить трёх минут – нужно только понять алгоритм, который совсем несложен.

Последовательность действий должна быть такой: кладём жарить две котлеты, но одну после первой минуты убираем со сковороды, и кладём сырую. Через минуту одна из первых двух котлет дожарится и на её место нужно будет положить первую – недожаренную. На третьей минуте дожарятся обе оставшиеся котлеты.

Хотите научиться решать такие задачи? Сегодня курс «Когнитивистика» со скидкой 20%! Промокод — SOBES.

Золотая цепочка

Условие: На постоялый двор нанёс визит странник. У него нет с собой денег, но есть золотая цепочка, состоящая из шести звеньев. Хозяин двора согласен взять оплату жилья в виде одного звена цепочки на каждый день, но при условии, чтобы распиленным оказалось только одно звено. Причём, оплата должна поступать именно ежедневно, т.к. странник не хочет вносить предоплату, а хозяин не готов к оплате по факту прожитых в его доме дней. Как должен странник распилить цепочку, чтобы была возможность вносить оплату ежедневно в течение пяти дней?

Решение: Разъединить шесть звеньев и получить пять целых по отдельности, распилив лишь одно звено, невозможно, т.к. звеньев шесть, а соединений между ними пять. Поэтому, для получения отдельных целых звеньев нужно будет сделать минимум три разреза.Но снова включаем креативное мышление: у нас есть термин «оплата», но, исходя из условий задачи, нет требования, чтобы странник оплачивал проживание только по одному звену. Однако есть требование, чтобы звеньев у хозяина каждый день становилось на одно больше. Далее нужно понять суть: и хозяин и странник могут обмениваться, а хозяин также может давать сдачу. Отсюда следует простое решение.Распиливаем конкретно третье звено, чтобы получить разменную «монету» в 1, 2 и 3 звена. На первые сутки странник платит одним звеном, на вторые – платит двумя, но забирает одно первое, на третьи – платит тремя, но забирает два вторых и т.д. до конца срока пребывания. В тоге мы имеем только одно распиленное звено, пять дней проживания и довольного хозяина.

Хотите научиться решать такие задачи? Сегодня курс «Когнитивистика» со скидкой 20%! Промокод — SOBES.

Горящие верёвки

Условие: Есть две верёвки и коробок со спичками. О каждой верёвке мы знаем, что если их поджечь, то они полностью сгорят за один час. Нам нужно отмерить пятнадцать минут. Но как нам это сделать, если мы знаем, что верёвки будут прогорать неравномерно?

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

Применяем креативное мышление: берём за единицу измерения время, за которое сгорает верёвка. Это время равно одному часу, исходя из условий. Однако соотнести это время с длиной мы не можем. Но верёвок у нас есть две. По этой причине время сгорания первой верёвки мы можем соотнести с временем сгорания второй. И тут мы находим решение.

Учитывая то, что верёвка горит один час, мы делаем вывод, что её подожгли с одного из концов. Поэтому, если поджечь оба конца, она прогорит за полчаса, пусть и гореть будет неравномерно. Далее мы можем сравнить: поджигаем одну из верёвок с двух краёв, а другую – только с одного края, чтобы засечь время. Первая сгорит за полчаса. Как только она сгорела, мы сразу же должны потушить вторую. Так у нас остаётся кусок второй верёвки, который сгорит за полчаса. Если мы подожжём его с двух концов, то получим 15 минут.

Читайте так же:
Выключатель для электрического полотенцесушителя

Как порезать торт?

Условие: Имеется круглый торт. Задача заключается в том, чтобы поделить его на восемь равных кусков, сделав при этом только три разреза.

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

Теперь думаем креативно. Решение задачи может быть вполне простым. И вообще этих решений есть два. Сначала нужно понять, что поделить торт на восемь одинаковых кусков тремя разрезами нельзя, по крайней мере, традиционным способом, когда просто открывают торт и начинают его резать, т.к. тут потребуется резать четыре раза. Но количество разрезов можно уменьшить, если представить торт не плоским кругом, а воспользоваться для решения пространственным мышлением.

В первую очередь, разрезаем торт крест-накрест двумя разрезами, и получаем четыре куска. Как же нам теперь порезать их все пополам? Для этого просто берём и ставим четыре куска друг на друга, и затем режем пополам и получаем восемь кусков – это только один вариант. Второй вариант заключается в том, что мы разрезаем торт не как обычно, а в горизонтальной плоскости, т.е. поперёк. Немного странными получатся в итоге куски, но вариант всё-таки хорош, согласитесь?

Хотите научиться решать такие задачи? Сегодня курс «Когнитивистика» со скидкой 20%! Промокод — SOBES.

Надеемся, эта информация вам пригодится, и вы сможете удивить своих потенциальных работодателей на собеседовании.

Ну, и чтобы не расслабляться, вот вам напоследок ещё одна интересная задачка, но уже без решения: посреди пшеничного поля был найден мёртвый мужчина, который крепко сжимает в руках спичку. Объясните причину его смерти.

«Найти умного»: Как решать логические задачи на собеседованиях Уильям Паундстоун рассказывает о головоломках, которые используют современные компании при найме сотрудников, и объясняет, как научиться их решать.

«Найти умного»: Как решать логические задачи на собеседованиях

Если говорить о решении головоломок как особом жанре, то нельзя не признать, что он условен и стилизован в не меньшей степени, чем японский театр кабуки. Если вы не понимаете характерных для жанра кабуки идиом, вам будет трудно понять происходящее. То же относится и к «задачам без ответа», предложениям спроектировать что-либо и т.д. Как и другие интересующие нас способности, способность решать головоломки — это сочетание врождённых задатков и приобретённых навыков. На первый взгляд вопросы кажутся бесконечно разнообразными, но если вы присмотритесь внимательнее, то поймёте, что в большинстве головоломок используется небольшой набор одних и тех же когнитивных трюков, особенно часто — эффект дизъюнкции и сбивающая вас с толку формулировка проблемы. Знания об этом могут вам помочь.

Монолог или диалог

Самые трудные вопросы, применяющиеся в интервью, требуют, чтобы вы объяснили ваш подход к решению проблемы и потом дали правильный или подходящий ответ. Нужно решить, требует данный вопрос монолога или диалога. Логические головоломки обычно подразумевают монолог. Вам намеренно дают ограниченное количество информации и ожидают, что вы сами найдёте ответ. Вам трудно в этом случае получить от интервьюера дополнительную информацию, поскольку её намеренно вам не сообщили.

Во многих случаях, когда задаются вопросы о разработке дизайна и анализе кейсов (конкретных ситуациях), интервьюеры ожидают, что вы попросите дополнительную информацию. Вам понизят оценку, если вы этого не сделаете. Для вопросов о дизайне («разработайте дизайн полки для специй») нет единственно правильного ответа. Умные кандидаты понимают, что дизайн — это трудная последовательность компромиссов.

Лучший способ начать диалог, который ожидается от вас, —
это объяснить, почему «очевидное» решение неверно

Интервьюер обращает внимание, задумываетесь ли вы о том, кто будет пользоваться этой полочкой и где именно она будет находиться. Он готов отвечать, и вы в результате получите массу важной дополнительной информации. Такая беседа может продолжаться долго.

Некоторые «открытые вопросы» («Какой из пятидесяти штатов США вы бы упразднили?») похожи на пятна Роршаха, которые используют в психологических проективных тестах, — люди смотрят на эти пятна, и каждый видит в них что-то своё. Открытые вопросы намеренно неструктурированны. Для всех типов вопросов, но особенно для этих, цель вопроса — завязать получасовую беседу. Заключение о том, насколько умён данный человек, делается на основе этой беседы. Хорошим планом будет предположить, что нужен диалог с интервьюером, если только для вас неочевидно, что данный вопрос — это обычная логическая головоломка. Под диалогом я подразумеваю, что, вероятно, говорить в основном будете вы, но при этом вы можете также и задавать интервьюеру умные вопросы.

Читайте так же:
Выключатель звукового сигнала акцент

Первая мысль ошибочна

Когда речь идёт о головоломках и загадках, первый потенциальный ответ, который приходит в голову разумному человеку, — это обычно неправильный ответ. Если бы это было не так, данный вопрос не стоило бы называть головоломкой. Подобно оптическим иллюзиям, или трюкам фокусников, или уловкам мошенников, головоломки рассчитаны на то, что вас собьёт с толку ваш собственный привычный повседневный опыт. Дети — это наиболее скептическая и трудная аудитория для фокусников, люди с некоторыми повреждениями мозга не подвержены оптическим иллюзиям, и мошенникам не удается обжулить абсолютно честного человека. То, что вы не можете «с ходу» решить головоломку, просто означает, что ваш мозг работает нормально, так и должно быть, когда вы их решаете. Многие люди начинают нервничать, если ответ не приходит им в голову немедленно. Лучший способ начать диалог, который ожидается от вас, — это объяснить, почему «очевидное» решение неверно. Это не только позволит прервать молчание, но и послужит отличным средством для того, чтобы понять, в чём проблема.

Забудьте об интегралах

Это относится, конечно, только к логическим головоломкам. Ни одна из распространённых в корпоративных интервью задач не потребует от вас знания интегралов. Если вы думаете, что для решения головоломки нужны более обширные знания, чем те, которыми обладают участники телешоу, подобных «Счастливому случаю» и иже с ним, в каких-то сферах, которые прямо не относятся к той области, где вы хотели бы работать, — скорее всего, вы ошибаетесь. Есть такой тип задач, которые, на первый взгляд, требуют знания интегрального счисления, но на самом деле у них есть простое решение. Всегда старайтесь дать простой ответ. Даже если вы нашли решение при помощи высшей математики, вы можете получить невысокую оценку, так как «за деревьями не видите леса».

Ищите сложные ответы

Для вопросов с простой, всего в одно предложение, формулировкой — например, «Почему в зеркальном отражении правое и левое меняется местами?» или «Почему пивные банки сужаются вверху и внизу?» — часто требуются длинные и сложные ответы. Позаботьтесь о том, чтобы хорошо продумать эти вопросы. Вы можете получить низкую оценку, если интервьюер решит, что вы упустили что-то важное в вашем ответе. Если короткий вопрос задаётся о дизайне или тестировании («Разработайте дизайн туалетной комнаты для Билла Гейтса»; «Как вы стали бы тестировать лифт?»), то это часто означает, что вы должны попросить дополнительную информацию от интервьюера.

«Безупречно логичные существа» не похожи на людей

Во многих логических головоломках речь идёт о «безупречно логичных существах» (БЛС). Примером могут служить задачи о супружеских изменах в деревне или о пиратах, которым нужно поделить золотые монеты. «Безупречно логичный» — это кодовое слово, которое понятно любителям головоломок, но непонятно тем, кто не входит в их круг. Если вы слышите такую кодовую фразу, это значит, что при решении этой задачи вам нужно забыть практически обо всём, что вы знаете о людской психологии. Вам нужно придерживаться следующих предположений: у БЛС очень простая одномерная мотивация, они озабочены только тем, чтобы получить как можно больше денег, убежать от демона, жёстко следовать какому-либо глупому закону и т. д.

большинство людей не может найти решение, потому
что считает, что им не хватает для этого информации

Всё остальное для них неважно. Следовательно, БЛС никогда не оказывают дружеских услуг — каждый из них сам за себя. БЛС никогда не отвлекается, никогда не делает ошибок, никогда ничего не забывает.

Для поступков обычных людей всегда характерна неопределённость. Это значит, что подразумеваемое решение головоломок, в которых действуют БЛС, абсолютно нереалистично. Они обычно формулируются так: A приходит к выводу, что B придёт к выводу, что C придёт к выводу, что D. и т. д. Такое никогда не случится в реальном мире. Вы можете использовать это как подсказку. Когда вы слышите о безупречно логичных существах, то решение почти всегда подразумевает рассуждения БЛС о других БЛС (или вы должны рассуждать так о самих себе, когда решаете задачи, в которых задаётся вопрос: «Что вы станете делать в такой ситуации?»).

Перечисляйте гипотезы

Подумайте о том, что произойдёт, если вы будете последовательно одно за другим отвергать эти предположения. В самых хитрых и сложных головоломках неверные предпосылки и предположения могут выглядеть так естественно, что вы даже вряд ли задумаетесь о них как о предположениях. И всё же стоит попробовать. Просмотрите список и предположите для каждого из них, что верно обратное. Помогает ли это решать задачу? Если вам повезёт, то вы увидите, что есть такое предположение, что, если от него отказаться, задача окажется решаемой. Даже если это вам не поможет и вы не решите задачу, мнение интервьюера о вас улучшится. Он увидит, что вы понимаете роль изменений формулировки проблемы для решения задач.

Читайте так же:
Концевые выключатели конструкция схемы

Подробности не нужны

Почти всегда то, что мы называем логическими головоломками, использует один и тот же трюк, а именно: большинство людей не может найти решение, потому что считает, что им не хватает для этого информации. Если головоломка — это дизъюнкция, вам неизвестно, что выбрать, одно или другое, и вы не знаете, как найти решение, вам нужно быть готовым методично продумать все возможные варианты и следствия. Предположим, что верен вариант Х — какие вы сможете сделать выводы? Допустим, что это Y — к каким заключениям можно прийти в этом случае? Вы почти всегда обнаружите, что этот способ рассуждения поможет выйти из тупика, и окажется, что вам не нужна для того, чтобы решить задачу, та самая «недостающая информация». Подумайте об этом так: если мост взорван, вам придётся переплыть реку. К счастью, вам никогда не нужно будет плыть очень долго (ведь мосты обычно строятся в самых узких местах рек).

Найдите нетривиальный ответ

Это в особенной степени важно при ответах на открытые вопросы, для которых не существует «правильных ответов». Интервьюеры много раз выслушивали обычные ответы на эти вопросы. Когда Сполски попросил одного из кандидатов на работу в Microsoft разработать дизайн полочки для специй для слепого человека, этот кандидат решил, что для слепого будет удобнее не полочка для специй, расположенная на уровне груди или лица, а выдвижной ящик для специй на уровне пояса. Он считал, что вместо того, чтобы искать полку со специями на ощупь, а потом, подняв руку, пытаться прочесть текст, написанный шрифтом Брайля, гораздо удобнее подойти к кухонному столу, найти нужный ящик, выдвинуть его и спокойно прочесть надписи на крышках баночек со специями, скользнув по ним пальцами. Такое эргономичное решение раньше никто из кандидатов не предлагал.

Также впечатляющим было и то, что кандидат эффективно переформулировал проблему. «Полочка для специй» не обязательно должна быть именно полочкой, если есть основание использовать другой дизайн». Сполски рассказывает: «На основании этого единственного ответа я принял на работу кандидата, который стал одним из лучших менеджеров программ в команде, разрабатывавшей Excel». Есть много примеров, которые убеждают меня в том, что интервьюеры не просто ценят, а, пожалуй, даже чрезмерно ценят оригинальные ответы. Может быть, это связано со скукой. Вы знаете, что некоторые простаки пытаются привлечь внимание работодателей, рассылая очень яркие резюме? Такой приём обычно не работает, но во время интервью творческий и хороший ответ поможет вам выделиться среди других кандидатов. Только позаботьтесь о том, чтобы это был действительно хороший ответ.

Попробуйте решить эти головоломки из реальных собеседований. Ответы мы опубликуем завтра.

У вас есть два ведра ёмкостью 3 литра и 5 литров и неограниченный запас воды. Как можно отмерить точно 4 литра воды?

Ответ: Налейте 5 литров воды в большее ведро, а затем аккуратно переливайте воду в 3-литровое ведро, пока оно не заполнится. А теперь стоп! Если вы ничего не пролили, то теперь у вас в 5-ли- тровом ведре ровно 2 литра воды. Если вы их оставите в 5-литровом ведре, то никогда не решите эту задачу. Единственный способ продвинуться в ее решении — опорожнить 3-литровое ведро и перелить два литра из 5-литрового ведра в 3-литровое. Теперь вам нужно наполнить до краев 5-литровое ведро, а затем аккуратно отливать из него воду в 3-литровое ведро, пока оно не заполнится до краев. Таким способом вы отольете из 5-литрового ведра 1 литр воды, а это значит, что в нем останется 4 литра воды.

У вас есть восемь бильярдных шаров. Один из них «дефектный» — он тяжелее, чем остальные. Как можно за два взвешивания на весах без гирь определить дефектный шар?

Ответ: Во время первого взвешивания положите по три любых шара на каждую чашку весов. Возможно два разных исхода. Первый — чаши могут уравновеситься. В этом случае дефектный шар — это один из тех двух шаров, которые вы не взвешивали. По- этому во время второго и последнего взвешивания вы кладете на весы эти два шара — более тяжелый и есть дефектный. Другой возможный исход первого взвешивания: одна из двух чашек весов оказывается тяжелее. Дефектный шар должен быть на этой перевесившей чашке весов. Во втором взвешивании вы срав- ниваете любые два шара из этой тройки. Если один из них оказыва- ется тяжелее, чем другой, — это и есть дефектный шар. Если шары одинакового веса — дефектный шар тот, который вы не взвешивали.

Читайте так же:
Икеа патроны с выключателем

В коридоре три выключателя. Один из них включает свет в комнате, находящейся в дальнем конце коридора. Дверь в эту комнату закрыта, и вы не видите, включён в ней свет или нет. Вам нужно понять, какой из трёх выключателей контролирует освещение в той комнате. Каким образом вы можете это надежно определить, всего лишь один раз зайдя в комнату?

Ответ: Пронумеруйте выключатели 1, 2 и 3. Затем включите выключатели 1 и 2 и выключите выключатель номер 3. Подождите при- мерно десять минут. Затем выключите выключатель номер 1, включите выключатель номер 2 и немедленно отправляйтесь в комнату. Если свет там горит, значит, его включает выключатель номер 2. Если свет не горит, но лампочка теплая, его контролирует выключа- тель номер 1. Если свет не горит и лампочка холодная, его контроли- рует выключатель 3.

Послесловие

А не существует ли еще более быстрой стратегии действий?

Для 10 заключенных, возможно, и нет, а вот для большего количества — есть. Автор этой стратегии Б. Фельгенауэр назвал ее «пирамидальной».

Чтобы ее было проще понять, давайте будем считать,что количество заключенных равно степени двойки, например 64. Как и в предыдущем решении, каждый должен либо отдать сигнал (ровно один), либо собрать все сигналы. Для того чтобы им было сподручнее это делать, все ночи разбиты на участки разной «стоимости»: сначала идут «1-ночи», в течение которых все отдают либо принимают одинарные сигналы, затем идут «2-ночи», в течение которых все отдают либо принимают «двойные» сигналы, то есть каждый сигнал сообщает о двоих заключенных, затем наступают «4-ночи», «8-ночи», и т. д. Если всё происходит успешно, то когда дело доходит до «32-ночей», носителями сигналов остаются ровно двое заключенных, и в течение 32-ночей один из них отдает свой сигнал другому, после чего тот понимает, что собрал коллекцию из всех 64 сигналов, и значит, в комнате побывали все.

Разумеется, такая «успешность» может и не случиться, поэтому после 32-ночей весь цикл 1-, 2-, 4-, 8-, 16-, 32-ночей повторяется сначала.

Как же происходит отдача и прием сигналов в пирамидальной схеме?

А вот как: если во время k-ночи заключенный пришел в комнату и видит переключатель в положении ON, то он принимает k-сигнал и ставит переключатель в OFF. Если к этому моменту у него уже был один k-сигнал, то теперь у него есть два таких сигнала, или один 2k-сигнал (который он попытается либо отдать, либо снова удвоить в период 2k-ночей). Если же он пришел в комнату со своим k-сигналом и видит OFF, то он ставит ON и считает k-сигнал отданным.

Вот, в целом, и всё. Остальное уже является занудными техническими подробностями (какова должна быть продолжительность ночей определенного типа для того, чтобы передача всех нужных сигналов состоялась с достаточной вероятностью, и при этом не было слишком большой задержки перед наступлением следующего типа ночей).

Эта задача имеет самое прямое отношение к теории информации — она демонстрирует, что даже самый узкий (всего 1 бит — ON/OFF) канал позволяет передать достаточно много информации.

Кто именно является автором «тюремной» формулировки, мне неизвестно, но именно эта забавная формулировка буквально покорила мир. Кроме того, несмотря на относительную молодость задачи, она уже успела обрасти кучей самых неожиданных вариаций и усложнений. Например:

Два переключателя. В комнате, куда приводят заключенных, не один, а целых два переключателя (следовательно, выйти на свободу можно быстрее. Вопрос: насколько?)

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

Разделение передатчика и приемника. Каждую полночь начальник тюрьмы ставит переключатель в положение OFF. В час ночи он приводит туда первого заключенного, потом уводит, а в два часа ночи приводит туда же второго. Таким образом, первый из них должен «сработать» передатчиком информации, а второй — приемником.

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

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector