Svinkovod.ru

Бытовая техника
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Игра быки и коровы алгоритм решения

Игра быки и коровы алгоритм решения

б) Правила игры те же, но загадывается 6-значное число с цифрами от 1 до 9, причем среди цифр допускаются одинаковые.

Примечание : Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута .

Итак, 1-ое что приходит в голову играть по следующему правилу: называть первое попавшееся число, которое может быть задуманно, т.е. при сопоставлении любого ранее спрошенного числа с новым должно получится такое-же количество ‘быков’ и ‘коров’. Число будем представлять в виде массива цифр.>

(Прим. вебмастера — прошу прощения за опечатки в исходниках: их составлял не я. Надеюсь, Вам не составит труда восстановить правильные программы по алгоритмам.)

Итак, наша программа работает следующим образом: мы путем последовательного увеличения на 1 генерируем все возможные 6-значные числа, отбираем среди них те, в которых все цифры различные, и, наконец, те из них, которые удовлетворяют хранящимся в массиве Info ответам, задается пользователю в качестве вопроса. Возникает ряд резонных вопросов: сколько всего интересующих нас 4-значных цифр и какая их часть не содержит повторений.

За сколько шагов может угадать ответ самый быстрый алгоритм и насколько хороша наша стратегия?

Давайте попытаемся ответить на них. Итак сколько всего чисел? Пусть k цифр и m позиций. В первой позиции может стоять любая

Из k цифр, что нам дает k вариантов. Во второй-также любая из k цифр, т.е. k 2 . И так далее m раз, т.е. всего k m вариантов. Обобщим эту идею.

Определение: размещение с n повторением из k элементов по m называется m-элементный массив натуральных чисел, каждое из которых не превосходит k.

Утверждение: Число размещений с повторениями из k по m равно k m . Доказательство проводим по индукции:

Базис индукции: При m=1 у нас ровно k вариантов.

Индуктивный переход: Пусть утверждение верно при m=n-1. Докажем, что оно верно при m=n. Зафиксируем число 1. Справа к этому числу припишем k n=1 размещений из k по n-1. Аналогично поступим с 1,2,3. k. Получим k n-1 *k=k n вариантов.

Таким образом, число 4-значных чисел с цифрами от 1 до 6 равно 6 4 =1296. Теперь посмотрим, сколько из них не содержит повторяющихся цифр.

Определения: размещением из k элементов по m называется m-элементный массив каждая компонента которого не превосходит k и среди них не встречаются одинаковые. Очевидно, что множество размещений не пусто лишь при m<=k.

Число размещений из k по m принято обозначать A.

Утверждение A=k*(k-1)*. (k-m+1)=k!/(k-m+1)!

Доказательство проводим по индукции:

Базис индукции: При m=1 у нас ровно k вариантов.

Индуктивный переход: Пусть утверждение верно при m=n-1. Выберем любое из k!/(k-n+1)! размещений из k по n-1. Чисел, которые в нем не участвуют-(k-n+1). Приписывая их поочередно справа к выбранному размещению мы получим (k-n+1) вариантов. Перебирая все размещения:

Читайте так же:
Игра грузится но не запускается

Таким образом,число 4-значных чисел с цифрами от 1 до 6 без повторений равно A46=6*5*4*3=360, т.е. в 3 раза меньше, чем число вариантов, которые мы перебирали. Итак мы нашли один способ для оптимизации нашей программы: генерировать не все числа, а лишь те, которые не содержат повторяющихся цифр. Возьмем это на заметку, а сейчас попробуем оценить максимальное число шагов, за которое отгадывает лучший игрок. Вариантов ответа у нас:

Пусть угадано 4 цифры. Среди них могут быть 2,1,0 «быков». Пусть угаданы 3 цифры. Среди них могут быть 3,2,1,0 «быков». И так далее: получаем 3+4+2+1=10 вариантов.

Таким образом за каждый вопрос количество допустимых чисел уменьшается, если мы рассматриваем худший случай, не более чем в 10 раз. Число шагов, за которое угадывает лучший игрок, не менее чем [log 10 360]+1=3

Ну а теперь попытаемся повысить эффективность работы программы. Как уже было отмечено выше, нам достаточно перебрать не 1096 комбинаций, а всего лишь 360. Это не отразится на быстроте угадывания, т.е. числе шагов, так как не изменим стратегии «первый попавшийся из подходящих», но уменьшит время обдумывания хода.

Генерировать числа будем следующим образом: для начала выберем множество цифр, которое в него входит, ну а затем будем переставлять элементы этого множества между собой. Множество цифр удобно, для наших целей, представить в виде массива длины 4, элементы которого расположены в порядке возрастания. Будем генерировать эти массивы в лексикографическом порядке, т.е. сначала сравниваются первые цифры, если они равны — вторые, и так далее. То есть:

Логическая игра быки-коровы. Алгоритм решения за 6 ходов!

Таким образом, после наложения всех ограничений (произведения вероятностей) число вариантов, как правило, становится вполне приемлемым.

Решение задач: метод перебора вариантов, на примере игры Быки-Коровы

Необходимость в методе перебора возникает всякий раз, когда «неизвестных» больше, чем ограничений (условий или причинно-следственных связей). Любое уравнение — это пример такого органичения (причинно-следственной связи).

Если уравнение одно, а неизвестных переменных две, то решение такого уравнения имеет несколько решений (не единственное).

Да, в этом случае в одну переменную в цикле, поочередно вставляем все допустимые значения и после этого получаем «одно уравнение — одна неизвестная».

Решение задач: метод перебора вариантов, на примере игры Быки-Коровы

Рис.1 Решение задач: метод перебора вариантов, на примере игры Быки-Коровы

На этом рисунке показано, как три ограничивающих условия «вопрос-ответ» сокращают количество вариантов перестановок с 5040 до 3 .

Вот такой калькулятор (решето) для игры БЫКИ-КОРОВЫ, который отсеивает все не нужные варианты перестановок!

Не играйте на деньги в интернете! (или с компьютерами)
Этот калькулятор доходчиво показывает, что играя с лохом, Вы можете вообще не загадывать свое число, а 6 раз уверенно говорить «Нет, не правильно» и называть в ответ число быков-коров, которые якобы в вашем числе образовались! И только на седьмом ходе, когда в решете останется только одна перестановка — Вы вынуждены будете согласиться, что противник угадал Ваше число.

Читайте так же:
Игра чего не хватает ответы

как решать Быки-Коровы

Первое, что необходимо — это умение подсчитывать количества «быков-коров», в задаваемых противником вопросах. Это не сложно и в Интернете достаточно примеров…

Второе, что необходимо — это решето, по отсеиванию «забракованных» перестановок после каждого ответа противника…

И третье — это алгоритм, который бы выдавал «следующий оптимальный вопрос».

Для справки: в Википедии игра названа «легкой».

Алгоритм и стратегия игры Быки и Коровы

Я могу доказать, что на седьмом ходе, программа не вопрос задает, а уже 100% результат сообщает. Тем не менее, противник получает право на седьмой ход. С правилами не поспоришь. Поэтому кто-то обоснованно может назвать этот алгоритм «за 7 ходов», но я считаю, что все-таки за 6…

Об алгоритме игры Быки и Коровы

Рис.2 Об алгоритме игры Быки и Коровы

Решатель — это симбиоз «решета» по отсеиванию перестановок и умения задавать умно-оптимальные вопросы.

А еще необходимо перепроверять пользователя, чтобы он не ошибся в подсчете быков и коров

6-ой ответ противника на вопрос — это максимум, чтобы в решете осталась одна перестановка (даже при самом плохом раскладе). Если вопросы задаешь «умные». А за пять ходов-ответов — это невозможно гарантировать. Только, на удачу! Но, на удачу, и с первого хода может получиться…

Флажок «с гарантией за 6 ходов» можно снимать, если играете с человеком, а не с другой программой или сервисом. Быстрее выиграете… Но с противником-машиной такие вольности не пройдут.

Где похожие задачи? Перспективы прикладного применения

Может кто-нибудь предложить прикладное применение этому алгоритму (приложению)?

Ведь «маленькие кусочки информации» машина увязывает в одно целое и на основании этого получается «достаточная информация» для принятия решения о следующем вопросе (остальные функции тривиальны).

Хотелось бы такую идею услышать и поучаствовать в ее реализации.

Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку .

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

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

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

Сколько комбинаций цифр можно составить? Первую цифру можно загадать десятью способами, вторую девятью и тд. И получаем 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. И бинго. Мы разгадали число!

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

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

Читайте так же:
Игра дестини 2 отвергнутые

Игра быки и коровы алгоритм решения

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 29.3.2005

Репутация: нет
Всего: нет

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Профиль
Группа: Участник
Сообщений: 148
Регистрация: 12.1.2005
Где: Общаги г. Киева

Репутация: 3
Всего: 8

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 29.3.2005

Репутация: нет
Всего: нет

И так правила игры — я и мой противник загадываем 4-значные числа, в котором не повторяются цифры(допустим мой противник загадал 1234).Далее я говорю 4-хзначное число — например 1753 — это будет 1 бык и 1 корова.Бык — если цифра и ее позиция совпадают(в нашем случае — 1), корова — если сопадает значение числа, но не его позиция(в нашем случае — 3).И так далее до тех пор пока один из противников не угадает число другого.Ноль не может быть первой цифрой числа!

Есть вариант задавать рандомом числа по 1-му методом :
1.1-ое число случайное — [1..9]
2.Шаг 2 рандом в диапазоне — [0..а1] и [а1..9].
3.если а1>а2 тогда рандом в диапазоне [0..а1] и [а1..а2] и [а2..9]
иначе рандом [0..а2][а2..а1][а1..9]
4.шаг аналогично только прибавится условие с а3.

Получили 4 числа — а дальше что?
Я делаю все время так — сначала говорю 2460, потом если сдесь есть 2 коровы, то ищу до 2-х быков,если есть 2 быка то ищу их положение, далее подставляю остальне цифры для поиска числа.
Иначе ищу до 2-быков и быка и коровы или 2-х коров, а далее по схеме.

Профиль
Группа: Участник
Сообщений: 148
Регистрация: 12.1.2005
Где: Общаги г. Киева

Репутация: 3
Всего: 8

Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 1

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.

  • Для решения контрольных, курсовых, дипломов и т.п. обращайтесь в Центр помощи
  • Похвалиться своими достижениями можно в разделе Интересные и занимательные задачи
  • Для поиска нужной литературы есть специальный раздел

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »

[ Время генерации скрипта: 0.1030 ] [ Использовано запросов: 20 ] [ GZIP включён ]

голоса
Рейтинг статьи
Ссылка на основную публикацию
Adblock
detector