1. Дивитися лекцію на: ІНТУЇТ | youtube.com
2. Алгоритм бінарного пошуку
3. Як грає комп'ютер?

Анотація: Гра "Бики і корови" На цьому уроці триває розгляд попередньої гри "Задумай число". Обговорюється алгоритм бінарного пошуку, що дає оптимальну стратегію пошуку задуманого числа. Наводиться реалізація цієї стратегії. В інтерфейсі гри з'являється нова кнопка "Комп'ютер, відгадай число". Розглядається проект, який реалізує нову гру "Бики і корови", де також потрібно відгадати число, задумане комп'ютером. Знайти задумане число в цій грі складніше, оскільки дозволяється задавати питання тільки одного типу "Число одно N?" З технічних причин не відбувся запис наступної лекції, де розглядалася варіація проекту "Бики і корови", в якій задумана комбінація випадковим чином вибиралася з безлічі, що включає 12 картинок. У тексті, що супроводжує даний урок, дається короткий опис цього проекту.

Дивитися лекцію на: ІНТУЇТ | youtube.com

Якщо проблеми з відео, натисніть вище посилання youtube

Урок починається з розбору домашнього завдання, виконаного школярем. У домашній роботі потрібно додати нові кнопки в інтерфейс гри і написати в коді відповідні обробники події. Школяр додав дві кнопки "Більше або дорівнює" і "Менше або дорівнює". Коректно написав відповідні обробники події. Хоча відповідь на поставлене запитання формувався не цілком точно, запропоноване рішення заслуговує гарної оцінки. Неточності відповіді легко переборні.

Коли школярі, граючи в гру, відгадували число, задумане комп'ютером, то, як правило, отримували звання "магістр гри". Це дозволило на інтуїтивному рівні зрозуміти суть одного з класичних алгоритмів пошуку даних в упорядкованому безлічі - алгоритму дихотомії або бінарного пошуку, заради вивчення якого і була написана ця гра.

В чому полягає суть гри "Задумай число"? Комп'ютер задумує число з деякого інтервалу [min, max]. Межі інтервалу повідомляються гравцеві. У гравця є можливість вибрати певну кількість N з даного інтервалу і задати комп'ютеру питання одного з трьох типів: "число N більше задуманого", "число N менше задуманого", "число N одно задуманому". На кожне питання комп'ютер відповідає "так", якщо твердження справедливе, і "немає" в іншому випадку. Щоб стати магістром гри потрібно задати не більше K питань, де K залежить від інтервалу [min, max].

Оптимальна стратегія гри визначається алгоритмом бінарного пошуку, який також називають алгоритмом дихотомії або шляхом розподілу навпіл. Розглянемо його докладніше.

Алгоритм бінарного пошуку

Суть даного алгоритму розглянемо на прикладі пошуку задуманого числа в заданому інтервалі [min, max]. Яка вихідна невизначеність? У заданому інтервалі знаходиться max - min + 1 число. Так в інтервалі [0,100] знаходиться сто одне число і задумане число може бути будь-яким з них. Так що невизначеність дорівнює числу чисел в даному інтервалі. Як задати питання так, щоб максимально можливо зменшити невизначеність. Серединою інтервалу є число mid, рівне (max - min) / 2, в нашому прикладі - це число 50. Поставивши запитання "задумане число більше (менше) mid", при будь-якій відповіді невизначеність скорочується вдвічі. Отримавши відповідь "так" на запитання "задумане більше mid?" Значення нижньої межі інтервалу min змінюється на число mid + 1. В іншому випадку змінюється верхня межа max на значення mid. З кожним питанням інтервал скорочується вдвічі. Коли інтервал скорочується до одного числа, то питання на рівність гарантовано дає задумане число. Загальна кількість питань, яке слід задати, так само округлений в більшу сторону значенням функції Log (N) - бінарного алгоритму числа N, де N - вихідна невизначеність, число чисел в інтервалі.

Розглянемо приклад. Задумано число 83 в інтервалі [0, 100]. Оптимальне число питань, що дозволяє відгадати задумане число одно Log 101, округленому до найближчого цілого, що дає число 7. Ось послідовність з 7-і питань, що дозволяє відгадати задумане:

1. Число більше 50? - Так.
2. Число більше 75? - Так.
3. Число більше 88? - Ні.
4. Число більше 81? - Так.
5. Число більше 84? - Ні.
6. Число більше 82? - Так.
7. Число одно 83? - Так.

Алгоритм бінарного пошуку широко застосовується в самих різних прикладних задачах, - усюди, де потрібно знайти елемент в відсортованому безлічі, над елементами якого визначена операція порівняння на "більше", "менше".

Як грає комп'ютер?

Комп'ютер, звичайно ж, "знає" оптимальну стратегію і тому завжди досягає звання "Магістр гри" будь-якого рівня. У наводиться варіанті стратегії використовується питання типу "Число більше". З кожним питанням інтервал невизначеності скорочується вдвічі, поки не буде містити рівно один елемент, який і є задуманим числом. Стратегія комп'ютера визначається розібраним вище методом бінарного пошуку. Так що обробник події Click командної кнопки "Комп'ютер, відгадай число" представляє собою реалізацію алгоритму бінарного пошуку, доповнену висновком відповідних повідомлень. Ось як виглядає код обробника події Click: