Сто заключенных и одна лампочка

Все, что вы хотели знать о программизме, но боялись спросить.
tasko
Графоман
Сообщения: 18705
Зарегистрирован: 20 июл 2003, 09:16
Откуда: Торонто

Сообщение tasko »

Эх, не то вы считаете. Включил - выключил, 27 лет. Это все верно, если программа работает как надо.

Но в жизни так не бывает. Практически бывает так, что за 27 лет лампочка перегорит не менее 100 раз (по аналогии, программа 100 раз зависнет). А это как учесть? Не можем же мы жизнью людей рисковать из-за какой-то там лампочки? Это только микрософт так может :)

Короче, решение такое. Лампочку не включаем, а заключенные рано или поздно и так загнутся! :D
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

ilid писал(а):Ладно, товарищ Циник, надоело мне ругаться изза пустяка
Taк ты ругался, значит, товарищ? Нехорошо.
складывается ощущение, что Вы, товарищ, только себя самого и слышите.

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

Я почему-то не уверен, что ты оценил его адекватно. И кстати, "вы" следует писать здесь с маленькой буквы, а еще лучше писать "ты".
Задачка-то понятная, только от этого менее дурацкой она не стала.
Узнаю тебя, товарищ Илид. По ухам.
Она не плохая, прикольная, весёлая, какая угодно слваная и забавная, но она дурацкая, я конечно понимаю, что Вас возможно тяготит опыт интервьюирования, но это когда-нибудь тоже пройдёт.
"Никогда не делайте лицо умнее того, которое вам идет" Немирович-Данченко
Всяческих благ!
Спасибо, товарищ, тебе тоже удачи и радости.
ilid
Завсегдатай
Сообщения: 255
Зарегистрирован: 19 мар 2003, 13:31

Сообщение ilid »

Да ладно, Циник, признайся сам, что задачка лишена изящества, ну может и не дурацкая, может слишком обидное слово, ну да ладно.
Циник писал(а):"Никогда не делайте лицо умнее того, которое вам идет" Немирович-Данченко
А чё тут делать то лица :) И так всё ясно. Сразу на глаз можно определить два типа людей - первый - игроки в настольный теннис (полу-профи), а второй - программисты. Может ты, Циник, и в пинг-понг на кандидата играешь :lol:
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

ilid писал(а):Да ладно, Циник, признайся сам, что задачка лишена изящества,
De gustibus et coloribus non est disputandum.
Как я уже говорил, я полагаю, что у этой изящной и весьма глубокой задачи есть все шансы стать классической. Не расстраивайся, если ты лично не видишь этой глубины и изящества, товарищ. Ничего страшного. Ты, наверно, просто программист современный, уже не из математики или физики вышедший :twisted:
А чё тут делать то лица :) И так всё ясно. Сразу на глаз можно определить два типа людей - первый - игроки в настольный теннис (полу-профи), а второй - программисты. Может ты, Циник, и в пинг-понг на кандидата играешь :lol:
Почему-то сдается мне, товарищ, что с психологией и физиогномикой у тебя такие же взаимоотношения, как и с матожиданием и теорией вероятностей :twisted:
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Кстати.

Часто задачи легко и изящно решаются, если посмотреть на них "с другой стороны" - например, для решения планиметрической задачи выйти в трехмерное пространство или представить клетки шахматной доски пуговицами на ниточках (как для решения известных задач обхода конем).

Кто-нибудь увидел в этой задаче конечные автоматы (state machines)?
Alexan
Завсегдатай
Сообщения: 213
Зарегистрирован: 17 фев 2003, 16:05
Откуда: NN - Montreal - Charlottetown - Montreal

Сообщение Alexan »

Как обещал продолжение. Сократить время ожидания можно на счет правильного выбора человека-счетчика. Это будет человек, который первым раз вошел в комнату второй раз. Он будет знать на какой день он вошел и следовательно сколько человек было в комнате до него. То есть ему остается сосчитать уже меньше людей. Как определить этого человека? Сначала лампочка выключена и приходящие люди ничего с ней не делают. Когда кто-то попадает в комнату второй раз, он включает лампочку и становится счетчиком. Остальные должны знать, что счетчик уже выбран, для этого лампочку не выключают пока не пройдет 100 дней с момента посещения первого человека. Т. е. первые 100 дней используются для назначения счетчика. Дальше все идет в соответствии с алгоритмом, который я уже описывал, только счетчику надо уже сосчитать не 99 человек, а меньше на количество дней, которые прошли до его назначения.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

Alexan писал(а):Как обещал продолжение. Сократить время ожидания можно на счет правильного выбора человека-счетчика. Это будет человек, который первым раз вошел в комнату второй раз.
Именно так, товарищи!
Таким образом от первоначального решения, где мы выбирали счетчика заранее, мы пришли к идее динамического выбора счетчика в процессе. Прогресс налицо - матожидание времени освобождения уменьшится на несколько лет. Но это все равно долго :twisted:
Еще будут идеи?
ilid
Завсегдатай
Сообщения: 255
Зарегистрирован: 19 мар 2003, 13:31

Сообщение ilid »

Зря вы, товарищ Циник так со мной, я ж и не програмист вовсе. Говоря железным языком, хочешь ты от человека сделать state machine с одним битом памяти двумя сотнями каунтеров... ну хоти конечно, только стоимость ошибки настолько высока, что боюсь что в конечном итоге будет слишком тяжело провести threshold.
Аватара пользователя
ajkj3em
Маньяк
Сообщения: 2063
Зарегистрирован: 12 ноя 2006, 06:53

Сообщение ajkj3em »

тем кому надоело или ломает ждать следующей серии -
http://www.ocf.berkeley.edu/~wwu/papers ... htBulb.pdf
(чей-то master thesis по всем решениям)
:twisted:
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

drain bamage писал(а):тем кому надоело или ломает ждать следующей серии
Неспортивно, товарищ Дрэйн!
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

ilid писал(а):Зря вы, товарищ Циник так со мной, я ж и не програмист вовсе.
А кто ты, товарищ?
Говоря железным языком, хочешь ты от человека сделать state machine с одним битом памяти двумя сотнями каунтеров... ну хоти конечно, только стоимость ошибки настолько высока, что боюсь что в конечном итоге будет слишком тяжело провести threshold.
Ничего не понимаю!.. :twisted:
ilid
Завсегдатай
Сообщения: 255
Зарегистрирован: 19 мар 2003, 13:31

Сообщение ilid »

Поясню. Для примера приведу систему обнаружения цели. Итак, летит например ракета, её задача поразить цель на земле. Она делает инфракрасные снимки земли. С помощью этих снимков ракета самонаводится на, скажем, ТАНК. Помимо танков на земле разумеется множество фальшивых целей, говоря по-английски clutters. У тебя есть разумеется алгоритм, который найдёт цель. Нас интересует алгоритм, который будет пользоваться статистическими методами, то есть начнёт получать различные статистические данные, по ним будет отметать клатеры и выбирать цель. Разумеется существует вероятность того что: цель будет принята за clutter, и наоборот. Задача алгоритма таким образом провести границу в данной области неопределённости таким образом, чтобы цена ошибки была как можно меньше. В приведённом мной случае цена ошибки разная, если цель будет отброшена по ошибке - очень плохо, цена ошибки большая, если же клаттер будет принят за цель, ничего кроме денег, потраченых на ракету не потеряется. Такая техника называется техника трешолда, наибольшее применеие естественно в области всяческих распознаваний обьектов, звуков и чего только захочется, есть противники статистических методов и они утверждают что чем больше трешолдов в системе, тем она хуже будет работать. Теперь, насчёт железа. Я просто подумал, как решить задачку в железе, то есть сделать статическую логику, получается: каждый заключённый должен считать дни когда он был в комнате и когда он там не был - 200 каунтеров (естественно если не каждый будет считать дни отсутствия, то меньше), далее лампочка - это память, с её помощью можно передать информацию между заключёнными, и ширина у памяти - 1 бит. Сама логика - state machine, в каждый шаг она имеет доступ к одной паре каунторов (chip-select у нас рандомальный и приходит из вне) и к памяти, она решает поднять бит, обнулить его или оставить без изменения, плюс ко всему она выводит сигнал типа all_true, который будет 1 если логика посчитает что все заключёные побували в комнате. Вот что я имел ввиду. Было бы интересно написать всё это на Verilog, просимулировать потом на Е и посмотреть, сколько в среднем лет будет уходить при каждом алгоритме.
Аватара пользователя
Циник
Завсегдатай
Сообщения: 442
Зарегистрирован: 17 фев 2003, 17:17

Сообщение Циник »

ilid писал(а):Поясню.
Спасибо за подробное пояснение, товарищ. Но ты так и не ответил, кто ты?
Было бы интересно написать всё это на Verilog, просимулировать потом на Е и посмотреть, сколько в среднем лет будет уходить при каждом алгоритме.
Вероятно, есть врачи, которым было бы интересно удалить гланды через нетрадиционное место. :twisted:
Не проще ли написать все это, просимулировать и посмотреть с помощью обычного Си, Паскаля, Фортрана, или даже Вижуал Бэйсика?
ilid
Завсегдатай
Сообщения: 255
Зарегистрирован: 19 мар 2003, 13:31

Сообщение ilid »

Циник писал(а): Спасибо за подробное пояснение, товарищ. Но ты так и не ответил, кто ты?
Я инженер электронщик, могу на ассемблере писать, RISC-овом, хотя на мой взгляд любой ассемблер за неделю учится. Могу ещё на Е писать.
Не проще ли написать все это, просимулировать и посмотреть с помощью обычного Си, Паскаля, Фортрана, или даже Вижуал Бэйсика?
Наверно не проще, а однохренственно :) Но, есть одна темка в Е - хороший управляемый генератор исходных значений. Например в нём ты можешь регулировать вероятность выбора заключённых. Так как всё последовательно происходит, то конечно нахрен это никому не нужно. А в общем плане, мне кажется когда проблема сужается до муксов да каунтеров уже не важно на чём писать.

P.S. Е - это эмулятор на С, не язык.
Alexander Ch.
Завсегдатай
Сообщения: 284
Зарегистрирован: 04 мар 2003, 08:49
Откуда: Hamilton, Ontario

Сообщение Alexander Ch. »

Невозможно смоделировать такую задачу чисто софтом. Надо железячный датчик случайных чисел (действительно случайных).
Я пробова Excel для этого приспособить, что получилось:
В одной выборке 100 случайных чисел от 1 до 100 было 98 уникальных,
в другой выборке 1000 случайных чисел от 1 до 100 было 52 уникальных числа.
Ответить