Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Свободное общение _ Трудные вопросы на собеседовании

Автор: compiler 6.06.2008 1:08

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

Цитата
Задача #1

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

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

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

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

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

В атаче задание на ангельском.
Источники(русскоязычный и англоязычный), приложены из-за моральных соображений, просьба не смотреть..
Спойлер (Показать/Скрыть)

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


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

Автор: klem4 6.06.2008 1:53

Спойлер (Показать/Скрыть)

Автор: compiler 6.06.2008 2:22

мое решение:

Спойлер (Показать/Скрыть)

Цитата(klem4 @ 5.06.2008 21:53) *
ps идея хорошая, если можешь выкладывай задачи дальше.
будут читать - буду выкладывать, ну и конечно, если Скакунов будет продолжать переводить..

Автор: andriano 6.06.2008 15:39

Спойлер (Показать/Скрыть)


Автор: compiler 6.06.2008 18:00

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

Автор: Michael_Rybak 6.06.2008 19:05

скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян smile.gif ждем еще.

Автор: compiler 6.06.2008 19:24

Цитата(Michael_Rybak @ 6.06.2008 15:05) *
скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян smile.gif ждем еще.
ну.. Постить сразу ответ, можно только если он есть на русском(мой перевод врядли кого устроит))), а на русскоязычном сайте выкладывают решение через неделю после условия(можно конечно дать им фору и брать уже с решением). А так, если очень не терпиться, есть ссылка на оригинал, есть гугл.. + если я буду выкладывать с решением, то сам буду его знать(
Насчет бояна, на англ. сайти задачи датированы 2001 годом, и это не значит что они не появились раньше, поэтому.. Но, надеюсь, следующии будут менее известны)

Автор: мисс_граффити 9.06.2008 5:01

Спойлер (Показать/Скрыть)

Автор: compiler 12.06.2008 22:29

Прошу прощение за задержку.. были проблемы с сетью + экзамены. Вобщем Вот решение в переводе того же Скакунова..

Спойлер (Показать/Скрыть)
оригинальное решение( by jliszka )
Спойлер (Показать/Скрыть)


Чесно говоря, я его не понял( Может кто объяснит?

Для следующий задачи создам следующую тему ( http://forum.pascal.net.ru/index.php?showtopic=22192 ), куда буду помещать все четные задания, а в этой теме неделя для обсуждения решения..

Автор: andriano 12.06.2008 23:49

Не понял чего?
Если английский текст, то по-русски написано то же самое.
Если же алгоритма, то по сути он не отличается от того, что предложила мисс граффити.

Автор: compiler 13.06.2008 0:09

отредактированнно.. проблема с алгоритмом.. подумаю еще сам.. может что-то не так понял..

Автор: мисс_граффити 13.06.2008 6:53

То же самое, только наоборот )) У них черные единицы, белые нули.

Автор: compiler 13.06.2008 13:59

Так и не понял ;(
Объясните пожалуйста на конкретной последовательности..

Автор: compiler 16.06.2008 22:42

Цитата
Задача #3

Как вы обернете порядок слов (не символов) в строке длиной n при постоянном объеме дополнительной памяти (constant extra space) за линейное время (linear time)?




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

Автор: мисс_граффити 17.06.2008 5:57

про первую задачу.
допустим, у нас 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

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

Автор: compiler 17.06.2008 15:18

Цитата(мисс_граффити @ 17.06.2008 1:57) *
про первую задачу...
спасибо.. понял.. give_rose.gif