В англо-российском словарике 80 страничек, на каждой из который по 50
В англо-российском словарике 80 страниц, на каждой из который по 50 слов. Петя открыл словарь на случайной странице и загадал случайное слово с этой странички. Сумеет ли Витя угадать его за 12 вопросов? Петя отвечает на вопросы только "да" либо "нет". (Если вы считаете, что Витя сумеет отгадать, то нужно написать эти 12 вопросов. Если вы считаете, что он не сумеет, то необходимо доказательство этого факта)
Задать свой вопрос1 ответ
Sergej
В данном случае превосходнейшей является стратегия половинного дробленья. Поначалу определяем страничку. Будем разделять каждый раз количество страниц, содержащих подходящую, напополам.
1-ый вопрос: "Подходящая страничка имеет номер больше 40?" Если да, то разглядываем страницы с 41 по 80, если нет - то странички с 1 до 40.
2-ой вопрос для варианта, когда номер странички был больше 40 будет выглядеть так: "Нужная страничка имеет номер больше 60?". А если номер странички был не больше 40, то спрашиваем "Подходящая страница имеет номер больше 20?".
При такой схеме количество нужных вопросов будет одинаково 7 ( 2lt;80lt;2).
Обнаружив подходящую страничку по таковой же схеме отыскиваем номер слова (от 1 до 50).
Так как 2lt;50lt;2, то потребуется задать 6 вопросов.
7 вопросов для определения номера странички и 6 для определения номера слова на ней - всего 13 вопросов. Поэтому за 12 вопросов отгадать слово не получится.
В то же время, если бы можно было пронумеровать все слова от 1 до 4000 (50х80=4000) и задавать вопросы по порядковым номерам слов, то 12 вопросов хватило бы (2lt;4000lt;2)
1-ый вопрос: "Подходящая страничка имеет номер больше 40?" Если да, то разглядываем страницы с 41 по 80, если нет - то странички с 1 до 40.
2-ой вопрос для варианта, когда номер странички был больше 40 будет выглядеть так: "Нужная страничка имеет номер больше 60?". А если номер странички был не больше 40, то спрашиваем "Подходящая страница имеет номер больше 20?".
При такой схеме количество нужных вопросов будет одинаково 7 ( 2lt;80lt;2).
Обнаружив подходящую страничку по таковой же схеме отыскиваем номер слова (от 1 до 50).
Так как 2lt;50lt;2, то потребуется задать 6 вопросов.
7 вопросов для определения номера странички и 6 для определения номера слова на ней - всего 13 вопросов. Поэтому за 12 вопросов отгадать слово не получится.
В то же время, если бы можно было пронумеровать все слова от 1 до 4000 (50х80=4000) и задавать вопросы по порядковым номерам слов, то 12 вопросов хватило бы (2lt;4000lt;2)
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
Игорь 14 лет назад был на 8 лет моложе, чем его
Математика.
Два тела массами m1 и m2 находящие на расстоянии R друг
Физика.
В сосуде 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 причём
Геометрия.
Облако тегов