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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Бики та корови
4digits 0.4 screenshot.png
Кількість гравців 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.