Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
Только один раз можно ответить не верно.
Каков оптимальный алгоритм решения этой задачи?

Здравствуйте, Аноним, Вы писали:

А>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>Только один раз можно ответить не верно.
А>Каков оптимальный алгоритм решения этой задачи?
Смотря какой критерий оптимальности.

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

UD>Здравствуйте, Аноним, Вы писали:

А>>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>>Только один раз можно ответить не верно.
А>>Каков оптимальный алгоритм решения этой задачи?
UD>Смотря какой критерий оптимальности.

Критерий: как можно меньше задать вопросов?

Здравствуйте, <Аноним>, Вы писали:

А>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>Только один раз можно ответить не верно.
А>Каков оптимальный алгоритм решения этой задачи?

Я так понимаю, диапазон известен. Тогда неплохим алгоритмом будет обычный, с половинным делением, только каждый вопрос будем повторять по два раза (вопросы вроде "Задуманное число больше X?" или "Задуманное число — X?", когда диапазон совсем сузился). Если оба ответа совпадают, двигаемся дальше. Если различаются — задаем последний вопрос еще раз, а последующие вопросы задаем однократно. В худшем случае будет задано 2*ceil(log(N))+1 вопросов.

Казалось бы, можно было как-то исхитриться, задавая вопросы по одному разу и выполняя откат при обнаружении противоречия. Но если вопросы ставить в той форме, как я привел, то задав ceil(log(N)) вопросов и обнаружив противоречие, придется выяснять, где же нас обманули. Могли обмануть самым первым ответом. Скажем, задумано число 1 из диапазона [1,1000]. На вопрос "Число больше 500?" отвечают "Да", а потом при исследовании диапазона [501,1000] на вопросы "Больше?" с честным видом отвечают "Нет". В итоге у нас остается один вариант — 501, на котором обнаруживается противоречие. Перепроверять ответы, начиная не с первого, невыгодно, потому что потом все равно придется исследовать диапазон [1,500], что в худшем случае дает примерно такое же количество вопросов, как в примитивном способе.

Если пофантазировать с возможными конструкциями вопросов, наверное, можно выжать еще что-то...

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

C>Здравствуйте, <Аноним>, Вы писали:

А>>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>>Только один раз можно ответить не верно.
А>>Каков оптимальный алгоритм решения этой задачи?

C>Я так понимаю, диапазон известен. Тогда неплохим алгоритмом будет обычный, с половинным делением, только каждый вопрос будем повторять по два раза (вопросы вроде "Задуманное число больше X?" или "Задуманное число — X?", когда диапазон совсем сузился). Если оба ответа совпадают, двигаемся дальше. Если различаются — задаем последний вопрос еще раз, а последующие вопросы задаем однократно. В худшем случае будет задано 2*ceil(log(N))+1 вопросов.

C>Казалось бы, можно было как-то исхитриться, задавая вопросы по одному разу и выполняя откат при обнаружении противоречия. Но если вопросы ставить в той форме, как я привел, то задав ceil(log(N)) вопросов и обнаружив противоречие, придется выяснять, где же нас обманули. Могли обмануть самым первым ответом. Скажем, задумано число 1 из диапазона [1,1000]. На вопрос "Число больше 500?" отвечают "Да", а потом при исследовании диапазона [501,1000] на вопросы "Больше?" с честным видом отвечают "Нет". В итоге у нас остается один вариант — 501, на котором обнаруживается противоречие. Перепроверять ответы, начиная не с первого, невыгодно, потому что потом все равно придется исследовать диапазон [1,500], что в худшем случае дает примерно такое же количество вопросов, как в примитивном способе.

C>Если пофантазировать с возможными конструкциями вопросов, наверное, можно выжать еще что-то...

Можно...
Есть способ уложиться примерно в ceil(log(N))+ 1 + ceil(log(ceil(log(N))+1))+1
За точное число не ручаюсь но примерно знаю как сделать.

А ввобще ИМХО задачке этой место в этюдах.

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

C>>Если пофантазировать с возможными конструкциями вопросов, наверное, можно выжать еще что-то...

T>Можно...
T>Есть способ уложиться примерно в ceil(log(N))+ 1 + ceil(log(ceil(log(N))+1))+1
T>За точное число не ручаюсь но примерно знаю как сделать.
Это если после обнаружения противоречия искать место ошибки тем же самым половинным делением (судя по виду формулы)? Но ведь потом придется угадывать число в уточненном диапазоне, что тоже требует вопросов (см. пример про 1 и 501). Попробовали отыскать число, задали O(log N) вопросов. Нашли ошибку — еще O(log log N) вопросов. Ошибка оказалась в первом вопросе. Все вопросы после первого не дают никакой информации, надо искать в другой половине диапазона.

Или как-то по-другому? Пытаться обнаруживать ошибку уже на этапе задавания вопросов? В принципе, можно попробовать. Только надо это аккуратно расписать. И надо учитывать, что при ответах на "мета-вопросы" тоже могут наврать

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

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

C>>>Если пофантазировать с возможными конструкциями вопросов, наверное, можно выжать еще что-то...

T>>Можно...
T>>Есть способ уложиться примерно в ceil(log(N))+ 1 + ceil(log(ceil(log(N))+1))+1
T>>За точное число не ручаюсь но примерно знаю как сделать.
C>Это если после обнаружения противоречия искать место ошибки тем же самым половинным делением (судя по виду формулы)? Но ведь потом придется угадывать число в уточненном диапазоне, что тоже требует вопросов (см. пример про 1 и 501). Попробовали отыскать число, задали O(log N) вопросов. Нашли ошибку — еще O(log log N) вопросов. Ошибка оказалась в первом вопросе. Все вопросы после первого не дают никакой информации, надо искать в другой половине диапазона.

C>Или как-то по-другому? Пытаться обнаруживать ошибку уже на этапе задавания вопросов? В принципе, можно попробовать. Только надо это аккуратно расписать. И надо учитывать, что при ответах на "мета-вопросы" тоже могут наврать

Пока в мыслях все вроде красиво складывается
Писанины наверное много будет, поэтому надо подготовиться. Так что щас схожу покурить и за дело (сорри за оффтоп)

Здравствуйте, Аноним, Вы писали:

А>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>Только один раз можно ответить не верно.
А>Каков оптимальный алгоритм решения этой задачи?

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

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

VC>Здравствуйте, Аноним, Вы писали:

А>>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>>Только один раз можно ответить не верно.
А>>Каков оптимальный алгоритм решения этой задачи?

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

И чем это отличается от обычного бинарного поиска?

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

VC>Здравствуйте, Аноним, Вы писали:

А>>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>>Только один раз можно ответить не верно.
А>>Каков оптимальный алгоритм решения этой задачи?

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

Пардон, не заметил условие про ошибку. Значит, вопросы надо задавать не про исходное число, а его код, позволяющий исправить одиночную ошибку (например, код Хэмминга).

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

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

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

T>И чем это отличается от обычного бинарного поиска?

По сути ничем, но для варианта с ошибками (см. мой второй пост на эту тему) в чистом виде применима теория кодов, исправляющих ошибки, так что ничего придумывать уже не надо.

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

T>Пока в мыслях все вроде красиво складывается
T>Писанины наверное много будет, поэтому надо подготовиться. Так что щас схожу покурить и за дело (сорри за оффтоп)

Нус, за дело.
Дели вопросы на 3 группы:
первая группа — состоит из одного вопроса — будут ли неверные ответы во второй группе вопросов (1)
вторая группа — вопросы поиска номера ошибки в третьей группе (2 -- n)
третья группа — собственно вопросы поика числа. (n+1 -- m)

для первой группы возможно четыре варианта ответов
"да" врет
"да" правда
"нет" врет
"нет" правда

При ответе "да" во второй группе вопросов спокойно общаемся о жизни (типа скока пива в тя влезет ) -- в третьей группе ошибки не будет точно
При ответе "нет" общаемся по САБЖу
В любом случае получаем предположительный номер где чувак должен соврать.
Если он соврал в первом вопросе этот номер будет (n+1), если нет, то реальный номер вранья.
То есть в третью группу первый вопрос надо продублировать.
Тогда если номер вранья будет равен (n+1) то в (n+2) будет правильный ответ
А если номер вранья не будет равен (n+1) то соответственно делаем операцию not() над ответом и работаем дальше.

Получается в третьей группе число вопросов равно c3 = ceil(log(count))+1
во второй группе -- c2 = ceil(log(c3))
в первой -- c1 = 1

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

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

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

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

T>>И чем это отличается от обычного бинарного поиска?

VC>По сути ничем, но для варианта с ошибками (см. мой второй пост на эту тему) в чистом виде применима теория кодов, исправляющих ошибки, так что ничего придумывать уже не надо.

А обгонит ли теория кодов мой вариант?

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

T>А обгонит ли теория кодов мой вариант?

С применением теории я вижу только одну тонкость — она заточена под известное число бит.

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

VC>Пардон, не заметил условие про ошибку. Значит, вопросы надо задавать не про исходное число, а его код, позволяющий исправить одиночную ошибку (например, код Хэмминга).

Только нехорошо пользователя заставлять переводить в двоичное представление и вычислять код Хэмминга
Если это удастся переформулировать в виде обычных вопросов —

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

C>Только нехорошо пользователя заставлять переводить в двоичное представление и вычислять код Хэмминга
C>Если это удастся переформулировать в виде обычных вопросов —

Легко! Первый вопрос:

младший бит этого числа в коде Хэмминга равен 0?

самый обычный вопрос

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

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

T>>А обгонит ли теория кодов мой вариант?

VC>С применением теории я вижу только одну тонкость — она заточена под известное число бит.
А я вижу еще одну тонкость
Для того чтбы закодировать последовательность бит -- ее нужно знать

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

VC>Легко! Первый вопрос:

VC>

VC>младший бит этого числа в коде Хэмминга равен 0?

VC>самый обычный вопрос

нехорошо пользователя заставлять ... вычислять код Хэмминга

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

VC>>самый обычный вопрос
C>

нехорошо пользователя заставлять ... вычислять код Хэмминга

C>)

Хорошо, можно в программе дополнительно предусмотреть вычисление кода Хэмминга введенного числа.

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

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

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

T>>>А обгонит ли теория кодов мой вариант?

VC>>С применением теории я вижу только одну тонкость — она заточена под известное число бит.
T>А я вижу еще одну тонкость
T>Для того чтбы закодировать последовательность бит -- ее нужно знать
Торможу

Здравствуйте, Аноним, Вы писали:

А>Программа должна отгадать задумманое число задавая вопросы на которые можно отвечать только да и нет.
А>Только один раз можно ответить не верно.
А>Каков оптимальный алгоритм решения этой задачи?

A0 — множество потенциальных задумманых чисел, если все ответы честные
A1 — множество потенциальных задумманых чисел, если один ответ нечестный
В начале все допустимые числа в A0
Алгоритм:
1. if size(A0+A1)=1 -> выдать ответ
2. S = половина чисел из A0 + половина чисел из A1
3. Вопрос: задумманое число в S?
4. Результаты: половина A0 уходит в A1, половина A1 пропадает
5. goto 1

Если слова "половина" заменить на f1(size(A0), size(A1)) и f2(size(A0), size(A1)), то алгоритм оптимальный при условии оптимальности f1 и f2. Осталось найти f1 и f2 (может это как раз div 2 +-1 и будут...)

P.S. ветку пора в Этюды

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


T>Получается в третьей группе число вопросов равно c3 = ceil(log(count))+1
T>во второй группе -- c2 = ceil(log(c3))
T>в первой -- c1 = 1
T>

Сорри, не учел случай, когда чувак все-таки не врет, но вроде больше вопросов не станет,
а вообще есть еще один вариант
1. Первым делом высчитываем количество ответов, которое надо для отгадывания без вранья.
2. Первым вопросом спрашиваем: (правду ли ты скажешь в "такком-то" вопросе) , номер вопроса должен быть за пределами высчитанного количества.
3. Говорим чуваку: (ты солгал!!! Потому что "таккой-то" вопрос задан не будет, поэтому ответ заведомо ложный)
4. Спокойно находим число