Question

Даю 80 баллов Ваш приятель Дима живёт в доме, в котором 8 квартир. Вы не знаете, в какой именно квартире он живёт. Подойдя к дому, вы встретили девочку, которая знает номер квартиры Димы, но после каждого вопроса лишь кивает головой (да) или мотает (нет). Какое наименьшее количество вопросов необходимо задать девочке, чтобы узнать номер квартиры Димы?(Пожалуйста надо сегодня сделать)​

Answer 1

В таких задачах всегда самый быстрый способ найти ответ это делить объем вариантов пополам и спрашивать каждый раз есть ли в выбранной половине ответ. В данной задаче цепочка будет такой: 1. Его номер квартиры больше 4? 0 если ответ да, то дальше цепочка такая же только номера надо будет брать из другого промежутка. 2. Его номер квартиры больше 2? 3. Его номер квартиры %3D 2?

Answer 2

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

Начнем с первого вопроса:

1. Вопрос: "Дима живет в первой половине дома?" - Если девочка кивает (да), то Дима живет в первой половине дома. Теперь у вас остались 4 квартиры. - Если девочка мотает (нет), то Дима живет во второй половине дома. Также у вас остались 4 квартиры.

Теперь у вас есть 4 возможных варианта. Продолжим бинарный поиск:

2. Вопрос: "Дима живет в первой половине из оставшихся квартир?" - Если девочка кивает (да), то остаются 2 квартиры. - Если девочка мотает (нет), то остаются 2 квартиры в другой половине.

Теперь у вас есть всего 2 возможных варианта. Последний вопрос:

3. Вопрос: "Дима живет в первой из оставшихся двух квартир?" - Если девочка кивает (да), то Дима живет в первой квартире. - Если девочка мотает (нет), то Дима живет во второй квартире.

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