|
В начале электронной книги, содержащей 18 страниц, приведена теория и задачи, напечатанные крупным шрифтом, а дальше идут ответы, напечатанные мелким шрифтом. Перед ними напечатан заголовок "Ответы". Мы пытаемся поскорее дойти до ответов, открывая книгу на некоторой странице. За какое наименьшее количество попыток можно узнать номер страницы, на которой начинаются ответы? Гарантируется, что на первой странице приведена только теория. В каждый момент времени показывается только одна страница. задан 29 Сен '15 21:49 
Анастасия9A |
|
В таких случаях обычно применяется "деление пополам". По условию, заголовок "Ответы" может встретиться на любой странице от 2-й до 18-й включительно. Поэтому уместно открыть книгу на средней из них, то есть на 10-й. При этом, если мы не увидим заголовок, то по размеру шрифта поймём, где надо искать: до или после. В каждом из случаев у нас останется по 8 вариантов. Если мы вместо 10-й откроем другую из страниц, то в случае, если нам не повезёт, может остаться более 8 страниц, на которых нужно искать, то есть такой вариант потребует не меньшего числа попыток. При поиске из 8 страниц открыть надо 4-ю или 5-ю из них (точно посередине уже нельзя). В худшем случае останется 4 страницы для поиска, и из них надо будет открыть одну "среднюю". Далее при невезении окажется 2 страницы, что даст ещё 2 попытки, если сразу не угадаем. Итого потребуется 5 попыток в худшем случае. отвечен 29 Сен '15 22:16 
falcao |