Re: Заключенные | |
---|---|
vk65 Сообщений: 402 Дата регистрации: 08.04.2008 |
Согласен. Каждый будет способен просчитать чётность/нечётность впередистоящих и вычислить своё число.
|
Re: Заключенные | |
---|---|
akvvohinc Сообщений: 4203 Откуда: Москва Дата регистрации: 11.11.2008 |
Цитата:Да нет, после уточнения условия задача существенно упростилась, и, действительно, гарантированно спасутся все, кроме первого. Первый назовет "общую" четность. Следующий видит четность впередистоящих и знает (от первого) четность с учетом своего номера - значит может узнать свой номер. Остальные, зная общую четность, четность впередистоящих, и ответы предыдущих, вычисляют свой номер. |
Re: Заключенные | |
---|---|
sphinx Автор Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Первый, как раз, ничего не видит перед собой. Разумеется, все начинается с последнего. ------------------ "Veni, vidi, vici!"(с) |
Re: Заключенные | |
---|---|
sphinx Автор Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Не может. Последний сообщил общую четность, но не назвал свою цифру. И предпоследний свою не знает. Чего-то не хватает, не? ------------------ "Veni, vidi, vici!"(с) |
Re: Заключенные | |
---|---|
akvvohinc Сообщений: 4203 Откуда: Москва Дата регистрации: 11.11.2008 |
Ты по-моему придираешься к словам.
Попробую сказать то же, но чуть иначе: Последний в очереди (начинающий) называет четность всех предыдущих заключенных. Допустим, четность единиц у них на затылках. Он говорит "1", что означает, что количество единиц у впередистоящих нечетно (они так договорились). Или он говорит "0", что означает, что количество единиц впередистоящих четно. После этого его расстреливают с вероятностью 0,5 (R.I.P.) Второй заключенный тоже посчитал четность единиц впередистоящих, и, зная также эту четность с учетом себя самого (ее сообщил первый), может легко узнать свой номер - если "четно-четно" или "нечетно-нечетно", то у него на затылке "0", в двух других случаях - у него "1". Третий заключенный посчитал четность единиц впередистоящих, определил также эту четность с учетом себя самого (за основу взял сообщение первого и откорректировал ее с учетом ответа второго). После этого он по тому же принципу, что и предыдущий, определил и назвал свой номер. И т.д. и т.п. На примере 3 заключенных (их номера от последнего (начинающего) к первому): 1 - 1 - 0 Первый говорит "1" (все узнают, что общее количество единиц в цепочке, которое он видит, нечетно - он видит перед собой только одну "1"). Кроме того, ему повезло, и он остается жив. Второй видит впереди четное количество единиц (ни одной). То есть для него получается вариант "нечетно-четно". Это означает, что у него "1", которую он и называет. Третий никого перед собой не видит, но может вычислить "свою цифру". Количество единиц, названное первым, было нечетным, а второй назвал "1". Значит, количество единиц впередистоящих (их нет) + количество единиц в его собственном номере четно. Следовательно, у него самого может быть только "0". Думаю, что можно сформулировать этот алгоритм и как-то попроще... Исправлено 3 раз(а). Последнее : akvvohinc, 14.08.12 05:33 |
Re: Заключенные | |
---|---|
sphinx Автор Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Ога, все верно. Последний называет общую четность заключенных от 1 до n-1 (свою цифру ведь все равно не знает). ------------------ "Veni, vidi, vici!"(с) Исправлено 1 раз(а). Последнее : sphinx, 14.08.12 07:18 |
Re: Заключенные | |
---|---|
Extortioner Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
Нашёл аналог этой задачи на сайте www.braingames.ru - оказывается у неё сложность = 2 (максимальная на этом сайте - 5).
|
Re: Заключенные | |
---|---|
akvvohinc Сообщений: 4203 Откуда: Москва Дата регистрации: 11.11.2008 |
Я тут вчера разработал элементарный механизм для заключенных, чтобы самые тупые не ошиблись, и никто не пострадал. Он не требует никаких расчетов, используется лишь 1 палец руки, например.
После того, как очередь выстроилась, и номера у всех были написаны, каждый заключенный делает следующее: Исходное положение - пальцы руки, сжатые в кулак. Далее он начинает "обрабатывать" цифры впередистоящих - каждый раз, когда у кого-то на затылке он видит "1", большой палец его руки отводится в сторону, если он был прижат, или прижимается, если он был отведен (палец работает как простейший тумблер). Нули просто игнорируются (положение пальца не меняется). Далее, когда предыдущие заключенные начинают называть свои номера, эта процедура продолжается - если называется "1", его палец "переключается" (а нули игнорируются). При этом когда очередь доходит до него самого он просто смотрит на свой палец - если тот отжат, называет "1", если прижат - "0". На примере 4 человек с номерами: 1 - 1 - 0 - 1 Например, для 3-го с конца заключенного (у которого "0"): - "обработал" единицы впередистоящих (палец стал в положение "отведен"); - первый назвал свое число = "0" и его увели на расстрел (палец остался в положении "отведен"); - следующий назвал свое число = "1" (палец стал в положение "прижат"); - подошла очередь нашего зека - он видит прижатый палец и называет свое число - "0". Можно проверить - этот способ будет работать для каждого заключенного при любых комбинациях их цифр, так как основан на выведенной ранее формуле: четность своего числа = (общая четность - четность впередистоящих - четность позадистоящих) Для 3-го зека (0 - 1 - 1) = 0 Исправлено 1 раз(а). Последнее : akvvohinc, 14.08.12 13:50 |
Re: Заключенные | |
---|---|
vk65 Сообщений: 402 Дата регистрации: 08.04.2008 |
Попадётся безрукий зэк, и весь алгоритм идёт лесом. |
Re: Заключенные | |
---|---|
sphinx Автор Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Ога. Или слепой. ------------------ "Veni, vidi, vici!"(с) |
Re: Заключенные | |
---|---|
vk65 Сообщений: 402 Дата регистрации: 08.04.2008 |
Не, это противоречит постановке задачи.
Все видят, что нарисовано у впередистоящих и слышат, кто что сказал. А про конечности ничего не было. |
Re: Заключенные | |
---|---|
akvvohinc Сообщений: 4203 Откуда: Москва Дата регистрации: 11.11.2008 |
Раз они могут говорить, значит, у них есть хотя бы язык - он будет для него тумблером.
|
Re: Заключенные | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Что мешает последнему заключенному назвать полное число в hex коде? Тогда каждый будет знать 0 или 1 у него на голове.
------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 1 раз(а). Последнее : Влад Колосов, 15.08.12 13:50 |
Re: Заключенные | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Ограничение задачи - я именно про это и спрашивал ранее ------------------ WBR, Igor |
Re: Заключенные | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
А, понятно! Слона-то не приметил.
Хм, гарантировано выживет 50%, как мне кажется, плюс половина оставшихся наудачу (если работают большие числа). Т.е. до 75% в пределе. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 2 раз(а). Последнее : Влад Колосов, 15.08.12 18:43 |
Re: Заключенные | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Влад. Читай тему полностью, тебя ждёт приятный сюрприз
------------------ WBR, Igor |
Re: Заключенные | |
---|---|
Nosovicka Сообщений: 7 Дата регистрации: 20.08.2012 |
Ну впринципе 50/50 спсутся в любом случае)зэков не жалко
|
Re: Заключенные | |
---|---|
sphinx Автор Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Зэки разные бывают. Есть педофилы и террористы, а есть и те, из кого признание силой выбили. И многие из зэков - прежде всего люди. ------------------ "Veni, vidi, vici!"(с) Исправлено 1 раз(а). Последнее : sphinx, 20.08.12 12:49 |
© 2000-2024 Fox Club  |