Бики та корови

Бики та корови (також відома як Корови та бики, Свині та бики) — логічна гра, призначена для двох гравців, в основі якої закладено вгадування числа, задуманого суперником. З початку розвитку комп'ютерних технологій з'явилися варіації гри поодинці, коли задумане число вгадує або гравець, або комп'ютер. Для гри удвох достатньо мати папір та ручку. Крім цього, гра можлива при використанні функції багатокористувацької гри на відстані.

Бики та корови
Кількість гравців 2
Час гри 5-30 хвилин
Вплив випадковості Середній
Необхідні здібності Вміння рахувати, Пам'ять

Правила гри

Настільний варіант гри Mastermind[1] для 4 місць та 6 кольорів

Правила гри можуть залежати від типу вгадуваної послідовності — це можуть бути числа, слова, кольори, піктограми тощо. В класичній версії гра відбувається між двома гравцями. Також можуть грати дві команди по декілька гравців (з членами команди обговорюють свою стратегію, перш ніж вибрати крок).

Версія з числами

В чисельній версії опонент задумує чотиризначне число (можливі варіанти з використанням числа будь-якої довжини). Всі цифри повинні бути різні. Тоді ж, в свою чергу, гравці намагаються вгадати число противника. Гравець пропонує свій варіант, а опонент дає кількість збігів. Якщо збігається цифра в її правильній позиції, то це є «бик», якщо не в своїй позиції — це «корова».

Наприклад:

   Задумане число: 4271
   Спроба суперника: 1234
   Відповідь: 1 бика і 2 корови. (Бик "2", корови "4" і "1".)

Перший, хто запропонує супернику загадане число (4 бики) виграє гру.

Версія з словами

У словесну версію зазвичай грають в усній формі. Так само, як і в числовій версії, опонент задумує слово із чотирьох (або іншої кількості) літер. Це повинно бути реальне слово із якої-небудь мови світу.

   Задумане слово: СІНО
   Спроба суперника: СНІГ
   Відповідь: 1 бика і 2 корови. (Бик "С", корови "Н" та "І".)

Версія з кольорами

У грі Mastermind[1] загадується послідовність з чотирьох кольорових фішок, при чому кольори можуть повторюватися. В ускладненому варіанті використовується більша кількість фішок.

Алгоритм

У загальному випадку кількість варіантів для k-значного числа в N-річній системі числення без повторень, буде дорівнювати числу розміщень: .

У разі варіанта з повтореннями кількість варіантів дорівнюватиме .

Найоптимальнішим алгоритмом вгадування числа є перебір чисел з відкиданням невідповідних варіантів. У зв'язку з тим, що можливих варіантів небагато і схема перебору елементарно реалізується, комп'ютер грає набагато сильніше людини. При чому, чим більше цифр (літер, фішок) у послідовності, тим більша різниця у силі гри людини та комп'ютера.

Наприклад, алгоритм для відгадування чотиризначного числа без повторень:

  1. Побудувати множину S із варіантів.
  2. Запропонувати будь-який варіант із множини.
  3. Отримати кількість «биків» та «корів»
  4. Виключити із множини S елементи, які мають іншу кількість «биків» та «корів» із запропонованим варіантом.
  5. Порахувати кількість елементів у множині.
  6. Повторювати алгоритм, починаючи з пункту 2, поки в множині не залишиться один елемент або не буде отримано 4 «бики».

Якщо після пункту 4 отриману порожню множину S, то гравець допустив помилку при підрахунку «биків» та «корів».

Реалізації

Існує безліч варіантів електронної реалізації гри, в тому числі для комп'ютерів та мобільних телефонів.

  • Fallout 3, Fallout New Vegas, та Fallout 4 — за допомогою міні-версії цієї гри здійснюється хакерський злом комп'ютера.
  • Sleeping Dogs включає в себе версію гри (з цифрами від 1 до 9) для злому камер безпеки.
  • Jotto42[2] — подібна гра зі словами
  • Mastermind[1] — подібна гра з кольоровими фішками.

Примітки

Посилання

Джерела

  • Е. Гик. Быки и коровы. «Наука и жизнь», № 2, 1978, с. 150—151; № 8, 1978, с. 142—143.
  • Чарльз Уэзерелл. Этюды по программированию, Великий комбинатор. М.: 1982, с. 140.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.