§ 4. Обработка информации. ГДЗ по Информатике для 10 класса. Босова.
13. В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.
Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.
Чтобы уменьшить количество открывания дверей, он действует следующим образом:
Сначала открывает склад со средним номером — склад № 16. Затем:
• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;
• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.
После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?
Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?
Ответ
Двоичный поиск эффективно определяет положение искомого элемента (или его отсутствие) в упорядоченном наборе. Это один из базовых и важных алгоритмов.
Если склады от №1 до №15 заполнены, то: — когда плотник открывает склад №16, он оказывается пуст (1-ая открытая дверь);
— тогда плотник решает искать между №1 и №15, открывает склад №8, он оказывается заполнен (2-ая открытая дверь);
— теперь он ищет между №9 и №15, открывает склад №12 — он заполнен (3-ья открытая дверь);
— далее он ищет между №13 и №15, открывает склад №14 — он заполнен (4-ая открытая дверь);
— наконец он открывает последний склад № 15 (5-ая дверь).
Правильный ответ: 5