Question

В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие. Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров. Чтобы уменьшить количество открывания дверей, он действует следующим образом: Сначала открывает склад со средним номером — склад № 16. Затем: • если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру; • если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру. После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть? Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?

Answer 1

Объяснение:

Решение:

Двоичный поиск эффективно определяет положение искомого элемента (или его отсутствие) в упорядоченном наборе.

Это один из базовых и важных алгоритмов.

Если склады от №1 до №15 заполнены, то:

- когда плотник открывает склад №16, он оказывается пуст (1-ая открытая дверь);

- тогда плотник решает искать между №1 и №15, открывает склад №8, он оказывается заполнен (2-ая открытая дверь);

- теперь он ищет между №9 и №15, открывает склад №12 — он заполнен (3-ья открытая дверь);

- далее он ищет между №13 и №15, открывает склад №14 - он заполнен (4-ая открытая дверь);

- наконец он открывает последний склад № 15 (5-ая дверь).

Правильный ответ: 5

Answer 2

Давайте разберемся с задачей.

Плотник начинает с открывания склада № 16. Если этот склад пуст, он будет искать незаполненный склад среди складов № 1-15. Он откроет склад № 8 и так далее, деля интервал пополам и двигаясь влево или вправо в зависимости от того, заполнен ли текущий склад.

Если склад № 16 оказался заполненным, то он будет искать среди складов № 17-31, начиная с склада № 24 и также действуя методом деления интервала пополам.

Таким образом, плотник использует метод бинарного поиска (двоичного деления), который позволяет быстро сокращать интервал поиска в два раза на каждом шаге.

Теперь посчитаем, сколько дверей ему пришлось открыть. Поскольку склады заполняются от № 1 до № 15 включительно, это означает, что плотник остановился на открытии склада № 15. Количество открытых дверей равно количеству шагов бинарного поиска до достижения склада № 15.

На первом шаге открыт склад № 16. Затем:

1. Открывается склад № 8 (2-й шаг).
2. Открывается склад № 12 (3-й шаг).
3. Открывается склад № 14 (4-й шаг).
4. Открывается склад № 15 (5-й шаг).

Итак, всего было открыто 5 дверей.

Таким образом, плотнику пришлось открыть 5 дверей, и он использовал метод бинарного поиска.