roboforum.ru

Технический форум по робототехнике.


Занимательные задачи которых нет в ин-ете

Все здесь

Re: Занимательные задачи которых нет в ин-ете

Сообщение =DeaD= » 12 янв 2009, 16:46

Digit писал(а):А! Понял :) Я там не корректно написал.

Именно :) и не в 1 месте :)


Digit писал(а):В общем, в моем 1-м алгоритме в первый день только заключенный №1 может включить телек без оглядки на его предыдущее состояние.

Не проходит, тогда последовательности 1 2 3 и 1 3 4 тоже обе дадут 1 на выходе.

Digit писал(а):с 1 по 11 день все также, как в способе №2.
с 12 дня включительно заключенные телек не трогают.
если на 20-й день телек работал, то косяк. А если на протяжении второго десятка дней телек был выключен, значит посмотрели все.

Вот это вроде правильное решение, ну или будем считать что правильно, остальное мелочи, давай я его короче сформулирую для всех:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если № заключенного не совпал с № дня - заключенный выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Теперь вопрос - есть ли алгоритм приводящий к правильном определению, были ли все, с большей вероятностью?

Добавлено спустя 5 минут 27 секунд:
Ну и можно ли доказать, что не существует более оптимального алгоритма :)

Добавлено спустя 5 минут 53 секунды:
По сути поведение каждого заключенного в каждый день представляется 2 битами - что он сделает если увидит состояние телевизор 0 и если увидит состояние телевизора 1.

Итого всего алгоритмов может быть - (2^2)^(10*20)=2^400, - есть где порыться :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 12 янв 2009, 17:07

=DeaD= писал(а):давай я его короче сформулирую для всех:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если № заключенного не совпал с № дня - заключенный выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Теперь вопрос - есть ли алгоритм приводящий к правильном определению, были ли все, с большей вероятностью?

Есть :)
Ты сформулировал мой первый алгоритм с доработкой из моего последнего поста. Но есть и мой алгоритм №2. В твоем стиле он напишется так:
1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если заключенный бывал уже у телика - он выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение =DeaD= » 12 янв 2009, 17:29

Digit писал(а):1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если заключенный бывал уже у телика - он выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Зачот! :) а еще быстрее выйти на свободу?

Пока вероятность срабатывания алгоритма 10!/10^10 ~= 0,036%

А вероятность, что побывают все сама по себе - сейчас прикину :)

Добавлено спустя 48 секунд:
PS: Digit, а ты в детстве не участвовал во всяких олимпиадах математических? :)

Добавлено спустя 12 минут 40 секунд:
Подсчет реальной вероятности, что все побывают в комнате минимум по 1 разу за 20 дней:
Всего исходов: 10^20.

Будем кодировать 2 уровнями возможные случаи, сгруппировав их в классы.

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

Понятно что размер класса в котором заключенные 1..10 побывали в комнате с телевизором N1..N10 раз есть 20!/(N1!*N2!*...*N10!).

Теперь нам надо быстро перебрать эти классы, чтобы сложить их размеры, для этого мы будем перебирать комбинации 10 чисел, таких, что каждая из них минимум единица и в сумме будет 20, что эквивалентно комбинациям 10 чисел, каждое из них минимум 0 и в сумме будет 10. А таких комбинаций у нас 19!/(10!*9!)=92378 :)

Чего-то тут надо программку писать уже :)


Добавлено спустя 1 минуту 6 секунд:
2Digit: Кстати, а что если такой алгоритм:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 20 день если заключенный бывал уже у телика 2 раза - он выключает телевизор;
3. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Он лучше или нет?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 12 янв 2009, 17:41

Dead, у меня от твоих выкладок моск вскипел :shock: :D
На олимпиадах математических был несколько раз в детстве, но безрезультатно 8)

=DeaD= писал(а):2Digit: Кстати, а что если такой алгоритм:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 20 день если заключенный бывал уже у телика 2 раза - он выключает телевизор;
3. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Он лучше или нет?

Я так понимаю, что на третий заход заключенного он вырубает, да?
Лучше ли... ХЗ :pardon: Либо такой же, либо лучше (точно не хуже). Мне кажется, что лучше. Но посчитать я не осилю :crazy:
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение =DeaD= » 12 янв 2009, 17:44

Вероятность этого алгоритма (когда на 3-й заход вырубает): 20!/(2^10)/10^20=0.0023%, вот! посчитал! :)

так что хуже оно...

Добавлено спустя 39 секунд:
Digit писал(а):На олимпиадах математических был несколько раз в детстве, но безрезультатно 8)

Оч странно :) неправильные олимпиады? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 12 янв 2009, 17:51

=DeaD= писал(а):Оч странно :) неправильные олимпиады? :)

просто у нас в стране много талантливых одаренных детей :)

Добавлено спустя 46 секунд:
=DeaD= писал(а):Вероятность этого алгоритма (когда на 3-й заход вырубает): 20!/(2^10)/10^20=0.0023%, вот! посчитал! :)

так что хуже оно...

Мдя...
Ну тогда думаем дальше :)
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение Ruslan » 12 янв 2009, 18:04

Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Я пытаюсь адаптировать этот алгоритм к 20 дням, но не получается. Может в условиях ошибка? Например, следует ли считать все визиты к телеку с первого дня или только визиты с начала 20-дневного периода?
Аватара пользователя
Ruslan
 
Сообщения: 603
Зарегистрирован: 03 июн 2007, 22:32
Откуда: Москва
ФИО: Руслан

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 12 янв 2009, 18:13

В нашем случае Н должен выключить телек 9 раз... Но к нашим условиям это решение не подходит, т.к. короткий и главное ограниченный промежуток времени. Т.е. условие не в том, чтоб определить, когда все посмотрят, а определить, все ли посмотрели.
В общем, это решение другой задачи
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение =DeaD= » 12 янв 2009, 18:22

Digit писал(а):просто у нас в стране много талантливых одаренных детей :)

Не настолько :) а ты на какого уровня олимпиадах был?

Добавлено спустя 3 минуты 11 секунд:
RiO писал(а):Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте :)

Добавлено спустя 38 секунд:
Digit писал(а):В общем, это решение другой задачи

Это не решение - где гарантия что все посмотрели, когда Н это объявил?

Добавлено спустя 3 минуты 10 секунд:
А вообще хороший вопрос - есть ли более эффективный алгоритм для 100 или 1000 дней и 10 заключенных? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 12 янв 2009, 22:58

=DeaD= писал(а):а ты на какого уровня олимпиадах был?

на краевых
=DeaD= писал(а):
RiO писал(а):Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте :)

на самом деле косяк не в отсутствии гарантии, а в том, что есть великий шанс, что Н не дождется 9 включений, т.к. при текущем описании алгоритма при попадении первый раз к ТВ заключенных №3, №8 и Н, последний зафиксирует только 1 включение, тогда как включалось по факту 2 раза и заключенный №8 больше включать телек не будет.


=DeaD= писал(а):А вообще хороший вопрос - есть ли более эффективный алгоритм для 100 или 1000 дней и 10 заключенных? :)

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

а вообще, что-то мне это все напоминает теорию кодирования и передачи сигналов :crazy:
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение Ruslan » 13 янв 2009, 00:12

=DeaD= писал(а):Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте :)

Если не был, то Н выключит телек только 18 раз.

Может уже автор поделится ответом для 20 дней?
Аватара пользователя
Ruslan
 
Сообщения: 603
Зарегистрирован: 03 июн 2007, 22:32
Откуда: Москва
ФИО: Руслан

Re: Занимательные задачи которых нет в ин-ете

Сообщение Digit » 13 янв 2009, 09:21

Rio, а что насчет моих мыслей, которые я привел выше, о твоем алгоритме?
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Занимательные задачи которых нет в ин-ете

Сообщение =DeaD= » 13 янв 2009, 09:24

2RiO: Не катит так. Вот если модифицировать чуть решение:

1. Выбирается заключенный "наблюдатель" (далее Н);
2. Заключенный пришедший в первый день инициализирует телевизор выключая его, а дальше действует как все, как будто только пришел;
3. Каждый заключенный кроме Н если попадает в комнату с выключенным телевизором и еще ни разу не переводил его в состояние ВКЛ, включает его;
4. Если Н видит включенный телевизор, он выключает его;
5. Если Н выключил телевизор 9 раз - значит все побывали уже.

Правда это будет эффективно при количестве дней наверное от 100 и выше, надо считать... но уже ломает такие сложные вещи считать по вероятности :) могу утверждать, что этот алгоритм будет очень эффективен при количестве дней от 500 :)

Добавлено спустя 57 секунд:
RiO писал(а):Может уже автор поделится ответом для 20 дней?

Ответ для 20 дней известен мне в 2 вариантах - когда заключенные только по своему номеру и дням называют и путём исключения 2-го посещения в первые 10 дней, в общем оба решения Digit'a.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Занимательные задачи которых нет в ин-ете

Сообщение Ruslan » 13 янв 2009, 10:21

Digit писал(а):на самом деле косяк не в отсутствии гарантии, а в том, что есть великий шанс, что Н не дождется 9 включений, т.к. при текущем описании алгоритма при попадении первый раз к ТВ заключенных №3, №8 и Н, последний зафиксирует только 1 включение, тогда как включалось по факту 2 раза и заключенный №8 больше включать телек не будет.

Действительно, в этом случае требуется поправка DeaDa (спасибо ему) . #8 должен дождаться пока увидит выключенный телек и таки включить его.
Аватара пользователя
Ruslan
 
Сообщения: 603
Зарегистрирован: 03 июн 2007, 22:32
Откуда: Москва
ФИО: Руслан

Пред.

Вернуться в Свободное общение

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Mail.ru counter