Быки и коровы (игра для детей). Быки и коровы правила Игра быки и коровы олимпиада

Когда я поступил в институте, очень популярной была игра «Быки и коровы ». Так совпало, что в это же время я прочитал математическую новеллу Альфреда Реньи «Дневник. – Записки студента по теории информации». Благодаря этой статье я познакомился с . И у меня родилась идея, как улучшить свои показатели в «Быках и коровах», опираясь на новые знания .

Кратко напомню правила. Играют двое. Каждый задумывает и записывает тайное 4-значное число с неповторяющимися цифрами (первой может быть и ноль). Игрок, который начинает игру по жребию, делает попытку отгадать число. Попытка - это 4-значное число с неповторяющимися цифрами, сообщаемое противнику в виде вопроса. Противник говорит в ответ, сколько цифр угадано с совпадением их позиций в тайном числе и сколько угадано без совпадения. Например: задумано тайное число 3219; попытка (вопрос) 2310; результат (ответ): один «бык» (цифра 1 из вопроса входит в тайное число и стоит на своем месте) и две «коровы» (цифры 2 и 3 из вопроса входят в тайное число, но стоят не на своем месте). Ответ сообщается в виде 2-значного числа. В нашем примере ответ – 12 (один «бык», две «коровы»). Игроки делают попытки по очереди. Побеждает тот, кто первым получит на свой вопрос ответ 40.

Скачать заметку в формате или , примеры в формате , пример в формате zip (внутри Excel-файл на 57МВ).

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

Вопрос нужно задавать так, чтобы ответ на него давал максимальное количество информации.
Для этого вопрос нужно формировать так, чтобы вероятности различных ответов были по возможности близкими.
Кроме того, вопрос должен быть таким, чтобы ответ на него не содержал информацию, полученную ранее из предыдущих вопросов.

Для лучшего понимания материала полезно также открыть Excel-файл.

1. Тайное число можно задумать 10*9*8*7 = 5040 способами (на первом месте может стоять любая из 10 цифр, на втором – любая из 9 оставшихся и т.д.). Для того, чтобы сформировать массив допустимых чисел я использовал простые алгоритмы в Excelе (см. листы «Подг1» и «Подг2»). Поскольку вероятность быть задуманным любого из 5040 чисел одинакова, неопределенность (Н) вычисляется по формуле Хартли : Н = log 2 N. Перед началом игры неопределенность составляет log 2 5040 = 12,30 бит информации.

2. Понятно, что первый вопрос может быть любым, например, 0123. На него возможны 14 ответов (см. также лист «Вопрос1» Excel-файла):

Ответ	Число ответов	р	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 – количество информации, полученное, если реализовался тот или иной ответ. Наиболее вероятный ответ – 01, означающий, что из вопроса в тайное число входит лишь одна цифра, причем стоит она не на своем месте. Ответ 01 подразумевает, что задуманным может быть одно из 1440 чисел, то есть неопределенность, оставшаяся после этого ответа, составляет log 2 1440 = 10,49 бит, а информация, полученная при таком ответе 12,30 – 10,49 = 1,81 бит. Ответ 40 дает 12,30 бит информации, а неопределенности после него не остается J Поскольку вероятности ответов различны, количество информации, содержащееся в вопросе определяется по формуле Шеннона: Н(x) = 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»):

Ответ	Число ответов	р	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,86 бита информации. Посмотрим, сколько информации дадут другие вторые вопросы. Для этих целей я создал отдельный файл «Неоптимальный второй вопрос.xlsx» (он «весит» 58МВ, поэтому будьте с ним аккуратнее:)). Второй вопрос может быть одним из 5040 возможных чисел (в том числе и повторение первого вопроса). В итоге этого исследования я получил количество информации, которое дают те или иные вторые вопросы (напомню, что анализ сделан в предположении, что первый вопрос 0123 дал ответ 01). Например, вопрос2 – 0123 дает ноль битов информации, так как на него возможен только один ответ 01, а (для N = 1) log 2 1 = 0. Вопрос2 0132 дает 0,65 бит информации, вопрос2 0148 – 2,53 бита информации. Максимальное количество информации дают 1440 вторых вопросов, сформированных по выше описанному правилу. Результаты исследования я перенес на лист «Разные вопросы2» файла «Быки-коровы.xlsx» и далее буду говорить только об этом файле.

Как я уже сказал, максимальное количество информации – 2,859 – будет получено на вопрос2, подготовленный следующим образом: надо взять одну цифру из первого вопроса, поставить ее на новое место и добавить три новые цифры:

Информация от вопроса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

Видно, что еще 180 вопросов дают почти столько же информации – 2,774 бита. Такое количество информации будет получено при ответе, например, на вопрос 1045 (см. лист «Вопрос2неопт»). Но этот вопрос не может дать ответа 40! То есть, вопрос подготовлен с нарушением сформулированного правила. Насколько велика разница в информации между 2,859 и 2,774 бита!? На первый взгляд она не выглядит большой. С другой стороны, при самом неблагоприятном ответе на вопрос2 4561 (01) останется 378 вариантов тайного числа, а при самом неблагоприятном ответе на вопрос2 1045 (также 01) – 408 вариантов. На 8% больше! Это и есть цена неоптимального вопроса.

4. При подготовке третьего (и последующих) вопросов я руководствуюсь следующим мнемоническим правилом. Необходимо составить агрегированную таблицу всех возможных тайных чисел, удовлетворяющих ответам на предыдущие вопросы. После этого сформировать вопрос3, используя ту часть этой таблицы, которая содержит больше вариантов (оценку произвожу «на глазок»). Немного запутанно? Давайте рассмотрим два примера.

Пример1.

Вопрос1	0123		Ответ1	01
Вопрос2	4561		Ответ2	01

Первый вариант: входит единица, тогда не входят, ни 023, ни 456; то есть входят, не использовавшиеся в первых двух вопросах, цифры – 789. Получаем набор цифр тайного числа 1789 (порядок их расположения любой, удовлетворяющий ответам на первые два вопроса). Вариантов, отвечающих этому набору, 12.

Второй вариант: единица не входит, тогда входит одна цифра из 023, одна – из 456, и две – из 789. Записываю я это так:

Ориентировочное число вариантов набора цифр равняется 3 (одна из 023) * 3 (одна из 456) * 3 (две из 789) = 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. Первые два вопроса и ответа были следующими:

Вопрос1	0123		Ответ1	02
Вопрос2	3541		Ответ2	02

Первый вариант: входят 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 коровы (шестерка и единица не на своих местах).

Оперируя данными о «скоте» противника, нужно угадать число быстрей него.

Первый же тривиальный алгоритм, который так и напрашивается, - это перебирать наборы «1111», «2222», «3333»... до тех пор, пока не будет получен полный набор, а затем генерировать перемещения этого набора.

Например, загадано то же число 1622 , мы предполагаем «1111» , получаем в ответ «быка» , затем «2222» - получаем в ответ уже 2 «быков» , «3333» - пусто, «4444» - пусто, «5555» - пусто, «6666» - 1 бык .
Дальше продолжать не будем, так как набралось уже 4 быка в сумме. Осталось найти нужную комбинацию. Будем генерировать перестановки, пока не получим Та-дааам: «1226», «1262», «1226», «1262», «1622» . Все.

Очевидно, что алгоритм не очень хорош, зато понятный и не запутаться. Максимальное число ходов для угадывания - 10(«7890»)+24 перестановки. 34 - это в самом худшем случае. Конечно возможно перебор и перестановки всячески оптимизировать, например перебирать поочередно с двух концов - «1111», «0000», «2222», «9999»... так же оптимизировать генерацию перестановок при наличии одинаковых цифр(как в нашем примере - несколько раз спрашиваем одно и то же).
Но не будем этим заниматься. Пусть данная стратегия будет у нас легким уровнем сложности компьютера.

Много я сидел на парах и играл сам с собой, пытаясь придумать какой то свой крутой алгоритм. Но приходили только единичные идеи, из которой я не мог составить единой стратегии. Начал изучать литературу. Наткнулся на статьи, рода «угадывание за 7 ходов». Они меня не привлекли, поскольку там очень много ветвления. Но прочитав книгу нашего Кировского профессора(но не из нашего университета) С.М. Окулова «Программирование в алгоритмах» , я нашел описание довольно простого и достаточно эффективного алгоритма. В нем используется так называемый «метод решета» (примером может служить известное «решето Эрастофена» - классическая задача поиска простых чисел). Мы рассматриваем конечное множество всех возможных чисел и каждый ход исключаем все элементы множества, не представляющие интереса.

Например, для загаданного числа 1234 мы предположили 5678 , и получили 0 быков и 0 коров , чего думать - мы исключаем все числа, содержащие 5, 6, 7, 8 . Сразу можете прикинуть, сколько отнимется из 10000. Не стоит пугаться множества из 10000 элементов. За 5-6 ходов останется всего несколько чисел.

Начнем со структур данных. Код на паскале:

Const Pmax=10000; Type Post=string; Var A:array of Post; //множество B:array of boolean; // массив флажков, 1 - значит подходит, 0 - исключено

Инициализация:

T:=1; for i:=0 to 9 do for j:=0 to 9 do for k:=0 to 9 do for l:=0 to 9 do begin a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); // формируем множество inc(t); end; for i:=1 to pmax do b[i]:=true; // по умолчанию все числа подходят

Функция, реализующая анализ элемента множества по значениям переменных (bk,kr - быки и коровы)

Function pr(a,b:post;bk,kr:integer):boolean; //b - наш ход, a- элемент "тестируемого" множества var i,x:integer; begin x:=0; for i:=1 to 4 do // проверка по быкам if a[i]=b[i] then inc(x); if x<>bk then begin pr:=false; exit; end; x:=0; for i:=1 to 4 do // проверка по коровам if (a[i]<>b[i]) and (pos(b[i],a)<>0) then inc(x); if x

Таким образом после каждого нашего хода запускаем решето

For i:=1 to Pmax do if b[i] and not pr(a[i],hod,bk,kr) then b[i]:=false;

В заключение можно сказать, что алгоритм затратен к памяти и по сравнению со стандартными алгоритмами будет думать «дольше», но насколько же он проще и вполне оптимизируется.
Ну вот и все, совсем не сложно. Первая моя статья, судить строго.

Аннотация: Игра "Быки и коровы" На этом уроке продолжается рассмотрение предыдущей игры "Задумай число". Обсуждается алгоритм бинарного поиска, дающий оптимальную стратегию поиска задуманного числа. Приводится реализация этой стратегии. В интерфейсе игры появляется новая кнопка "Компьютер, отгадай число". Рассматривается проект, реализующий новую игру "Быки и коровы", где также требуется отгадать число, задуманное компьютером. Найти задуманное число в этой игре сложнее, поскольку разрешается задавать вопрос только одного типа "Число равно 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 :

///

/// Стратегия компьютера /// Реализация алгоритма бинарного поиска ///

/// /// private void buttonCompGuess_Click(object sender, EventArgs e) { int min_c = min; int max_c = max; int mid = (min + max) / 2; countQuestion = 0; listBoxQA.Items.Add(COMP); //Бинарный поиск while (min_c != max_c) { countQuestion++; question = countQuestion.ToString() + ". "; question += "Число больше "; question += mid + "?"; if (number > mid) { question += " - Да!"; min_c = mid + 1; } else { question += " - Нет!"; max_c = mid; } mid = (min_c + max_c) / 2; listBoxQA.Items.Add(question); } //границы интервала неопределенности совпадают. //Ответ найден countQuestion++; question = countQuestion.ToString() + ". "; question += "Число равно "; question += min_c + "?"; question += " - Да!"; textBoxResult.Text = COMP_ANSWER + number; listBoxQA.Items.Add(question); }

Открыл технологию угадывания 4-значного числа! Абсолютная безотказность. Количество необходимых попыток - 5 -6 , ну в случае фатального невезения может потребоваться 7.
Такая технология, правда, требует от Вас хорошей сообразительности и достаточно большого промежутка времени для отгадывания чисел (у меня уходило от 70 до 160 секунд). Если для Вас это - пустяки, можете смело прибегать к этой технологии)
Принцип такой.
Первые 4 попытки пишем следующие числа:
1234
4567
3480
6043
И смотрим на результаты.
В частности нас интересует СУММА всех быков и коров за эти 4 попытки.
Вы спросите в чем дело, почему именно эти числа? Можно и другие, на самом деле, но обязательно условие такое:
ОДНА цифра должна повторяться ЧЕТЫРЕ раза (в данном случае это 4 ) и желательно стоять во всех числах на разных позициях;
ОДНА цифра - ТРИ раза (в данном случае это 3 );
ДВЕ цифры - по ДВА раза (6 и 0 );
и ОДНА цифра - отсутствовать вовсе (9 ).
При этом пять цифр будут повторяться по одному разу - это 1, 2, 5, 7 и 8 .
Еще одна особенность: в числе 6043 , которое мы ввели 4-ой попыткой, присутствуют все цифры, которые повторяются в данной комбинации более чем один раз (это 4, 3, 6 и 0 ) - и ТОЛЬКО они. Это сыграет также важную роль. Зачем это надо - потом скажу.
Итак, теперь считаем сумму полученных быков и коров. Их может быть от 3 до 11. Это нам надо для того, чтобы определить, какие из повторяющихся цифр встречаются в загаданном числе.
Например, если в итоге получилось 3 быка и коровы - ясное дело, что загаданное число содержит три цифры, которые повторяются в комбинации один раз, и цифру, которая отсутствует. Другого варианта быть не может.
Для тех, кто хочет сэкономить время, приводу шпаргалку:
Сумма БК/Повторения
3 = 1110
4 = 2110 или 1111.
5 = 3110/2210/2111
6 = 4110/3210/3111/2211
7 = 4210/4111/3220/3211
8 = 4310/4220/4211/3221
9 = 4320/4311/4221
10 = 4321
11 = 4322
Если сумма равна от 4 до 9, то вариантов, как вы видите, несколько.
В этом случае на помощь приходит число 6043 (то самое, где встречаются только повторяющиеся цифры). Смотрим сумму быков и коров именно у него.
Например, если общая сумма равна 7 , а у четвертой попытки только один бык, то ясное дело - иначе как 4111 вариантов быть не может.
Вот например:
1234 - 1б, 1к
4567 - 1б, 1к
3480 - 0б, 2к
6043 - 1б, 0к.
Подставляем и получаем следующее:
Цифра 4 - ТОЧНО есть , причем стоит она на 3-ей позиции.
Цифр 3, 6, 9, 0 - ТОЧНО нет .
Подставляем результаты в третью попытку: Цифра 8 - точно есть .
И еще есть одна из цифр 12 , и одна из цифр 57 . Обе - стоят на своих позициях (так как в обоих случаях 4 - это корова).
Возможные варианты: 1847 , 1548 , 8247 .
Более точно мы определить число пока не можем, но заметьте - уже свели количество возможных вариантов к трем (при том что всего их ни много ни мало 4536 , при условии что число не начинается с нуля). Вероятность того, что мы угадаем с 5-ой попытки, равна 33%. Вопрос - что вводить 5-ой попыткой ?
Посмотрим варианты.
Если мы введем 1847 , то:
Если загадано число 1548 , результат будет - 2 быка 1 корова .
Если загадано число 8247 , результат будет - 2 быка 1 корова .
Вывод: число 1847 вводить не стоит, если только Ваши экстрасенсорные способности не подсказывают Вам, что загадано именно оно.
Если мы введем 1548 , то:
Если загадано 1847 , результат будет - 2 быка 1 корова .
Если загадано 8247 , результат будет - 1 бык 1 корова .
Уже лучше! Делаем пятую попытку. С вероятностью 33% - она оказывается удачной, если же нет - то шестая попытка уже точно будет последней. =)))
Если жа и после такой проверки вариантов все равно осталось несколько (например, общая сумма = 8, сумма у 4-го числа = 2, варианты - 4310 и 4211) тогда уже анализируйте дальше, исходя из кол-ва быков и коров на каждой попытке.
Еще один пример:
1234 - 1б, 1к
4567 - 0б, 2к
3480 - 2б, 0к
6043 - 0б, 2к
Сумма = 8. 8 = 4310/4220/4211/3221.
После проверки 4-ой попыткой возможные варианты: 4211, 4310 .
Проверим сначала 4310 . Может быть такое? Может. Это означает, что цифры 3 и 4 - есть, 6 и 0 - нет, 9 - есть. Все подходит.
Теперь определим местоположение. Третья попытка - два быка, и кроме как 3 и 4 вариантов быть не может. СТО-о-оп! А где же тогда бык в первой попытке? Согласно ей, цифр 1 и 2 быть не может, а 3 и 4 уже заняты... Не получается!
ЗНАЧИТ - 3 все-таки нет, а единственный вариант оставшийся - 4211 .
То есть: 4 есть, также есть 6 или 0 , 9 нет. 3 - тоже нет.
Если предположить, что есть 4 и 6 , тогда есть еще 8 , а также 1 или 2 .
Если же предположить, что есть 4 и 0 , то есть еще 5/7 или 1/2 .
Еще один момент: В первой попытке остался неиспользованным один бык. Причем это точно цифра 1 , так как на второй позиции стоит цифра 4 (согласно 3-ей попытке), а цифры 3 вообще нет.
Итак, первые две цифры числа 14 .
Варианты: 1450, 1470, 1486.
И опять с вероятностью 33% мы угадываем с пятой попытки, с вероятностью 67% - с шестой.
Конечно, значительную роль в игре играют быки. В третьей попытке получилось два быка - и в итоге мы сэкономили один ход. Но на самом деле бывает так, что мне удалось выиграть с пятой попытки (и даже без угадывания в конце!!!) имея лишь одного быка.

Например:
1234 - 0б, 2к
4567 - 1б, 0к
3480 - 0б, 3к
6043 - 0б, 3к .
Сумма = 9 . 9 = 4320/4311/4221.
6043 = 3 коровы
Остаются варианты 4320 и 4221 .
Пробуем оба этих варианта. Согласно первому:
Есть цифры 4, 3 и 9 , также есть 6 или 0 .
Или:
Есть 4, 6 и 0 , а также еще одна цифра из неповторяющихся - 1, 2, 5, 7 или 8 .
Какая? Смотрим по быкам. И натыкаемся на несоответствие - во второй попытке 4567 имеем только одного быка, а согласно этому варианту есть 4 и 6 . Не подходит .
Следовательно, подходит только первый вариант, причем как мы только что выяснили, цифры 6 нет, значит есть 3, 4, 9 и 0 .
Теперь вычислим местоположение этих цифр. 4 - единственный бык во второй попытке, значит, она на первой позиции.
Цифра 3 может находиться только на 2-ой позиции, так как она была использована в первой и в четвертой попытке на 3-ей и 4-ой позиции, и нигде нет ни одного быка. Значит, у нас два варианта: 4390 и 4309 . 4390 - быть не может, так как в третьей попытке у нас тоже нет быков. Остается единственный ваариант - 4309 , который мы и вводим 5-ой попыткой и выигрываем!
Но могут изредка возникать ситуации, когда четырех попыток маловато, чтобы свести дальнейший процесс к тупо угадыванию.
1234 - 0б, 1к
4567 - 1б, 0к
3480 - 0б, 1к
6043 - 0б, 1к .
Итого - 4 в сумме. 4 = 2110 или 1111.
На 4-ой попытке - одна корова. Это означает, что вариант 1111 нам не подходит - только 2110 .
Из этого делаем вывод следующий:
9 - есть
Есть также 6 или 0
Есть также 1 или 2 (исходя из первого числа)
И еще одна цифра. Это может быть 5 или 7 , но если есть одна из этих цифр, значит 6 нет, а есть 0 . Или же если есть 6 , то есть 8 обязательно.
Проще говоря, варианты цифр: 1/2 - 6 - 8 - 9 , или 1/2 - 5/7 - 9 - 0.
О местоположении цифр догадываться мы пока не можем - маловато быков.
Возможных вариантов пока много. Делаем пятую попытку. Лучше первым проверять тот вариант, где меньше точно известных цифр. Пусть это будет число 2907 .
Получилось: 1 бык, 1 корова.
Что это означает?
1: Цифры 9 и 0 - верны, а 2 и 7 надо заменить на 1 и 5 .
2: Вариант неверен, и совпали цифры 2 и 9 , а оставшиеся две - 6 и 8 .
То есть набор цифр получается следующий: либо 1-5-9-0 , либо 2-6-8-9 .
Рассмотрим сначала первый вариант. Мы имеем следующее:
5 может быть только на второй позиции;
0 - не на четвертой, значит на третьей позиции (в начале числа он не может стоять). Это и есть бык;
1 - не на первой позиции.
Единственный вариант - 9501 . Пока не спешим его вводить...
Теперь второй вариант - с набором 2-6-8-9 :
6 - на третьей позиции;
2 - не на второй позиции.
Варианты: 2869, 2968, 8962, 9862
Варианты 2968 и 9862 - не подходят, так как в первом случае получается 2 быка, а во втором - ни одного.
Остается три варианта: 9501, 2869, 8962. Тут уже - только вопрос везения. Мне не повезло, я ввел 8962 и получил 1 корову и только) оказалось как раз 9501(((получилось 7 попыток.
Конечно, выглядит сложно на первый раз. Но нужно просто попрактиковаться, и все будет хорошо). А главное - это РАБОТАЕТ ! Реально, я только что 40 раз сыграл с компьютером, в 52,5% случаев (21 из 40) угадал с 5 попыток, в 42,5% (17 из 40) - с 6-ти, и лишь дважды (5%) мне не повезло и пришлось использовать седьмую.
Хотя бывают, конечно, и исключительные случаи. С вероятностью 1 к 1134 компьютер может загадать одно из чисел 1234, 4567, 3480, 6043 . Однажды он загадал число 4576 , которое я благополучно угадал с трех попыток) А может оказаться так, что после ввода, к примеру, 3480 Вы получите 0 быков 0 коров , что делает почти бессмысленным ввод числа 6043 . Но факт есть факт - при использовании этой стратегии вероятность отгадывания с 4 попыток равна 0.09%
не более чем с 5 попыток = около 50%
не более чем с 6 попыток = около 90%
не более чем с 7 попыток = 100%!
Может быть конечно я и ошибаюсь, но на мой взгляд - это самая оптимальная стратегия отгадывания четырехзначного числа. В настоящее время я еще думаю над стратегией отгадывания 5-значных, 6-значных и даже 9-значных чисел. Как додумаюсь - поделюсь, если конечно это будет интересно.
В завершении даю ссылку на мою версию программы, которую я написал за 1,5 часа на Delphi 7. Ее особенность - возможность отгадывать числа как четырехзначые, так и других разрядностей, а также возможность проходить Чемпионаты, т.е. последовательность раундов с отгадыванием чисел разных разрядностей с ограничением по кол-ву попыток и времени (мой рекорд по прохождению чемпионата на 8 раундов - 58 попыток и 590 секунд, уровень Экстрасенс).
Вот она -