ГДЗ по информатике, 10 класс, Босова, номер 4.13: Обработка информации

У нас есть 31 склад с номерами от 1 до 31. Склады заполнены по порядку возрастания номеров. Известно, что склады с № 1 по № 15 включительно заполнены . Следовательно, первый незаполненный склад — это склад № 16.

Метод половинного деления (бинарный поиск) работает следующим образом: мы проверяем средний элемент диапазона. Если он соответствует условию «искать дальше», мы сужаем диапазон поиска вдвое.

• Начальный диапазон поиска: [1;31].
• Цель: найти границу между заполненными и пустыми складами или сам первый пустой склад.

Проследим действия плотника шаг за шагом, учитывая, что склады 1-15 заполнены, а склад 16 пуст.

Давайте пересмотрим логику остановки. Обычно бинарный поиск ищет конкретный индекс. Здесь мы ищем переход. 1. Проверили 16: пуст. Значит, ответ где-то слева или это 16, если бы слева были пустые? Нет, условие говорит: «если пуст — ищет в диапазоне 1–15». Это значит, что плотник считает, что пустой склад может быть среди первых 15? Или он ищет первый пустой? Если склады 1-15 заполнены, то первый пустой — 16. При проверке склада 16 плотник видит, что он пуст. Согласно правилу: «если пуст — ищет в диапазоне 1–15». Почему? Потому что он не знает заранее, что 1-15 заполнены. Он предполагает, что пустых может быть больше, и хочет найти самый первый (с наименьшим номером). Поэтому, увидев пустой склад 16, он решает проверить, нет ли пустых складов с меньшими номерами. Он переходит к поиску в [1;15].

Продолжим моделирование:

• Проверка 1: Склад № 16. Пуст. Ищем первый пустой в [1;15]. Открыта 1 дверь.
• Проверка 2: Склад № 8 (середина 1-15). Заполнен. Значит, пустые склады (если они есть в этом диапазоне) находятся правее 8. Ищем в [9;15]. Открыта 2-я дверь.
• Проверка 3: Склад № 12 (середина 9-15). Заполнен. Ищем в [13;15]. Открыта 3-я дверь.
• Проверка 4: Склад № 14 (середина 13-15). Заполнен. Ищем в [15;15]. Открыта 4-я дверь.
• Проверка 5: Склад № 15. Заполнен. Ищем в [16;15]? Диапазон пуст. Здесь возникает вопрос интерпретации. Мы искали первый пустой в диапазоне [1;15]. Мы проверили все кандидаты на роль «самого левого пустого» внутри этого поддиапазона через механизм бинарного поиска. Когда мы проверили 15 и он оказался заполненным, а весь диапазон [1;15] был исследован методом половинного деления с целью найти там пустой, и ни одного пустого не нашли (все проверенные точки оказались заполненными, а промежуточные области исключались как содержащие только заполненные склады относительно найденной границы?), то вывод таков: в диапазоне [1;15] пустых складов нет. Следовательно, первый пустой склад — тот, который мы уже видели и отбросили как «не самый первый»? Нет, мы отбросили его как «не единственный кандидат», решив искать лучше слева. Когда поиск слева завершился неудачей (весь диапазон 1-15 заполнен), мы возвращаемся к выводу, что первый пустой — это 16. Однако, сколько раз физически открывалась дверь? 1. № 16 2. № 8 3. № 12 4. № 14 5. № 15 После проверки № 15 (заполнен), алгоритм должен понять, что в левой части (1-15) пустых нет. Значит, ответ — 16. Дверь № 16 была открыта первой. Нужно ли открывать её снова? В условии сказано: «Сколько дверей пришлось открыть плотнику?». Обычно в таких задачах считается количество проверок (обращений к памяти/складу). Давайте проверим альтернативную логику. Может быть, после того как выяснилось, что в [1;15] всё заполнено, плотник делает вывод, что искомый склад — 16. Он уже открывал дверь 16. Повторно открывать не нужно. Итого проверок: 5. Есть ли вариант, что проверка № 16 не считается, если мы ищем в 1-15? Нет, мы начали с 16. Рассмотрим глубину дерева поиска для N=15 элементов (диапазон 1-15). Максимальное число сравнений для бинарного поиска в массиве из 15 элементов равно ⌈log₂(15+1)⌉=4? Или ⌊log₂15⌋+1=3+1=4? Давайте посчитаем шаги для диапазона 1-15: 1. Середина 8. (1) 2. Если 8 заполнен, идем вправо 9-15. Середина 12. (2) 3. Если 12 заполнен, идем вправо 13-15. Середина 14. (3) 4. Если 14 заполнен, идем вправо 15-15. Середина 15. (4) 5. Если 15 заполнен, диапазон исчерпан. Таким образом, чтобы убедиться, что в диапазоне 1-15 нет пустых складов (при условии, что мы ищем первый пустой и знаем, что 16 пуст, но хотим проверить, нет ли раньше), нам потребовалось 4 дополнительные проверки после первой. Всего проверок: 1 (склад 16) +4 (поиск в 1-15) =5. Ответ: 5 дверей.

В условии прямо указано: «он применяет метод половинного деления». В информатике этот алгоритм также известен как бинарный поиск (binary search).

Суть метода заключается в том, что на каждом шаге область поиска сокращается ровно в два раза. Для массива из N элементов максимальное количество шагов составляет ⌈log₂N⌉ или около того, в зависимости от реализации граничных условий.