IPB
ЛогинПароль:

> Трудные вопросы на собеседовании, hard interview questions
сообщение
Сообщение #1


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Добрый день!
Итак, один из ресурсов рунета решил опубликовать цикл ”Трудные вопросы на собеседовании” на русском языке. Каждую неделю там будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую преследуют этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений.
Всего 33 вопрса. На англоязычном оригинали есть уже все ответы, но найти и посмотреть не спортивно, имхо... Русскоязычный аналог начал публикации 2.06. Перевод от Скакунова Александра.
В общем почему бы не продублировать цикл здесь?
Цитата
Задача #1

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

У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.

Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).

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

Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?

В атаче задание на ангельском.
Источники(русскоязычный и англоязычный), приложены из-за моральных соображений, просьба не смотреть..
Говорю сразу, я ответы не смотрел да и нет их еще на русском, а мой английский не тот)... в любом случае, пытаемся ответить сами!

Сообщение отредактировано: compiler -


Прикрепленные файлы
Прикрепленный файл  01.txt ( 779 байт ) Кол-во скачиваний: 357


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


про первую задачу.
допустим, у нас 5 гномов.
им надели колпаки и построили в такой ряд:
ч ч б ч б
то есть
1 1 0 1 0
последний гном считает
1 xor 1 xor 0 xor 1 = 1
говорит: черный
его убивают (не повезло).

предпоследний получает такую задачу:
1 xor 1 xor 0 xor х = 1
(х - его шляпа. цвет неизвестен ему)
находит, что х=1 (черный).

третий гном:
1 xor 1 xor х xor 1 = 1
находит, что х=0

так же поступают оставшиеся гномы


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
compiler   Трудные вопросы на собеседовании   6.06.2008 1:08
klem4   Хах, давно уже знаю эту задачу, вроде даже на фор…   6.06.2008 1:53
compiler   мое решение: каждый гном говорит цвет шапок, кото…   6.06.2008 2:22
andriano   Разбиваются на пары, один из пары (кто стоит сзади…   6.06.2008 15:39
compiler   И вот еще вопрос по оформлению темы, стоит ли скры…   6.06.2008 18:00
Michael_Rybak   скрытый ответ, думаю, можно постить сразу. идея хо…   6.06.2008 19:05
compiler   скрытый ответ, думаю, можно постить сразу. идея хо…   6.06.2008 19:24
мисс_граффити   считаем белый истиной, черный - ложью (можно наоб…   9.06.2008 5:01
compiler   Прошу прощение за задержку.. были проблемы с сетью…   12.06.2008 22:29
andriano   Не понял чего? Если английский текст, то по-русски…   12.06.2008 23:49
compiler   отредактированнно.. проблема с алгоритмом.. подума…   13.06.2008 0:09
мисс_граффити   То же самое, только наоборот )) У них черные едини…   13.06.2008 6:53
compiler   Так и не понял ;( Объясните пожалуйста на конкретн…   13.06.2008 13:59
compiler   RE: Трудные вопросы на собеседовании   16.06.2008 22:42
мисс_граффити   про первую задачу. допустим, у нас 5 гномов. им на…   17.06.2008 5:57
compiler   про первую задачу...спасибо.. понял.. :give_rose:   17.06.2008 15:18


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 23:15
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name