Сколько вопросов, на которые следует ответ "да/нет", нужно задать, чтобы наверняка
Сколько вопросов, на которые следует ответ "да/нет", нужно задать, чтоб наверное угадать загаданного ученика школы (в ней 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
Статьи
Информатика
Статьи
Последние вопросы
В сосуде 4целых одна пятая литр воды что бы заполнить сосуд
Математика.
Двум малярам Диме И Олегу поручили выкрасить фасад дома они разделили
Разные вопросы.
найти порядковый номер 41Э если в ядре 20 нейтронов
Разные вопросы.
в ряду натуральных чисел 3, 8, 10, 24, … 18 одно
Математика.
Предприятие по производству с/хоз продукции на производство затратило 3527000 руб Валовый
Разные вопросы.
Математика, задано на каникулы. ВАРИАНТ 1004
НОМЕР 1,2,3,4,5,6,7,8.
Математика.
Имеются три конденсатора емкостью С1=1мкФ, С2=2мкФ и С3=3мкФ. Какую наименьшую емкость
Физика.
Из точки м выходят 3 луча MP MN и MK причём
Геометрия.
выпиши в свою тетрадь те правила этикета которые тебе не были
Разные вопросы.
Анна хорошо учится у неё много подруг свободное от учёбы время
Обществознание.
Облако тегов