Интересная задача
От: gloomy rocker Россия  
Дата: 20.11.02 14:30
Оценка: 24 (2) :)
Есть три автомата, которые умеют отвечать на любой вопрос, на который можно ответить "Да" или "Нет". Естественно все множество возможных ответов исчерпывается двумя вариантами: "Да", "Нет". Один из них всегда говорит правду, один всегда лжет, а оставшийся отвечает произвольным образом. Необходимо задать 3 вопроса и выяснить, кто есть кто.

16.01.03 23:49: Перенесено из 'Алгоритмы'
Скука — двигатель прогресса.
Re: Интересная задача
От: bnk СССР http://unmanagedvisio.com/
Дата: 20.11.02 16:13
Оценка: :)
Здравствуйте, gloomy rocker, Вы писали:

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

1 вопрос: Ответит ли 1-ый автомат на вопрос правдиво ?
2 вопрос: Ответит ли 2-ой автомат на вопрос правдиво ?
3 вопрос: Ответит ли 3-ий автомат на вопрос правдиво ?

Повисшие — те, которые говорят всегда правду и неправду, с ними разобраться элементарно.
Оставшийся в живых — случайный
Re: Интересная задача
От: WolfHound  
Дата: 20.11.02 16:18
Оценка:
Здравствуйте gloomy rocker, Вы писали:

GR>Есть три автомата, которые умеют отвечать на любой вопрос, на который можно ответить "Да" или "Нет". Естественно все множество возможных ответов исчерпывается двумя вариантами: "Да", "Нет". Один из них всегда говорит правду, один всегда лжет, а оставшийся отвечает произвольным образом. Необходимо задать 3 вопроса и выяснить, кто есть кто.
Задача не коректна ибо тот который отвечает произвольно может три раза солгать или три раза сказать правду.
... << RSDN@Home 1.0 alpha 12 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Интересная задача
От: WolfHound  
Дата: 20.11.02 17:04
Оценка:
Здравствуйте bnk, Вы писали:

bnk>Повисшие — те, которые говорят всегда правду и неправду, с ними разобраться элементарно.
bnk>Оставшийся в живых — случайный
Вопрос кто есть кто. Вот попробуй сказать кто есть кто из висящих.
... << RSDN@Home 1.0 alpha 12 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Интересная задача
От: gloomy rocker Россия  
Дата: 20.11.02 17:04
Оценка:
Здравствуйте, bnk, Вы писали:

bnk>1 вопрос: Ответит ли 1-ый автомат на вопрос правдиво ?
bnk>2 вопрос: Ответит ли 2-ой автомат на вопрос правдиво ?
bnk>3 вопрос: Ответит ли 3-ий автомат на вопрос правдиво ?

bnk>Повисшие — те, которые говорят всегда правду и неправду, с ними разобраться элементарно.
bnk>Оставшийся в живых — случайный

Каждый вопрос адресуется одному из трех автоматов, а не всем сразу.
Если я чего-то не понял, поясните, который из вопросов какому из автоматов задается.
Скука — двигатель прогресса.
Re[2]: Интересная задача
От: gloomy rocker Россия  
Дата: 20.11.02 17:07
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Задача не коректна ибо тот который отвечает произвольно может три раза солгать или три раза сказать правду.

Задача абсолютно корректна даже в этом случае. Решение я знаю, но не скажу, ибо так будет не интересно. Решение основано на обычной логике (Булевской), так что думайте.
Скука — двигатель прогресса.
Re[3]: Интересная задача
От: gloomy rocker Россия  
Дата: 20.11.02 17:12
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Вопрос кто есть кто. Вот попробуй сказать кто есть кто из висящих.

Точно, точно! Нужен по крайней мере четвертый вопрос, но попробуй задай его зависшему автомату
Скука — двигатель прогресса.
Re[3]: Интересная задача
От: bnk СССР http://unmanagedvisio.com/
Дата: 20.11.02 17:13
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

bnk>>Повисшие — те, которые говорят всегда правду и неправду, с ними разобраться элементарно.
bnk>>Оставшийся в живых — случайный
WH>Вопрос кто есть кто. Вот попробуй сказать кто есть кто из висящих.

И правда
Не все так просто как кажется
Re: Интересная задача
От: Atilla Россия  
Дата: 20.11.02 20:48
Оценка:
Эх... ща инет отключится на профилактику, а отгадку так и не придумал ((
Кр-ть — с.т.
Re[3]: Интересная задача
От: bnk СССР http://unmanagedvisio.com/
Дата: 21.11.02 04:33
Оценка:
Здравствуйте, gloomy rocker, Вы писали:

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

WH>>Задача не коректна ибо тот который отвечает произвольно может три раза солгать или три раза сказать правду.

GR>Задача абсолютно корректна даже в этом случае. Решение я знаю, но не скажу, ибо так будет не интересно. Решение основано на обычной логике (Булевской), так что думайте.

Чего-то мне так не кажется. Без "завешиваний" по-моему, не обойтись.
Ведь тот, который отвечает произвольно, может ответить на все 3 вопроса так же как и любой из первых двух,
и тогда он неотличим
Может предлагается довольствоваться вероятностью ?
Или под "произвольно" понимается что он отвечает по очереди "Да" и "Нет" ?
Re[4]: решение
От: Atilla Россия  
Дата: 21.11.02 05:13
Оценка: 36 (3)
тут "эмулятор" этих автоматов и 2 способа решения (одно попонятнее, другое — покороче) 



#include <ctime>
#include <cstdlib>
#include <cassert>
#include <string>
#include <iostream>

using namespace std;

const int liar=-1, crafty=0, honest=+1;

int a[3]; // = { liar, crafty, honest};

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]);
}

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

void Solve(int b[3])
{
    unsigned int j, k;
    if(ASK(0, a[1]>a[2]))// #1
        j=2, k=1;
    else
        j=1, k=2;
    // assert(a[j]!=crafty);
    if(ASK(j, a[j]!=crafty))// #2
    {
        b[j]=honest;
        if(ASK(j, a[0]!=crafty))// #3
            b[0]=liar, b[k]=crafty;
        else
            b[0]=crafty, b[k]=liar;
    }else
    {
        b[j]=liar;
        if(ASK(j, a[0]!=crafty))// #3
            b[0]=crafty, b[k]=honest;
        else
            b[0]=honest, b[k]=crafty;
    }
}

#define SWAP(A, B) {unsigned int t=A; A=B; B=t;}

void Solve2(int b[3])
{
    unsigned int A=0, B=1, C=2;
    if(ASK(A, a[B]>a[C]))// #1
        SWAP(B, C)

    bool flag=(ASK(B, a[B]!=crafty));// #2

    if(ASK(B, a[A]!=crafty)==flag)// #3
        SWAP(A, C)

    if(flag) SWAP(B, C)

    b[A]=crafty, b[B]=liar, b[C]=honest;
}

void main()
{
    srand(time(NULL));

    for(int i=0;i<1000;i++)
    {
        Shuffle();
        cout << "cond:" << a[0] << ", " << a[1] << ", " << a[2] << endl ;

        int b[3];
        Solve(b);
        cout << "answ:" << b[0] << ", " << b[1] << ", " << b[2] << endl ;
        assert(a[0]==b[0] && a[1]==b[1] && a[2]==b[2]);
        
        Solve2(b);
        cout << "ans2:" << b[0] << ", " << b[1] << ", " << b[2] << endl ;
        assert(a[0]==b[0] && a[1]==b[1] && a[2]==b[2]);

        cout << "==============" << endl << endl;

    }
    cout << "Ok!!!" << endl;
}


идея такая: первым вопросом определяем, какой автомат точно не является случайным. Вторым определяем, какой это именно автомат: врущий или правдивый. А третим — кто есть who из оставшихся автоматов. Хитростей тут две: 1) алгоритм адаптивный, т.е. заранее не известно у кого и что будем спрашивать во 2-й и 3-й раз. 2) вопросы задаем только 2-м автоматам (последние 2 — одному и тому же автомату).
Кр-ть — с.т.
Re[5]: решение
От: bnk СССР http://unmanagedvisio.com/
Дата: 21.11.02 05:34
Оценка:
Здравствуйте, Atilla, Вы писали:

A> if(ASK(0, a[1]>a[2]))// #1

Предположим, что 1 автомат всегда говорит правду.
Значит, на самом деле он он не знает априори значение выражения a[1]>a[2]
(он знает это только потому что находится в одной программе с остальными
и массив уже проинициализирован ).
Следовательно, при таком вопросе первый автомат повисает.
Re[5]: решение
От: bnk СССР http://unmanagedvisio.com/
Дата: 21.11.02 06:28
Оценка:
Здравствуйте, Atilla, Вы писали:

A>тут "эмулятор" этих автоматов и 2 способа решения (одно попонятнее, другое — покороче)

Как я был неправ
Re[5]: решение
От: UgN  
Дата: 21.11.02 08:08
Оценка:
Здравствуйте, Atilla, Вы писали:

A>идея такая: первым вопросом определяем, какой автомат точно не является случайным.

Лень в программе копаться.

Можно ли кратенько суть, как одним вопросом, узнать какой автомат точно не является случайным?
Re[5]: решение
От: gloomy rocker Россия  
Дата: 21.11.02 08:15
Оценка:
Здравствуйте, Atilla, Вы писали:

A>тут "эмулятор" этих автоматов и 2 способа решения (одно попонятнее, другое — покороче)

Зачем такие сложности с 1000 испытаний ?
Такой код эффективнее. 
#include <ctime>
#include <cstdlib>
#include <iostream>

using namespace std;
const int liar=-1, crafty=0, honest=+1;

int i = 0;
int a[6][3] = 
{
    { liar, crafty, honest},
    { liar, honest, crafty},
    { honest, crafty, liar},
    { honest, liar, crafty},
    { crafty, liar, honest},
    { crafty, honest, liar},
};

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

void Solve(int b[3])
{
    unsigned int j, k;
    if(ASK(0, a[i][1]>a[i][2]))// #1
        j=2, k=1;
    else
        j=1, k=2;
    if(ASK(j, a[i][j]!=crafty))// #2
    {
        b[j]=honest;
        if(ASK(j, a[i][0]!=crafty))// #3
            b[0]=liar, b[k]=crafty;
        else
            b[0]=crafty, b[k]=liar;
    }else
    {
        b[j]=liar;
        if(ASK(j, a[i][0]!=crafty))// #3
            b[0]=crafty, b[k]=honest;
        else
            b[0]=honest, b[k]=crafty;
    }
}

void main()
{
    srand(time(NULL));
    int b[3];
    for(i=0;i<6;i++)
    {
        cout << "cond:" << a[i][0] << ", " << a[i][1] << ", " << a[i][2] << endl ;
        Solve(b);
        cout << "answ:" << b[0] << ", " << b[1] << ", " << b[2] << endl ;        
        cout << "==============" << endl << endl;
    }
    cout << "Ok!!!" << endl;
}


A>идея такая: первым вопросом определяем, какой автомат точно не является случайным. Вторым определяем, какой это именно автомат: врущий или правдивый. А третим — кто есть who из оставшихся автоматов. Хитростей тут две: 1) алгоритм адаптивный, т.е. заранее не известно у кого и что будем спрашивать во 2-й и 3-й раз. 2) вопросы задаем только 2-м автоматам (последние 2 — одному и тому же автомату).

Идея абсолютно правильная!!!
Я покапался в программе и понял, что реализация идеи тоже правильная.
Скука — двигатель прогресса.
Re: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 08:21
Оценка:
Спрашиваем первого: ты дипломат?.
Да — первый либо дипломат либо лжец.
Спрашиваем второго: ты сейчас ответишь также правдиво, как предыдущий?
Да — первый дипломат
Спрашиваем второго: первый дипломат?
Да — второй рыцарь, третий лжец
Нет — второй лжец, третий рыцарь
Нет — первый лжец
Спрашиваем первого: второй дипломат?
Да — второй рыцарь, третий дипломат
Нет — второй дипломат, третий рыцарь
Нет — первый либо дипломат либо рыцарь
Спрашиваем второго: ты сейчас ответишь также правдиво, как предыдущий?
Да — первый рыцарь
Спрашиваем первого: второй дипломат?
Да — второй дипломат, третий лжец.
Нет — второй лжец, третий дипломат.
Нет — первый дипломат
Спрашиваем второго: первый дипломат?
Да — второй рыцарь, третий лжец
Нет — второй лжец, третий рыцарь

второй вопрос — серебряная пуля против дипломата!
Re[2]: Интересная задача
От: Pushkin Россия www.linkbit.com
Дата: 21.11.02 08:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

чёрт! форматирование забыл, вот:

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


второй вопрос — серебряная пуля против дипломата!
Re[3]: Интересная задача
От: UgN  
Дата: 21.11.02 08:35
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


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

Первый — лжец — на первый вопрос ответил Да (Лжет, что он дипломат)
Второй — дипломат — на второй вопрос ответил Да ( Случайным образом )

А у тебя из этого следует, что первый — дипломат.
Re[6]: решение
От: Atilla Россия  
Дата: 21.11.02 08:46
Оценка:
Здравствуйте, gloomy rocker, Вы писали:


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

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

GR>Идея абсолютно правильная!!!
GR>Я покапался в программе и понял, что реализация идеи тоже правильная.

главное — работает.
Кр-ть — с.т.
Re[6]: решение
От: Atilla Россия  
Дата: 21.11.02 08:52
Оценка: 26 (2)
Здравствуйте, UgN, Вы писали:

UgN>Лень в программе копаться.

UgN>Можно ли кратенько суть, как одним вопросом, узнать какой автомат точно не является случайным?

int A[6][3] = 
{
    { liar, crafty, honest},
    { liar, honest, crafty},
    { honest, crafty, liar},
    { honest, liar, crafty},
    { crafty, liar, honest},
    { crafty, honest, liar},
};


а этот вопрос задается первому: "Второй автомат правдивее третьего?". В случаях A[0] или A[2] ответ будет "да", в случаях A[1] или A[3] — "нет", в остальных — неопределен. Значит, если ответ "да", то 3-й автомат не случайный, а если "нет" — то второй. Считается, что honest правдивее crafty, который правдивее liar.
Кр-ть — с.т.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.