Fireman Опубликовано 22 апреля, 2019 Поделиться Опубликовано 22 апреля, 2019 Первый день сидит клубень-1, второй день сидит клубень-2. С какой вероятностью клубень-3 окажется там в третий день? 1/2 - вот с такой, поскольку выбор будет случайный между клубнем-1 и клубнем-3. Но ведь никто не запрещает несколько раз одного и того же сажать. 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 22 апреля, 2019 Поделиться Опубликовано 22 апреля, 2019 Я пока не могу понять, как счётчик по дням организовать, чтобы он каждому клубню был понятен, т.к. клубни могут вызываться как угодно рандомно и повторно по сто раз. Необходимы исключения: Клубни не могут вызываться более одного раза - 1я задача Не более двух раз 2я задача Трёх раз - 3я. И т.д. Тогда счётчик дней можно использовать 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 апреля, 2019 Автор Поделиться Опубликовано 22 апреля, 2019 Но ведь никто не запрещает несколько раз одного и того же сажать. Я недавно уже рассуждал на эту тему -> 1. Посмотрим внимательнее. В условии ничего не сказано как именно злые админы выбирают очередную жертву. Есть же два варианта: забирают из карцера вчерашнего фанклубня, отводят в его камеру, а потом уже случайно выбирают нового. То есть, в "лотерее" участвуют все забаненные клубни. Но мне кажется, что для админов это слишком сложно и надо два раза в карцер ходить. То есть, они приходят к оставшимся фанклубням, выбирают случайного и потом меняют местами того, кто уже сидит - и нового. То есть, в выборке участвуют "все минус один". Ну, если принимаем гипотезу неленивых админов, то ладно - пускай все забаненные клубни случайно участвуют в лотерее. Тогда решение для тривиальных случаев тоже самое, но при условии "минус один клубень". 2 клубня. Второй знает, что он ни разу не был в карцере. И как только там оказывается - они на свободе. 3 клубня. А вот тут без лампочки не обойтись.. Необходимы исключения: Клубни не могут вызываться более одного раза - 1я задача Не более двух раз 2я задача Трёх раз - 3я. Нет! Нет никаких исключений. Клубни в карцер попадают совершенно случайно. И, как мы только что договорились, в лотерее участвуют все забаненные клубни, включая того, который сидит в карцере. 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 апреля, 2019 Автор Поделиться Опубликовано 22 апреля, 2019 1. Посмотрим внимательнее. В условии ничего не сказано как именно злые админы выбирают очередную жертву. Есть же два варианта: забирают из карцера вчерашнего фанклубня, отводят в его камеру, а потом уже случайно выбирают нового. То есть, в "лотерее" участвуют все забаненные клубни. Но мне кажется, что для админов это слишком сложно и надо два раза в карцер ходить. То есть, они приходят к оставшимся фанклубням, выбирают случайного и потом меняют местами того, кто уже сидит - и нового. То есть, в выборке участвуют "все минус один". Нет! Нет никаких исключений. Клубни в карцер попадают совершенно случайно. И, как мы только что договорились, в лотерее участвуют все забаненные клубни, включая того, который сидит в карцере. Кстати, этот тезис нисколько не противоречит ленивости админов. Просто они кидают жребий и если он выпадает на уже сидящего в карцере клубня, то они вообще никуда не идут и сразу начинают пить пиво.. Итак, какова стратегия клубней, если их три или больше? Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 апреля, 2019 Автор Поделиться Опубликовано 22 апреля, 2019 Увы, "жаль подмога не пришла, подкрепленье не прислали, что ж обычные дела..." (с) ... да ладно, я шучу. Но, очень жаль, что решение задачки пришло не из фанклуба. А несчастных фанклубней, томящихся в казематах злобных админов, - опять спасать мне.. Алгоритм: 1) Забаненный фанклубень, который первым попадает в карцер (далее "первый фанклубень" = ПФК), в первый день своего заточения включает лампочку. И всё. 2) При последующих заточениях в карцере ПФК смотрит на лампочку: - если она горит, то он ничего не делает вообще. Сидит и ждёт. - если лампочка НЕ горит, то он делает "memory++" и включает лампочку. 3) Все остальные клубни знают, что они пропустили первый день; что не они считают задачку. У них другой алгоритм: - каждый не-ПФК должен ОБЯЗАТЕЛЬНО выключить лампочку, но только ОДИН раз за всё время отсидки. То есть, - если лампочка горит и он УЖЕ выключал её хоть раз, то он сидит и ничего не трогает. - если лампочка горит, но он НЕ ВЫКЛЮЧАЛ её ни разу, то он её выключает. И больше не трогает никогда. 4) ПФК, каждый раз снова попадая в карцер, видит был ли новый фанклубень за время его отсутствия или же нет. Так вот, вторая задачка: рассчитать примерное количество дней, когда они - ура!! - и пошли пить пиво. Хе-хе, чмоки! // но вижу, что задачка не понравилась... Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 Мне понравилась Я не подумал на счёт того, чтобы ПФК всех пересчитывал - интересное решение, Спасибо. Ссылка на комментарий Поделиться на другие сайты Поделиться
Fireman Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 (изменено) Есть ещё самый быстрый (!!!!) в максимуме, но и наверное самый медленный в среднем способ вытащить клубней Для удобства покажу это на 7 клубнях. Каждому клубню назначается свой день недели - понедельник, вторник, ..., воскресенье если клубень-понедельник приходит в понедельник (т.е. в свой день), то он включает свет если любой из клубней приходит не в свой день - он выключает свет (если свет горит) если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении Такой алгоритм даёт самый быстрый способ определить, что все клубни побывали в помещении - всего 7 дней и быстрее быть уже не может, но... это очень редкий случай. Теперь давайте подсчитаем какая вероятность побывать всем клубням в помещении за определённое кол-во дней: пусть кол-во клубней - N вероятность того, что каждый клубень попадёт на свой день равна 1/Nn (всего возможно Nn комбинаций перемешивания N клубней в течении N дней, при этом один клубень может в течении N дней по нескольку раз бывать в помещении слез и печали ) вероятность того, что ситуации, когда каждый клубень попадёт на свой день соответственно (1 - 1/Nn) пусть всего было k циклов по N дней вероятность того, что за все k циклов клубни так и не побывали каждый в своем дне в течении одного цикла будет (1-1/Nn)k вероятность того, что за k циклов клубни таки побывают каждый в своем дне в течении одного цикла соответственно будет (1 - (1-1/Nn)k) пусть всего над клубнями издевались D дней, т.е. k = D/N циклов вероятность p выйти за D дней тогда будет (1 - (1-1/Nn)D/N) = p т.е. кол-во дней D за которые вероятность выйти N клубням на свободу составит p равна D = N log(1-1/Nn)(1-p) вот так это выглядит на графике т.е. 4 бедных клубней при такой системе выйдет с вероятностью 50% только через 708 дней , а 7 "недельных" клубней очутятся на свободе всего через 10952 года Изменено 23 апреля, 2019 пользователем Fireman Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении тоже интересное решение, но частное. По логике немного совпадает с логикой Е.К.@Fireman, для клубней больше 7ми не годится, т.к. лампочка может уже остаться включенной на 7м, но при этом 8й и дальше могут и не побывать Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 23 апреля, 2019 Автор Поделиться Опубликовано 23 апреля, 2019 Для удобства покажу это на 7 клубнях. Каждому клубню назначается свой день недели - понедельник, вторник, ..., воскресенье если клубень-понедельник приходит в понедельник (т.е. в свой день), то он включает свет если любой из клубней приходит не в свой день - он выключает свет (если свет горит) если клубень-воскресенье приходит в свой день и видит, что свет горит - всё, значит все клубни побывали в помещении 1. Не понял.. Пусть жребий выпал таким образом, что с понедельника по пятницу в карцере сидят клубень-понедельник и клубень-вторник только. А в субботу в карцер попадает клубень-суббота, включает свет, чем вводит в заблуждение завтрашнего клубня-воскресенье.. Что-то не так в алгоритме. Теперь давайте подсчитаем какая вероятность побывать всем клубням в помещении за определённое кол-во дней: 2. А давайте подсчитаем вероятность 50% выхода для моего "линейного" решения. пусть кол-во клубней - N вероятность попадания клубня в карцер равна 1/N ... ой, мне пора по делам бежать. Считайте без меня пока! Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 (изменено) в субботу в карцер попадает клубень-суббота, включает свет он оставляет свет включенным, если и до него этот свет был включенным. Каждый клубень по дням недели должен ждать, чтобы перед ним тоже свет был включенным. Но этот алгоритм действует только для 7х. А вот если все в фан-клубе пересчитаются и у каждого будет свой индивидуальный порядковый номер - тут может и можно что-то придумать Изменено 23 апреля, 2019 пользователем oit Ссылка на комментарий Поделиться на другие сайты Поделиться
Fireman Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 (изменено) Что-то не так в алгоритме. имеется в виду, что способ описывает ситуацию, когда все клубни побывают только в свои дни и этот факт будет отражён горящей лампочкой например, если у нас есть 365 клубней, то мы ждём ситуацию, когда каждый клубень будет выбран в свой день, если это не произошло и клубень выключил свет, все - свет сможет включить только первый клубень 1 января (если на него падёт жребий) понятно, что такой способ безумно медленный, но существует вероятность, что все клубни сразу попадут в свои дни - тогда описанный способ даст самый быстрый способ Тоже интересное решение, но частное. не совсем частное - в первом случае первый клубень выступает в роли счётчика (есть даже термин для такой ситуации - "битовый счётчик") во втором - счётчика как такового нет, последний клубень просто устанавливает факт, что начальное состояние системы так и не было изменено (т.е. система развивалась в установленном направлении. Изменено 23 апреля, 2019 пользователем Fireman Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 @Fireman, вы же по дням недели раскладывали клубней ... Ссылка на комментарий Поделиться на другие сайты Поделиться
Fireman Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 Тоже интересное решение, но частное. не совсем частное - в первом случае первый клубень выступает в роли счётчика (есть даже термин для такой ситуации - "битовый счётчик") во втором - счётчика как такового нет, последний клубень просто устанавливает факт, что начальное состояние системы так и не было изменено (т.е. система развивалась в установленном направлении. Ссылка на комментарий Поделиться на другие сайты Поделиться
oit Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 Вероятность конечно же есть, но чем больше клубней, тем ниже вероятность Ссылка на комментарий Поделиться на другие сайты Поделиться
Fireman Опубликовано 23 апреля, 2019 Поделиться Опубликовано 23 апреля, 2019 Вероятность конечно же есть, но чем больше клубней, тем ниже вероятность конечно, причём если судить по формулам, то очень быстро падает в практически 0. Поэтому метод с первым клубнем-счётчиком гораздо эффективнее в среднем. Надо прикинуть вероятность выйти, но она на порядки (!!!) должна быть выше чем во втором случае Для первого метода с вероятностью p выйти за D дней получается следующее (если я не ошибся): весь процесс с выходом клубней на свободу можно разбить на (N - 1) циклов, в каждом цикле один из клубней выбирается впервые, в клубень #1 подсчитывает его таким образом на каждый цикл затрачивается r = D / (N - 1) дней каждый цикл можно разбить на 2 этапа - на первом этапе (скажем в течении x дней ожидаем выбора очередного клубня #i, а в течении следующих (r - x) дней ожидаем выбора клубня #1, чтобы он подсчитал клубня #i вероятность выбора любого клубня в любой день 1/N вероятность не выбрать клубня в любой день (1 - 1/N) вероятность не выбрать клубня в течении x дней (1-1/N)x вероятность выбрать клубня в течении x дней (1 - (1-1/N)x) вероятность выбрать клубня #i в течении х дней и клубня #1 в течении (r - x) дней соответственно q = (1 - (1-1/N)x)*(1 - (1-1/N)r-x) максимальная вероятность этого события при x = r/2 и равна q = (1 - (1-1/N)0.5r)2 а итоговая вероятность p соответственно равна p = qN-1= (1 - (1-1/N)0.5r)2(N-1) D = (N - 1) log(1-1/N)(1 - p0.5/(N-1))2 тут вероятность получается гораздо приятнее Т.е. с вероятностью 50% 100 клубней обретут свободу всего за 300 лет Ссылка на комментарий Поделиться на другие сайты Поделиться
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти