ГДЗ по информатике 10 класс Босова, номер §4 № 13

§ №

Поиск методом половинного деления

В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.

Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.

Чтобы уменьшить количество открывания дверей, он действует следующим образом:
Сначала открывает склад со средним номером — склад № 16.
Затем:
• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;
• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.
После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?

Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?

Решение

Поскольку склады заполняли по возрастанию номеров, заполненные образуют начальную часть ряда, а пустые — его конец. По результату открытия среднего склада можно отбросить половину номеров. Это метод половинного деления.

Открытие	Склад	Состояние	Где теперь первый пустой склад
		пуст	–
		заполнен	–
		заполнен	–
		заполнен	–
		заполнен

Сначала пустота склада показывает, что первый пустой имеет номер не больше . Склад заполнен, значит, все склады – тоже заполнены. По тому же правилу заполненность складов , и последовательно исключает номера –, – и . В итоге последним заполненным оказывается , а первым пустым — .

Таким образом, открыты двери складов , , , и — всего дверей.

Ответ

дверей; использован метод половинного деления.

Помогло?

Номер §4 № 13