Метод поділу навпіл - студопедія
Метод поділу навпіл є прекрасною стратегією пошуку, коли заздалегідь не існує причин для вибору шляхів вирішення з послідовно організованої безлічі. Припустимо, що через засмічення водопроводу у вас на кухні з крана не тече вода. Засмічення сталося десь між місцем приєднання ваших труб до магістрального водопроводу і кухонним краном. Як ви знайдете місце засмічення в трубі, зробивши при цьому мінімальну кількість отворів?
У цьому випадку рішення (місце освіти пробки) треба шукати по всій довжині труби. Найкращим способом вирішення такого завдання є метод поділу навпіл. Оскільки завдання передбачає, що ви будете свердлити трубу в кожному обраному місці, треба максимально ефективно вибирати ці місця. Почніть з середини шляху між відведенням від головної труби і кухонним краном. Якщо ви виявите, що до цього місця вода вільно надходить, то місце засмічення труби знаходиться десь між цією точкою і вашої раковиною. Після цього розбийте навпіл вже цю ділянку. Якщо вода тече і тут, то вам стане ясно, що пробка знаходиться десь ближче до раковини, і вам слід розбити навпіл залишився ділянку.
Припустимо, в результаті першої спроби ви виявили, що вода не доходить до просвердленого місця. Тоді засмічення має бути між головною трубою і цією точкою. Наступний пошук ви повинні вести саме на цій ділянці. Таким способом ви будете продовжувати пошук, поки місце засмічення трубопроводу не буде знайдено. Це дуже зручний спосіб розв'язання подібних задач - наприклад, при вирішенні завдання пошуку місця розриву електропроводки в вашому домі чи автомобілі.
Ви можете скористатися методом ділення навпіл в грі під назвою «Вгадай вік» (я її сама придумала). Ваші друзі можуть «прикинутися» людьми будь-якого віку. Ви можете вгадати вік будь-якого з них від 0 до 100 не більше ніж за сім висловлених припущень. Як це зробити? Почніть з віку, лежачого посередині між 0 і 100 - тобто з 50. Гравець повинен буде відповісти, старше або молодше 50 років задуманий вік. Відповідь буде «старше» або «молодший». Покладемо, він відповідає, що «молодший». Який вік ви назвете наступним? Вам слід вибрати вік посередині між 0 і 50 - тобто 25. Припустимо, тепер він відповість «старше». Ваша третя гіпотеза повинна лежати посередині між 25 і 50. Оскільки ми маємо справу лише з цілими числами, то наступним має бути названо число 38. Якщо тепер він відповість «молодший», ви називаєте 32, т. Е. Число, яке лежить посередині між 25 і 38. Якщо відповідь «старше», ви вибираєте 35 (середина між 32 і 38). Якщо відповідь «молодший», ви називаєте 33. Тепер ви точно знаєте, що гравець загадав собі вік або 33, або 34. Таким чином, будь-який вік може бути визначений не більше ніж за сім висловлених припущень. Спробуйте зробити це з деякими зі своїх друзів. Це буде для вас хорошою практикою використання стратегії розподілу навпіл. Згадуйте про цю стратегію в ситуаціях, коли завдання має кілька можливих рівноймовірно рішень.