Быки и коровы алгоритм

screenshot-2022-12-01-at-18-10-32-byki-i-korovy-algoritm-igry Инструкции

Правила игры изложены в отдельной статье, а здесь мы займёмся изучением вопроса оптимального алгоритма  поиска числа противника в игре быки и коровы. И так, есть общие принципы как следует задавать вопросы:

  • Вопрос должен быть таким, чтобы ответ был максимально информативен.
  • Категорически избегаем повторений. Нет нужды спрашивать то, что мы уже знаем.
  • Немного везения как никогда будет кстати.

Сколько комбинаций цифр можно составить? Первую цифру можно загадать десятью способами, вторую девятью и тд. И получаем 10*9*8*7 = 5040. Вот это общее количество комбинаций. А вариантов ответов может быть всего 14, они все показаны на рисунке.

Быки и коровы алгоритм

В приведённой таблице рассмотрены все варианты ответов. Самый желанный и вкусный – это 4 быка, то есть сразу выигрыш. И такой вариант один. Самый вариативный это 1 корова – имеет 1440 вариантов расстановки цифр. По большому счёту наши дальнейшие шаги буде определять наш первый ход. А тут мы может положиться только на нашу удачу, расположение звёзд, расставленной мебели по фен-шую и наличию кофе. То есть любую комбинацию цифр. И по полученному ответу мы планируем дальнейшие шаги. Рассмотрим варианты, кроме 4быков:

  • 0 быков, 0 коров – это тоже вполне удачный ход! Эти цифры сразу исключаем из угадываемого числа, но можем использовать для выявления быков.
  • 1 бык или 1 корова – то есть мы нашли одну цифру, но какая она не ясно.
  • 1 бык и 1 корова, или 2 быка или 2 коровы – нашли 2 цифры.
  • 3 быка и 0 коров, 2 быка и 1 корова, 1 бык 2 коровы. Нашли 3 цифры, но самый желанный – это три быка, всего 24 комбинации! На практике 4 хода.
  • 2 быка и 2 коровы, 1 бык и 3 коровы, 4 коровы – то есть мы нашли все цифры. Здесь мы можем кричать ура, так как выигрыш считайте у нас в кармане! Самое большее 9 комбинаций!

Дальнейшую стратегию рассмотрим на примерах игры, так будет гораздо наглядней и проще.

Первый пример

На первый вопрос 1234 мы получили ответ одна корова. Вторым вопросом была комбинация 5678. И тут удача – два быка и одна корова. Логика третьего хода следующая: мы угадали три цифры, нужно определить их расположение. И мы точно знаем что цифра 9 и 0 отсутствуют в загаданном числе. Потому берём две цифры из второго вопроса, но ставим на другие места и доставляем 0 и 9.

Получаем такой вопрос: 7890, на который мы получили ответ 2 коровы. Поздравляем – мы точно определили 2 быка: 7 на третьем месте, 8 на четвёртом. Далее мы знаем что 5 или 6 точно есть в загаданном числе. Уберём одно и поставим на другое место. Последнее число возьмём из первого вопроса, тут без разницы какое – чистое везение. Получаем такой вопрос – 4578. И радуемся победе, мы отгадали, ответ четыре быка!

Второй пример

На первый вопрос 0123 мы получили ответ 1 бык, 2 коровы. Вторым вопросом задаём 4567. Получаем в ответе 1 корова. Всё, мы снова исключили две цифры – это 8 и 9. И теперь мы возьмём две цифры с первого вопроса и как обычно поставим на другое место, добавим 8 и 9.

Получился такой вопрос 2389, ответ на который был одна корова. Казалось бы результат так себе, но не тут-то было! Скомбинируем третий вопрос так – возьмём ноль с первого вопроса, но менять его место не будем, возьмём двойку с третьего и поставим на второе и разбавим несуществующими. Вот что получили: 0289. Ответом было два быка! Теперь тройку тоже вычеркнем, а это значит, что единичка точно в числе есть. Теперь осталось всего два варианта и мы выбираем 0215. И получаем 4 быка! Пятёрочка – это чистое везение.

Третий пример

В первый раз спросим 9012. Получаем 2 коровы. Второй вопрос – 3456 – тоже две коровы. Так, 7 и 8 исключаем. Теперь перетасовываем второй вопрос и уберём одну, заменив на семерку. Получаем такой вариант : 6573. Ответ – одна корова. Что мы поняли? Цифра 4 точно есть и получили расположения, где цифры 3, 5 и 6 точно не стоят.

Четвёртый вопрос формируем так – комбинируем третий и первый вопрос, меняя местами. Вот какую комбинацию мы получили – 1234. Ответ – три быка. 3 и 4 стоят на своих местах, проверяем только первые цифры. 9234 – ответом на него было 2 быка, одна корова. Всё, мы нашли число! 1934.

Четвёртый пример

Первый вариант у нас 4590, ответ – один бык. Второй ход 1236 и ответ три коровы. Снова 7 и 8 вне игры. На третьем ходу тасуем цифры третьего вопроса и разбавляем 7. 7263, что даёт нам снова 3 коровы. Значит единичку выбрасываем.

Теперь нам нужно правильно расположить наших коров и найти быка с первого вопроса. Задаём такой вариант – 4623, ответ на него два быка и одна корова. Значит не четвёрка. Тройку мы не меняли и потому точно можем сказать, что именно тройка не на своём месте! Пробуем ещё раз – 3620. И бинго!!!! Мы разгадали число!

Бытует мнение, что выявив цифры, которые точно отсутствуют в загаданном числе, то их использовать дальше нельзя. И следует оперировать только найденными коровами, чтобы найти быков. Я придерживаюсь другого мнения. “Пустышки” крайне полезны в выявлении быков, так как мы можем точно определить цифры, которые стоят на своих местах. И это не будет какой либо потерей хода. Наоборот, оперируя только найденными коровами можно запутаться в том, какая из коров в данный момент стала быком.

Я старался в кратце описать ход своих мыслей при игре в быков и коров. Конечно, у каждого свой стиль игры. и многое зависит от везения. И на последок, удачи Вам и приятной игры.

Оцените статью
Робомозг
Добавить комментарий