Question

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

Answer 1

А можно еще сократить вот так: Задаем вопросы след образом:

Ты родился в первую половину года? - да (янв, фев, март, апр, май, июнь)

В первую половину первой половины? - да (янв, фев, март)

В первую половину этих трех месяцев - нет (с 15 фев по март т.е. 44 дня)

В первую половину этих 44 дней - да (первые 22)

В первую половину этих 22 дней - да (первые 11)

затем первые 6

затем первые 3

затем перые 2

затем 1

Итого за 9 вопоросов вне зависимости ответов да или нет.

Answer 2

Пойдем от минимального:

-ты родился зимой-да

-в январе-да

-в первой декаде месяца-да

-первого числа-да Всего 8 вопросом

Пойдем от максимального:

-ты родился зимой-нет

-весной-нет

-летом-нет

-осенью-да

-в сентябре-нет

-в октябре-нет

-в ноябре-да

-в первой декаде месяца-нет

-во второй-нет

-в третей-да

-в первые пять дней третей декады-нет

-во вторые пять дней-да

-26-нет

-27-нет

-28-нет

-29-нет

-30-нет

-31-да

Всего 18 вопросов

 

Answer 3

Если мартышка хочет узнать день рождения Слоненка и Слоненок может отвечать только "да" или "нет", то мартышке нужно задать минимальное количество вопросов, чтобы определить день рождения.

Для этого можно применить стратегию бинарного поиска. Сначала мартышка спрашивает Слоненка о дне рождения, например: "Твой день рождения 1-го числа?". Если Слоненок отвечает "да", то мартышка знает, что день рождения Слоненка находится среди чисел от 1 до 15 (поскольку в марте 31 день, а половина от 31 - это 15,5, округляем вниз до 15). Если же Слоненок отвечает "нет", то мартышка знает, что день рождения Слоненка находится среди чисел от 16 до 31.

Далее мартышка задает вопросы, сужая диапазон возможных дней рождения Слоненка пополам. Например, если мартышка спрашивает: "Твой день рождения 8-го числа?", и Слоненок отвечает "нет", то мартышка знает, что день рождения Слоненка находится среди чисел от 16 до 31, и далее спрашивает: "Твой день рождения 23-го числа?".

Продолжая эту стратегию, мартышке потребуется задать максимум 5 вопросов, чтобы определить день рождения Слоненка. Если мартышка задаст вопросы о числах 1, 8, 16, 23 и 29 (или 31), то она сможет с уверенностью узнать день рождения Слоненка.