В
Все
Б
Биология
Б
Беларуская мова
У
Українська мова
А
Алгебра
Р
Русский язык
О
ОБЖ
И
История
Ф
Физика
Қ
Қазақ тiлi
О
Окружающий мир
Э
Экономика
Н
Немецкий язык
Х
Химия
П
Право
П
Психология
Д
Другие предметы
Л
Литература
Г
География
Ф
Французский язык
М
Математика
М
Музыка
А
Английский язык
М
МХК
У
Українська література
И
Информатика
О
Обществознание
Г
Геометрия

В- словарике 80 страниц, на каждой из который по 50 слов. петя открыл словарь на случайной странице и загадал случайное слово с этой страницы. сможет ли витя угадать его за 12 вопросов? петя отвечает на вопросы только "да" или "нет". (если вы считаете, что витя сможет отгадать, то нужно написать эти 12 вопросов. если вы считаете, что он не сможет, то нужно доказательство этого факта)

Показать ответ
Ответ:
SKIRLES
SKIRLES
30.07.2020 06:29
В данном случае наилучшей является стратегия половинного деления. Сначала определяем страницу. Будем делить каждый раз количество страниц, содержащих нужную, пополам.
Первый вопрос: "Нужная страница имеет номер больше 40?" Если да, то рассматриваем страницы с 41 по 80, если нет - то страницы с 1 до 40.
Второй вопрос для случая, когда номер страницы был больше 40 будет выглядеть так: "Нужная страница имеет номер больше 60?". А если номер страницы был не больше 40, то спрашиваем "Нужная страница имеет номер больше 20?".
При такой схеме количество необходимых вопросов будет равно 7 ( 2⁶<80<2⁷).

Найдя нужную страницу по такой же схеме ищем номер слова (от 1 до 50).
Поскольку 2⁵<50<2⁶, то потребуется задать 6 вопросов.

7 вопросов для определения номера страницы и 6 для определения номера слова на ней - всего 13 вопросов. Поэтому за 12 вопросов отгадать слово не удастся.

В то же время, если бы можно было пронумеровать все слова от 1 до 4000 (50х80=4000) и задавать вопросы по порядковым номерам слов, то 12 вопросов хватило бы (2¹¹<4000<2¹²)
0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота