Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 232
может им всегда молчать? никого тогда не расстреляют...
Ну никто не запрещает как я понимаю перемещать книги относительно друг друга.
К примеру сигналы каждого человека:
1. Маркс и Энгельс лежат рядом, почти касаясь друг друга.
2. Маркс лежит правее Энгельса, на дистанции к примеру больше чем ширина книги.
3. Маркс левее Энгельса ...
4. Маркс выше Энгельса ...
5. Маркс ниже Энгельса ...
Как только кто-то получает сигналы от всех по 2 раза (чтобы исключить ошибку из-за начального положения книг), тот и говорит что мы тут были все. Возможно я неправ...
К примеру сигналы каждого человека:
1. Маркс и Энгельс лежат рядом, почти касаясь друг друга.
2. Маркс лежит правее Энгельса, на дистанции к примеру больше чем ширина книги.
3. Маркс левее Энгельса ...
4. Маркс выше Энгельса ...
5. Маркс ниже Энгельса ...
Как только кто-то получает сигналы от всех по 2 раза (чтобы исключить ошибку из-за начального положения книг), тот и говорит что мы тут были все. Возможно я неправ...
Забыл добавить тыльной стороной или обложкой - пофигу.
Я уже один раз написал "Горячо", получил -1 :)
Рациональное зерно в предложении есть, но со взаимным расположением книг это никак не связано. Данных в задаче хватает для решения, а стол может оказаться настолько маленьким, что книги на нем еле умещаются.
Рациональное зерно в предложении есть, но со взаимным расположением книг это никак не связано. Данных в задаче хватает для решения, а стол может оказаться настолько маленьким, что книги на нем еле умещаются.
"Маркс и Энгельс лежат рядом, почти касаясь друг друга."
Новая поза?
Новая поза?
Думаю, что в таком случае просто заранее пронумероваться и вырывать из какой-либо книги страницы со соответствующими номерами.
Похожую задачку задавали в Яндексе на собеседовании :)
Назначить одного человека "исполнителем".
Далее следующий алгоритм: всем кроме исполнителя переворачивать Маркса на спину, если он уже не перевёрнут. Если перевёрнут - переворачивать Энгельса.
Исполнителю, если Маркс перевёрнут, перевернуть назад и прибавить к счётчику единицу. Если не перевёрнут, перевернуть Энгельса.
Если счётчик достиг величины (количество заключённых-1), т. е. в нашем случае 4, значит, в Ленинской комнате все были.
Это при условии, что в самом начале книжки лежат лицом вверх.
Назначить одного человека "исполнителем".
Далее следующий алгоритм: всем кроме исполнителя переворачивать Маркса на спину, если он уже не перевёрнут. Если перевёрнут - переворачивать Энгельса.
Исполнителю, если Маркс перевёрнут, перевернуть назад и прибавить к счётчику единицу. Если не перевёрнут, перевернуть Энгельса.
Если счётчик достиг величины (количество заключённых-1), т. е. в нашем случае 4, значит, в Ленинской комнате все были.
Это при условии, что в самом начале книжки лежат лицом вверх.
Книжки лежат лицом кто куда.
Хорошо.
Перевёрнутый Маркс при первом посещении ленинской комнаты исполнителем - это либо сигнал от кого-то из ранее прибывших, либо случайно брошенная книжка в начале. Прибавим к "критической" величине счётчика единицу и всё ок )
В предыдущем решении забыл добавить, что после однократного переворачивания Маркса все кроме исполнителя в дальнейшем должны переворачивать только Энгельса.
Перевёрнутый Маркс при первом посещении ленинской комнаты исполнителем - это либо сигнал от кого-то из ранее прибывших, либо случайно брошенная книжка в начале. Прибавим к "критической" величине счётчика единицу и всё ок )
В предыдущем решении забыл добавить, что после однократного переворачивания Маркса все кроме исполнителя в дальнейшем должны переворачивать только Энгельса.
Хм. А как же он узнает, это случайность или знак?
Если ориентироваться на 4 переворота (первый из которых вполне может быть случайным), то можно остановиться после трех посещений и умереть.
Если на 5 переворотов - то можно и не дождаться.
Может что-то в консерватории подправить?
Если ориентироваться на 4 переворота (первый из которых вполне может быть случайным), то можно остановиться после трех посещений и умереть.
Если на 5 переворотов - то можно и не дождаться.
Может что-то в консерватории подправить?
Ориентироваться на 5.
Не дождаться можно и четырёх. В конце концов, начальник концлагеря волен всё время одного человека водить.
Не дождаться можно и четырёх. В конце концов, начальник концлагеря волен всё время одного человека водить.
да, мне вот тоже не понятен момент начала отсчета...
а вариант с кручением вокруг оси дает больше вариаций - ведь кроме челов в комнату входить никто не будет, может и выравнивать тоже...
а вариант с кручением вокруг оси дает больше вариаций - ведь кроме челов в комнату входить никто не будет, может и выравнивать тоже...
Ну конечно, вы ничего не теряете, если ждете пятого.
Но потратить время до вечера можно с большей пользой. Думайте.
Но потратить время до вечера можно с большей пользой. Думайте.
у вас хорошее начало но решение не закончено.
итак: у нас есть 1 счетчик и 4 исполнителя.
задача исполнителя: если маркс лежит обложкой верх - переворачиваем энгельса, если обложкой вниз переворачиваем маркса мордой вверх. каждый испольнитель считает количество переворотов маркса - если он перевернул его 2 раза - больше он его на мордой вверх не переворачивает.
счетчик: каждый раз когда он видит маркса перевернутого мордой вверх он увеличивает счетчик +1 и переворачивает маркса вниз лицом. если маркс лежите вниз лицом он циклически переворачивает энгельса.
когда счетчик дойдет до 8 - он может сказать что все побывали в комнате.
считать до 8 (а не до 4х) нужно чтоб обойти ситуацию когда 1м в комнату попадает счетчик, а там маркс лежит мордой вверх.
итак: у нас есть 1 счетчик и 4 исполнителя.
задача исполнителя: если маркс лежит обложкой верх - переворачиваем энгельса, если обложкой вниз переворачиваем маркса мордой вверх. каждый испольнитель считает количество переворотов маркса - если он перевернул его 2 раза - больше он его на мордой вверх не переворачивает.
счетчик: каждый раз когда он видит маркса перевернутого мордой вверх он увеличивает счетчик +1 и переворачивает маркса вниз лицом. если маркс лежите вниз лицом он циклически переворачивает энгельса.
когда счетчик дойдет до 8 - он может сказать что все побывали в комнате.
считать до 8 (а не до 4х) нужно чтоб обойти ситуацию когда 1м в комнату попадает счетчик, а там маркс лежит мордой вверх.
Хм.
Рассмотрим случай:
# - номер зека
#* - счётчик
М - морда вверх
Ж - жопа вверх
# Мркс Эглс
Ж М
1 М М
2* Ж М +1
3 М М
4 М Ж
5 М Ж
1 М Ж
1 М М
1 М Ж
1 М М
...
Т. е. если надзиратель будет водить только первого зека, то алгоритм зациклится, хотя все пятеро и побывали :(
Рассмотрим случай:
# - номер зека
#* - счётчик
М - морда вверх
Ж - жопа вверх
# Мркс Эглс
Ж М
1 М М
2* Ж М +1
3 М М
4 М Ж
5 М Ж
1 М Ж
1 М М
1 М Ж
1 М М
...
Т. е. если надзиратель будет водить только первого зека, то алгоритм зациклится, хотя все пятеро и побывали :(
Так у вас ещё дольше получается, аж до восьми нужно ждать.
Лично для меня это был самый сложный шаг в задаче.
Отлично.
Отлично.
Почему вы не написали в условии, что побывавший в комнате зек обязательно когда-нибудь туда снова попадёт? Если же это не так, то решение не верно!
Если это не так, то решения вообще нет, равно как и смысла ставить задачу.
Извините, но вы не правы. В таком случае могла, подразумеваться ещё какая-то деталь, которая делает решение возможным. Например, известное начальное положение книг. Спасибо за задачу, но прошу вас впредь внимательнее относиться к формулировке условия. Лучше перебдеть, чем недобдеть.
ЗЫ. Кстати говоря, если бы условие было более формально сформулировано, не было бы бесконечных дискуссий на тему «а можно ли ещё как-то поворачивать книги?»
ЗЫ. Кстати говоря, если бы условие было более формально сформулировано, не было бы бесконечных дискуссий на тему «а можно ли ещё как-то поворачивать книги?»
Согласен с решением.
Не имеет значения каким зашел счетчик, отсчет он начинает с момента маркс перевернут(либо другое заранее оговоренное значение). Далее "счетчик" считает до 4х изменений положения Маркса. Остальные четверо переворачивают Маркса в положение "счетчик+1", если они делают это впервые, при повторном заходе крутят Энгельса который счетчик не учитывает никак. Если Маркс находится в положении, которое нельзя изменить на значение "счетчик+1", крутят Энгельса и ждут следующего захода.
Не имеет значения каким зашел счетчик, отсчет он начинает с момента маркс перевернут(либо другое заранее оговоренное значение). Далее "счетчик" считает до 4х изменений положения Маркса. Остальные четверо переворачивают Маркса в положение "счетчик+1", если они делают это впервые, при повторном заходе крутят Энгельса который счетчик не учитывает никак. Если Маркс находится в положении, которое нельзя изменить на значение "счетчик+1", крутят Энгельса и ждут следующего захода.
в таком случае я решения не вижу
А если исполнителя пустят туда только один раз?
Эх..похоже придется вспомнить молодость, да полистать учебник по прикладной математике..
у меня получается, что их выпустят только если случится так, что в один из дней в комнату пять раз введут кого-нибудь не повторяясь (то есть каждого по разу).
Ну и мода же на ночь задачки загадывать )
Ну и мода же на ночь задачки загадывать )
Меня все же озарило:
Четверо — нападающие, один — квотербек =).
Нападающий переворачивает всегда левую книгу, кроме того случая, если правая лежит обложкой вверх, и он ее еще не переворачивал.
Квотербек также всегда переворачивает левую книгу, кроме тех случаев, когда правая лежит обложкой вниз, тогда он переворачивает ее обложкой вверх и записывает +1 к себе в карму.
Когда карма достигнет +4, он плюсует еще полтора разка за себя, срёт в карму начальнику (имея карму >5) и говорит, что дело сделано.
Четверо — нападающие, один — квотербек =).
Нападающий переворачивает всегда левую книгу, кроме того случая, если правая лежит обложкой вверх, и он ее еще не переворачивал.
Квотербек также всегда переворачивает левую книгу, кроме тех случаев, когда правая лежит обложкой вниз, тогда он переворачивает ее обложкой вверх и записывает +1 к себе в карму.
Когда карма достигнет +4, он плюсует еще полтора разка за себя, срёт в карму начальнику (имея карму >5) и говорит, что дело сделано.
О-ппа
«Книжки лежат лицом кто куда.»
«Книжки лежат лицом кто куда.»
Имеет ли значение начальное положение книг? В условии не упоминается то, как они лежат изначально. Это надо понимать как то, что они обе лежат лицом вверх или как то что это не важно?
каждый из заключенных независимо от начального положения кладет книжки по-своему:
1-й - лицом, лицом
2-й - лицом, спиной
3-й - спиной, лицом
4-й - спиной, спиной
5-й запоминает, какие комбинации уже были, и когда все пройдут - может говорить
но это при условии, что водить их будут до бесконечности
1-й - лицом, лицом
2-й - лицом, спиной
3-й - спиной, лицом
4-й - спиной, спиной
5-й запоминает, какие комбинации уже были, и когда все пройдут - может говорить
но это при условии, что водить их будут до бесконечности
Давайте нам уже ответ белым! :)
Может им до вечера кого-нить из 5 в расход пустить?
Или Хеппи Энд не минуем? =)
Или Хеппи Энд не минуем? =)
Кстати, переворачивать можно только со спины на обложку? Или можно ещё "вверх ногами" класть? Хм, хотя это ведь тоже переворачивать... Тогда можно ведь на каждой книге 4 комбинации - вверх обложкой и вверх ногами, вверх обложкой и вниз ногами и т.д....
Я правильно понимаю, что как только мы скажем, что книжки можно по разному переворачивать в зависимости от того, куда смотрит переплёт, задачка решается очевидно.
Я имею в виду, что каждая книжка получит по 4 состояния:
# - [лицо, переплёт]
1 - (вверх, вправо)
2 - (вверх, влево)
3 - (вниз, вправо)
4 - (вниз, влево)
Более того, состояния 1-3 и 2-4 взаимозаменяемые — те можно переходить из одного в другое. Также можно переходить из 1 в 4 и из 2 в 3.
Таким образом:
1ый вошедший — крутит Маркса в состояниях 1-3
2ой вошедший — крутит Маркста в состояниях 2-4
3ий вошедший — крутит Энгельса в состояниях 1'-3'
4ый вошедший — крутит Энгельса в состояниях 2'-4'
5ый вошедший — кричит ура и все идут пить пиво
?
Я имею в виду, что каждая книжка получит по 4 состояния:
# - [лицо, переплёт]
1 - (вверх, вправо)
2 - (вверх, влево)
3 - (вниз, вправо)
4 - (вниз, влево)
Более того, состояния 1-3 и 2-4 взаимозаменяемые — те можно переходить из одного в другое. Также можно переходить из 1 в 4 и из 2 в 3.
Таким образом:
1ый вошедший — крутит Маркса в состояниях 1-3
2ой вошедший — крутит Маркста в состояниях 2-4
3ий вошедший — крутит Энгельса в состояниях 1'-3'
4ый вошедший — крутит Энгельса в состояниях 2'-4'
5ый вошедший — кричит ура и все идут пить пиво
?
Имхо это и есть правильный вариант, я так и рассуждал. Но какой-то он не красивый. Давайте рассуждать.
Есть 4 "исполнителя", и один "наблюдатель".
"Наблюдатель" не всегда приходит после какого-то "исполнителя". Точно так же и исполнитель может ходить несколько раз подряд, и ему же тоже нужно что-то делать? - переворачивать что-то и как-то, выходит каждый "исполнитель" должен знать два положения своих книг. Даже не так! За каждым исполнителем закреплено 2 положения одной (!) книги, иначе что ему делать, если обе его книги лежат так, как ему положено их класть? Одна беда, исполнитель не сможет с уверенность и вообще как-нибудь :) сказать, что были все, пока не побывает в комнате после каждого.
Есть 4 "исполнителя", и один "наблюдатель".
"Наблюдатель" не всегда приходит после какого-то "исполнителя". Точно так же и исполнитель может ходить несколько раз подряд, и ему же тоже нужно что-то делать? - переворачивать что-то и как-то, выходит каждый "исполнитель" должен знать два положения своих книг. Даже не так! За каждым исполнителем закреплено 2 положения одной (!) книги, иначе что ему делать, если обе его книги лежат так, как ему положено их класть? Одна беда, исполнитель не сможет с уверенность и вообще как-нибудь :) сказать, что были все, пока не побывает в комнате после каждого.
Я думал над выделением ролей — исполнитель/наблюдатель, но эта идея не очень пошла, так как бойцы могут входить в комнату произвольно. Те если есть кто-то кто делает ключевое действие, то оно может не произойти или произойти слишком рано. Я понимаю, что это "махание руками", тем не менее верю, что действия не должны зависеть от человека — иначе, все зеки исполняют один и тот же алгоритм
5-й после второго увидит то же самое, что и после 4-го.
Вы ничего не знаете про стол. Возможно он не позволяет крутить книжки по оси.
Сосредоточьтесь на том что точно можно - со спины на живот и наоборот. Этого вполне достаточно.
Сосредоточьтесь на том что точно можно - со спины на живот и наоборот. Этого вполне достаточно.
Я так понимаю, заключённые понимают, что кто-то пошёл. Тогда можно использовать книги, как двоичный счетчик ;)
тут ничего не сказано о расположении книг.. если это не важно, то
1) если каждый заключенный при посещении зала? он просто переворачивает книгу, с тыльной на лицевую, любую не важно какую
2) а суть подсчета заключается в том что 1 заключенный кладет крест-накрест книги сверху Энгельс снизу Ленин
2-й впервые посещающий видя такое условие кладет книги 1 на другую, параллельно( можно под 45градусов)), книгу Энгельса на книгу Ленина
3-й впервые посещающий кладет крест-накрест книги сверху Ленин снизу Энгельс
4-й впервые посещающий кладет 1 книгу на другую параллельно(можно под 45 градусов) книгу Ленина на книгу Энгельса
5-й впервые посещающий видит предыдущий знак и заявляет
причем если любой из заключенный заходит повторно, он просто переворачивает верхнюю книгу не меняя расположение знака
PS за отсутствие хайдов не минусуйте, не знаю как ставятся
1) если каждый заключенный при посещении зала? он просто переворачивает книгу, с тыльной на лицевую, любую не важно какую
2) а суть подсчета заключается в том что 1 заключенный кладет крест-накрест книги сверху Энгельс снизу Ленин
2-й впервые посещающий видя такое условие кладет книги 1 на другую, параллельно( можно под 45градусов)), книгу Энгельса на книгу Ленина
3-й впервые посещающий кладет крест-накрест книги сверху Ленин снизу Энгельс
4-й впервые посещающий кладет 1 книгу на другую параллельно(можно под 45 градусов) книгу Ленина на книгу Энгельса
5-й впервые посещающий видит предыдущий знак и заявляет
причем если любой из заключенный заходит повторно, он просто переворачивает верхнюю книгу не меняя расположение знака
PS за отсутствие хайдов не минусуйте, не знаю как ставятся
чтобы их отпустили нужно доказать, что были оба, если предположить, что книги сразу лежат обложкой вверх, то все просто. Допустим они договариваются, что если один из них увидит перевернутую книгу, значит здесь уже один был. Допустим первого водят три раза подряд, он сначала переворачивает первую книгу, потом вторую, потом ворочает одну книгу.
для выхода на свободу:
1. увидел книжку тыльной стороной
2. изменилось расположение книг с твоего последнего, прибывания)
я вот так подумал
для выхода на свободу:
1. увидел книжку тыльной стороной
2. изменилось расположение книг с твоего последнего, прибывания)
я вот так подумал
А вы что здесь ожидали увидеть?
Вы забываете что с началом эксперимента они перестают общаться и получать информацию. Соотвественно передавать ее друг другу они могут только через книги. В условии не сказано про начальное положение книг, значит следует считать что рандомно лежат. Тоесть заключенные не смогут имееть одинаковые начальные данные и соответсвенно не смогут провести нужные расчеты с преворачиванием и четко сказать да я последний, или нет еще пара человек не ходило сюда.Чисто матиматически можно привести что через цать циклов походов с вероятностью такой то все заключенные прошли через эту комнату, в реальности всегда останется место ошибки и по сути задача решена небудет. Посему единственное что пришло в голову:заключенные пересчитываются, назначают каждому свои уникальный номер, а дальше при походе в комнату каждый вырывает из заранее оговоренной книги страницу соответствующую его номеру.
Мне кажется решения с счетчиком не подходят, потому что заведующий концлагерем может провести счетчика в комнату только один раз. Тогда никто никогда не скажет что все были, потому что говорить должен счетчик, а его в комнату для того чтобы посчитать не пускают.
Первый побывавший кладет маркса и ленина обложкой вниз (вверх, если они так (обе вверх) лежат по дэфолту, и вниз - если это возможно). Далее, сколько бы он не посещал, пока не увидит, что обе кники снова лицом в стол, он не будет их трогать вообще. Второй переворачивает ленина лицом вверх, третий - добавляет к "ленину" лицо маркса, четвертый убирает ленина обложкой вниз. Пятый восстанавливает изначальную ситуацию. Первый кто вновь видит две книги обложкой вниз - говорит, что все побывали.
л0 - ленин обложкой вниз, л1- обложкой вверх, м0, м1 - аналогично.
Первый ход:
л0 м0
Второй побывавший видит это, создает такую картину:
ло м1
Третий кто посещает комнату делает так:
л1 м1
Четвертый кто побывал в Ленинской комнате делает вот что:
л1 м0
Последний (только если видит л1 м0) - восстанавливает ситуацию.
л0 м0.
Для условия, в котором обе книги изначально обложкой вверх - 0 превратить в 1 и наоборот.
Что делать, что делать - учиться считать в двоичной системе счисления.
Хотя, моё решение имеет уязвимость и не может считаться решением. Буду думать.
хм... может им просто нужно всем до вечера зайти в библиотеку?
Эта задача для Хабра уже в некотором роде боян: Новая задачка. Теперь про узников.
http://habrahabr.ru/blog/zadachki/18955.…
Разве не похоже?
Разве не похоже?
Ну раз похоже - реши. Кто мешает? Условия разные, абсолютно, а формулировка просто похожая, чтобы не выдумывать что-то мудреное.
Тут тоже самое!
Лампочка - одна книга. Когда менять лампочку не надо переворачиваем другую книгу.
А опубликовал ту задачу я, так что ответ знаю.
Лампочка - одна книга. Когда менять лампочку не надо переворачиваем другую книгу.
А опубликовал ту задачу я, так что ответ знаю.
Параметры:
0 - обложка вниз
1- обложка вверх
Условия:
1. Каждый человек должен запомнить состояние книг при первом своем заходе в комнату.
2. Идет цикличность.
3. Если первый раз заходишь прибавляешь на 1 (т.е если было 01 то будет 10... если 11 то соотвественно 00)
4. Если второй раз заходишь то убавляешь на единицу(т.е. думаю что все понятно)
5. как только число книг при входе больше или равно твоему изначальному то значит все побывали уже
Вроде все учел, хотя могу и ошибаться :)
0 - обложка вниз
1- обложка вверх
Условия:
1. Каждый человек должен запомнить состояние книг при первом своем заходе в комнату.
2. Идет цикличность.
3. Если первый раз заходишь прибавляешь на 1 (т.е если было 01 то будет 10... если 11 то соотвественно 00)
4. Если второй раз заходишь то убавляешь на единицу(т.е. думаю что все понятно)
5. как только число книг при входе больше или равно твоему изначальному то значит все побывали уже
Вроде все учел, хотя могу и ошибаться :)
Интересно на сколько секунд я опоздал с ответом, :-)
Вроде тоже самое написал...
Вроде тоже самое написал...
счётчик Маркса и Энгельса переполнен и 11 превращается в 00 ? :)
- Завели 1-го узника. Он увеличил счётчик на единицу.
- Опять завели 1-го узника. Он уменьшил счетчик на единицу.
- Опять завели 1-го узника. Он увидел, что счёчик равен изначальному и сказал, что все здесь были.
- Unhappy end.
- Опять завели 1-го узника. Он уменьшил счетчик на единицу.
- Опять завели 1-го узника. Он увидел, что счёчик равен изначальному и сказал, что все здесь были.
- Unhappy end.
00=0
01=1
10=2
11=3
Каждый зашедший в свое нечетное посещение плюсует, в четное - минусует. Как только первый, зашедший в одно из посещений, увидит комбинацию, которую он оставил после первого своего посещения, то значит все были.
01=1
10=2
11=3
Каждый зашедший в свое нечетное посещение плюсует, в четное - минусует. Как только первый, зашедший в одно из посещений, увидит комбинацию, которую он оставил после первого своего посещения, то значит все были.
Кстати, можно еще засечки на краю обложки ногтем ставить 8-)
1) нельзя перейти из состояния 01 в состояние 10 одним переворотом книжки
2) Предположим ситуацию: завели узника № 1, затем № 1. Тогда во второе посещение он увидит то же состояние, которое было после первого.
2) Предположим ситуацию: завели узника № 1, затем № 1. Тогда во второе посещение он увидит то же состояние, которое было после первого.
Придумал.
Выбирают одного счетчика.
В первый день все кто приходят переворачивают Капитал обложкой вверх (если она обложкой вниз) - инициализируем начальное состояние.
В последующие дни, если капитал обложкой вверх - переворачиваем. Но каждый заключенный только один раз за весь этап.
В обратное состояние может переворачивать только счетчик. Он же считает сколько раз он перевернул. Как только он перевернет четыре раза - он говорит что всё.
Выбирают одного счетчика.
В первый день все кто приходят переворачивают Капитал обложкой вверх (если она обложкой вниз) - инициализируем начальное состояние.
В последующие дни, если капитал обложкой вверх - переворачиваем. Но каждый заключенный только один раз за весь этап.
В обратное состояние может переворачивать только счетчик. Он же считает сколько раз он перевернул. Как только он перевернет четыре раза - он говорит что всё.
Пишите ответы белым.
Основная проблема при решении этой задачи, на мой взгляд, кроется в том, что книги надо обязательно переворачивать, иными словами 2мя битами нам не обойтись. Но можно ли увеличить разрядность? Можно, это же книги Ж)
Во-первых можно определять какая книжка лежит выше, это даст 1 дополнительный бит. Во-вторых, можно определить, как книги будут лежать относительно друг-друга, т.е. переплеты в разные стороны или в одну: это даст еще 2 бита.
Более того, необходимо определить правильную последовательность подсчета состояния, а именно как бы книжки друг-на друге не лежали, сначала смотрится положение первой книжки("Капитал") и только потом второй. Это необходимо, чтобы обеспечить постоянный гарантированный переворот, который ни на что не влияет.
Итого имеем 5 бит, с которыми уже много проще решить, к примеру:
0) Заключенные назначают значения 5ти бит положениям книг и выбирают среди себя счетчика
1) Каждому из 4х оставшихся назначаются биты, если заключенный входит и видит, что его бит установлен не им, значит надо инициализировать и установить все биты на 00000.
2) Если заключенный видит, что его бит не установлен, он его устанавливает и если это не вызывает переворота, то использует запасной.
3) Счетчик всегда смотрит и использует запасной переворот. Как только он видит, что первые 4 биту установлены, он радостно бежит к начальнику и просится на свободу.
При этом:
1) Если заключенному надо просто сменить ориентацию переплета, а его книжка лежит сверху и на ней не определен резервный поворот, то он берет книжку снизу, переворчивает её и кладет снова вниз, при этой операции он может повернуть свою, не переворачивая. Ж)
2) Если наоборот: ему надо повернуть, а книга лежит снизу, значит он должен использовать резервный переворот и ждать, пока книги поменяются местами(бит какого-нибудь заключенного).
Во-первых можно определять какая книжка лежит выше, это даст 1 дополнительный бит. Во-вторых, можно определить, как книги будут лежать относительно друг-друга, т.е. переплеты в разные стороны или в одну: это даст еще 2 бита.
Более того, необходимо определить правильную последовательность подсчета состояния, а именно как бы книжки друг-на друге не лежали, сначала смотрится положение первой книжки("Капитал") и только потом второй. Это необходимо, чтобы обеспечить постоянный гарантированный переворот, который ни на что не влияет.
Итого имеем 5 бит, с которыми уже много проще решить, к примеру:
0) Заключенные назначают значения 5ти бит положениям книг и выбирают среди себя счетчика
1) Каждому из 4х оставшихся назначаются биты, если заключенный входит и видит, что его бит установлен не им, значит надо инициализировать и установить все биты на 00000.
2) Если заключенный видит, что его бит не установлен, он его устанавливает и если это не вызывает переворота, то использует запасной.
3) Счетчик всегда смотрит и использует запасной переворот. Как только он видит, что первые 4 биту установлены, он радостно бежит к начальнику и просится на свободу.
При этом:
1) Если заключенному надо просто сменить ориентацию переплета, а его книжка лежит сверху и на ней не определен резервный поворот, то он берет книжку снизу, переворчивает её и кладет снова вниз, при этой операции он может повернуть свою, не переворачивая. Ж)
2) Если наоборот: ему надо повернуть, а книга лежит снизу, значит он должен использовать резервный переворот и ждать, пока книги поменяются местами(бит какого-нибудь заключенного).
Тут все время проскакивают варианты с обеими книгами но в условии черным по белому сказано :)
Читать ничего не надо, но нужно будет обязательно взять любую (но только одну) из книг и перевернуть ее (с тыльной стороны на обложку или наоборот).
Читать ничего не надо, но нужно будет обязательно взять любую (но только одну) из книг и перевернуть ее (с тыльной стороны на обложку или наоборот).
Если ставить задачу в формулировке: "как им действовать, чтобы через некоторое время гарантированно выйти на свободу", то, можно показать, что задача решения не имеет (все, разумеется, ИМХО). Допустим, что это не так и существует гарантированный алгоритм. Далее представим, что ЗК водят в таком порядке: 1-й, 2-й, 3-й, 4-й, 5-й, 5-й, 5-й, 5-й... и т. д. до бесконечности. Тогда пятый должен в одно из своих посещений сказать "опа! пора...". Но поскольку с момента его первого посещения никакой информации его политзаключенные товарищи ему передать не могут, то он может определить, что все были до него в первое-же посещение. Но так как начальное расположение книг не известно, то любое расположение книг в его первое посещение может получиться в случае, если никого до него и не водили.
Предлагаю вариант поведения группы товарищей, в предположении, что заведующий этим пионерлагерем действует достаточно рандомно, и периодически все зеки посещают ленинскую комнату:
Заключенные расчитываются на номера с 1 по 5. Все дни, начиная со следующей недели циклически нумеруются с 1 до 5, т е 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5 и т д. Каждый заключенный, когда его приводят, действует следующим образом:
1) Смотрит и запоминает, как лежит Ленин.
2) Если это первое посещение, то распрямляет все пальцы на левой руке (инициализирует счетчик).
2) Если посещение не первое и ленин лежит не так, как в прошлый раз, то загибает себе палец на левой руке и держит так до следующего посещения :-)
3) Если видит что все пальцы загнуты, то радостно кричит "Мы тут все уже были!".
4) Иначе если номер дня совпадает с порядковым номером заключенного, то он переворачивает Ленина, иначе переворачивает Маркса.
Но похоже, что этот алгоритм можно еще оптимизировать...
Предлагаю вариант поведения группы товарищей, в предположении, что заведующий этим пионерлагерем действует достаточно рандомно, и периодически все зеки посещают ленинскую комнату:
Заключенные расчитываются на номера с 1 по 5. Все дни, начиная со следующей недели циклически нумеруются с 1 до 5, т е 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5 и т д. Каждый заключенный, когда его приводят, действует следующим образом:
1) Смотрит и запоминает, как лежит Ленин.
2) Если это первое посещение, то распрямляет все пальцы на левой руке (инициализирует счетчик).
2) Если посещение не первое и ленин лежит не так, как в прошлый раз, то загибает себе палец на левой руке и держит так до следующего посещения :-)
3) Если видит что все пальцы загнуты, то радостно кричит "Мы тут все уже были!".
4) Иначе если номер дня совпадает с порядковым номером заключенного, то он переворачивает Ленина, иначе переворачивает Маркса.
Но похоже, что этот алгоритм можно еще оптимизировать...
Ну то есть, не Ленин, а Энгельс, разумеется...
Как сильно совковые штампы-то въелись :-)
Как сильно совковые штампы-то въелись :-)
Уточнение к пункту 4) - разумеется Энгельса каждый сам переворачивает только один раз, а потом тупо крутит маркса.
Этот образ действий гарантирует, что никого не расстреляют, не требует отдельного счетчика, но при увеличении количества зеков становится очень маловероятно скорое их освобождение...
Этот образ действий гарантирует, что никого не расстреляют, не требует отдельного счетчика, но при увеличении количества зеков становится очень маловероятно скорое их освобождение...
О, сколько уже комментариев. Я не опоздал? :-)
Итак, мы имеем дело с цифрами — нулем и единицей. Пусть ноль — состояние, когда книга лежит обложкой вниз.
Начальное состояние может быть любым, и, к счастью, нас это не интересует.
Давайте произвольно выберем:
i j
1 1
Опишем наши функции:
Одна из пяти функций(осужденных, ага) будет, как правильно говорилось выше, «счетчиком».
Опишем функцию «счетчик»:
1) «Счетчик» всегда устанавливает старший разряд (i) в «0». Всегда. И увеличивает свое значение на единицу.
2) Если старший разряд уже «0», когда «счетчик» пришел — просто меняет значение младшего разряда (j). Его значение нам вообще не интересно.
Опишем остальные функции. Назовем их «гости».
Целью «гостя» является установка старшего разряда в единицу. Это не обязательно произойдет в его первый визит.
1) Если i=0, он меняет его на единицу. Выполнить эту операцию функция «гость» может только один раз. При следующих «срабатываниях» функция будет тупо вертеть младший разряд j, значение которого никого не интересует.
1) Если i=1 и «гость» его еще ни разу не менял, вертит «j» и уходит, до следующего раза.
ВСЁ!
Итак, мы имеем дело с цифрами — нулем и единицей. Пусть ноль — состояние, когда книга лежит обложкой вниз.
Начальное состояние может быть любым, и, к счастью, нас это не интересует.
Давайте произвольно выберем:
i j
1 1
Опишем наши функции:
Одна из пяти функций(осужденных, ага) будет, как правильно говорилось выше, «счетчиком».
Опишем функцию «счетчик»:
1) «Счетчик» всегда устанавливает старший разряд (i) в «0». Всегда. И увеличивает свое значение на единицу.
2) Если старший разряд уже «0», когда «счетчик» пришел — просто меняет значение младшего разряда (j). Его значение нам вообще не интересно.
Опишем остальные функции. Назовем их «гости».
Целью «гостя» является установка старшего разряда в единицу. Это не обязательно произойдет в его первый визит.
1) Если i=0, он меняет его на единицу. Выполнить эту операцию функция «гость» может только один раз. При следующих «срабатываниях» функция будет тупо вертеть младший разряд j, значение которого никого не интересует.
1) Если i=1 и «гость» его еще ни разу не менял, вертит «j» и уходит, до следующего раза.
ВСЁ!
было почти вначале. Алгоритм сбивается если книги вначале лежат в случайном положении. «счетчик» примет начальное положение книги за посетителя, даже если он вошел первым
все в порядке если счетчиком будет тот, кто идет в первый день. он выставляет старший разряд в 0 (или меняет младший, если менять старший не нужно), все остальные ЗНАЮТ что они не ходили в первый день и действуют по заданому алгоритму. это работает.
Остальные-то знают что они не ходили в первый день, а вот счетчик не знает. Не может быть ситуации в которой он скинет в ноль старший разряд и не засчитает посещение, для этого ему нужно знать что он первый, что невозможно.
А вот если считать до 6, то вроде как получается...
А вот если считать до 6, то вроде как получается...
может испортить только одна мелочь, если одного из узников заведут в библиотеку, он перевернет книгу для счетчика. Счетчик зайдет первый раз и "скинет" значение, предполагая что это может быть ошибка. Но если первого узника больше никогда не поведут к книгам то его счетчик уже не дождется и будет все рвемя думать что его ждать, хотя на самом деле все уже были.
Итог - в библиотеке все побывали, счетчик заклинило :) Остается только надется что первого еще хотябы раз сводят в читальню
Итог - в библиотеке все побывали, счетчик заклинило :) Остается только надется что первого еще хотябы раз сводят в читальню
Никак не пойму, а что будет если счетчик заходит первым и старший разряд уже 1? Он скидывает его в 0 и засчитывает посещение?
Именно так.
Начальное значение счетчика = 0
Счетчик считает до пяти.
Проверьте.
Начальное значение счетчика = 0
Счетчик считает до пяти.
Проверьте.
Так посещения-то не было, кого он посчитал?
Пронумеруем четырех гостей от 1 до 4, пятый - счетчик. Если начальное положение i=0, то после следующей последовательности посещений 1,5,2,5,3,5,4,5 функция счетчика будет равена четырем, а учитывая что "Выполнить эту операцию функция «гость» может только один раз", счетчик никогда уже не достигнет 5. То есть работать-то дальше будет, но завершения алгоритма уже гарантированно не получится при любой дальнейшей последовательности вызова функций.
Немного расплывчатые условия задачи
Книги в начале лежат в случайном состоянии или строго обложками вверх?
Можно ли пользоваться "поворотами" книг и прочими условиями не связанными с переворотом?
Если можно, то задача решается забавно — каждый заключенный вырывает страницу из Энгельса и хавает ее! Тот кто зайдет и увидит 4 вырванных страницы говорит что я — последний :) Т.к. нигде не сказанно что этого делать нельзя, считаю выриант самым быстрым и простым :)
Книги в начале лежат в случайном состоянии или строго обложками вверх?
Можно ли пользоваться "поворотами" книг и прочими условиями не связанными с переворотом?
Если можно, то задача решается забавно — каждый заключенный вырывает страницу из Энгельса и хавает ее! Тот кто зайдет и увидит 4 вырванных страницы говорит что я — последний :) Т.к. нигде не сказанно что этого делать нельзя, считаю выриант самым быстрым и простым :)
Немного оптимизируем и ...можно отрывать и кушать только уголки, где написаны номера страниц. Хотя если кушать хочется, то можно и целиком...
Можно я сам себя процитирую? «Начальное состояние может быть любым, и, к счастью, нас это не интересует.»
Пользоваться нужно именно переворотом. В этом соль задачи.
Пользоваться нужно именно переворотом. В этом соль задачи.
Перворачивать таким образом, чтобы книги были с перевернутой обложкой\лицевой стороной, и договорится о комбинациях, причем таким образом что каждая комбинация обозначает двух человек - того кто зашел, и предыдущего. Количества комбинаций вполне хватает для того чтобы всех "промаркировать"
Чёт намудрили народ. Всё же гораздо проще.
Есть 4 комбинации книг которые можно получить:
Верх1 Верх2
Верх1 Тыл2
Тыл1 Верх2
Тыл1 Тыл2
Закрепляем каждую комбинацию за одним человеком.
5 ничего не делает и при входе в команту не переворацичвает книги.
Каждый заходит в комнату и пытается извменить положение книг так, что бы получилась та комбинация которую ему присвоили.
Когда вызывают пятого он смотрит на положение книг и запоминает. Когда пятый уидит все комбинации - он может говорить что мы все тут уже были.
Ну и ещё: если один из четвёрки не может привести комбюинацию к своей - он не трогает книги вообще.
Есть 4 комбинации книг которые можно получить:
Верх1 Верх2
Верх1 Тыл2
Тыл1 Верх2
Тыл1 Тыл2
Закрепляем каждую комбинацию за одним человеком.
5 ничего не делает и при входе в команту не переворацичвает книги.
Каждый заходит в комнату и пытается извменить положение книг так, что бы получилась та комбинация которую ему присвоили.
Когда вызывают пятого он смотрит на положение книг и запоминает. Когда пятый уидит все комбинации - он может говорить что мы все тут уже были.
Ну и ещё: если один из четвёрки не может привести комбюинацию к своей - он не трогает книги вообще.
Я посмотрел задачу про комнату с лампочкой.
Если добавить одно дополнительное условие: "Рано или поздно любой из вас пойдёт ещё раз", fl00r прекрасно решил задачу.
А так - непонятно.
Если добавить одно дополнительное условие: "Рано или поздно любой из вас пойдёт ещё раз", fl00r прекрасно решил задачу.
А так - непонятно.
Во. Второй вариант.
При котором не учитывается начальное положение книг.
Определим за каждым заключённым одну из комбинаций: 00(1) 01(2) 11(3) 10(4) 00(5) — В скобках номера заключённых. Именно в такой последовательности.
После каждого вызова каждый заключённый пытается привести текущее положение книг в то положение которое назначено ему.
Если он не может этого сделать он пытается привести положенее книг к виду положение "слева от него". Т.е если я номер 3 пришёл и вижу: 00 я делаю 01.
Говорить что "мы побывали тут все" может заключённый под номером 5, но только в том случае если он перевернул книги из положения 4 в положение 5.
При котором не учитывается начальное положение книг.
Определим за каждым заключённым одну из комбинаций: 00(1) 01(2) 11(3) 10(4) 00(5) — В скобках номера заключённых. Именно в такой последовательности.
После каждого вызова каждый заключённый пытается привести текущее положение книг в то положение которое назначено ему.
Если он не может этого сделать он пытается привести положенее книг к виду положение "слева от него". Т.е если я номер 3 пришёл и вижу: 00 я делаю 01.
Говорить что "мы побывали тут все" может заключённый под номером 5, но только в том случае если он перевернул книги из положения 4 в положение 5.
первый зашёл 4 (сделал свою комбинацию) потом 5.
А. Я немного не доописал. Двигаем книги только тогда если они установлены в такое положение которое находится в спсике от меня слева. Если так не получается - двигаем книги так что бы получилась комбинация слева.
В сущности таким способом мы будем просто ждать того момента пока начальник конслагеря сам не проведёт всех заключённых поочереди в нужном нам порядке.
совсем не то, по вашему алгоритмы выжить — как в лотерею выиграть :)
Вопщем лучше наверно переописать. А то я уже запутался в своих же измышлениях.
Итак имеем заранее определённый порядок положений книг:
1 - 00
2 - 01
3 - 11
4 - 10
5 - 00
Когда заходит любой из заключённых, он смотрит на текущее положение книг. Если в списке это положение находится слева от него. Он переворачивает книги так что бы получилась комбинация присвоенная ему.
Если не удаётся повернуть книгу так что бы получилась его комбинация или текущее положение книг не такое как надо, он переворачивает книгу так что бы получилась комбинация слева от текущего положения. (Делает шаг назад).
Итак имеем заранее определённый порядок положений книг:
1 - 00
2 - 01
3 - 11
4 - 10
5 - 00
Когда заходит любой из заключённых, он смотрит на текущее положение книг. Если в списке это положение находится слева от него. Он переворачивает книги так что бы получилась комбинация присвоенная ему.
Если не удаётся повернуть книгу так что бы получилась его комбинация или текущее положение книг не такое как надо, он переворачивает книгу так что бы получилась комбинация слева от текущего положения. (Делает шаг назад).
а если там 00 и заходит третий? ему надо сделать 11? Он не может.
Если он сделает 01 то засчитают за второго, а если сделает 10 то потом зайдет пятый и радостно скажет что все были
Если он сделает 01 то засчитают за второго, а если сделает 10 то потом зайдет пятый и радостно скажет что все были
Он должен сделать 01. Но нет ничего страшного в том что его засчитают за второго.
Так как для успешного прохождения всего пути надо что бы каждый перевернул правильно.
И тогда последний поймёт что всё было правильно до него и сделает вывод что все были.
Идём от обратного.
Если 5 увидит 10 - он поймёт что предыдущий был либо он либо 4. Если это был он сам - то возвращаемся в начало предложения. Если это был четвёртый - становимся на место четвёртого.
Если четвёртый видит 11 - он поймёт что предыдущий были либо он сам либо 3. Ну и т.д..
Так как для успешного прохождения всего пути надо что бы каждый перевернул правильно.
И тогда последний поймёт что всё было правильно до него и сделает вывод что все были.
Идём от обратного.
Если 5 увидит 10 - он поймёт что предыдущий был либо он либо 4. Если это был он сам - то возвращаемся в начало предложения. Если это был четвёртый - становимся на место четвёртого.
Если четвёртый видит 11 - он поймёт что предыдущий были либо он сам либо 3. Ну и т.д..
А если осужденных не 5, а 50, тогда как? :-)
Вставлю свои пять копеек. Если начальное положение книг произвольно и заранее не известно, тогда решение вряд ли существует, поскольку заключённые не могут своими силами инициализировать книги (какой бы ни был выбран алгоритм, всегда можно подобрать контрпример). Если же начальное положение книг известно, то задача замечательно решается с помощью Кода Грея (как писали выше). Первые четыре уникальные заключённые увеличивают двоичный счётчик. Пятый, когда видит максимальное значение счётчика выдаёт результат.
Отставим в покое всякие биты и заморочки с дополнительными положениями книг, поскольку это не красиво и это хаки :)
Значит так:
Одного из зэков назначают счетчиком. В качестве флага мы выберем, например маркса. Если маркс лицом вверх - значит кто-то тут уже был. Счетчик, видя маркса лицом вверх, делает i++ и переворачивает его лицом вниз. Все остальные имеют право перевернуть маркса лицом вверх только один раз asap. Во всех остальных случаях переворачивают энгельса - нам плевать лицом куда он лежит. Как только у счетчика получится i=4 значит все тут были. Но! Так как мы не знаем изначальное состояние системы то может получиться что маркс изначально лежал лицом вверх и изначально i=1. Поэтому нам нужно чуть избыточности, ну, скажем переворачивать маркса лицом вверх каждый будет два раза. Тоесть как только i=8 - все были минимум один раз (если изначально i=1 то не_счетоводы были в комнате по два раза, кроме одного, который был всего один раз). Система рано или поздно сработает, при условии, что количество посещений каждого не лимитировано. Если заведующий лагерем знает решение, то в его силах либо позволить им выйти, либо сделать так чтобы они никогда не вышли.
Таким образом получется что зэки выживут в любом случае и у них есть шанс ещё и оказаться на свободе.
Но если зеки не придумают этого решения у них есть один простой способ - подождать ну, скажем, год, а потом рискнуть и сказать что все были, поскольку время играет им на руку - чем дальше, тем больше шансов на то, что они все уже были. :)
Значит так:
Одного из зэков назначают счетчиком. В качестве флага мы выберем, например маркса. Если маркс лицом вверх - значит кто-то тут уже был. Счетчик, видя маркса лицом вверх, делает i++ и переворачивает его лицом вниз. Все остальные имеют право перевернуть маркса лицом вверх только один раз asap. Во всех остальных случаях переворачивают энгельса - нам плевать лицом куда он лежит. Как только у счетчика получится i=4 значит все тут были. Но! Так как мы не знаем изначальное состояние системы то может получиться что маркс изначально лежал лицом вверх и изначально i=1. Поэтому нам нужно чуть избыточности, ну, скажем переворачивать маркса лицом вверх каждый будет два раза. Тоесть как только i=8 - все были минимум один раз (если изначально i=1 то не_счетоводы были в комнате по два раза, кроме одного, который был всего один раз). Система рано или поздно сработает, при условии, что количество посещений каждого не лимитировано. Если заведующий лагерем знает решение, то в его силах либо позволить им выйти, либо сделать так чтобы они никогда не вышли.
Таким образом получется что зэки выживут в любом случае и у них есть шанс ещё и оказаться на свободе.
Но если зеки не придумают этого решения у них есть один простой способ - подождать ну, скажем, год, а потом рискнуть и сказать что все были, поскольку время играет им на руку - чем дальше, тем больше шансов на то, что они все уже были. :)
зачем 8? достаточно 5 (т.е. N раз)
не выйдет. если книга изначально была в подожении 0, а не_счетчики будут переворачивать маркса только один раз, то счетчик никогда не достигнет значения 5. Если они будут переворачивать маркса по два раза, то запросто может получиться что первый был 2 раза, второй тоже 2 раза, а третий и четвертый - ни разу. Всем кирдык.
пожалуй это верно, нужно действительно минимум 8
В общем, получается, что одну из книг исполнители используют вхолостую - чтобы "ход пропустить". А вторая книга - чтобы отметиться, что был. Если вторая книга лежит лицом книзу - исполнитель ее переворачивает. Все, он уже отметился и теперь будет только переворачить первую ("холостую") книгу. Счетчик переворачивает вторую книгу, если она лицом кверху (т.е. фиксирует отметку), либо крутит первую. Счетчик должен достичь числа N переворачиваний (по одному за каждого другого узника + 1 переворачивание для подстраховки, если вторая книга изначально лежала лицом кверху)
думаю это правильный ответ, причем для любого кол-ва заключенных
он уже был в разных вариациях выше, но это пожалуй самая простая и универсальная формулировка
он уже был в разных вариациях выше, но это пожалуй самая простая и универсальная формулировка
нет, вру. Решение неверно.
Если изначально лежали книги ВВ (верх верх) то заключенные перевернут их для счетчика 4 раза, а вот счетчик будет ждать пятого (ведь первый он "не засчитал", вдруг книги изначально лежали неверно) — проблема в том что он никогда не дождется, ведь все уже перевернули книгу-счетчик и не имеют более права это делать
Если изначально лежали книги ВВ (верх верх) то заключенные перевернут их для счетчика 4 раза, а вот счетчик будет ждать пятого (ведь первый он "не засчитал", вдруг книги изначально лежали неверно) — проблема в том что он никогда не дождется, ведь все уже перевернули книгу-счетчик и не имеют более права это делать
нет. количество срабатываний должно быть (N-1)*2, иначе не получится.
уточняйте, попадет ли хоть один из зеков больше одного раза в комнату:
или возможен вариант, что всех в один день по одному разу отвели в комнату и дело с концом?
Вариант со счетчиками недееспособен, без повторяемости...
или возможен вариант, что всех в один день по одному разу отвели в комнату и дело с концом?
Вариант со счетчиками недееспособен, без повторяемости...
Я так думаю что мы не используем одно очень важное условие. Это то что время таки дискретно и измерятеся в днях.
Щас подумаю и попробую придумать что то с днями.
Щас подумаю и попробую придумать что то с днями.
Каждый заключённый когда первый раз туда попадает отрывает (загибает уголок и т.п.) по 1 странице с книги, когда в книгах не будет хватать 5 страниц - они все там побывали
В условии пропущен один важный момент, который делает правильную стратегию бесполезной:
>> Рано или поздно каждый из вас побывает в Ленинской комнате и не один раз.
Проще говоря, при времени стремящемся к бесконечности каждый побывает в комнате количество раз стремящееся к бесконечности.
>> Рано или поздно каждый из вас побывает в Ленинской комнате и не один раз.
Проще говоря, при времени стремящемся к бесконечности каждый побывает в комнате количество раз стремящееся к бесконечности.
Счетчики нафиг! Необходимо выделить следящего и обозначить протокол передачи ему информации о побывавших в камере.
Каждый информатор старается сообщить о себе (оставив Маркса лицом), если перед ним это не сделал другой информатор и следящий не обозначил, что он это принял (Маркс жопой). Иначе он ждет своей очереди. Соответственно следящий считает, сколько там уже побывали. В первый день не учитывается никто и к началу второго дня Маркс должен лежать жопой, чтобы следящий, зайдя в комнату в первый день, не воспринял случайный сигнал за истинный.
Каждый информатор старается сообщить о себе (оставив Маркса лицом), если перед ним это не сделал другой информатор и следящий не обозначил, что он это принял (Маркс жопой). Иначе он ждет своей очереди. Соответственно следящий считает, сколько там уже побывали. В первый день не учитывается никто и к началу второго дня Маркс должен лежать жопой, чтобы следящий, зайдя в комнату в первый день, не воспринял случайный сигнал за истинный.
Проблема счетчика
Выше, предлагается использовать одного товарища как счетчика. Кажется, что счетчик это тупиковая идея.
Что если счетчик побывает в комнате не много раз, а N-1?
Или он будет в комнате много больше N, но в самом начале игры, до того как в комнату поведут остальных заключенных, и больше в комнату его водить не будут?
В таких случаях он просто физически не сможет сосчитать всех.
Выше, предлагается использовать одного товарища как счетчика. Кажется, что счетчик это тупиковая идея.
Что если счетчик побывает в комнате не много раз, а N-1?
Или он будет в комнате много больше N, но в самом начале игры, до того как в комнату поведут остальных заключенных, и больше в комнату его водить не будут?
В таких случаях он просто физически не сможет сосчитать всех.
Если думать так, то теоретически один из заключенных вообще может ни разу не побывать в комнате с книгами. При любой стратегии. Вопрос в оптимальности решения.
Согласен, ваш пост забивает последний гвоздь в гроб идеи со счетчиком.
Получается что всех могут сводить по разу подряд и больше не водить вообще и при этом задача должна иметь решение...
Получается что всех могут сводить по разу подряд и больше не водить вообще и при этом задача должна иметь решение...
отстой
Мое решение с PHP-кодом:
Чем то мне это напоминает T-Триггер http://ru.wikipedia.org/wiki/%D0%A2%D1%8…(%D1%8D%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%B8%D0%BA%D0%B0)#T-.D1.82.D1.80.D0.B8.D0.B3.D0.B3.D0.B5.D1.80
все основано на операции not и соблюдении четности,
можно красиво сделать через операторы ~ и <<, но мне лень ;)
Результат кода:
bash-3.1#php test.php
Zek #1: I'm here at first time; I see: 01, I made: 11
Zek #2: I'm here at first time; I see: 11, I made: 10
Zek #1: I'm here was 2 times; I see: 10, I made: 00
Zek #1: I'm here was 3 times; I see: 00, I made: 01
Zek #3: I'm here at first time; I see: 01, I made: 11
Zek #4: I'm here at first time; I see: 11, I made: 10
Zek #5: I'm here at first time; I see: 10, I made: 00
We are free!!!
Чем то мне это напоминает T-Триггер http://ru.wikipedia.org/wiki/%D0%A2%D1%8…(%D1%8D%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%B8%D0%BA%D0%B0)#T-.D1.82.D1.80.D0.B8.D0.B3.D0.B3.D0.B5.D1.80
все основано на операции not и соблюдении четности,
можно красиво сделать через операторы ~ и <<, но мне лень ;)
$test = new test();
$test->run();
class test
{
public $currentBookState = '01'; // Расположение книг первоначальное
public $order = array(1,2,1,1,3,4,5,1); // Очередность пускания Зеков к книгам
function run()
{
$zekMemory = array(); // память зека, какую комбинацию он увидел при входе
$zekBinMemory = array(); // сколько раз был у книг
foreach ($this->order as $zek) {
$zekBinMemory[$zek] = intval($zekBinMemory[$zek]) + 1;
if (isset($zekMemory[$zek]) // Если зек здесь был
&& $this->invertor($this->currentBookState) == $zekMemory[$zek] // если он видел эту комбинацию
&& $zekBinMemory[$zek] % 2 == 0 // И если это не он снова пришел (N-раз подряд)
) {
echo "Zek #{$zek}: We are free!!!\n";
break;
}
// Если мы в первый раз, то запоминаем комбинацию книг
if (!isset($zekMemory[$zek])) {
echo "Zek #{$zek}: I'm here at first time; I see: {$this->currentBookState}, I made: " .$this->invertor($this->currentBookState). " \n";
$zekMemory[$zek] = $this->currentBookState;
$this->currentBookState = $this->invertor($this->currentBookState);
} else {
echo "Zek #{$zek}: I'm here was {$zekBinMemory[$zek]} times; I see: {$this->currentBookState}, I made: " .$this->invertor($this->currentBookState). " \n";
$this->currentBookState = $this->invertor($this->currentBookState);
}
}
}
/**
* Простеццкий инвертор
*/
function invertor($val)
{
switch ($val) {
case '00':
return '01';
case '01':
return '11';
case '11':
return '10';
case '10':
return '00';
}
}
}
?>
Результат кода:
bash-3.1#php test.php
Zek #1: I'm here at first time; I see: 01, I made: 11
Zek #2: I'm here at first time; I see: 11, I made: 10
Zek #1: I'm here was 2 times; I see: 10, I made: 00
Zek #1: I'm here was 3 times; I see: 00, I made: 01
Zek #3: I'm here at first time; I see: 01, I made: 11
Zek #4: I'm here at first time; I see: 11, I made: 10
Zek #5: I'm here at first time; I see: 10, I made: 00
We are free!!!
- час рабочего времени на рисование диаграмм переходов, в результате пришел к тому как в http://habrahabr.ru/blog/zadachki/42678.html#comment862945
Думается решение следующее...
Зеки выбирают счетчика. Когда обычный зек заходит в комнату в первый раз - переворачивает маркса лицом вниз, если маркс уже лежит так - то ждет следующего раза, и крутит энгельса. Каждый зек должен перевернуть маркса лицов вниз ровно один раз. Счетчик переворачивает маркса лицом вверх и считает +1, когда насчитает N+1 - все свободны. По условиям задачи время отсидки неограничено - значит рано или поздно счетчик насчитает нужное количество
Зеки выбирают счетчика. Когда обычный зек заходит в комнату в первый раз - переворачивает маркса лицом вниз, если маркс уже лежит так - то ждет следующего раза, и крутит энгельса. Каждый зек должен перевернуть маркса лицов вниз ровно один раз. Счетчик переворачивает маркса лицом вверх и считает +1, когда насчитает N+1 - все свободны. По условиям задачи время отсидки неограничено - значит рано или поздно счетчик насчитает нужное количество
Гы, http://www.eruditor.ru/z/?29
И ответ: http://www.eruditor.ru/f/?z=29
И ответ: http://www.eruditor.ru/f/?z=29
нужно оставлять следы на книжках в разных местах, а если там второй раз, то не оставлять, ну или оставить на предыдущем месте :)
Самая большая проблема в том, что не известно начально положение книг. Если предположить, что обе книги лежат лицом вверх и корешком влево, тогда получается 16 состояний и известно 1-е.
Из каждого состояния можно сделать 4 перехода, 2 из которых оставляют состояние в той же 4-ке сотосяний, а одно позволяет перейти в следующую 4-ку. 1 вошедший переводит текущее состояние в состояние из 2-ой 2-ки (например в 4) и если он снова заходи в следующий раз он оставляет состояние из второй двойки, входит 2-й и переводит в состояние из 2-ой четверки, и так далее. Когда последний 5-й человек зайдет - он увидит что состояние из 4-ой 4-ки и, перевернув книгу как угодно, скажет: "Я 5-й и остальные 4-ро уже здесь побывали"
Таблица переходов http://konnikov.ru/temp/images/zeki.png
Из каждого состояния можно сделать 4 перехода, 2 из которых оставляют состояние в той же 4-ке сотосяний, а одно позволяет перейти в следующую 4-ку. 1 вошедший переводит текущее состояние в состояние из 2-ой 2-ки (например в 4) и если он снова заходи в следующий раз он оставляет состояние из второй двойки, входит 2-й и переводит в состояние из 2-ой четверки, и так далее. Когда последний 5-й человек зайдет - он увидит что состояние из 4-ой 4-ки и, перевернув книгу как угодно, скажет: "Я 5-й и остальные 4-ро уже здесь побывали"
Таблица переходов http://konnikov.ru/temp/images/zeki.png
Да, ребята. Зеки из вас — никакие!
К а п и т а л А н т и - Д ю р и н г
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Каждый приходящий знает отмечал он букву или нет. Если не отмечал, то просто переворачивает книгу и уголком этой книги отмечает ту следующую букву. Если отмечал - переворачивает и оставляет на том же месте.
При наличии имен авторов на титульной странице, можно больше человек спасти от фрика-начальника концлагеря :).
з.ы. от 0 до 1 людей понадобится, чтобы убедиться что, хотя бы одна книга лежит титульным листом вверх
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Каждый приходящий знает отмечал он букву или нет. Если не отмечал, то просто переворачивает книгу и уголком этой книги отмечает ту следующую букву. Если отмечал - переворачивает и оставляет на том же месте.
При наличии имен авторов на титульной странице, можно больше человек спасти от фрика-начальника концлагеря :).
з.ы. от 0 до 1 людей понадобится, чтобы убедиться что, хотя бы одна книга лежит титульным листом вверх
Их блин 19 человек с целым вечером на составление плана. Составить план и бежать, бежать из этого концлагеря с маньяком-начальником! :)
Я понимаю, что задача на логику и т.п.
Но если подойти к задаче по другому.
возраст заключенных возьмем 20 лет.
вероятность того, что они проживут больше 50 лет = 0.01%, приравниваем 0
остаток жизни 30 лет.
Вероятность того, что начальник заведет всех в течении 10 лет = 100%
В противном случае теряется смысл.
Если решение не найдено и:
Если срок 10 лет, соглашаемся и через 10 лет говорим, что мы все были.
А теперь серьезно:
Автор задачи все время упирает на то, что переворота книг достаточно.
Из этого следует, что мы имеем, как уже многие говорили 4 состояния:
00, 01, 10, 11
00 и 01 – нулевой уровень (обнуляет только счетчик)
11 или 10 – я впервые отметился (все остальные поддерживают это состояние, до обнуления)
01 и 10 превращается только в 00 или 11
00 и 11 превращается только в 01 или 10
Без счетчика задача не решается (нет начального уровня), если не использовать еще какое либо состояние. На пример книжка, на книжку или вращение книжок.
Но автор упирал на то, что этих четырех состояний достаточно.
Короче говоря, все варианты уже тут перебрали и без меня.
Ждем ответа автора.
Но если подойти к задаче по другому.
возраст заключенных возьмем 20 лет.
вероятность того, что они проживут больше 50 лет = 0.01%, приравниваем 0
остаток жизни 30 лет.
Вероятность того, что начальник заведет всех в течении 10 лет = 100%
В противном случае теряется смысл.
Если решение не найдено и:
Если срок 10 лет, соглашаемся и через 10 лет говорим, что мы все были.
А теперь серьезно:
Автор задачи все время упирает на то, что переворота книг достаточно.
Из этого следует, что мы имеем, как уже многие говорили 4 состояния:
00, 01, 10, 11
00 и 01 – нулевой уровень (обнуляет только счетчик)
11 или 10 – я впервые отметился (все остальные поддерживают это состояние, до обнуления)
01 и 10 превращается только в 00 или 11
00 и 11 превращается только в 01 или 10
Без счетчика задача не решается (нет начального уровня), если не использовать еще какое либо состояние. На пример книжка, на книжку или вращение книжок.
Но автор упирал на то, что этих четырех состояний достаточно.
Короче говоря, все варианты уже тут перебрали и без меня.
Ждем ответа автора.
решение для любого(!) количества заключённых:
* один из заключённых обьявляется счётчиком. все знают, что он счётчик. он в итоге и скажет, что все были в комнате.
* все заключённые переворачивают только первую книгу.
* вторая книга переворачивается заключённым только в том случае, если:
1. книга лежит лицевой стороной вверх.
2. заключённый первый раз увидел, что книга лежит лицевой стороной вверх.
3. при повторном визите при любом положении второй книги крутится первая книга.
* во всех остальных случаях переворачивается первая книга.
если счётчик заходит в комнату и видит, что вторая книга перевёрнута тыльной стороной - он обнуляет значение маркера(возвращает книгу в исходной положение) и считает, что один из заключённых уже был в комнате. к количеству посетивших добавляется один.
и так продолжать до тех пор, пока счётчик не насчитает количество заключённых минус один(он сам).
т.е. счётчик должан вернуть вторую книгу в иходную позицию столько раз, какое количество заключённых побывало в комнате, за исключением его самого.
если заключённый заходит в комнату в первый раз и видит, что вторая книга перевёрнута - он её не трогает, а переворачивает первую т.к. сбросит значение, известное счётчику. При таком подходе будут повторные визиты, но когда счётчик насчитает нужное число обнулений маркера - можно с уверенностью сказать, что все побывали в комнате один или более раз.
если что непонятно - поясню.
* один из заключённых обьявляется счётчиком. все знают, что он счётчик. он в итоге и скажет, что все были в комнате.
* все заключённые переворачивают только первую книгу.
* вторая книга переворачивается заключённым только в том случае, если:
1. книга лежит лицевой стороной вверх.
2. заключённый первый раз увидел, что книга лежит лицевой стороной вверх.
3. при повторном визите при любом положении второй книги крутится первая книга.
* во всех остальных случаях переворачивается первая книга.
если счётчик заходит в комнату и видит, что вторая книга перевёрнута тыльной стороной - он обнуляет значение маркера(возвращает книгу в исходной положение) и считает, что один из заключённых уже был в комнате. к количеству посетивших добавляется один.
и так продолжать до тех пор, пока счётчик не насчитает количество заключённых минус один(он сам).
т.е. счётчик должан вернуть вторую книгу в иходную позицию столько раз, какое количество заключённых побывало в комнате, за исключением его самого.
если заключённый заходит в комнату в первый раз и видит, что вторая книга перевёрнута - он её не трогает, а переворачивает первую т.к. сбросит значение, известное счётчику. При таком подходе будут повторные визиты, но когда счётчик насчитает нужное число обнулений маркера - можно с уверенностью сказать, что все побывали в комнате один или более раз.
если что непонятно - поясню.
Хм, а если в исходное позиции вторая книга уже была перевёрнута? тогда счётчик насчитает на единицу больше, следовательно он скажет, что все уже прошли, но на самом деле один человек ещё не прошёл. Как бороться с этим?
а я кажется додумался, как с этим бороться! =)
По твоему решению заключённый должен ставить маркер только один раз. Если заставить их ставить маркер два раза, то когда счётчик сделает 2*X (X - колличество заключённых) обнуления маркера, он сможет с полной уверенностью сказать, что в комнате хотя бы по разу побывали все (или каждый "поставил маркер" по два раза, или в самом начале книга уже была перевёрнута, и один из заключённых поставил маркер один раз)
По твоему решению заключённый должен ставить маркер только один раз. Если заставить их ставить маркер два раза, то когда счётчик сделает 2*X (X - колличество заключённых) обнуления маркера, он сможет с полной уверенностью сказать, что в комнате хотя бы по разу побывали все (или каждый "поставил маркер" по два раза, или в самом начале книга уже была перевёрнута, и один из заключённых поставил маркер один раз)
Если задачка на самом деле сводится к задаче, опубликованной 
ttim
В противном случае мне на самом деле ОЧЕНЬ интересно узнать, как её можно решить, имея две книги с двумя состояниями и произвольное количество заключённых.
ttimВ противном случае мне на самом деле ОЧЕНЬ интересно узнать, как её можно решить, имея две книги с двумя состояниями и произвольное количество заключённых.
решение - мой камент выше ;)
Представьте следующую ситуацию.
Сначала по-очереди запускаются первые десять заключённых (среди них нет счётчика). Потом по-очереди запускаются оставшиеся. Впоследствии запускается только вторая часть заключённых - первая десятка уже НИКОГДА не запускается в библиотеку.
Бедные заключенные будут вечно томиться в ожидании, пока "счётчик" скажет "Мы все здесь уже были!" ... а он не скажет:(.
Сначала по-очереди запускаются первые десять заключённых (среди них нет счётчика). Потом по-очереди запускаются оставшиеся. Впоследствии запускается только вторая часть заключённых - первая десятка уже НИКОГДА не запускается в библиотеку.
Бедные заключенные будут вечно томиться в ожидании, пока "счётчик" скажет "Мы все здесь уже были!" ... а он не скажет:(.
это единственный вариант, имхо.
решение валидно при двух условиях:
1. в исходном положении вторая книга лежит лицом вверх.
2. заключённых пускают повторно и в произвольном порядке.
ещё одно имхо: второе условие подразумевается исходя из:
"Выбирать заключенных я буду как мне хочется: например, сегодня первого три раза свожу, а завтра всех по очереди..."
решение валидно при двух условиях:
1. в исходном положении вторая книга лежит лицом вверх.
2. заключённых пускают повторно и в произвольном порядке.
ещё одно имхо: второе условие подразумевается исходя из:
"Выбирать заключенных я буду как мне хочется: например, сегодня первого три раза свожу, а завтра всех по очереди..."
Произвольный порядок вовсе не подразумевает повторный запуск КАЖДОГО заключённого бесконечное число раз (я уже привёл один пример произвольного запуска). А вот процитированное мною чуть выше условие из похожей задачи подразумевает. Его в обсуждаемой задаче нет, поэтому ваше решение считаю неподходящим. Не расстраивайтесь, быть может, автор случайно убрал это условие "за ненадобностью";).
Кто видел "Капитал" вживую, подтвердит, что книга из четырех приличных томов, а Энгельс толстых книжек не писал. Итак, у нас пять томов для переворота и пять зеков =))
Ну а если подвох не в этом, то почему бы другой, менее провокационный, труд в место Капитала поставить?
Ну а если подвох не в этом, то почему бы другой, менее провокационный, труд в место Капитала поставить?
Как на счет варианта крутить по кругу только одну книгу.
Побывал второй раз, переворачивать вторую.
Побывал второй раз, переворачивать вторую.
Вот эта вот фишечка:
>>>3. Условие о том, что каждый заключенный побывает в комнате несколько (да что там, много!) раз не было явно указано, т.к. если бы это было не так, у задачи очевидно не было бы решения.
вот это вот меня очень расстоило. Вы намеренно убрали одно из условий мотивируя, что, мол что это очевидно. Простите, но исходя из данных условий вытекает один единственный вывод - задача решения не имеет.
Что такое, в данном случае, задача? Набор условий и ограничений и в этих рамках нужно найти решение. Если задача, будем говорить математическая, а не загадка из разряда "Сколько нужно чукчей для того чтобы поменять лампочку", а у Вас как раз математическая задача. То тогда можно составить алгоритм, написать программу которая будет решать эту задачу. Выше были попытки, да. Так вот, подобный алгоритм выдаст решение вовсе не для каждого набора входных данных. Вам придется внимательно изучать в каком порядке и какое кол-во походов каждый заключенный делает в Лененскую комнату, прежед чем запустить эти данные на вход алгоритма. Иначе, иногда этот алгоритм не будет срабатывать и заключенные будут сидеть вечно.
Я правильно понял, что же все же задача математическая, ни кто же в здравом уме не может предстваить себе подобную ситуацию в жизни, да?
Два выхода:
1. задача состалена не корректно.
2. задача решения не имеет.
Уповать на "очевидность" чего-то — глупо. Точно так же, очевидно - вырывать страницы. Так же очевидно - ложить книги друг на друга, ориентировать их относительно друг друга, стола, и т.п. Все это очевидные вещи. Но почему-то, Вы их отрицаете. А другие "очевидные" вещи, нет, принимаете, мол так и должно быть - все будут ходить в комнату до скончания веков. Грустно.
Так что если Вы что-то не упомянули в условии, значит этого нет в условии, и решать задачу нужно исходя из условий.
>>>3. Условие о том, что каждый заключенный побывает в комнате несколько (да что там, много!) раз не было явно указано, т.к. если бы это было не так, у задачи очевидно не было бы решения.
вот это вот меня очень расстоило. Вы намеренно убрали одно из условий мотивируя, что, мол что это очевидно. Простите, но исходя из данных условий вытекает один единственный вывод - задача решения не имеет.
Что такое, в данном случае, задача? Набор условий и ограничений и в этих рамках нужно найти решение. Если задача, будем говорить математическая, а не загадка из разряда "Сколько нужно чукчей для того чтобы поменять лампочку", а у Вас как раз математическая задача. То тогда можно составить алгоритм, написать программу которая будет решать эту задачу. Выше были попытки, да. Так вот, подобный алгоритм выдаст решение вовсе не для каждого набора входных данных. Вам придется внимательно изучать в каком порядке и какое кол-во походов каждый заключенный делает в Лененскую комнату, прежед чем запустить эти данные на вход алгоритма. Иначе, иногда этот алгоритм не будет срабатывать и заключенные будут сидеть вечно.
Я правильно понял, что же все же задача математическая, ни кто же в здравом уме не может предстваить себе подобную ситуацию в жизни, да?
Два выхода:
1. задача состалена не корректно.
2. задача решения не имеет.
Уповать на "очевидность" чего-то — глупо. Точно так же, очевидно - вырывать страницы. Так же очевидно - ложить книги друг на друга, ориентировать их относительно друг друга, стола, и т.п. Все это очевидные вещи. Но почему-то, Вы их отрицаете. А другие "очевидные" вещи, нет, принимаете, мол так и должно быть - все будут ходить в комнату до скончания веков. Грустно.
Так что если Вы что-то не упомянули в условии, значит этого нет в условии, и решать задачу нужно исходя из условий.
Итак, опущено условие о том, что люди будут в комнате много раз.
Возможные варианты интерпретации:
1. Люди будут в комнате неограниченное количество раз.
2. Люди будут в комнате ограниченное количество раз.
Если согласиться с первым, то задача имеет смысл (хотя решение все еще найти тяжело).
Если согласиться со вторым, то задача смысла явно не имеет, т.к. в условии явно сказано, что водить будут как угодно!
И мне не понятно, почему вы решили выбрать ту интерпретацию, при которой задача решения не имеет.
Все ограничения и условия упомянуть в тексте невозможно, поэтому там приведены только те, что показались мне разумными. Я не упомянул в задаче, например, что заключенные смотрят на книги, но вы же не стали приводить контрпример с темной Ленинской комнатой, в которой книги, да и обложку от спины различить невозможно.
Возможные варианты интерпретации:
1. Люди будут в комнате неограниченное количество раз.
2. Люди будут в комнате ограниченное количество раз.
Если согласиться с первым, то задача имеет смысл (хотя решение все еще найти тяжело).
Если согласиться со вторым, то задача смысла явно не имеет, т.к. в условии явно сказано, что водить будут как угодно!
И мне не понятно, почему вы решили выбрать ту интерпретацию, при которой задача решения не имеет.
Все ограничения и условия упомянуть в тексте невозможно, поэтому там приведены только те, что показались мне разумными. Я не упомянул в задаче, например, что заключенные смотрят на книги, но вы же не стали приводить контрпример с темной Ленинской комнатой, в которой книги, да и обложку от спины различить невозможно.
-- в условии явно сказано, что водить будут как угодно!
Как угодно, как раз и подразумевает, что как угодно. Могут водить всех до бесконечности, а могут провести всех по одному разу. Как угодно - подразумевает, что, порядок и количество походов в комнату не регламентированно, главное что бы каждый побвал в комнате, а сколько раз не сказано. И при этом, в любом случае, задача должна решаться.
Хорошо, Вы говорите, как угодно. Вот, мне угодно так 1, 2, 3, 4, 5. Ваше решение не срабатывает. Но все ограничения задачи выполнены. Значит задача решения не имеет.
Нет решения - это тоже ответ, это тоже надо доказывать и т.п. Но убрав из задачи одно из условий Вы свели ее из решаемой, к нерешаемой.
Потеря фразы "ни для кого визит не будет последним" - очень много значит.
Как угодно, как раз и подразумевает, что как угодно. Могут водить всех до бесконечности, а могут провести всех по одному разу. Как угодно - подразумевает, что, порядок и количество походов в комнату не регламентированно, главное что бы каждый побвал в комнате, а сколько раз не сказано. И при этом, в любом случае, задача должна решаться.
Хорошо, Вы говорите, как угодно. Вот, мне угодно так 1, 2, 3, 4, 5. Ваше решение не срабатывает. Но все ограничения задачи выполнены. Значит задача решения не имеет.
Нет решения - это тоже ответ, это тоже надо доказывать и т.п. Но убрав из задачи одно из условий Вы свели ее из решаемой, к нерешаемой.
Потеря фразы "ни для кого визит не будет последним" - очень много значит.
Фраза "ни для кого визит не будет последним" не является решающей.
Читаем условие:
Вам этого недостаточно? Ясно же, что последовательность приводом абсолютно случайна и непредсказуема. Единственная оговорка:
"Нет решения" - это ответ на вопрос "есть ли решение у задачи", а не на вопрос "как сделать так-то так-то".
Предложенный Вами вариант 1,2,3,4,5 некорректен, так как водить заключенных будут до тех пор, пока кто-то не скажет, что все уже побывали в комнате. Так что цепочка будет продолжена.
Читаем условие:
Выбирать заключенных я буду как мне хочется: например, сегодня первого три раза свожу, а завтра всех по очереди, а послезавтра обойдетесь.
Вам этого недостаточно? Ясно же, что последовательность приводом абсолютно случайна и непредсказуема. Единственная оговорка:
Рано или поздно каждый из вас побывает в Ленинской комнате
"Нет решения" - это ответ на вопрос "есть ли решение у задачи", а не на вопрос "как сделать так-то так-то".
Предложенный Вами вариант 1,2,3,4,5 некорректен, так как водить заключенных будут до тех пор, пока кто-то не скажет, что все уже побывали в комнате. Так что цепочка будет продолжена.
Во-первых, ни где не сказано, что водить будут до каких-то пор, ну да ладно.
Во-вторых, по поводу случайности, у меня нет ни каких вопросов, случайно это как угодно. Почему бы и не 1 2 3 4 5?
Давайте соблюдем все условия, такая цепочка корректна?
1 2 3 4 5 4 5 4 5 4 5...
решайте.
Во-вторых, по поводу случайности, у меня нет ни каких вопросов, случайно это как угодно. Почему бы и не 1 2 3 4 5?
Давайте соблюдем все условия, такая цепочка корректна?
1 2 3 4 5 4 5 4 5 4 5...
решайте.
1. Водить перестанут в двух случаях - если всех расстреляют или отпустят. Оба варианта следуют за фразой "все побывали". Не сказано, но ведь логично?
2. Если мы говорим про случайности, то теоретически когда-нибудь сложится последовательность, верная для нашего алгоритма. Опять же, в условии описана скорее случайность выбора узников, чем маниакальная привязанность к кому-либо конкретному.
2. Если мы говорим про случайности, то теоретически когда-нибудь сложится последовательность, верная для нашего алгоритма. Опять же, в условии описана скорее случайность выбора узников, чем маниакальная привязанность к кому-либо конкретному.
1. За фразой "Рано или поздно каждый из вас побывает в Ленинской комнате" следует, что каждому гарантировано как минимум одно посещение. Гарантий в бесконечных походах к Марксу и Энгельсу в этой фразе нет. Помоему это логично. Один раз отведут обязательно. А вот больше, могут и водить.
2. А может и не сложится. На то она и случайность, что можно говорить только о вероятности. Утверждать что, будет так - нельзя. Случайность на то и случайность, что может быть любой, а не той на которую вы расчитываете. Вы расчитываете на нормальное распределение, а его может и не быть. Правильно, заведующий концлагерем, он же явно не нормальный. Нельзя от него требовать нормального распределения. Вы не можете быть уверенны как он будет выбирать заключенных, поэтому должны просчитать все варианты.
2. А может и не сложится. На то она и случайность, что можно говорить только о вероятности. Утверждать что, будет так - нельзя. Случайность на то и случайность, что может быть любой, а не той на которую вы расчитываете. Вы расчитываете на нормальное распределение, а его может и не быть. Правильно, заведующий концлагерем, он же явно не нормальный. Нельзя от него требовать нормального распределения. Вы не можете быть уверенны как он будет выбирать заключенных, поэтому должны просчитать все варианты.
1. А где написано, что прекратят водить их туда? Смысл в том, что у них в общем-то два пути:
- Дружно молчать и "вечно" переворачивать книжки.
- Сказать когда-либо "мы все были тут" с двумя известными развязками.
Не выдумывайте лишних проблем. Аналогично можно спросить "а где условие, что они не слепые/безрукие" и т.д.
2. Подобные задачи решаются в общем виде, а не на конкретном наборе входных данных. Теоретически выборка бесконечно, так что вероятность непоявления одного из узников больше нулевая.
3. Где написано, что он "явно" ненормальный?
Ваши слова:
Повторюсь - решайте для удовольствия, не для ворчания.
- Дружно молчать и "вечно" переворачивать книжки.
- Сказать когда-либо "мы все были тут" с двумя известными развязками.
Не выдумывайте лишних проблем. Аналогично можно спросить "а где условие, что они не слепые/безрукие" и т.д.
2. Подобные задачи решаются в общем виде, а не на конкретном наборе входных данных. Теоретически выборка бесконечно, так что вероятность непоявления одного из узников больше нулевая.
3. Где написано, что он "явно" ненормальный?
Ваши слова:
Здравый смысл оставим в стороне, согласитесь, что он к этой задаче ни какого отношения не имеет.
Повторюсь - решайте для удовольствия, не для ворчания.
Вы же математик. Согласитесь, что если алгоритм работает в 99 случаях из 100, то его нельзя считать корректным. То же самое для вашей задачи. Опущенное условие является ключевым при доказательства корректности решения.
Попробуйте сами составить условие данной задачи так, чтобы она решалась корректно, была максимально усложнена и не имела побочных решений типа "съесть страницу".
Не забывайте, что хоть задача и математическая, но она приближена к жизни, ибо условия "Маркса и Энгельса" намного приятнее сухих Иксов и Игреков. Соответственно нелогично, если бы заведующего лагерем кто-то мог заставить вызывать кого-то столько раз, а другого один раз или ни разу. Он просто олицетворяет генератор случайных чисел в данной задаче.
Помимо алгоритмов при решении обязательно надо включать здравый смысл (либо юмор, если цель получить удовольствие от процесса поиска альтернативного, заведомо неправильного, но смешного решения).
PS. Извините, если обижу, но Вы показали себя занудой.
Не забывайте, что хоть задача и математическая, но она приближена к жизни, ибо условия "Маркса и Энгельса" намного приятнее сухих Иксов и Игреков. Соответственно нелогично, если бы заведующего лагерем кто-то мог заставить вызывать кого-то столько раз, а другого один раз или ни разу. Он просто олицетворяет генератор случайных чисел в данной задаче.
Помимо алгоритмов при решении обязательно надо включать здравый смысл (либо юмор, если цель получить удовольствие от процесса поиска альтернативного, заведомо неправильного, но смешного решения).
PS. Извините, если обижу, но Вы показали себя занудой.
Генератор случайных чисел говорите - так на то они и случайные числа что, ни кто не может гарантировать что и когда выпадет, и вападет ли вообще определенное число. Порешайте задачи на теорию вероятностей. Или, лучше на рулетке поиграйте, и объясните шарику, что вот не должен ты 10 раз подряд на черное падать.
Здравый смысл оставим в стороне, согласитесь, что он к этой задаче ни какого отношения не имеет.
---Извините, если обижу, но Вы показали себя занудой.
Спасибо, сочту за комплимент.
Здравый смысл оставим в стороне, согласитесь, что он к этой задаче ни какого отношения не имеет.
---Извините, если обижу, но Вы показали себя занудой.
Спасибо, сочту за комплимент.
>>Здравый смысл оставим в стороне, согласитесь, что он к этой задаче ни какого >>отношения не имеет.
Решите-ка эту задачу БЕЗ здравого смысла, а я посмотрю :)
Если говорить про теорию вероятности, то альтернативы (выбор узника для экскурсии в комнату) равновероятны, так что как раз неоднократное появление всех узников в комнате за какой-либо период очень даже предсказуемо. Гарантию никто не даст, конечно. Как никто не даст гарантию, что у заведующего не случится сердечного приступа или на обеих книжках не сотрутся заголовки.
Решайте задачу для себя, для интереса, а не для того, чтобы придираться к задающему.
Решите-ка эту задачу БЕЗ здравого смысла, а я посмотрю :)
Если говорить про теорию вероятности, то альтернативы (выбор узника для экскурсии в комнату) равновероятны, так что как раз неоднократное появление всех узников в комнате за какой-либо период очень даже предсказуемо. Гарантию никто не даст, конечно. Как никто не даст гарантию, что у заведующего не случится сердечного приступа или на обеих книжках не сотрутся заголовки.
Решайте задачу для себя, для интереса, а не для того, чтобы придираться к задающему.
-- Гарантию никто не даст, конечно.
Нет гарантии нет и решения, тут даже обсуждать нечего.
--Если говорить про теорию вероятности, то альтернативы (выбор узника для экскурсии в комнату) равновероятны, так что как раз неоднократное появление всех узников в комнате за какой-либо период очень даже предсказуемо.
1. С чего это Вы взяли, что альтернативы равновероятны?
2. Даже если это и так, если вы переходите в плоскость вероятностей, то решение гораздо проще. Надо каждому считать сколько раз он был в комнате, и когда сосчитает до 10, то значит и другие уже были в Ленинке, с очень высокой вероятностью.
--Решайте задачу для себя, для интереса, а не для того, чтобы придираться к задающему.
:))) с таким же успехом я могу сказать Вам, - "Ну Вы решили, задачу? Получили удовольствие от этого? Развили свой кругозор? Интересно было? Вот и здорово! И чего это Вы теперь решили ко мне придираться?"
Но не буду.
Я не придираюсь, а говорю о явной ошибке в условии задачи.
Нет гарантии нет и решения, тут даже обсуждать нечего.
--Если говорить про теорию вероятности, то альтернативы (выбор узника для экскурсии в комнату) равновероятны, так что как раз неоднократное появление всех узников в комнате за какой-либо период очень даже предсказуемо.
1. С чего это Вы взяли, что альтернативы равновероятны?
2. Даже если это и так, если вы переходите в плоскость вероятностей, то решение гораздо проще. Надо каждому считать сколько раз он был в комнате, и когда сосчитает до 10, то значит и другие уже были в Ленинке, с очень высокой вероятностью.
--Решайте задачу для себя, для интереса, а не для того, чтобы придираться к задающему.
:))) с таким же успехом я могу сказать Вам, - "Ну Вы решили, задачу? Получили удовольствие от этого? Развили свой кругозор? Интересно было? Вот и здорово! И чего это Вы теперь решили ко мне придираться?"
Но не буду.
Я не придираюсь, а говорю о явной ошибке в условии задачи.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Маркс и Энгельс