Собеседование для инженеров (загадка)

[isnull]

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


Суть в том, что нам нужно получить наиболее элегантный и креативный алгоритм решения, а решений может быть много.

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

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

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

Надеюсь я ничего не упустил :)

Варианты решения:

[img width=300]http://igraem-s-mamoi.ru/wp-content/uploads/2016/05/vlevo.jpg[/img]

Спойлер

1. Если в шеренге никого нет, то просто встать
2. Если в шеренге все цвета камней одинаковые, то встать в начале (или в конце, без разницы)
3. Если в шеренге два гнома с разными цветами, то встать между ними

Изменено 26 мая, 2017 пользователем isnull

[woldtar]

Снять шляпу и посмотреть какого цвета камень. Условием не запрещено. Зачем усложнять? :)

[isnull]

Снять шляпу и посмотреть какого цвета камень. Условием не запрещено. Зачем усложнять? :)

Вы нам не подходите, спасибо за ваше время :)

Есть основное условие: - Гномы не знают, какой у них в шапке камень
Это бьет все зеркала, отражения в воде, в глазах, снимание и надевание.

[woldtar]

Снять шляпу и посмотреть какого цвета камень. Условием не запрещено. Зачем усложнять? :)

Вы нам не подходите, спасибо за ваше время :)

Есть основное условие: - Гномы не знают, какой у них в шапке камень
Это бьет все зеркала, отражения в воде, в глазах, снимание и надевание.

Даже отражение в глазах не проходит?)

[isnull]

Даже отражение в глазах не проходит?)

Просто отсортируйте массив элегантным решением :-> И не заморачивайтесь ролевой составляющей

[woldtar]

И как "Варианты решения" должны прийти в голову всем гномам сразу???

[isnull]

И как "Варианты решения" должны придти в голову всем гномам сразу???

Это единый набор действий для всех. По условию задачи каждый гном им обладает. Один на всех

[woldtar]

И как "Варианты решения" должны придти в голову всем гномам сразу???

Это единый набор действий для всех. По условию задачи каждый гном им обладает. Один на всех

Бредовая задача, если бы был программистом, то может решил бы, а так любую по физике легко решу.

[Arioh]

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

[Baikal]

Вообще не надо знать,какого цвета камень :)
Главное,чтобы в одной группе все были одинаковые
Алгоритм простой:из толпы гномов выходят по одному на видное всем место
Когда к первому гному подходит второй,он спрашивает у всех окружающих,одинаковый или нет у него камень
Если одинаковый,остаётся,если нет - переходит в другое место
Соблюдаются условия: нет лидеров(все лидеры),каждый выполняет одинаковый набор действий,не знают какого цвета камень и не сообщают друг другу об этом

[isnull]

Когда к первому гному подходит второй,он спрашивает у всех окружающих,одинаковый или нет у него камень

"Гномы не могут сообщать друг другу, какой камень в шапке (ни жестами, ни знаками, ни вербально, ни ментально)"

Эта загадка для инженеров, для программистов. Элемент не может спрашивать другие элементы ни о цвете, ни об одинаковости. Алгоритм должен быть простым и красивым.

Зачем тогда спрашивать про одинаковость, если уже пусть они друг друга расставят по цветам, при этом они тоже типа не сообщат какой цвет. Просто молча расставят по цветам.
Если тебе говорят, что ты имеешь одинаковый цвет вот с ним, то тебе сообщают, что у тебя тоже красный, или тоже зеленый. Изменено 29 мая, 2017 пользователем isnull

[woldtar]

Вот где задача для инженеров! Ну какой кусок выгоднее? Обоснуйте кто.

[isnull]

woldtar, надо вычислить площадь сектора круга для обоих кусков (S=Pi*r^2*(угол сектора / 360 град))

Выходит, что площадь куска за 1.5 долл ~ 118 кв. см
Площадь куска за 1.7 долл ~ 127 кв. см

Пицца диаметром 30 см стоит 9 баксов, а ее площадь около 708 кв. см
Пицца диаметром 36 см стоит 13.6 баксов, а ее площадь около 1016 кв. см

В итоге, большая пицца стоит дороже в 1.5 раза, но ее площадь больше в 1.4 раза. При этом стоимость 1 кв. см маленькой пиццы стоит 1.27 цента, а 1 кв. см большой пиццы = 1.34 цента.

Ответ: выгоднее покупать маленькую пиццу за 9 баксов, так как ее площадь дешевле

[shrike74]

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

---

Добавлено: 29-05-2017 21:00:10

---

блин, бегло прочитал и не заметил что варианты уже есть в нулевом посте. Изменено 29 мая, 2017 пользователем shrike74

[Archikzn]

По условиям задачи нет ограничения на подходы к Дракону на проверку. Отсюда вывод что они могу меняться местами постоянно пока один раз случайно не совпадет по камням и тогда Дракон их выпустит. 8->

[akzest]

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

[Posobil]

Гномы должны встать в кольцо, и каждый смотреть в затылок впереди стоящему. Если гном видит перед собой гнома с красным камнем - он говорит сделать ему шаг в право (за пределы кольца), если с зеленым - шаг в лево. Получается два кольца внешнее и внутреннее, красное и зеленое соответственно

[Timofei]

Первые три гнома встают в любом порядке.А каждый последующий в промежуток между разноцветными.Так они разделят себя на две части .С одной стороны окажутся все красные,а с другой зелёные.

Без гугла!

[Mint]

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