Метод деления пополам

Метод деления пополам является прекрасной стратегией поиска, когда заранее не существует причин для выбора путей решения из последовательно организованного множества. Предположим, что из-за засорения водопровода у вас на кухне из крана не течет вода. Засорение произошло где-то между местом подсоединения ваших труб к магистральному водопроводу и кухонным краном. Как вы найдете место засорения в трубе, сделав при этом минимальное количество отверстий?

В этом случае решение (место образования пробки) надо искать по всей длине трубы. Наилучшим способом решения такой задачи является метод деления пополам. Поскольку задача предполагает, что вы будете сверлить трубу в каждом выбранном месте, надо максимально эффективно выбирать эти места. Начните с середины пути между отводом от главной трубы и кухонным краном. Если вы обнаружите, что до этого места вода свободно поступает, то место засорения трубы находится где-то между этой точкой и вашей раковиной. После этого разбейте пополам уже этот участок. Если вода течет и здесь, то вам станет ясно, что пробка находится где-то ближе к раковине, и вам следует разбить пополам оставшийся участок.

Допустим, в результате первой попытки вы обнаружили, что вода не доходит до просверленного места. Тогда засорение должно быть между главной трубой и этой точкой. Следующий поиск вы должны вести именно на этом участке. Таким способом вы будете продолжать поиск, пока место засорения трубопровода не будет найдено. Это очень удобный метод решения подобных задач – например, при решении задачи поиска места разрыва электропроводки в вашем доме или автомобиле.

Вы можете воспользоваться методом деления пополам в игре под названием «Угадай возраст» (я ее сама придумала). Ваши друзья могут «прикинуться» людьми любого возраста. Вы можете угадать возраст любого из них от 0 до 100 не более чем за семь высказанных догадок. Как это проделать? Начните с возраста, лежащего посередине между 0 и 100 – т.е. с 50. Игрок должен будет ответить, старше или моложе 50 лет задуманный возраст. Ответ будет «старше» или «моложе». Положим, он отвечает, что «моложе». Какой возраст вы назовете следующим? Вам следует выбрать возраст посередине между 0 и 50 – т.е. 25. Предположим, теперь он ответит «старше». Ваша третья догадка должна лежать посередине между 25 и 50. Поскольку мы имеем дело только с целыми числами, то следующим должно быть названо число 38. Если теперь он ответит «моложе», вы называете 32, т. е. число, лежащее посередине между 25 и 38. Если ответ «старше», вы выбираете 35 (середина между 32 и 38). Если ответ «моложе», вы называете 33. Теперь вы точно знаете, что игрок загадал себе возраст либо 33, либо 34. Таким образом, любой возраст может быть определен не более чем за семь высказанных предположений. Попробуйте проделать это с некоторыми из своих друзей. Это будет для вас хорошей практикой использования стратегии деления пополам. Вспоминайте об этой стратегии в ситуациях, когда задача имеет несколько возможных равновероятных решений.

Оглавление