Комментарии
developers.org.ua решили опубликовать замечательный цикл “Трудные вопросы на собеседовании” на русском языке. Каждую неделю будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую мы преследуем этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Итак!..
Задача #1
Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.
У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.
Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).
Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?
Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?
Источник http://www.developers.org.ua
← Вернуться к журналу «CHaos»
Мы такие задачки в ЕГЭ по информатике решали) только там совсем другие игры били, но суть похожая - определить стратегию))
ну и CHaos!!! Столько я времени потратила... вместо учебы тут сидела и анализировала))) Совести у тебя нет!!)) Зацепил задачкой..)))
- 0RI0N: Тим, CHaos уже написал, что
выживают в лучшем случае все, в худшем - одного первого гнома убивают.
Так что тут просто сторатегия минимизации потерь. И убьют первого гнома или нет - это не суть важно для цели задачи (хотя тут вероятность рассчитать можно при наличии данных о кол-ве гномов, кол-ве белых и черных шляп...Но это уже задачка для мехматовцев, а не для собеседования по русскому языку)))) ).
- Мдя... Суть стратегии Оля уже выложила, и это верно, но вот задачка в том, чтобы сохранить жизнь первому гному...) Его шанс остаться в живых 1:2) Так что блин....)) Иначе как удачей самого высокого это не объяснить))
Во маги офигели совсем! Даже фашисты помойму так не развлекались как эти маги! Я считаю что для того чтобы минимизировать количество убиенных гномов - нужно всей гномячей деревней собраться и сжечь деревню магов нафег! Но есть и другой путь - гномам нужно всего лишь раз в год, когда приходят маги, валить с деревни в пещеры какие-нить там или в лес, и там пережидать.
- 1-ый видит, что у второго ЧЕРНЫЙ и говорит: ЧЕРНЫЙ
2-ой слышит слово "ЧЕРНЫЙ" и теперь знает, что у него ЧЕРНЫЙ. Смотрит на 3-его, видит:
а) что у того ЧЕРНЫЙ и спокойно говорит "ЧЕРНЫЙ" - тем самым и свой правильно называет, и след. дает понять, что у него черный
б) что у него БЕЛЫЙ, говорит: "НЕ БЕЛЫЙ" - тем самым дает понять, что у него не белый, а черный (ибо третьего не дано и остается жить) и при этом следующий слышит слово БЕЛЫЙ, понимая, что у него БЕЛЫЙ..
И т.д... про 3-его.. тут НЕ может получиться, что убьют кого-то еще, кроме первого... и то, первому может повезти, и он угадает свой цвет..
- Не ангел, если гном видит цвет последующего и назвает его, то не факт, что у него такой же - его могут убить - и так с любым гномом - так что это самый худший вариант с максимальным кол-вом убитых
Ндя.. а меня на последнем собеседовании по железу гоняли...
- стратегия проста начиная с самого высокого по цепочке гномы называют цвет шляпы впереди стоящего, в хучшем случае гномы потеряют только самого высокого
- перечитай повнимательнее то, что я написала, потому что подход правильный на мой взгляд.. а уж какая еще есть вариация..)))
- и вообще, так гном будет и свой цвет знать и следующему сможет подсказать его цвет
- это почему это?? если они знают, что надо ориентироваться на цвет, который произносит предыдущий гном, а не на то, с частицой "не" или без нее это все произносится, но все нормально)
Нет, Оля, в твоем случае потери могут быть до 50%
- самый высокий гном видит, какого цвета шляпа у того, который ниже его ростом и стоит следующим - вот этот цвет он и должен назвать... Тогда второй гном с конца шеренги будет знать цвет своей шляпы.. При этом, если он видит, что у след.гнома цвет такой же, то он смело называет "Черный (белый)".. А вот если он видит, что у след.гнома цвет не такой, какой у него, то просто-напросто добаляет частицу "не" и называет не свой цвет))
т.е. если у него белый цвет, а у след.гнома черный, то он говорит "не черный" - таким образом свой цвет он называет правильно, а след.гном слышит слово "черный" и теперь знает, что шляпа у него черная.. и т.д.)))
Вобщем, такой вот бред мне в голову пришел - так есть вероятность, что убьют 1 гнома))) а может ему повезет и у него будет такой же цвет, как и у следующего)
- Я честно скажу задачку не решил) но ответ понравился!
Подсказка: Правильно ответ: выживают в лучшем случае все, в худшем - одного первого гнома убивают.
А вот как это реализовать думайте:)