Перейти к содержимому


Фотография

Загадка


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 37

#21 ang

ang

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 417 сообщений

Отправлено 07 Ноябрь 2011 - 14:14

Я долго не мог понять правильный ответ. Но теперь понял, перефразирую:
заключенный а[n];
натуральное число count=0;
положение_рычага=вниз;
пока (count!=n-1)
{
натуральное_число r;
r=случайное(n);
//вводим заключенного под номером r
если (r=x)и(положение_рычага=вниз)
{
положение_рычага=вверх;
count=count+1;
}
если (r!=x)и(положение_рычага=вверх)и(a[r].переключал_рычаг=ложь)
{
положение_рычага=вниз;
a[r].переключал_рычаг=истина;
}
}


x -номер выбранного заключенного

Это сообщение отредактировано ang - 7 ноября 2011 | 15:18


#22 hamster

hamster

    Pixelhunter

  • Пользователи
  • PipPipPip
  • 7 832 сообщений

Отправлено 07 Ноябрь 2011 - 14:21

Хоть кто-то смог по действиям объяснить, а то я со слов exelenz ничего не понял. Я в начале думал, что сделать нужно за один цикл прогулки.


#23 Wasteland Rat

Wasteland Rat

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 403 сообщений

Отправлено 07 Ноябрь 2011 - 14:45

Ну лично я решение сразу понял, проблемка-то в этом:
r=случайное(n);

И сколько таких "стохастических испытаний" надо провести, чтобы все точно побывали на прогулке? 10? 100? может 10^9? Да и то точно никогда не получится, получится что с такой-то вероятностью после стольких-то испытаний все побывают на прогулке. Мутное это "обещание" начальника тюрьмы, мутное и неформализованное.


#24 ang

ang

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 417 сообщений

Отправлено 07 Ноябрь 2011 - 14:54

Хех, смотря как часто водить будут, и сколько заключенных может появиться. Но если мы возьмем честных тюремщиков, которые будут водить дейсвительно случайного заключенного. То за разумные сроки все будет.


#25 Massaraksh

Massaraksh

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 706 сообщений

Отправлено 07 Ноябрь 2011 - 15:02

QUOTE
Пусть переключатель изначально находится в положении "верх" и количество заключенных = K. Тогда все заключенные кроме одного должны будут при входе в комнату поставить переключатель "вниз", но только один раз. Оставшийся заключенный всегда переключает его "вверх", считая количество переключений.

Так я не понял, а как заключенные об этом друг с другом договорятся, если по условиям задачи общение друг с другом им запрещено?


#26 eye-eye mkII

eye-eye mkII

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 913 сообщений

Отправлено 07 Ноябрь 2011 - 15:32

QUOTE
Так я не понял, а как заключенные об этом друг с другом договорятся, если по условиям задачи общение друг с другом им запрещено?

Ага! Не я один такой!
QUOTE
Читаем решение ещё раз:

QUOTE
...После этого заключённым разрешили собраться и обсудить стратегию, потом развели по камерам.

Вообще, конечно, за корявую формулировку задачи, Фриказоиду неуважение.


#27 Wasteland Ghost

Wasteland Ghost

    Маленькое Злое Привидение

  • Пользователи
  • PipPipPip
  • 3 451 сообщений

Отправлено 07 Ноябрь 2011 - 16:59

QUOTE
И сколько таких "стохастических испытаний" надо провести, чтобы все точно побывали на прогулке? 10? 100? может 10^9? Да и то точно никогда не получится, получится что с такой-то вероятностью после стольких-то испытаний все побывают на прогулке. Мутное это "обещание" начальника тюрьмы, мутное и неформализованное.

Что-то в теме прям торжество невнимательности. :) Я же писала: если заключённых 100 и выводят их раз в сутки по одному, то среднее время выполнения цикла — 28 лет. Строгое математическое доказательство (а также другие варианты решения) — в статье по ссылке (инглиш, правда).


#28 Artem13

Artem13

    13-й воин

  • Пользователи
  • PipPipPip
  • 2 390 сообщений

Отправлено 07 Ноябрь 2011 - 18:06

Ой Ё! Как то я про 1 раз тоже прошляпил....


#29 Wasteland Rat

Wasteland Rat

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 403 сообщений

Отправлено 07 Ноябрь 2011 - 20:00

QUOTE
Что-то в теме прям торжество невнимательности. :) Я же писала: если заключённых 100 и выводят их раз в сутки по одному, то среднее время выполнения цикла — 28 лет. Строгое математическое доказательство (а также другие варианты решения) — в статье по ссылке (инглиш, правда).


Твоя думать моя дурак, ничего не понимать? Моя магистр математики, моя хорошо знать английский и матстат. Какое еще среднее время выполнения цикла??? Речь в доказательстве идет о матожидании. Чтобы результаты реальных стохастических экспериментов как-то сошлись к матожиданию, надо сделать их, грубо говоря, очень много. Перефразируя, если собрать 100500 групп заключенных по 100 человек, тогда большинство этих групп, пользуясь этим алгоритмом, действительно выйдут на свободу через 28 лет. При этом будут группы, которые выйдут через 5 лет, и будут группы, которые подохнут от старости. Одной конкретной группе из 100 человек никто не может гарантировать ни 28, ни 128, ни 100500 лет.

П.С. А, да, и посмотрите на вариацию, которая о-большое от эн в кубе. Ну т.е. разброс плюс-минус тыщу лет к 28 годам в выборке из 100500 групп обеспечен.

Это сообщение отредактировано Wasteland Rat - 7 ноября 2011 | 21:10


#30 Wasteland Ghost

Wasteland Ghost

    Маленькое Злое Привидение

  • Пользователи
  • PipPipPip
  • 3 451 сообщений

Отправлено 07 Ноябрь 2011 - 20:26

QUOTE
Твоя думать моя дурак, ничего не понимать? Моя магистр математики, моя хорошо знать английский и матстат. Какое еще среднее время выполнения цикла??? Речь в доказательстве идет о матожидании. Чтобы результаты реальных стохастических экспериментов как-то сошлись к матожиданию, надо сделать их, грубо говоря, очень много. Перефразируя, если собрать 100500 групп заключенных по 100 человек, тогда большинство этих групп, пользуясь этим алгоритмом, действительно выйдут на свободу через 28 лет. При этом будут группы, которые выйдут через 5 лет, и будут группы, которые подохнут от старости. Одной конкретной группе из 100 человек никто не может гарантировать ни 28, ни 128, ни 100500 лет.

Моя к.т.н., дальше что? Будем меряться неизвестно чем или внимательно читать? В задаче нет ни слова о гарантированном выходе на свободу через заданное количество лет. Время по условию не ограничено. Собственно, там нет времени как такового, есть неограниченное число попыток. С какой частотой заключённых будут водить в комнату тоже не сказано. Может, одного в минуту. А может одного в сутки. Это чистой воды математическая задача из теории вероятностей, а вовсе не из мат. статистики. Ограничение по времени — это новое условие, которое не имеет отношения к этой задаче. Ежу понятно, что для любой сколь угодно длинной случайной последовательности выбора вероятность того, что хотя бы один заключённый так и не посетит камеру отлична от нуля, хоть и близка к нему. Ровно тому же ежу понятно, что кроме мат. ожидания есть ещё и дисперсия. И даже целому стаду ежей понятно, что мат. статистика и теория вероятностей — не одно и то же. А если уж очень хочется, так попробуй ответить на вопрос "за какое время (или при какой длине последовательности) данный алгоритм сработает с заданной вероятностью (например, 0,9)?"

PS Заодно повспоминай на досуге такие термины как "стационарный случайный процесс" и "эргодическое свойство стационарного случайного процесса".

PPS Я тоже, конечно, сейчас мешаю в кучу мух и котлеты. Тем не менее. Кто-то упёрся рогом сначала в один бит, затем в продолжительность жизни заключённых. Всё это, конечно, прекрасно. Но не имеет отношения ни к теории вероятностей, ни к мат. статистике, ни, что самое главное, к решаемой задаче. Проблема не в статистике, не в мат. ожидании, которое не равно выборочному среднему, ни в дисперсии плюс/минус тысячу лет. Проблема в новых ограничениях, не предусмотренных условием. Хочется решать задачу при условии ограничения продолжительности жизни заключённых? Велкам. С учётом начального возраста? Да пожалуйста! Возможно, ты её даже решишь. Но снова получишь результат, который будет справедлив лишь в среднем. И для конкретной группы конкретных людей может не сработать. Это теория вероятностей, товаристч. Магистр же, должен был привыкнуть. ;)


#31 Wasteland Rat

Wasteland Rat

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 403 сообщений

Отправлено 07 Ноябрь 2011 - 21:55

QUOTE
Я же писала: если заключённых 100 и выводят их раз в сутки по одному, то среднее время выполнения цикла — 28 лет. Строгое математическое доказательство (а также другие варианты решения) — в статье по ссылке (инглиш, правда).


Вот это ваши слова. Это... ммм... ну просто неверно. И вообще, там в статье всё в предположении, что выборка заключенных равновероятная (uniform), о чём в этой теме (и в ваших же переформулировках задачи) речи вообще не было.

QUOTE
Моя к.т.н., дальше что? Будем меряться неизвестно чем или внимательно читать?


Я сюда не мериться пришел, просто перестаньте мне тыкать что я что-то там невнимательно прочитал. Я все внимательно прочитал, я подумал, пришел к этому же решению, потом еще подумал и пришел к выводу что оно практически неприменимо. Я также прочитал приведенную статью и особенно пункт, там где оценивается матожидание срока выхода заключенных в 28 дней. Так что нечего еще и меня обвинять в невнимательности.

QUOTE
Это чистой воды математическая задача из теории вероятностей

Да-а-а? Может, в статье, на которую вы так старательно ссылаетесь. Но явно не у топикстартера.

QUOTE
Ограничение по времени — это новое условие, которое не имеет отношения к этой задаче.

Ну да, ну да. Во-первых, задача про людей все-таки а не про абстрактыне предметы (по крайней мере была сформулирована так). Во-вторых, весь сыр-бор в приведенной статье со множеством алгоритмов как раз из-за того чтобы сократить время. В третьих, ну давайте тогда все практические задачи, для которых есть NP-трудные алгоритмы решения, считать решенными, а чего же ими дальше заниматься, алгоритм же есть?
Практического решения эта конкретная задача не имеет, приведенная вами статья не несет практической пользы. Поэтому и столько формул и выкладок и т.п. (кое-как свели матожидание к O(n(lnn)^2), да и то это только матожидание, которое к конкретной попытке конкретной группы заключенных отношения не имеет).

QUOTE
Ежу понятно, что для любой сколь угодно длинной случайной последовательности выбора вероятность того, что хотя бы один заключённый так и не посетит камеру отлична от нуля, хоть и близка к нему.

Условие равномерной выборки отсутствует в исходных условиях задачи, так что ежу не понятно.

QUOTE
Ровно тому же ежу понятно, что кроме мат. ожидания есть ещё и дисперсия.

Ну да, есть, и что?

QUOTE
И даже целому стаду ежей понятно, что мат. статистика и теория вероятностей — не одно и то же.

Ой, ну вот не надо вот этого, умоляю, вы же к.т.н., взрослый человек, что за пустые придирки?

QUOTE
А если уж очень хочется, так попробуй ответить на вопрос "за какое время (или при какой длине последовательности) данный алгоритм сработает с заданной вероятностью (например, 0,9)?"

Это характеризует работу алгоритма в целом, на большом числе случайных последовательностей. И что это даст для решения конкретной проблемы, если в формулировке задачи мы проводим один единственный эксперимент с одной единственной группой заключенных? У НАС НЕТ ВЫБОРКИ!





#32 IRI

IRI

    Генерал Фейлор

  • Пользователи
  • PipPipPip
  • 3 775 сообщений

Отправлено 08 Ноябрь 2011 - 05:23

> там в статье всё в предположении, что выборка заключенных равновероятная (uniform), о чём в этой теме (и в ваших же переформулировках задачи) речи вообще не было

Почему, а
> the warden picks a prisoner equally at random

А у топикстартера задача недоформулирована. Если этим пользоваться, то можно предложить целую кучу тривиальных решений. Например, каждый заключённый отрубает себе рубильником палец и аккуратно кладёт в общий ряд. Кто видит 99 пальцев — кричит «я последний».


#33 Wasteland Ghost

Wasteland Ghost

    Маленькое Злое Привидение

  • Пользователи
  • PipPipPip
  • 3 451 сообщений

Отправлено 08 Ноябрь 2011 - 07:37

Wasteland Rat, не надо ссылаться на некорректную формулировку. Обсуждаем мы всё-таки решение exelenz, которое относилось к этой формулировке. В отличие от англоязычного оригинала здесь нет слов "равномерное распределение", однако, есть слова "в произвольном порядке". Что означают эти слова в переводе на научный язык? Если нет оснований полагать, что одно событие является более вероятным чем другое, то все вероятности полагаются равными. Кстати, равномерное оно или нет — не важно. Важно лишь, чтобы каждый заключённый имел возможность побывать там неограниченное количество раз. Распределение будет влиять на время выполнения, но не на саму возможность.

Что касается прочих придирок. Первоклашки решают задачи про землекопов. Там тоже необходимо учесть среднюю продолжительность жизни, количество перекуров, переломов и прочая, и прочая? Формулировка абстрактной задачи в конкретных терминах помогает подтолкнуть мысль. Я более чем уверена, что изначальная проблема не имела никакого отношения к заключённым (задачка появилась на форуме физматиков). Так что давай не будем цепляться к человеческому фактору. А то, знаешь, и лампочка (в варианте с лампочкой) за 28 лет сто раз перегорит, и охрана начнёт прикалываться и зеки углы метить.

Что касается статьи. На оригинальном ресурсе речь шла о поиске оптимального решения. Перевожу на русский: какой-то параметр надо ниминизировать или максимизировать. В качестве параметра в статье взято среднее время выполнения алгоритма (цикла, процедуры, whatever). Поэтому его и нашли. А вовсе не для того, чтобы доказать, что через сколько-то там лет кто-то там гарантированно освободится из реальной тюрьмы.

О практической пользе. Я ф шоке. Где в задаче шла речь о применении данного алгоритма на практике?!?! Задачка полностью, совершенно и абсолютно абстрактна, потому что ни одна тюрьма не будет проводить подобный эксперимент.

Засим. В исходной задаче имени "100 заключённых и одна лампочка" отсутствует ограничение по времени. Если тебе хочется ввести такое ограничение — вводи и решай. Но не занудствуй, пожалуйста, по поводу задачи уже решённой.

PS Так, по секрету, алгоритмы в твоём сотовом тоже оптимальны в среднем, тем не менее, это не мешает тебе успешно общаться. Пр наличии случайных факторов любое решение задачи не даёт гарантированного результата. Но это пока ещё никого не останавливало от применения данных решений на практике.


#34 Wasteland Rat

Wasteland Rat

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 403 сообщений

Отправлено 08 Ноябрь 2011 - 09:02

QUOTE
Если этим пользоваться, то можно предложить целую кучу тривиальных решений. Например, каждый заключённый отрубает себе рубильником палец и аккуратно кладёт в общий ряд. Кто видит 99 пальцев — кричит «я последний».

5 баллов, мне это решение нравится намного больше :)))

2 Wasteland Ghost
Да ну и фиг с ним, собственно :)


#35 Wasteland Ghost

Wasteland Ghost

    Маленькое Злое Привидение

  • Пользователи
  • PipPipPip
  • 3 451 сообщений

Отправлено 08 Ноябрь 2011 - 12:55

QUOTE
Да ну и фиг с ним, собственно :)

Плюсадын, камрад! :)


#36 Massaraksh

Massaraksh

    Продвинутый пользователь

  • Пользователи
  • PipPipPip
  • 706 сообщений

Отправлено 08 Ноябрь 2011 - 15:51

QUOTE
Читаем решение ещё раз:

Пардон.

А вообще эта задача имеет известное, т.н. "официальное" решение? А то, сильно уж похоже на известную задачу, по составлению слова "счастье".


#37 Wasteland Ghost

Wasteland Ghost

    Маленькое Злое Привидение

  • Пользователи
  • PipPipPip
  • 3 451 сообщений

Отправлено 08 Ноябрь 2011 - 18:56

QUOTE
А вообще эта задача имеет известное, т.н. "официальное" решение?

Да. То самое, которое описал exelenz.


#38 hamster

hamster

    Pixelhunter

  • Пользователи
  • PipPipPip
  • 7 832 сообщений

Отправлено 08 Ноябрь 2011 - 19:38

В архив.




Похожие темы Свернуть

  Название темы Форум Автор Статистика Последнее сообщение


Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных

Рейтинг@Mail.ru