Re[7]: решение
От: gloomy rocker Россия  
Дата: 21.11.02 08:57
Оценка:
Здравствуйте, Atilla, Вы писали:

A>Здравствуйте, gloomy rocker, Вы писали:


A>

GR>>Зачем такие сложности с 1000 испытаний ?
GR>>Такой код эффективнее.

A>ан-нет. Этот тест будет неверным, т.к. crufty отвечает случайным образом.


Этот тест будет верным! Дело в том, что вариантов всего 6, а именно: те которые забиты в массив. И смысла по нескольку раз проверять один и тот же вариант (имеется в виду цикл 0-1000) нет. Дочтаточно сделать это один раз.
Скука — двигатель прогресса.
Re[8]: решение
От: Atilla Россия  
Дата: 21.11.02 09:06
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

GR>Этот тест будет верным! Дело в том, что вариантов всего 6, а именно: те которые забиты в массив. И смысла по нескольку раз проверять один и тот же вариант (имеется в виду цикл 0-1000) нет. Дочтаточно сделать это один раз.


реально вариантов работы программы не 6, а 8: 1:A[0], ..., 4:A[3],
5:A[4] и первый автомат сказал правду, 6:A[4] и первый автомат соврал,
7:A[5] и первый автомат сказал правду, 8:A[5] и первый автомат соврал.

Если прогу проверять только 6 раз, как Вы написали, то из вариантов 5 и 6 проверится только один, из 7 и 8 — тоже только один. Я уже не говорю о том, что если в программе глюки, то "лукавый" автомат может опрашиваться более одного раза.
Кр-ть — с.т.
Re[4]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 09:11
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, Pushkin, Вы писали:


P>>
P>>Спрашиваем первого: ты дипломат?. 
P>>  Да - первый либо дипломат либо лжец. 
P>>  Спрашиваем второго: ты сейчас ответишь также правдиво, как предыдущий? 
P>>    Да - первый дипломат 
P>>


UgN>Неправильно.


UgN>Первый — лжец — на первый вопрос ответил Да (Лжет, что он дипломат)

UgN>Второй — дипломат — на второй вопрос ответил Да ( Случайным образом )

Предположим, что второй дипломат и он сейчас лжёт,
т.е. отвечает так же правдиво , как предыдущий (лжец)
значит моё утверждение истинно,
а дипломат, напомню, лжёт, т.е. должен сказать Нет

Если же дипломат сейчас говорит правду,
то он говорит не так же правдиво, как предыдущий (лжец),
т.е. моё утверждение ложно,
а дипломат, напомню, говорит сейчас правду, значит говорит ... опять Нет

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

Если же он говорит первое, что приходит в голову, не задумываясь о логике,
то это уже всё выходит за рамки таких задач. Эдак и лжец всегда будет хитро
прикидывать, как бы получше и похитрее ввести тебя в заблуждение и говорить
не всегда чистую ложь, а иезуитсткую ложь.
Re[5]: Интересная задача
От: UgN  
Дата: 21.11.02 09:24
Оценка:
Здравствуйте, Pushkin, Вы писали:


P>Вся фишка в том, что бедному дипломату всяко приходится говорить Нет,

P>по логике , по крайней мере

Из условия:

отвечает произвольным образом


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

P>то это уже всё выходит за рамки таких задач.

Боюсь, ему нет дела до твоей логики — он отвечает либо Да либо Нет произвольным (случайным) образом.

Хотя идея верная — заставить их отвечать про самих себя

См.вариант
Автор: Atilla
Дата: 21.11.02
от Atilla.
Re: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 09:28
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

GR>Есть три автомата, которые умеют отвечать на любой вопрос, на который можно ответить "Да" или "Нет". Естественно все множество возможных ответов исчерпывается двумя вариантами: "Да", "Нет". Один из них всегда говорит правду, один всегда лжет, а оставшийся отвечает произвольным образом. Необходимо задать 3 вопроса и выяснить, кто есть кто.


Важные уточнения к автору

1) Можно задавать вопросы типа 2x2=4?

2) Автоматы всё друг про друга знают и слышат ответы других?
Т.е. можно задавать вопросы "Сосед справа лжец?" и "Предыдущий сказал правду?"

3) Не обязательно задавать каждому по одному вопросу? Хоть все одному, да?

4) Можно ли задавать вопросы, на которые автомат не может ответить?
Т.е. исчерпывается ли множество ответов вариантами Да\Нет или есть третий — молчание?

5) Дипломат отвечает произвольным образом ни секунды не задумываясь или он сначала
принимает решение "а совру-ка я сейчас" и потом пытается соврать?
Re[6]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 09:36
Оценка:
Здравствуйте, UgN, Вы писали:


UgN>См.вариант
Автор: Atilla
Дата: 21.11.02
от Atilla.


я ни фига не пойму, разве разрешаются вопросы, ответ на которые неопределён?
Re[2]: Интересная задача
От: Atilla Россия  
Дата: 21.11.02 09:38
Оценка:
Я не автор вопроса, но у нас с ним совпали ответы. Поэтому скажу за него:

1) Да
2) Они знают про все и могут ответить на любой вопрос на который возможен ответ.
3) Да
4) Вопрос должен подразумевать двусложный ответ.
5) Как он отвечает — не известно. Т.е. считай, что RND.
Кр-ть — с.т.
Re[9]: решение
От: gloomy rocker Россия  
Дата: 21.11.02 09:40
Оценка:
Здравствуйте, Atilla, Вы писали:

A>Здравствуйте, gloomy rocker, Вы писали:


GR>>Этот тест будет верным! Дело в том, что вариантов всего 6, а именно: те которые забиты в массив. И смысла по нескольку раз проверять один и тот же вариант (имеется в виду цикл 0-1000) нет. Дочтаточно сделать это один раз.


A>реально вариантов работы программы не 6, а 8: 1:A[0], ..., 4:A[3],

A>5:A[4] и первый автомат сказал правду, 6:A[4] и первый автомат соврал,
A>7:A[5] и первый автомат сказал правду, 8:A[5] и первый автомат соврал.

A>Если прогу проверять только 6 раз, как Вы написали, то из вариантов 5 и 6 проверится только один, из 7 и 8 — тоже только один. Я уже не говорю о том, что если в программе глюки, то "лукавый" автомат может опрашиваться более одного раза.


Я исхожу из того, что вариант работы программы определяется результатом работы процедуры:

void Shuffle()
{
    a[0]=rand()%3-1;
    do a[1]=rand()%3-1; while(a[1]==a[0]);
    do a[2]=rand()%3-1; while(a[2]==a[0] || a[2]==a[1]);
}


В результате работы этой процедуры массив а[] может оказаться в одном из шести, а не восьми состояний. Если вы под вариантами работы программы понимаете что-то другое, то нужно заранее договориться, иначе получится, что мы говорим о разных вещах.
Скука — двигатель прогресса.
Re[7]: Интересная задача
От: UgN  
Дата: 21.11.02 09:42
Оценка:
Здравствуйте, Pushkin, Вы писали:

UgN>>См.вариант
Автор: Atilla
Дата: 21.11.02
от Atilla.


P>я ни фига не пойму, разве разрешаются вопросы, ответ на которые неопределён?


Почему не определены?
Если ты говоришь о термине "правдивее", то замени это на развернутое "чаще говорить правду"
Очевидно,
Лжец никогда не говорит правду — 0%
Тот, кого ты назвал дипломатом >0..100<
Правдивый говорит правду всегда — 100%

Поэтому их и можно сравнить по "правдивости".
Re[10]: решение
От: Atilla Россия  
Дата: 21.11.02 09:45
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

GR>Я исхожу из того, что вариант работы программы определяется результатом работы процедуры:


GR>
GR>void Shuffle()
GR>{
GR>    a[0]=rand()%3-1;
GR>    do a[1]=rand()%3-1; while(a[1]==a[0]);
GR>    do a[2]=rand()%3-1; while(a[2]==a[0] || a[2]==a[1]);
GR>}
GR>


нет, не только!!!
Есть еще

#define ASK(n, expr) (a[n]==honest ? (expr) : a[n]==liar ? !(expr) : (rand()%2==0))

а rand раз на раз не приходится. Один раз повезет — прога отрботает верно, второй раз — нет.
Кр-ть — с.т.
Re[8]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 09:46
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, Pushkin, Вы писали:


UgN>>>См.вариант
Автор: Atilla
Дата: 21.11.02
от Atilla.


P>>я ни фига не пойму, разве разрешаются вопросы, ответ на которые неопределён?


UgN>Почему не определены?

UgN>Если ты говоришь о термине "правдивее", то замени это на развернутое "чаще говорить правду"

да нет же!
я задаю вопрос, такой, на который он не может ответить
например я спрашиваю рыцаря: сосед на вопрос 2х2=4 ответит Да?
а рыцарь НЕ ЗНАЕТ, потому что сосед дипломат
рыцарь не может ответить! молчать будет? и я сразу пойму, что сосед дипломат?
или так нельзя спрашивать?
Re[3]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 09:48
Оценка:
Здравствуйте, Atilla, Вы писали:

A>4) Вопрос должен подразумевать двусложный ответ.


не понял,
я могу спросить у рыцаря "сосед на вопрос 2х2=4 ответит Да?"
если сосед дипломат, то рыцарь не может ответить — он молчит?
или такие вопросы запрещены?
Re[4]: Интересная задача
От: Atilla Россия  
Дата: 21.11.02 09:53
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>не понял,

P>я могу спросить у рыцаря "сосед на вопрос 2х2=4 ответит Да?"
P>если сосед дипломат, то рыцарь не может ответить — он молчит?
P>или такие вопросы запрещены?

значит этот вопрос с тремя вариантами ответа: да, нет и как получится. И такой вопрос не допустим.
Кр-ть — с.т.
Re[11]: решение
От: gloomy rocker Россия  
Дата: 21.11.02 09:55
Оценка:
Здравствуйте, Atilla, Вы писали:

A>нет, не только!!!

A>Есть еще

A>
A>#define ASK(n, expr) (a[n]==honest ? (expr) : a[n]==liar ? !(expr) : (rand()%2==0))
A>

A>а rand раз на раз не приходится. Один раз повезет — прога отрботает верно, второй раз — нет.

Протест понял. Просто под вариантами работы мы понимали разные вещи. Я сейчас напишу свой вариант решения. Думаю, интересно будет обсудить и его.
Скука — двигатель прогресса.
Re: Вот мой вариант решения.
От: gloomy rocker Россия  
Дата: 21.11.02 10:35
Оценка: 21 (2)
1) Обзовем эти автоматы A,B,C.
2) Обозначим -1 — лжец, 0 — "переменный", 1 — правдец.
3) Нарисуем таблицу из шести возможных вариантов

  |   A  |   B   |   C
-------------------------
1 |   1  |  -1   |   0
2 |  -1  |   1   |   0
3 |   1  |   0   |  -1
4 |  -1  |   0   |   1
5 |   0  |   1   |  -1
6 |   0  |  -1   |   1


4) Теперь нужно задать вопрос автомату А, на который он в первых двух случаях ответит "да", а следующих двух — "нет".
Вопросы могут быть разные, например такой:
Верно ли, что ты говоришь правду и B лжет или С говорит правду и ты лжешь?

Если он ответит "да", то можно исключить варианты 3,4, т.к. они подразумевают ответ "нет"
Если он ответит "нет", то можно исключить варианты 1,2, т.к. они подразумевают ответ "да"

Заметьте, что в первом случае удаляюся варианты, где С — "переменный", а во втором случае — варианты, где B — "переменный".

В случае, если А окажется "переменным", удаляются заведомо не подходящие варианты, так что он просто обязан выдать, кто из B и С не "перременный"

Таким образом могут остаться два набора вариантов:

1)

  |   A  |   B   |   C
-------------------------
3 |   1  |   0   |  -1
4 |  -1  |   0   |   1
5 |   0  |   1   |  -1
6 |   0  |  -1   |   1

Здесь второй вопрос задается C

2)

  |   A  |   B   |   C
-------------------------
1 |   1  |  -1   |   0
2 |  -1  |   1   |   0
5 |   0  |   1   |  -1
6 |   0  |  -1   |   1


Здесь второй вопрос задается B

Оставшиеся два вопроса сформулировать не сложно.
Скука — двигатель прогресса.
Re[5]: Интересная задача
От: Кодт Россия  
Дата: 21.11.02 10:50
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Вся фишка в том, что бедному дипломату всяко приходится говорить Нет,

P>по логике , по крайней мере

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

P>то это уже всё выходит за рамки таких задач. Эдак и лжец всегда будет хитро
P>прикидывать, как бы получше и похитрее ввести тебя в заблуждение и говорить
P>не всегда чистую ложь, а иезуитсткую ложь.

Этот прием — намеренный выход за пределы исчисления высказываний.
Напомню:
— есть булева алгебра, которая оперирует "числами" false|true и функциями над ними.
— есть исчисление высказываний — в котором булевы функции "!", "==" и "<=" определены на произвольном множестве.
— есть исчисление предикатов (булевы функции любой арности, определенные на произвольных множествах).
Но ни одно из этих исчислений не использует в качестве области определения сами функции (объекты высшего порядка), тем более рекурсивно!
Перекуём баги на фичи!
Re[2]: Вот мой вариант решения.
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 11:52
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

Гениально!
Первый вопрос только кривоват.
Можно я итоговый рецепт сформулирую?
Станет менее понятно, но зато очень коротко!

1)Спрашиваем первого "Из двух других тот кто правее тот правдивее?"
2)Тому, кто согласно ответу менее правдив задаём тот же вопрос.
Тот, кто согласно второму ответу более правдив — тот "переменный".
3)Последним вопросом спрашиваем у любого оставшегося "он переменный?"
и указываем на найденного в пункте 2 "переменного".
Таким образом узнаём кто лжец.

По моему это тоже самое, что ты написал, но при эксперименте не надо рисовать таблиц (но их надо рисовать, чтобы понять, почему это так)

И ещё
Фразу "Дипломат отвечает случайным образом" можно понимать двояко.
— Он случайным образом выбирает ответ Да/Нет.
— Он случайным образом выбирает Соврать/Не соврать.
Во втором случае можно так поставить вопрос,
что при любом решении дипломат ответит Да.
Например, "Ты сейчас скажешь правду?".
Тогда можно предложить другое решение
Re[3]: Вот мой вариант решения.
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 12:13
Оценка:
Здравствуйте, Pushkin, Вы писали:

иными словами — ха! — каждый следующий вопрос мы задаём наименее правдивому (если верить ответу на предыдущий вопрос) автомату
Re[6]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 13:01
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Pushkin, Вы писали:


P>>Вся фишка в том, что бедному дипломату всяко приходится говорить Нет,

P>>по логике , по крайней мере

К>- есть исчисление предикатов (булевы функции любой арности, определенные на произвольных множествах).

К>Но ни одно из этих исчислений не использует в качестве области определения сами функции (объекты высшего порядка), тем более рекурсивно!

Не понял.
Так могу я задать такой вопрос. "Ты сейчас скажешь правду?"
Мне кажется, могу, и все трое ответят Да.

С рыцарем понятно.

Лжец рассуждает так :
Я сейчас точно совру — я же лжец!
Поэтому утверждение, что я сейчас скажу правду, ложно.
Поэтому я должен говорить противоположное, т.е. Да.

Дипломат принимает решение, будет он врать при ответе
на этот вопрос, и в зависимости от принятого решения,
отвечает как рыцарь (Да) или как лжец (Да)

Здесь что-то неверно?
Re[3]: Вот мой вариант решения.
От: gloomy rocker Россия  
Дата: 21.11.02 13:05
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>По моему это тоже самое, что ты написал, но при эксперименте не надо рисовать таблиц (но их надо рисовать, чтобы понять, почему это так)

Стало действительно менее понятно Но на первый взгляд все вроде нормально. Посижу вечерком таблицы порисую

P>И ещё

P>Фразу "Дипломат отвечает случайным образом" можно понимать двояко.
Atilla сразу понял, что имеется в виду. Дипломат = генератор случайных чисел.
Скука — двигатель прогресса.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.