Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Общие темы > Загадки

Загадки Постим и отгадываем загадки. Флуд запрещён - только условия и обсуждение решений.

Ответ
 
Опции темы
Старый 27.01.2013, 02:15   #1
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Миссионер, заблудившийся в Южной Калифорнии

Задача позаимствована из книги Э. Таненбаума "Архитектура компьютера" (5-е издание)
Миссионер, заблудившийся в Южной Калифорнии, остановился на развилке дороги. Он знает, что в этом районе обитают две мотоциклетные банды. Одна из них всегда говорит правду, а другая всегда лжёт. Он хочет узнать, какая дорога ведёт в Диснейленд. Какой вопрос он должен задать?
Ответы постить в OFFTOP-тег: не ломайте кайф остальным!
Искать непосредственно решение в интернетах - не комильфо.

Мой ответ:

ВНИМАНИЕ - ДАЛЕЕ ОТВЕТ:
Изначально, я вообще не собирался решать эту задачу (придумал первый попавшийся алгоритм - и успокоился). Но, забавы ради, кинул её Джокеру.
Общее решение было примерно следующим: задать составной вопрос, содержащий в себе маркер - подвопрос, ответ на который индицирует тип банды, позволив определить истинность ответа на второй подвопрос.
Маркером может выступать любое априорное знание: например, факт нахождения спрашивающего в Южной Калифорнии.

Однако скоро, мне вывалили иное решение. Без доказательства, но однозначно работающее. Учитывая специфику книги, я попробовал восстановить ход мыслей, дающих красивое решение.

Сразу обратим внимание, что нам достаточно знать: выводит ли к цели ОДНА, фиксированная дорога (например, левая) - характеристика второй, получается очевидным образом. LEFT=1-RIGHT.
Итак, как работает банда? Мы можем задать ей некий вопрос, например: "Эта дорога выведет меня к Диснейленду?". Если банда ЛЖЁТ, то ответ буден инвертирован, а если нет - выдан без изменений. Схема на логических элементах выглядит, например, так:
Нажмите на изображение для увеличения
Название: схема_банды.jpg
Просмотров: 1582
Размер:	31.3 Кб
ID:	18537
Нетрудно составить таблицу значений функции:
(Ответ - О; Лгать - Л; Выход - В)
ОЛ В
00 0
01 1
10 1
11 0
По таблице легко заметить, что перед нами обычный XOR или сложение по модулю два.
Типовой пример взаимодействия с неизвестной бандой можно изобразить следующим образом:
Нажмите на изображение для увеличения
Название: схема_банды_xor.jpg
Просмотров: 1437
Размер:	23.5 Кб
ID:	18538
Даже спросив по отдельности первую и вторую банду мы ничего не узнаем, кроме априорного: ответы будут противоположны.
Суть решения сводится к тому, что в совокупности на две банды, сигнал искажается единожды. Таким образом, собрав цепь из последовательно включённых банд, мы получим всего-лишь одну инверсию. Возможные варианты:
1. Ложь(Правда(Факт))
2. Правда(Ложь(Факт))
Нетрудно заметить, что Ложь и Правда действуют на бистабильный ответ подобно умножению на "один" и "минус один": минус на плюс - даёт минус, плюс на минус - минус, минус на минус - плюс. Иными словами: солгать правду - лгать, не перевирать ложь - лгать, искажать ложь - говорить правду.
Как реализовать это в схеме? Ведь мы можем опросить только одну банду. Нам требуется пропустить через фильтр одной банды, ответ другой. Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники?
Если перед нами лгуны, то ситуация: Ложь(Правда(Факт)). В противном случае: Правда(Ложь(Факт)). Как видим: "минус на плюс" и "плюс на минус", соответственно. В обоих ситуациях мы получаем лживый ответ. Осталось только его инвертировать.
Реализовать в схеме "что ответили бы на вопрос ваши соперники" можно инвертировав сигнал УПРАВЛЕНИЕ РЕЖИМОМ ЛЖИ и подав его в типовую схему банды с предыдущего рисунка. Затем пропустим выход через банду, стоящую перед нами, и, наконец, инвертируем ответ.
Нажмите на изображение для увеличения
Название: схема_результат.jpg
Просмотров: 1504
Размер:	37.3 Кб
ID:	18539
Так ли это на самом деле? Покажем это с помощью таблицы истинности.
(Ответ - О; Режим Текущей Банды - РТБ; Инверсия РТБ - ИРТБ; Ответ Конкурентов - ОК; Ответ Банды - ОБ; Результат - Р)
О РТБ ИРТБ ОК ОБ Р
0.0..1...1..1....0
0.1..0...0..1....0
1.0..1...0..0....1
1.1..0...1..0....1
Как видно, значения вектора О совпадают со значениями вектора Р.
Докажем верность решения, упростив выражение, формально описывающее работу схемы:
ANS=NOT( ( NOT(U) XOR A ) XOR U ).
Здесь U - Режим Текущей Банды, A - Факт.
Нетрудно заметить, что отрицание XOR даёт эквиваленцию. Последнее можно заключить как из определения операции, так и инвертировав вектор "выходных значений" XOR (0110 -> 1001) и подобрав (или поняв, посмотрев на носитель функции) подходящую новую функцию.
Следовательно:
ANS=NOT( NOT(U) XOR A ) EQ NOT(U)=
=( NOT(NOT(U)) EQ NOT(A) ) EQ NOT(U)=
=( U EQ NOT(A) ) EQ NOT(U).
Я так и не смог отыскать упоминания того, что для эквиваленции справедлива ассоциативность, поэтому я тупо сверил носители функций (A EQ B) EQ C и (A EQ C) EQ B. В общем, можно упростить далее:
ANS= U EQ NOT(U) EQ NOT(A)
Очевидно, что U EQ NOT(U) тождественно равно ЛЖИ.
ANS= 0 EQ NOT(A)
Эквиваленция лжи соответствует унарной операции инверсии операнда. Это обстоятельство можно получить или из анализа таблицы истинности, или из определения: действительно, истинно равной (=1) лжи, может быть только ложь (0), и наоборот неравной лжи (=0) может быть только истина (1)
ANS= NOT(NOT(A))=A.

Ответ:
Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники? Выберем вторую (другую) дорогу.

__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
den (27.01.2013), Dream (27.01.2013), SBJoker (27.01.2013)
Старый 27.01.2013, 03:05   #2
jimon
 
Сообщений: n/a
Ответ: Миссионер, заблудившийся в Южной Калифорнии


1) спросить у первой банды
2) получить пиздюлей
3) спросить у второй банды
4) получить пиздюлей
5) придумать хитрожопый соц. эксперимент (как Импер например)
6) провести эксперимент на бандах
7) получить пиздюлей
8) подумать, проверить календарь - там 2013 год
9) посмотреть по GPS\карте или спросить по телефону
10) ....
11) PROFIT !
 
Ответить с цитированием
Эти 7 пользователя(ей) сказали Спасибо за это полезное сообщение:
Amatsu (27.01.2013), Arton (27.01.2013), impersonalis (27.01.2013), Mr_F_ (27.01.2013), St_AnGer (28.01.2013), Taugeshtu (28.01.2013), tormoz (27.01.2013)
Старый 27.01.2013, 12:09   #3
den
Дэвелопер
 
Аватар для den
 
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений
(для 2,419 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Одна из них всегда говорит правду, а другая всегда лжёт.
Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо den за это полезное сообщение:
Антихрист (27.01.2013), Arton (27.01.2013), pax (28.01.2013)
Старый 27.01.2013, 12:25   #4
Mr_F_
Терабайт исходников
 
Аватар для Mr_F_
 
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений
(для 6,051 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии


Спросить, сколько будет "2+2" ?
получить пиздюлей
они же не обязаны отвечать на все твои тупые вопросы. думаю если задашь большинству пешеходов такой вопрос, ответ будет "дурак шоле?", и это не правда/ложь а тупо отказ от ответа
(Offline)
 
Ответить с цитированием
Старый 27.01.2013, 13:15   #5
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Сообщение от Den Посмотреть сообщение

Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.
__________________
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо SBJoker за это полезное сообщение:
den (27.01.2013), impersonalis (27.01.2013)
Старый 27.01.2013, 13:33   #6
BlackDragon
Проектировщик
 
Аватар для BlackDragon
 
Регистрация: 25.03.2007
Сообщений: 536
Написано 252 полезных сообщений
(для 715 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

"Пацаны, до Диснейленда подбросте. По братски, а?"
(Offline)
 
Ответить с цитированием
Старый 27.01.2013, 16:37   #7
Dream
быдло
 
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений
(для 1,489 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Сообщение от SBJoker Посмотреть сообщение
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же
(Offline)
 
Ответить с цитированием
Старый 27.01.2013, 18:56   #8
SBJoker
Злобный Админ
 
Аватар для SBJoker
 
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений
(для 9,330 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Сообщение от Dream Посмотреть сообщение
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же
Повторяю, есть всего одна попытка спросить, и разговариваем мы по условию с одной бандой, но не известно с какой.
__________________
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо SBJoker за это полезное сообщение:
Антихрист (28.01.2013), impersonalis (27.01.2013)
Старый 28.01.2013, 13:28   #9
MiXaeL
Бывалый
 
Аватар для MiXaeL
 
Регистрация: 22.08.2006
Сообщений: 700
Написано 146 полезных сообщений
(для 267 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Это же детский сад вроде, нет? Ответ, а точнее вопрос: "Что скажет другая банда, если я спрошу дорогу у них в Диснейленд?" Сами догадаетесь, почему надо выбрать другую дорогу.
Ответы не читал, может кто уже так и ответил.
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
SBJoker (17.05.2013)
Старый 28.01.2013, 13:44   #10
Nerd
Чудо-кот
 
Аватар для Nerd
 
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений
(для 1,471 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Миссионер небось исламистский, и едет в Диснейленд творить справедливость.
__________________

(Offline)
 
Ответить с цитированием
Старый 28.01.2013, 15:12   #11
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Arton (30.01.2013)
Старый 28.01.2013, 16:13   #12
MiXaeL
Бывалый
 
Аватар для MiXaeL
 
Регистрация: 22.08.2006
Сообщений: 700
Написано 146 полезных сообщений
(для 267 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Сообщение от pax Посмотреть сообщение
У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.
Наверняка у развилки табличка с описанием местных банд.
(Offline)
 
Ответить с цитированием
Старый 28.01.2013, 19:39   #13
tormoz
Гигант индустрии
 
Аватар для tormoz
 
Регистрация: 14.12.2005
Сообщений: 2,785
Написано 1,183 полезных сообщений
(для 4,437 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

Миссионеры - зло.
(Offline)
 
Ответить с цитированием
Старый 29.01.2013, 00:30   #14
k(void)
Hard airsofter
 
Аватар для k(void)
 
Регистрация: 10.10.2006
Адрес: В этой стране
Сообщений: 197
Написано 9 полезных сообщений
(для 13 пользователей)
Ответ: Миссионер, заблудившийся в Южной Калифорнии

По информации из википедии
Климат штата субтропический, часть территории занимает Нижнекалифорнийская пустыня. Умеренные ветры с Тихого океана и холодного Калифорнийского течения делают климат вдоль тихоокеанского побережья приятным круглый год. Дождей мало. Холодное океаническое Калифорнийское течение часто является причиной густых туманов на побережье. В горах наблюдается альпийский климат. Лето здесь прохладное, а зимы могут быть холодными, а ночью температуры часто опускаются ниже 0 °С. В горах часто выпадает и долго не тает снег с декабря по апрель. Восточная сторона полуострова – весьма засушлива. Далее на юг вдоль побережья засушливый климат сохраняется, но он становится мягче и не таким жарким. Осадков выпадает мало, в среднем 300 – 600 мм в год. На островах в Калифорнийском заливе – пустыни.

У миссионера обезвоживание, ему развилки и банды байкеров мерещатся...
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Arton (30.01.2013)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 21:45.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com