В начале электронной книги, содержащей 18 страниц, приведена теория и задачи, напечатанные крупным шрифтом, а дальше идут ответы, напечатанные мелким шрифтом. Перед ними напечатан заголовок "Ответы". Мы пытаемся поскорее дойти до ответов, открывая книгу на некоторой странице. За какое наименьшее количество попыток можно узнать номер страницы, на которой начинаются ответы? Гарантируется, что на первой странице приведена только теория. В каждый момент времени показывается только одна страница.

задан 29 Сен '15 21:49

10|600 символов нужно символов осталось
1

В таких случаях обычно применяется "деление пополам". По условию, заголовок "Ответы" может встретиться на любой странице от 2-й до 18-й включительно. Поэтому уместно открыть книгу на средней из них, то есть на 10-й. При этом, если мы не увидим заголовок, то по размеру шрифта поймём, где надо искать: до или после. В каждом из случаев у нас останется по 8 вариантов. Если мы вместо 10-й откроем другую из страниц, то в случае, если нам не повезёт, может остаться более 8 страниц, на которых нужно искать, то есть такой вариант потребует не меньшего числа попыток.

При поиске из 8 страниц открыть надо 4-ю или 5-ю из них (точно посередине уже нельзя). В худшем случае останется 4 страницы для поиска, и из них надо будет открыть одну "среднюю". Далее при невезении окажется 2 страницы, что даст ещё 2 попытки, если сразу не угадаем. Итого потребуется 5 попыток в худшем случае.

ссылка

отвечен 29 Сен '15 22:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×89

задан
29 Сен '15 21:49

показан
563 раза

обновлен
29 Сен '15 22:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru