P>Все — а сейчас я буду думать над решением, если надумаю — отвечу в следующем посте.
Т.к. из условия не ясно видно ли из камер состояние лампочки, то будем решать разные варианты:
Итак вариант когда ламочка видна отвсюду простой, его решение следующее:
если лампочка включена, то все ее выключают
если лампочка включена, то:
-если человек не включал лампочку — он включает
-если человек уже включал лампочку — он ничего не делает
В итоге как только последний человек войдет первый раз в камеру * 1.5 (коллизии на уже включенную лампочку) —
мы сразу это заметим. Следовательно все выйдут ровно через месяц...
Для варианта когда лампочка не видна все сложнее — буду думать...
P>>Все — а сейчас я буду думать над решением, если надумаю — отвечу в следующем посте.
Кстати уточнение к моей оценки ваших решений, время, которое потребуется для решения вашего варианта равно не 200 дней, а 2000:
т.е. 100*100*2 / 10 итераций в день... Вот такие пироги поэтому нужно искать более лучшие решения.
А>Для варианта когда лампочка не видна все сложнее — буду думать...
Есть неточное решение, зависящее от свойств генератора случайных чисел охранника
Алгоритм таков:
Когда человек первый раз входит в комнату — он инвертирует состояние лампочки
В остальных случаях он ничего не делает, а только запоминает информацию о состоянии.
Таким образом, если состояние меняется с момента последнего посещения — значит недавно был
первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже
давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!)
можно предположить что все уже были.
Собственно нужны доп. условия. Т.к. эта задача наверняка из реальной жизни (например какого-нибудь распознавания образа и т.п.),
то всегда можно сделать допущения на точность в обмен на скорость, а значит это решение может быть лучшим.
P>Таким образом, если состояние меняется с момента последнего посещения — значит недавно был P>первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже P>давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!) P>можно предположить что все уже были.
Собственно можно уточнить это число следующим образом:
это число должно быть не меньше 10, но и не меньше 2*К, где К — количество его посещений в ситуации
когда лампочка меняла свое состояние. Таким образом выполняется некоторая калибровка генератора случ.
чисел охранника. Например на случай если он будет водить одного и того же человека через раз. В этом
случае он 100 раз заметит изменение, а потом наступит затишье...
Собственно коэффициент 2, как и число 10 взято наобум, но примерно отражают суть — точные значения нужно брать
из эксперимента.
S>чтобы каждый из твоих родичей убрался в комнате по одному разу.
А как это вообще возможно? Убраться в комнате можно только один раз, поскольку если один человек уберётся в комнате, то она станет чистой, а чистую комнату убрать в дальнейшем невозможно. Следовательно, больше никто не сможет убрать мою комнату. Следовательно, все родители убраться в моей комнате не могут.
S> Ну вот теперь ответь на такой вопрос: "После какой по числу уборки ты будешь уверен, что заходили все твои родичи, если никто, кроме тебя, в комнате свинячить не имеет права, а ты не любишь убираться?"
Даже если предположить что одну комнату можно убрать несколько раз или же я каждый день там свинячу, я никогда не буду уверен что в комнате побывали все мои родичи. Отец мог всё время проваляться на диване и не двигаться, а мать часто заходить в мою комнату и постоянно там убираться. Или я неправ?
P>>Таким образом, если состояние меняется с момента последнего посещения — значит недавно был P>>первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже P>>давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!) P>>можно предположить что все уже были. P>Собственно можно уточнить это число следующим образом: P>это число должно быть не меньше 10, но и не меньше 2*К, где К — количество его посещений в ситуации P>когда лампочка меняла свое состояние. Таким образом выполняется некоторая калибровка генератора случ. P>чисел охранника. Например на случай если он будет водить одного и того же человека через раз. В этом P>случае он 100 раз заметит изменение, а потом наступит затишье...
P>Собственно коэффициент 2, как и число 10 взято наобум, но примерно отражают суть — точные значения нужно брать P>из эксперимента.
Загвоздка ещё в том, что один из заключённых может за это время:
а) умереть;
б) быть освобождён;
в) заболеть заразной болезнью.
Таким образом, со временем, с увеличением вероятности прохода всех заключённых через эту комнату, увеличивается также вероятность исключения заключённого из эксперимента, а значит, сведения задачи к нерешаемой, поскольку по условию задачи, один из зэков должен сказать что все 100 прошли через эту комнату. Если из эксперимента выбыл тот участник, что в комнате не был, задача становится нерешаемой. Другими словами, увеличение шансов на победу со временем компенсируется уменьшением шансов успешной комбинации так таковой.
Третий случай — пример отношения тюремщика к заключённому. Если тюремщик боится выпускать зэка их камеры или боится к нему подойти, то маловероятно что через комнату пройдут все зэки.
JP>А как это вообще возможно? Убраться в комнате можно только один раз, поскольку если один человек уберётся в комнате, то она станет чистой, а чистую комнату убрать в дальнейшем невозможно. Следовательно, больше никто не сможет убрать мою комнату. Следовательно, все родители убраться в моей комнате не могут.
JP>Даже если предположить что одну комнату можно убрать несколько раз или же я каждый день там свинячу, я никогда не буду уверен что в комнате побывали все мои родичи. Отец мог всё время проваляться на диване и не двигаться, а мать часто заходить в мою комнату и постоянно там убираться. Или я неправ?
... Ты им так и говоришь: "Каждый зашедший в комнату должен убраться, если там грязно и если он еще не убирался там, начиная с сегодняшнего дня! В противном случае убираться запрещаю!" ...
т.е.
if ((грязно)&&(не убирался)) { уберись }
else { свободен };
... << Rsdn@Home 1.1.4 beta 1 >> В winamp'е зажигает Woman From Tokyo
JP>Так бы сразу и сказал. Только мне всё равно неясно: после какого раза я могу уверенно сказать что в моей комнате перебывали все?
ТОчнее, не так. В случае с комнатой всё очевидно. Я — единственный кто знает сколько раз я там насвинячил и единственный кто веду статистику уборок. ПОэтому достаточно насвинячить ровно столько раз сколько членов остальной семьи в доме. В случае же с тюрмой, статистику посещений ведёт только надзиратель. Никто из зэков не знает сколько раз в комнате перебывало народу и не знает сколько раз была включена/выключена лампочка. Вот в чём дело.
Здравствуйте, J-peg, Вы писали:
JP>>Так бы сразу и сказал. Только мне всё равно неясно: после какого раза я могу уверенно сказать что в моей комнате перебывали все?
JP>ТОчнее, не так. В случае с комнатой всё очевидно. Я — единственный кто знает сколько раз я там насвинячил и единственный кто веду статистику уборок. ПОэтому достаточно насвинячить ровно столько раз сколько членов остальной семьи в доме. В случае же с тюрмой, статистику посещений ведёт только надзиратель. Никто из зэков не знает сколько раз в комнате перебывало народу и не знает сколько раз была включена/выключена лампочка. Вот в чём дело.
в случае с тюрьмой известно, сколько раз включалась лампочка, поскольку кроме тебя там никто свет не включает (так же как в случае с комнатой никто не свинячит, кроме тебя).
... << Rsdn@Home 1.1.4 beta 1 >> В winamp'е зажигает Woman From Tokyo
S>в случае с тюрьмой известно, сколько раз включалась лампочка, поскольку кроме тебя там никто свет не включает (так же как в случае с комнатой никто не свинячит, кроме тебя).
Да, теперь я понял. Выбирается один человек, кто включает лампочку. Остальные её выключают если они ещё этого не делали. Отсюда выходит ещё одно "но". 99 заключённых должны побывать в комнате хотя бы один раз. Один заключённый должен побывать там не менее 99 раз.
