Страница 47-49 параграф 4 номер 13, ГДЗ по информатике за 10 класс к учебнику Босовой
Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.
Чтобы уменьшить количество открывания дверей, он действует следующим образом:
Сначала открывает склад со средним номером — склад № 16.
Затем:
• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;
• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.
После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?
Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Плотник использует метод поиска половинного деления.
Открытая дверь 1: склад с номером 16 центральный склад в последовательности номеров складов. Так как он пуст, а склады заполнялись последовательно по возрастанию, от отбрасывает просмотр всех складов правее 16-го и его в том числе.
Открытая дверь 2: склад с номером 8 является центральным среди последовательности 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Склад заполнен, значит все предыдущие тоже заполнены (т.к. заполнялись по возрастанию номеров).
Открытая дверь 3: дверь склада 12 является центральной среди последовательности 9 10 11 12 13 14 15, плотник открывает дверь и склад тоже заполнен.
Открытая дверь 4: плотник открывает дверь склада 14 (13 14 15), склад заполнен.
Открытая дверь 5: плотник открывает дверь склада с номером 15. Склад заполнен.
Получается, что склады с номерами с 1 по 15 заполнены (16 был пусть).
Ответ: плотнику пришлось открыть 5 дверей.
