Метод решіт у грі «Бики і корови»
Вітаю. Ще восени на 2 курсі як лабораторна робота з «Теорії автоматів» викладач на ходу вигадував нам завдання, орієнтуюсь на наші побажання в оцінці. Здебільшого це були ігри. Комусь дістався хокей, комусь теніс, мені ж дісталася не така відома логічна гра «Бики і корови».
Гравець та комп'ютер загадують чотиризначні числа, використовуючи цифри від0до9. Гравці намагаються розгадати числа суперника, посилаючи йому можливі варіанти чисел, у відповідь отримуючи два числа - число«биків»та число«корів». Що це за числа такі?
- "Бики" - правильні цифри на правильних місцях. Чотири «бики» — запорука перемоги, мрія кожного фермера.
- Корови — правильні цифри на неправильних місцях.
Для розуміння наведу приклад:
Загадано число1622. Якщо ми припустимо6112, то у відповідь прийде:1 бик(четверта цифра «2» на своєму місці),2 корови(шістка та одиниця не на своїх місцях).
Оперуючи даними про «худобу» супротивника, потрібно вгадати число швидше за нього.
Перший же тривіальний алгоритм, який так і напрошується, - це перебирати набори "1111", "2222", "3333".
Наприклад, загадано те ж число1622, ми припускаємо«1111», отримуємо у відповідь«бика», потім« 2222»- отримуємо у відповідь вже2 «биків»,«3333»- порожньо,«4444»- порожньо,«5555»- порожньо,«6666»-1 бик. Далі продовжувати не будемо, оскількинабралося вже 4 бикау сумі. Залишилося знайти необхідну комбінацію. Будемо генерувати перестановки, поки не отримаємо Та-Дааам: «1226», «1262», «1226», «1262», «2» «1622» . Всі.
Очевидно, що алгоритм не дуже добрий, зате зрозумілий і не заплутався. Максимальна кількість ходів для вгадування - 10 (7890) + 24 перестановки.34- це в найгіршому випадку. Звичайно можливо перебір і перестановки всіляко оптимізувати, наприклад перебирати почергово з двох кінців - 1111, 0000, 2222, 9999. Так само оптимізувати генерацію перестановок за наявності однакових цифр прикладі — кілька разів запитуємо одне й те саме). Але не будемо цим займатися. Нехай ця стратегія буде у нас легким рівнем складності комп'ютера.
Багато я сидів на парах і грав сам із собою, намагаючись придумати якийсь свій крутий алгоритм. Але приходили лише поодинокі ідеї, з яких я не міг скласти єдиної стратегії. Почав вивчати літературу. Натрапив на статті, роду «вгадування за 7 ходів». Вони мене не залучили, оскільки там дуже багато розгалуження. Але прочитавши книгу нашого Кіровського професора (але не з нашого університету) С.М. Окулова «Програмування в алгоритмах», я знайшов опис досить простого і досить ефективного алгоритму. У ньому використовується так званий «метод решета» (прикладом може бути відоме «решето Ерастофена» – класичне завдання пошуку простих чисел). Ми розглядаємо кінцеву множину всіх можливих чисел і кожен хід виключаємо всі елементи множини, які не становлять інтересу.
Наприклад, для загаданого числа1234ми припустили5678, таотримали0 бугаїв і 0 корів, чого думати - ми виключаємо всі числа, що містять5, 6, 7, 8. Відразу можете прикинути, скільки забереться з10000.Не варто лякатися безлічі з10000елементів. За5-6ходів залишиться лише кілька чисел.
Почнемо із структур даних. Код на паскалі:
Функція, що реалізує аналіз елемента множини за значеннями змінних (bk, kr - бики та корови)
таким чином після кожного нашого ходу запускаємо решето