Сколько вопросов, на которые следует ответ "да/нет", нужно задать, чтобы наверняка
Сколько вопросов, на которые следует ответ "да/нет", нужно задать, чтоб наверное угадать загаданного ученика школы (в ней 560 человек) и его денек рождения (год разгадывать не нужно)?
1 ответ
Ева Палушина
Имеет смысл пользоваться способом "дихотомии" (разделенья напополам).
Если с деньком рождения все понятно: в году максимум 366 дней и нужно определить нужный, то неясно, как быть с задуманным воспитанником - их условно пронумеровать и спрашивать о номере?
Поэтому принимаем такое решение. Мы разделяем перечень воспитанников на два доли (например, написав сведения о каждом на отдельной карточке и разложив эти карточки на две одинаковые кучки по 560/2 = 280 человек в каждой. Потом задаем вопрос: загаданный воспитанник находится в первой кучке? По результатам ответа кучку, содержащую загаданного ученика, опять разделяем напополам. Процесс повторяем пока не остается одна карточка. Подобно поступаем с датами рождения.
Тогда количество вопросов определится, как ступень числа 2, дающая число, не наименьшее количества учеников (дней рождения).
2 lt; 560 lt; 2, потому воспитанник будет угадан максимум за 10 вопросов.
2 lt; 366 lt; 2, потому денек рождения будет угадан максимум за 9 вопросов.
В сумме потребуется задать не более 9+10 = 19 вопросов.
Конечно, можно придумать более продвинутую систему, когда на карточках учеников будут указаны сразу и даты их рождения, тогда количество вопросов можно снизить.
Если с деньком рождения все понятно: в году максимум 366 дней и нужно определить нужный, то неясно, как быть с задуманным воспитанником - их условно пронумеровать и спрашивать о номере?
Поэтому принимаем такое решение. Мы разделяем перечень воспитанников на два доли (например, написав сведения о каждом на отдельной карточке и разложив эти карточки на две одинаковые кучки по 560/2 = 280 человек в каждой. Потом задаем вопрос: загаданный воспитанник находится в первой кучке? По результатам ответа кучку, содержащую загаданного ученика, опять разделяем напополам. Процесс повторяем пока не остается одна карточка. Подобно поступаем с датами рождения.
Тогда количество вопросов определится, как ступень числа 2, дающая число, не наименьшее количества учеников (дней рождения).
2 lt; 560 lt; 2, потому воспитанник будет угадан максимум за 10 вопросов.
2 lt; 366 lt; 2, потому денек рождения будет угадан максимум за 9 вопросов.
В сумме потребуется задать не более 9+10 = 19 вопросов.
Конечно, можно придумать более продвинутую систему, когда на карточках учеников будут указаны сразу и даты их рождения, тогда количество вопросов можно снизить.
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
там лежат три яйца.у дома рос клен.Это гнездо сойки.на клёне гнездо
Русский язык.
Тыныштық күйіндегі карусель 35 с-та 3,0 рад/с бұрыштық жылдамдықпен үдей қозғалады.
Разные вопросы.
Сочинение на тему "Русский язык не сможет умереть!"
Математика.
Приветствую!
Меня зовут Станислав, я представляю компанию under.site.
Хотел бы предложить интересное решение
Разные вопросы.
Масса трёх одинаковых пакетов чая 180г чему равна масса
Математика.
Газообразный аммиак объёмом 2.24 л (н.у.) был полностью поглощён 14.68 мл
Химия.
Упражнение 2 Выпишите глаголы и вставьте пропущенные буквы
Русский язык.
Радиус окружности, описанной около равностороннего треугольника, равен 6. Найдите сторону треугольника
Геометрия.
Вычислите силу с которой при давлении 100 КПа атмосфера давит на
Физика.
Синтаксический разбор и схема Но мы сказали, что нам ничего не
Русский язык.
Облако тегов