Решение задач конкурса "Бобер"

Задачи для 7-8 классов







Плотник в Бобровой Деревне использует 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