Задачи, размещенные в этом посте, используются на собеседовании при приеме на работу в кампании Microsoft и Intel. Проверьте, взяли бы вас на работу в это софтверные гиганты или нет.
Задача 1.
Человек хочет пройти через туннель для поездов. Он начинает свой путь в начале туннеля, и когда он пройдет четверть пути, то услышит, что сзади приближается поезд. Неизвестно - как быстро поезд едет, и на сколько он далеко.
Известно только вот что:
Задача 2.
На далёком острове существует популяция разноцветных хамелеонов. 13 красных, 15 зеленых и 17 синих. В каждый момент времени встречаются два хамелеона разных цветов, и меняют цвет на третий. То есть если встретились синий и зеленый, то они меняют оба цвет на красный. Может ли получиться, что на острове все хамелеоны окажутся одного цвета, и почему?
Задача 3.
Существует небольшой город-королевство в несколько сотен жителей. В городе установился матриархат. В отношении населения городка верны следующие утверждения:
Задача 1.
Человек хочет пройти через туннель для поездов. Он начинает свой путь в начале туннеля, и когда он пройдет четверть пути, то услышит, что сзади приближается поезд. Неизвестно - как быстро поезд едет, и на сколько он далеко.
Известно только вот что:
- Если человек развернется и побежит назад, то он достигнет начала туннеля одновременно с поездом
- Если человек побежит вперед, то конца туннеля он также достигнет одновременно с поездом
Задача 2.
На далёком острове существует популяция разноцветных хамелеонов. 13 красных, 15 зеленых и 17 синих. В каждый момент времени встречаются два хамелеона разных цветов, и меняют цвет на третий. То есть если встретились синий и зеленый, то они меняют оба цвет на красный. Может ли получиться, что на острове все хамелеоны окажутся одного цвета, и почему?
Задача 3.
Существует небольшой город-королевство в несколько сотен жителей. В городе установился матриархат. В отношении населения городка верны следующие утверждения:
- Каждая женщина поступает очень логично, и знает, что тоже самое можно сказать об остальных женщинах в городе.
- Каждая женщина знает всё о поведении каждого мужчины в городе, за исключением поведения своего мужа, если она замужем. Никто в городе не имеет права говорить с женщиной о её муже.
- В городе существует обычай - если женщина узнает о том что муж ей изменил, она обязана той же ночью вывести его на центральную площадь и застрелить. Согласно обычаю жители поступают всегда.
- В городе сорок неверных мужей.
Вопрос - что произойдет после этого сообщения, и когда?
Задача 4.
У Вас есть два яйца неизвестной птицы, и есть доступ в стоэтажное здание. Каждое из яиц имеет скорлупу из неизвестного материала, оно может разбиться при падении с первого этажа, а может и не разбиться при падении с сотого этажа здания. Оба яйца одинаковы. Как определить, при падении с какого этажа яйцо разобьется? Нужно постараться определить этаж за минимальное количество тестов.
Задача 5.
В закрытой комнате есть три лампочки. Выключатели от этих лампочек находятся снаружи комнаты. Вам разрешается как угодно манипулировать выключателями. После этого вы можете войти в комнату, не трогая выключателей. Как определить, какой выключатель какой лампочкой управляет?
Этот пост -- заказной. Меня его попросила написать одна моя хорошая знакомая, с которой мы знакомы такое количество лет. что аж страшно становится. Как говорит в таких случаях мой младший брат -- "Да ну нафиг. Столько и не живут". Живут... к сожалению. Ладно, это было лирическое…
Comments
1. Через четверть пути поезд всё равно окажется у входа (куда бы человек ни побежал). Сейчас он на четверти пути, значит, когда он окажется на середине пути, поезд окажется в начале. И оставшийся путь они проделают за одно время — поезд весь путь, а человек половину. Значит, поезд движется вдвое быстрее человека.
3. Очень интересная задача. Ответ — в первые 39 ночей ничего не произойдёт, а на сороковую все женщины выведут своих неверных мужей на площадь. Я бы вряд ли догадалась, но встречала объяснение похожей задачи на Khan Academy. Проще всего понять это, если представить, что неверный муж всего один. Его жена знает, что у других женщин мужья не изменники, значит, единственный изменник — её муж. При таком раскладе она в первую же ночь выведет его на площадь. Если же неверных мужей два, то каждая обманутая жена знает всего об одном. В первую ночь она предполагает, что жена изменника, следуя описанной выше логике, выведет своего мужа на площадь. Когда же этого не происходит, несчастная догадывается, что в городе есть ещё один казанова. А поскольку про своих подруг она всё знает, то остаётся одно — что этот второй изменник — её собственный муж. Обе женщины так рассуждают, поэтому выведут своих мужей на площад на вторую ночь. И так далее: расправа всегда будут осуществляться через то число ночей, которое соответствует количеству неверных мужей.
4. Я думаю, тут стоит начать так же, как при угадывании любого числа: всё время выбирать среднее, пока не разобьётся первое яйцо, а потом (поскольку оставшимся яйцом рисковать нельзя), придётся перебирать по одному. То есть берём первое яйцо и сначала бросаем его с пятидесятого этажа. Если не разбилось — бросаем с двадцать пятого и так далее. Как только яйцо разбилось, мы идём на самый нижний из “проверенных” этажей и оттуда уже бросаем второе яйцо, пока оно не разобьётся.
На N4 ответ неверный. См. https://dxdy.ru/topic9229.html
Edited at 2019-02-07 12:38 am (UTC)
Оба яйца одинаковы. Как определить, при падении с какого этажа яйцо разобьется?
Бросая яйца с 100 этажа можно обойтись вообще одним испытанием. Мы получили ответ: с 100-го яйцо разбивается. Если нет- значит ото не разбивается вообще, но задача решена.
Второй вопрос: А разбиение вообще зависит от этажа или это процесс случайный?
оно может разбиться при падении с первого этажа, а может и не разбиться при падении с сотого этажа здания.
Тогда по этажам можно вообще не бегать, а тупо кидать вверх. Ну, если автор начнёт передёргивать с условиями, вводя очень большие яйца- кидать будем с первого этажа.
Не заглядывая в справочники по закону равномерного распределения и числу испытаний и прочим методам Монте-Карло, рискну предположить, что оба яйца наверняка можно грохнуть раза с 6-7.