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

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

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. Спокойно находим число