• Главная
  • Карта сайта
Не найдено

НОУ ІНТУЇТ | лекція | Гра "Бики і корови"

  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:

/// <summary> /// Стратегія комп'ютера /// Реалізація алгоритму бінарного пошуку /// </ summary> /// <param name = "sender"> </ param> /// <param name = "e" > </ param> private void buttonCompGuess_Click (object sender, EventArgs e) {int min_c = min; int max_c = max; int mid = (min + max) / 2; countQuestion = 0; listBoxQA.Items.Add (COMP); // Бінарний пошук while (min_c! = Max_c) {countQuestion ++; question = countQuestion.ToString () + "."; question + = "Число більше"; question + = mid + "?"; if (number> mid) {question + = "- Так!"; min_c = mid + 1; } Else {question + = "- Ні!"; max_c = mid; } Mid = (min_c + max_c) / 2; listBoxQA.Items.Add (question); } // межі інтервалу невизначеності збігаються. // Відповідь знайдена countQuestion ++; question = countQuestion.ToString () + "."; question + = "Число одно"; question + = min_c + "?"; question + = "- Так!"; textBoxResult.Text = COMP_ANSWER + number; listBoxQA.Items.Add (question); }Знайти задумане число в цій грі складніше, оскільки дозволяється задавати питання тільки одного типу "Число одно N?
В чому полягає суть гри "Задумай число"?
Яка вихідна невизначеність?
Отримавши відповідь "так" на запитання "задумане більше mid?
Число більше 75?
Число більше 88?
Число більше 81?
Число більше 84?
Число більше 82?
Число одно 83?
Новости
Провайдеры:
  • 08.09.2015

    Batyevka.NET предоставляет услуги доступа к сети Интернет на территории Соломенского района г. Киева.Наша миссия —... 
    Читать полностью

  • 08.09.2015
    IPNET

    Компания IPNET — это крупнейший оператор и технологический лидер на рынке телекоммуникаций Киева. Мы предоставляем... 
    Читать полностью

  • 08.09.2015
    Boryspil.Net

    Интернет-провайдер «Boryspil.net» начал свою работу в 2008 году и на данный момент является одним из крупнейших поставщиков... 
    Читать полностью

  • 08.09.2015
    4OKNET

    Наша компания работает в сфере телекоммуникационных услуг, а именно — предоставлении доступа в сеть интернет.Уже... 
    Читать полностью

  • 08.09.2015
    Телегруп

    ДП «Телегруп-Украина» – IT-компания с 15-летним опытом работы на рынке телекоммуникационных услуг, а также официальный... 
    Читать полностью

  • 08.09.2015
    Софтлинк

    Высокая скоростьМы являемся участником Украинского центра обмена трафиком (UA — IX) с включением 10 Гбит / сек... 
    Читать полностью