При таком решении, максимальная потеря 1 гном | Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Усложненная задача про гномиков |
| Автор: FoxyMia 3.9.2007, 19:33 |
| Здравствуйте! Народ помогите решить след. задачку: Людоед поймал N гномиков. И сказал, что завтра наденет на них разноцветные колпачки в K-цветов (количество колпачков неизвестно). K<N. Он поставит их в ряд, друг за другом. Каждый из гномиков будет видеть только колпачки, которые надеты на всех впереди стоящих (т.е.последний гномик будет видеть, что надето на всех гномиках впереди него, а первый гномик-никого не будет видеать ).Причем каждый гномик не увидит какого цвета колпачок надет на нём. Разговаривать и подавать знаки они не смогут. Людоед будет их спрашивать по одному, начиная с последнего гномика, какой колпачёк на нём одет. Если гномик ответит правильно, то он его отпустит, если нет - съест. За ночь гномики должны придумать оптимальную стратегию поведения, что спаслось мах. кол-во гномиков. Что они придумают? Подсказка: кол-во спасенных гномиков будет больше N/2 |
| Автор: JackYF 3.9.2007, 19:56 |
| Честно говоря, странно. Вот простой пример. У нас есть 3 гномика. Людоед выкрасил их в красный и синий цвета. Первого и второго - в красный, третьего - в синий. Первый гномик ничего не увидел и не знает - съел. Второй гномик ничего из этого (он знает, что первый в красном) не получит - его тоже съедят. Третий, естественно, спасется. Гномики смогли спасти 1 человек из 3. Это меньше половины. |
| Автор: FoxyMia 3.9.2007, 20:00 |
| Извините за неточность, людоед начинает спрашивать с конца ряда, т.е. с самого послденего гномика, котрый видит всех |
| Автор: SelenIT 3.9.2007, 20:21 |
| Напрашивается вариант, что гномики рассчитываются на "первый-второй", и каждый "первый" гномик в паре называет цвет колпачка стоящего перед ним, тот в свою очередь повторяет его ответ и заведомо спасается. Поскольку существует вероятность, что кто-то из "первых" просто угадает (ведь цвета заведомо повторяются!), то при четном кол-ве гномиков число спасенных будет не меньше половины. Но при нечетном кол-ве "первых" окажется больше, чем "вторых", и если никто из них не угадает своего цвета - условие не выполнится... буду думать дальше;). |
| Автор: FoxyMia 3.9.2007, 21:29 |
| ну да я тоже рассматривала такой алгоритм, но он дейтсвительно не спасет мах. кол-во гномиков. доалвьно просто решаеся задачка, если там всего 2 цвета колпачков-там гномики просто договариваются что последний гном сосчитав кол-во например белых колпачков, если оно четное-говорит БЕЛЫЙ (нечетное-ЧЕРНЫЙ), его могут сожрать, но тогда гномиик будут знать, что у последнего был черный колпачок, и уже предпоследний -сам сможет вычислить свой цвет, и так по цепочке. спасутся все кроме последнего, у которго кстати шанс выжить 50/50. Но к сожалению тут К-кол-вл цветов и поентому я не знаю как здесь поступить. |
| Автор: SelenIT 3.9.2007, 22:01 |
| [сорри, ступил:] |
| Автор: Akina 3.9.2007, 22:28 |
| Условие задачи некорректно. Количество колпачков, с одной стороны, неизвестно (см. по тексту). С другой стороны (по тексту же), на КАЖДОГО гномика будет надет колпачок, т.е. количество колпачков будет равно количеству гномиков. Если же допустить, что в условии ляп и неизвестно количество ЦВЕТОВ колпачков - то задача решаема только в том случае, если известен ПОЛНЫЙ НАБОР возможных цветов колпачков. Пусть даже людоед о половине из них не знает, а половину ему известных - не использует. Так вот - при известном ПОЛНОМ наборе возможных цветов максимум будет съеден один гномик - тот, кто стоИт последним и кому отвечать первым. А если ему повезет (на что, впрочем, шансов мало) - то людоед вообще останется голодным. |
| Автор: FoxyMia 3.9.2007, 23:05 |
| Количество колпачков равно кол-ву гномиков естественно, но количесвто цветов этих колпачков-К т.е. гномиков N , а цветов колпачков-К, K<N т.е. у вас может быть 5 гномиков, а на них надето колпачков хоть 2-х цветов, хоть 3-х цветов, хоть 4-х цветов, лишь бы меньше кол-ва гномиков. (5 гномиков, 4 цвета: красн, зел, синий, бел.) |
| Автор: Fin 3.9.2007, 23:22 |
| Очень и очень давно было такое понятие "Бит четности". Задача решается точно по такому же принципу, как и работает это понятие. Дальше подсказывать уже не буду. Теряется весь кайф решения задачи При таком решении, максимальная потеря 1 гном |
| Автор: Akina 3.9.2007, 23:41 | ||
FoxyMia, Повторяю - пофиг сколько цветов, но ВСЕ ОНИ должны быть гномикам заведомо известны. И вовсе необязательно
Вполне возможно, что гномиков пятеро, а колпачок на каждом может быть любого из цветов радуги (т.е. из 7). Впрочем, очевидно, что количество ИСПОЛЬЗОВАННЫХ цветов из этого набора будет не больше количества гномиков. Суть решения Fin озвучил. Остальное элементарно. Как, впрочем, очевидно и то, что колпачок гномика, отвечающего первым и соответственно стоящего последним, не видит вообще никто, кроме людоеда, т.е. этого гномика может спасти лишь случайность. |
| Автор: _Nikolas_ 5.9.2007, 09:55 |
Обьясните идиоту, как можно отделаться одним?  Мне кажется К гномиков надо, чтобы каждый назвал четность К-го цвета. |
| Автор: Akina 5.9.2007, 14:43 | ||
Очень просто... Обозначаем все возможные цвета числами от 0 до К-1. Последний гномик складывает числа цветов всех колпаков, которые видит, и называет цвет, соответствующий остатку деления полученной суммы на К. Предпоследний тоже считает такую сумму. Сравнив ее с тем, что сказал последний, определяет цвет своего колпака и называет его. Пред-предпоследний тоже считает такую сумму, вычитает цвет колпака предпоследнего, определяет цвет своего колпака и называет его. И так далее, до самого первого. Ну а повезет последнему или нет, совпадет названный им цвет с цветом его колпака... вероятность = 1/К, т.е. ненулевая, хоть и мала. |
| Автор: apook 5.9.2007, 14:48 |
| Дак если неизвестно количество цветов или даже известно но можно в колпачке использовать несколько то вроде не решается задачка Дак а с другой стороны если известны цвета и их количество и используется только один цвет на колпачек то задача проста вобщем можно не браться решать.... |
| Автор: _Nikolas_ 5.9.2007, 16:11 | ||||
Гран мерси  |
| Автор: Smaug 9.9.2007, 12:36 | ||
и всетаки оптимальное решение в реальных условиях - гномик отвечающий первым ,просто называет колпак впереди стоящего..и так далее. |
| Автор: apook 9.9.2007, 12:45 | ||
|
| Автор: Smaug 9.9.2007, 15:35 |
| ах цвета не чередуются! плохо :( |
| Автор: JackYF 9.9.2007, 20:16 | ||
и большинство гномиков умрет, так как их цвет не совпадёт с цветом впереди стоящего. Оптимальное решение дал Akina. |
| Автор: pompei 12.12.2007, 14:41 |
| Если все гномики знают сколько каких цветов должно быть, то последний гномик видя всех впереди стоящих, сможет легко вспомнить и вычислить, методом исключений, какой на нём и громко это ответить. Остальные услышав его вычаслят какие остались. Предпоследний станет последним и будет знать какие остались. И так до самого последнего, верней первого. Спасутся все гномики. |
| Автор: iluvatar 14.12.2007, 11:07 |
| да ну? подсчитай-ка: перед тобой стоит 4 гнома, на 2-х красные колпаки, на 2-х желтые. какой на тебе? не забывай, что ты будешь съеден если ответишь неправильно |
