Бики і корови олімпіада плюс. Розробка оптимальної стратегії гри «Бики і корови» на основі теорії інформації. Дивитися що таке "Бики і корови" в інших словниках
Бики і корови - логічна гра для двох гравців. Для неї достатньо мати листок паперу і ручку, вільний час і трохи везіння. Як правило, такий час знаходиться у школярів і студентів. Але мені, вашому покірному слузі, не довелось в свої роки дізнатися цю забаву. Хоча чому б не розім'яти своє сіра речовина на дозвіллі? Це непогане тренування для розуму, що не вимагає сильного напруги, і як розвага цілком себе виправдовує.
У своєму класичному варіанті правила дуже прості і не вибагливі. Грають дві людини, кожен загадує в таємниці від опонента чотири цифри без повторень. Наприклад, це може бути число 0834. Нуль є також цифрою і цілком може бути на першому місці.
Далі гравці по черзі роблять ходи, тобто намагаються вгадати задумане противником число. Але питати вони зобов'язані так само у вигляді чотиризначного числа. Наприклад нас запитають: "Твоє число 3094?". У відповідь же ми повинні повідомити кількість биків і корів. Бик - це цифра, яка є в нашому загаданном числі і знаходиться на тій же позиції. А корова - це цифра, яка так само є в нашому числі, але знаходиться не на своєму місці. У нашому випадку отримуємо дві корови, це цифри 3 і 0, і один бик, це 4. Тепер будемо питати ми, і так далі, до тих пір, поки хтось не розгадає повністю число. Тобто у відповіді він отримає чотири бика. На зображенні показаний приклад гри. Часу на одну партію потрібно зовсім небагато. На практиці зазвичай потрібно від 5 до 8 ходів, але є унікуми, які примудряються і за три ходи перемогти. Звичайно в такому успіху є чимала частка везіння.
На нашому сайті Ви можете грати в "бики і корови" як проти комп'ютера, так і онлайн з живим противником. Внизу ігрової кімнати для Вашої зручності є ігровий чат, в якому можна підібрати собі противника для гри по мережі, або запитати ради. Так само якщо у Вас є зауваження по реалізації нашої гри, пропозиції щодо її поліпшення або розвитку - то пишіть нам. Можна писати як на форумі, так і нам на пошту [Email protected]сайт.
різновиди гри
Варіантів гри безліч:
- 1. За типом вгадується послідовності - це може бути число. У класиці - це чотиризначне без повторень, що складається з цифр від 0 до 9. Так само може збільшуватися кількість цифр в числі, можливість їх повторення. Як послідовності можуть використовуватися колір, яка-небудь криптограма, слово.
- 2. За типом самої гри. В епоху комп'ютерів з'явилася можливість грати одному. Коли людина вгадує число, задумане комп'ютером, або проти комп'ютера. Але машину важко перемогти, тут більше питання правильно закладеного алгоритму в неї. Гравці грають в класичний варіант, але знаходяться на значній відстані один від одного. Гравці вгадують по черзі число, яке задумав комп'ютер - тут можливі варіанти як так званого гарячого стільця, коли опоненти знаходяться поруч і грають за одним комп'ютером, так і віддалено.
На даний момент реалізований тільки класичний варіант гри. Якщо у Вас є ідеї, який варіант биків і корів повинен з'явитися на нашому сайті, то поділіться ними з нами.
анотація: Гра "Бики і корови" На цьому уроці триває розгляд попередньої гри "Задумай число". Обговорюється алгоритм бінарного пошуку, що дає оптимальну стратегію пошуку задуманого числа. Наводиться реалізація цієї стратегії. В інтерфейсі гри з'являється нова кнопка "Комп'ютер, відгадай число". Розглядається проект, який реалізує нову гру "Бики і корови", де також потрібно відгадати число, задумане комп'ютером. Знайти задумане число в цій грі складніше, оскільки дозволяється задавати питання тільки одного типу "Число одно N?" З технічних причин не відбувся запис наступної лекції, де розглядалася варіація проекту "Бики і корови", в якій задумана комбінація випадковим чином вибиралася з безлічі, що включає 12 картинок. У тексті, що супроводжує даний урок, дається короткий опис цього проекту.
Урок починається з розбору домашнього завдання, виконаного школярем. У домашній роботі потрібно додати нові кнопки в інтерфейс гри і написати в коді відповідні обробники події. Школяр додав дві кнопки "Більше або дорівнює" і "Менше або дорівнює". Коректно написав відповідні обробники події. Хоча відповідь на поставлене запитання формувався не цілком точно, запропоноване рішення заслуговує гарної оцінки. Неточності відповіді легко переборні.
Коли школярі, граючи в гру, відгадували число, задумане комп'ютером, то, як правило, отримували звання "магістр гри". Це дозволило на інтуїтивному рівні зрозуміти суть одного з класичних алгоритмів пошуку даних в упорядкованому безлічі - алгоритму дихотомії або бінарного пошуку, заради вивчення якого і була написана ця гра.
В чому полягає суть гри "Задумай число"? Комп'ютер задумує число з деякого інтервалу. Межі інтервалу повідомляються гравцеві. У гравця є можливість вибрати певну кількість N з даного інтервалу і задати комп'ютеру питання одного з трьох типів: "число N більше задуманого", "число N менше задуманого", "число N одно задуманому". На кожне питання комп'ютер відповідає "так", якщо твердження справедливе, і "немає" в іншому випадку. Щоб стати магістром гри потрібно задати не більше K питань, де K залежить від інтервалу.
оптимальна стратегія гри визначається алгоритмом бінарного пошуку, який також називають алгоритмом дихотомії або шляхом розподілу навпіл. Розглянемо його докладніше.
Алгоритм бінарного пошуку
Суть даного алгоритму розглянемо на прикладі пошуку задуманого числа в заданому інтервалі. Яка вихідна невизначеність? У заданому інтервалі знаходиться max - min + 1 число. Так в інтервалі знаходиться сто одне число і задумане число може бути будь-яким з них. Так що невизначеність дорівнює числу чисел в даному інтервалі. Як задати питання так, щоб максимально можливо зменшити невизначеність. Серединою інтервалу є число mid, рівне (max - min) / 2, в нашому прикладі - це число 50. Поставивши запитання "задумане число більше (менше) mid", при будь-якій відповіді невизначеність скорочується вдвічі. Отримавши відповідь "так" на запитання "задумане більше mid?" Значення нижньої межі інтервалу min змінюється на число mid + 1. В іншому випадку змінюється верхня межа max на значення mid. З кожним питанням інтервал скорочується вдвічі. Коли інтервал скорочується до одного числа, то питання на рівність гарантовано дає задумане число. Загальна кількість питань, яке слід задати, так само округлений в більшу сторону значенням функції Log (N) - бінарного алгоритму числа N, де N - вихідна невизначеність, число чисел в інтервалі.
Розглянемо приклад. Задумано число 83 в інтервалі. Оптимальне число питань, що дозволяє відгадати задумане число одно Log 101, округленому до найближчого цілого, що дає число 7. Ось послідовність з 7-і питань, що дозволяє відгадати задумане:
- Число більше 50? - Так.
- Число більше 75? - Так.
- Число більше 88? - Ні.
- Число більше 81? - Так.
- Число більше 84? - Ні.
- Число більше 82? - Так.
- Число одно 83? - Так.
Алгоритм бінарного пошуку широко застосовується в самих різних прикладних задачах, - усюди, де потрібно знайти елемент в відсортованому безлічі, над елементами якого визначена операція порівняння на "більше", "менше".
Як грає комп'ютер?
Комп'ютер, звичайно ж, "знає" оптимальну стратегію і тому завжди досягає звання "Магістр гри" будь-якого рівня. У наводиться варіанті стратегії використовується питання типу "Число більше". З кожним питанням інтервал невизначеності скорочується вдвічі, поки не буде містити рівно один елемент, який і є задуманим числом. Стратегія комп'ютера визначається розібраним вище методом бінарного пошуку. Так що обробник події Click командної кнопки "Комп'ютер, відгадай число" представляє собою реалізацію алгоритму бінарного пошуку, доповнену висновком відповідних повідомлень. Ось як виглядає код обробника події Click:
///
Добрий день.
Ще восени на 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», «Тисячі шістсот двадцять дві» . Усе.
Очевидно, що алгоритм не дуже хороший, зате зрозумілий і не заплутатися. Максимальне число ходів для вгадування - 10 ( «7890») + 24 перестановки. 34 - це в найгіршому випадку. Звичайно можливо перебір і перестановки всіляко оптимізувати, наприклад перебирати по черзі з двох кінців - «1111», «0000», «2222», «9999» ... так само оптимізувати генерацію перестановок при наявності однакових цифр (як у нашому прикладі - кілька разів запитуємо одне і те ж).
Але не будемо цим займатися. Нехай дана стратегія буде у нас легким рівнем складності комп'ютера.
Багато я сидів на парах і грав сам із собою, намагаючись придумати якийсь свій крутий алгоритм. Але приходили тільки поодинокі ідеї, з якою я не міг скласти єдиної стратегії. Почав вивчати літературу. Натрапив на статті, роду «вгадування за 7 ходів». Вони мене не залучили, оскільки там дуже багато розгалуження. Але прочитавши книгу нашого Кіровського професора (але не з нашого університету) С.М. Окулова «Програмування в алгоритмах», Я знайшов опис досить простого і досить ефективного алгоритму. У ньому використовується так званий «Метод решета» (Прикладом може служити відоме «Решето Ерастофен» - класична задача пошуку простих чисел). Ми розглядаємо кінцеве безліч всіх можливих чисел і кожен хід виключаємо всі елементи множини, що не представляють інтересу.
Наприклад, для задуманого числа 1234 ми припустили 5678 , І отримали 0 биків і 0 корів, Чого думати - ми виключаємо всі числа, що містять 5, 6, 7, 8 . Відразу можете прикинути, скільки відніметься з 10000. Не варто лякатися безлічі з 10000 елементів. за 5-6 ходів залишиться всього кілька чисел.
Почнемо зі структур даних. Код на Паскалі:
Const Pmax \u003d 10000; Type Post \u003d string; Var A: array of Post; // безліч B: array of boolean; // масив прапорців, 1 - значить підходить, 0 - виключено
ініціалізація:
T: \u003d 1; for i: \u003d 0 to 9 do for j: \u003d 0 to 9 do for k: \u003d 0 to 9 do for l: \u003d 0 to 9 do begin a [t]: \u003d inttostr (i) + inttostr (j) + inttostr (k) + inttostr (l); // формуємо безліч inc (t); end; for i: \u003d 1 to pmax do b [i]: \u003d true; // за замовчуванням всі числа підходять
Функція, що реалізує аналіз елемента безлічі за значеннями змінних (bk, kr - бики і корови)
Function pr (a, b: post; bk, kr: integer): boolean; // b - наш хід, a- елемент "тестованого" безлічі var i, x: integer; begin x: \u003d 0; for i: \u003d 1 to 4 do // перевірка по бикам if a [i] \u003d b [i] then inc (x); if x<>bk then begin pr: \u003d false; exit; end; x: \u003d 0; for i: \u003d 1 to 4 do // перевірка по коровам if (a [i]<>b [i]) and (pos (b [i], a)<>0) then inc (x); if x Таким чином після кожного нашого ходу запускаємо решето For i: \u003d 1 to Pmax do if b [i] and not pr (a [i], hod, bk, kr) then b [i]: \u003d false; На закінчення можна сказати, що алгоритм витратний до пам'яті і в порівнянні зі стандартними алгоритмами буде думати «довше», але наскільки ж він простіше і цілком оптимізується. Добрий день. Перший же тривіальний алгоритм, який так і напрошується, - це перебирати набори «1111», «2222», «3333» ... до тих пір, поки не буде отримано повний набір, а потім генерувати переміщення цього набору. Багато я сидів на парах і грав сам із собою, намагаючись придумати якийсь свій крутий алгоритм. Але приходили тільки поодинокі ідеї, з якою я не міг скласти єдиної стратегії. Почав вивчати літературу. Натрапив на статті, роду «вгадування за 7 ходів». Вони мене не залучили, оскільки там дуже багато розгалуження. Але прочитавши книгу нашого Кіровського професора (але не з нашого університету) С.М. Окулова «Програмування в алгоритмах», Я знайшов опис досить простого і досить ефективного алгоритму. У ньому використовується так званий «Метод решета» (Прикладом може служити відоме «Решето Ерастофен» - класична задача пошуку простих чисел). Ми розглядаємо кінцеве безліч всіх можливих чисел і кожен хід виключаємо всі елементи множини, що не представляють інтересу. Const Pmax \u003d 10000; Type Post \u003d string; Var A: array of Post; // безліч B: array of boolean; // масив прапорців, 1 - значить підходить, 0 - виключено ініціалізація: T: \u003d 1; for i: \u003d 0 to 9 do for j: \u003d 0 to 9 do for k: \u003d 0 to 9 do for l: \u003d 0 to 9 do begin a [t]: \u003d inttostr (i) + inttostr (j) + inttostr (k) + inttostr (l); // формуємо безліч inc (t); end; for i: \u003d 1 to pmax do b [i]: \u003d true; // за замовчуванням всі числа підходять Функція, що реалізує аналіз елемента безлічі за значеннями змінних (bk, kr - бики і корови) Function pr (a, b: post; bk, kr: integer): boolean; // b - наш хід, a- елемент "тестованого" безлічі var i, x: integer; begin x: \u003d 0; for i: \u003d 1 to 4 do // перевірка по бикам if a [i] \u003d b [i] then inc (x); if x<>bk then begin pr: \u003d false; exit; end; x: \u003d 0; for i: \u003d 1 to 4 do // перевірка по коровам if (a [i]<>b [i]) and (pos (b [i], a)<>0) then inc (x); if x Таким чином після кожного нашого ходу запускаємо решето For i: \u003d 1 to Pmax do if b [i] and not pr (a [i], hod, bk, kr) then b [i]: \u003d false; На закінчення можна сказати, що алгоритм витратний до пам'яті і в порівнянні зі стандартними алгоритмами буде думати «довше», але наскільки ж він простіше і цілком оптимізується. Коли я вступив в інституті, дуже популярною була гра «Бики і корови». Так співпало, що в цей же час я прочитав математичну новелу Альфреда Рен `ї« Щоденник. - Записки студента з теорії інформації ». Завдяки цій статті я познайомився с. І у мене народилася ідея, як поліпшити свої показники в «Биках і коровах», спираючись на нові знання. Коротко нагадаю правила.Грають двоє. Кожен задумує і записує таємне 4-значний номер з неповторяющимися цифрами (першої може бути і нуль). Гравець, який починає гру за жеребом, робить спробу відгадати число. Спроба - це 4-значний номер з неповторяющимися цифрами, повідомляється противнику у вигляді питання. Противник каже у відповідь, скільки цифр вгадано з збігом їх позицій в таємному числі і скільки вгадано без збігу. Наприклад: задумано таємне число 3219; спроба (питання) 2310; результат (відповідь): один «бик» (цифра 1 з питання входить в таємне число і стоїть на своєму місці) і дві «корови» (цифри 2 і 3 з питання входять в таємне число, але коштують не на своєму місці). Відповідь повідомляється у вигляді 2-значного числа. У нашому прикладі відповідь - 12 (один «бик», дві «корови»). Гравці роблять спроби по черзі. Перемагає той, хто першим отримає на своє питання відповідь 40. Завантажити замітку в форматі або, приклади в форматі, приклад в форматі zip (всередині Excel-файл на 57МВ). Ось які ідеї теорії інформації мені здалися корисними для поліпшення показників в грі (див.): Для кращого розуміння матеріалу корисно також відкрити Excel-файл. 1. Таємне число можна задумати 10 * 9 * 8 * 7 \u003d 5040 способами (на першому місці може стояти будь-яка з 10 цифр, на другому - будь-яка з 9 залишилися і т.д.). Для того, щоб сформувати масив допустимих чисел я використовував прості алгоритми в Excelе (див. Листи «Подг1» і «Подг2»). Оскільки ймовірність бути задуманим будь-якого з 5040 чисел однакова, невизначеність (Н) обчислюється за формулою Хартлі: Н \u003d log 2 N. Перед початком гри невизначеність становить log 2 5040 \u003d 12,30 біт інформації. 2. Зрозуміло, що перше питання може бути будь-яким, наприклад, 0123. На нього можливі 14 відповідей (див. Також лист «Вопрос1» Excel-файлу): Тут: р - вірогідність відповіді, Н - невизначеність, що залишилася після відповідного відповіді, h - кількість інформації, отримане, якщо реалізувався той чи інший відповідь. Найбільш ймовірний відповідь - 01, що означає, що з питання в таємне число входить лише одна цифра, причому коштує вона не на своєму місці. Відповідь 01 має на увазі, що задуманим може бути одне з 1440 чисел, тобто невизначеність, що залишилася після цієї відповіді, становить log 2 1440 \u003d 10,49 біт, а інформація, отримана при такому відповіді 12,30 - 10,49 \u003d 1,81 біт. Відповідь 40 дає 12,30 біт інформації, а невизначеності після нього не залишається J Оскільки ймовірності відповідей різні, кількість інформації, що міститься в питанні визначається за формулою Шеннона: Н (x) \u003d p 1 log 2 (1 / p 1) + p 2 log 2 (1 / p 2) + ... + p N log 2 (1 / p N). Перше питання приносить 2,77 біт інформації. 3. При виборі другого питання слід керуватися трьома ідеями сформульованими вище. На практиці це означає, що питання має допускати відповідь 40. Правило формування другого питання.Нехай на перше питання (0123) ми отримали відповідь 01. Для другого питання візьмемо одну цифру з першого питання, поставимо її на нове місце і додамо три нові цифри. Отримаємо, наприклад, 4561. Якщо на вопрос1 був отриманий, наприклад, відповідь 11, треба взяти дві цифри з першого питання, одну залишити на своєму місці, другу поставити на нове місце, і додати дві нові цифри; наприклад, 0435. На вопрос2 4561 також можливі 14 відповідей (див. Лист «Вопрос2»): Обраний нами друге питання приніс 2,86 біта інформації. Подивимося, скільки інформації дадуть інші другі питання. Для цих цілей я створив окремий файл «Неоптимальний другий вопрос.xlsx» (він «важить» 58МВ, тому будьте з ним акуратніше :)). Друге питання може бути одним з 5040 можливих чисел (в тому числі і повторення першого питання). В результаті цього дослідження я отримав кількість інформації, яку дають ті чи інші другі питання (нагадаю, що аналіз зроблений в припущенні, що перше питання 0123 дав відповідь 01). Наприклад, вопрос2 - 0123 дає нуль бітів інформації, так як на нього можливий тільки один відповідь 01, а (для N \u003d 1) log 2 1 \u003d 0. Вопрос2 0132 дає 0,65 біт інформації, вопрос2 0148 - 2,53 біта інформації . Максимальна кількість інформації дають 1440 друге питань, сформованих за вище описаним правилом. Результати дослідження я переніс на лист «Різні вопроси2» файлу «Бики-корови.xlsx» і далі буду говорити тільки про цей файл. Як я вже сказав, максимальна кількість інформації - 2,859 - буде отримано на вопрос2, підготовлений таким чином: треба взяти одну цифру з першого питання, поставити її на нове місце і додати три нові цифри: Видно, що ще 180 питань дають майже стільки ж інформації - 2,774 біта. Така кількість інформації буде отримано при відповіді, наприклад, на питання тисяча сорок п'ять (див. Лист «Вопрос2неопт»). Але це питання не може дати відповіді 40! Тобто, питання підготовлений з порушенням сформульованого правила. Наскільки велика різниця в інформації між 2,859 і 2,774 біта !? На перший погляд вона не виглядає великою. З іншого боку, при найсприятливішому відповіді на вопрос2 4561 (01) залишиться 378 варіантів таємного числа, а при найбільш несприятливому відповіді на вопрос2 1045 (також 01) - 408 варіантів. На 8% більше! Це і є ціна неоптимального питання. 4. При підготовці третього (і наступних) питань я керуюся таким мнемонічним правилом. Необхідно скласти агрегований таблицю всіх можливих таємних чисел, що задовольняють відповідей на попередні питання. Після цього сформувати вопрос3, використовуючи ту частину цієї таблиці, яка містить більше варіантів (оцінку виробляю «на око»). Трохи заплутано? Давайте розглянемо два приклади. Приклад 1. Перший варіант: входить одиниця, тоді не входять, ні 023, ні 456; тобто входять, що не використалися в перших двох питаннях, цифри - 789. Отримуємо набір цифр таємного числа 1789 (порядок їх розташування будь-, що задовольняє відповідей на перші два питання). Варіантів, що відповідають цій набору, 12. Другий варіант: одиниця не входить, тоді входить одна цифра з 023, одна - з 456, і дві - з 789. Записую я це так: Орієнтовна кількість варіантів набору цифр дорівнює 3 (одна з 023) * 3 (одна з 456) * 3 (дві з 789) \u003d 27. А з урахуванням місць розташування цифр варіантів істотно більше 100. Для вопроса3 беремо одну цифру з 023, одну з 456, дві з 789. Маємо цифри так, щоб не було збігів місць розташування з вопросом1 і вопросом2. Більш того, в своєму розпорядженні цифри, які раніше вже зустрічалися (4 і 2) на абсолютно нових місцях, тобто на 2-м або 4-м. Наприклад, вопрос3 7482 краще, ніж 2784. Так як в першому випадку 4-ка і 2-ка стоять на місцях, які в вопросе1 і вопрос2 вони не займали. У той же час, в вопросе3 2784 цифра 2 стоїть на місці 4-ки з вопроса2 (див. Лист «Вопрос3»). Відповідь на вопрос3 4782 містить 2,958 біт інформації, а відповідь на питання 3 2784 - «тільки» 2,955. Приклад 2. Перші два питання і відповіді були наступними: Перший варіант: входять 13, тоді не входять, ні 02, ні 45, а з решти цифр входять дві: Кількість таємних числі в варіанте1 - 48. Другий варіант: входить одна цифра з 13, тоді входить одна - з 02, одна - з 45, і одна - з 6789: Орієнтовна кількість таємних чисел в варіанте2 - понад 100. Третій варіант: чи не входять 13, тоді входять і 02, і 45: 0245. Кількість таємних чисел в варіанте3 - 8. 5. Коли таємних чисел залишається мало (від 4 до 10 ... 20), я переходжу на повний перебір всіх можливих варіантів. Грайте з алгоритмом, побудованим на основі теорії інформації, і вигравайте! Нурим Кенжебек написав програму, що дозволяє грати з комп'ютером. Програма працює під Windows 7, 8, 8.1 з встановленим Framework 4.5. Гра мені дуже сподобалася, але алгоритм явно далекий від оптимального. Я зіграв тричі і всі три рази виграв. Завантажити програму в форматі. http://slovesnov.narod.ru/articles/bullcow.pdf . Сказати по правді, мені не вдалося її подужати 🙂 Але згадок теорії інформації при побіжному перегляді я в ній не знайшов ...
Ну ось і все, зовсім не складно. Перша моя стаття, судити строго.
Ще восени на 2 курсі в якості лабораторної роботи по «Теорії автоматів» викладач на ходу вигадував нам завдання, оріентіруяюсь на наші побажання в горизонтальній осі. В основному це були ігри. Кому-то дістався хокей, кому-то теніс, мені ж дісталася не настільки відома логічна гра «Бики і корови».
Потрібно було реалізувати хоч якесь обґрунтоване поведінку комп'ютера в грі з людиною. Але я пішов далі і вже через місяць комп'ютер в більшості випадків легко обігравав моїх однокурсників. А по предмету був отриманий автомат. Програму отримаєте після опису алгоритмів.суть гри
Гравець і комп'ютер загадують чотиризначні числа, використовуючи цифри від 0
до 9
. Гравці намагаються розгадати числа суперника, посилаючи йому можливі варіанти чисел, у відповідь отримуючи два числа - число «Биків» і число «Корів». Що ж це за числа такі?
Для розуміння наведу приклад: загадане число 1622
. Якщо ми припустимо 6112
, То у відповідь прийде: 1 бик(Четверта цифра «2» на своєму місці), 2 корови(Шістка і одиниця не на своїх місцях).
Оперуючи даними про «худобі» супротивника, потрібно вгадати число швидше нього. Наприклад, загадане той же число 1622
, ми припускаємо «1111», Отримуємо у відповідь «Бика», потім «2222» - отримуємо у відповідь вже 2 «биків», «3333» - порожньо, «4444» - порожньо, «5555» - порожньо, «6666» - 1 бик.
Далі продовжувати не будемо, так як набралося вже 4 бика у сумі. Залишилося знайти потрібну комбінацію. Будемо генерувати перестановки, поки не отримаємо Та-дааам: «1226", «1262», «1226", «1262», «Тисячі шістсот двадцять дві»
. Усе.
Очевидно, що алгоритм не дуже хороший, зате зрозумілий і не заплутатися. Максимальне число ходів для вгадування - 10 ( «7890») + 24 перестановки. 34
- це в найгіршому випадку. Звичайно можливо перебір і перестановки всіляко оптимізувати, наприклад перебирати по черзі з двох кінців - «1111», «0000», «2222», «9999» ... так само оптимізувати генерацію перестановок при наявності однакових цифр (як у нашому прикладі - кілька разів запитуємо одне і те ж).
Але не будемо цим займатися. Нехай дана стратегія буде у нас легким рівнем складності комп'ютера. Наприклад, для задуманого числа 1234
ми припустили 5678
, І отримали 0 биків і 0 корів, Чого думати - ми виключаємо всі числа, що містять 5, 6, 7, 8
. Відразу можете прикинути, скільки відніметься з 10000.
Не варто лякатися безлічі з 10000
елементів. за 5-6
ходів залишиться всього кілька чисел.
Почнемо зі структур даних. Код на Паскалі:
Ну ось і все, зовсім не складно. Перша моя стаття, судити строго.відповідь
число відповідей
р
H
h
00
360
7,1%
8,49
3,81
01
1440
28,6%
10,49
1,81
02
1260
25,0%
10,30
2,00
03
264
5,2%
8,04
4,25
04
9
0,2%
3,17
9,13
10
480
9,5%
8,91
3,39
11
720
14,3%
9,49
2,81
12
216
4,3%
7,75
4,54
13
8
0,2%
3,00
9,30
20
180
3,6%
7,49
4,81
21
72
1,4%
6,17
6,13
22
6
0,1%
2,58
9,71
30
24
0,5%
4,58
7,71
40
1
0,02%
0,00
12,30
5040
100,0%
12,30
2,77
відповідь
число відповідей
р
H
h
00
54
3,8%
5,75
4,74
01
378
26,3%
8,56
1,93
02
369
25,6%
8,53
1,96
03
91
6,3%
6,51
3,98
04
6
0,4%
2,58
7,91
10
126
8,8%
6,98
3,51
11
222
15,4%
7,79
2,70
12
83
5,8%
6,38
4,12
13
6
0,4%
2,58
7,91
20
57
4,0%
5,83
4,66
21
31
2,2%
4,95
5,54
22
5
0,3%
2,32
8,17
30
11
0,8%
3,46
7,03
40
1
0,07%
0,00
10,49
1440
100,0%
10,49
2,86
Інформація від вопроса2, біт
Число таких питань
0,000
1
0,650
6
0,811
8
0,918
9
1,899
24
2,104
72
2,258
144
2,268
72
2,365
216
2,372
48
2,530
180
2,624
360
2,664
720
2,756
360
2,766
480
2,767
720
2,774
180
2,859
1440
Разом
5040
вопрос1
0123
відповідь1
01
вопрос2
4561
Ответ2
01
вопрос1
0123
відповідь1
02
вопрос2
3541
Ответ2
02