Логические игры, они же головоломки, очень полезны для симметричного развития личности человека. Во время игры развивается логическое мышление, скорость мышления, человек начинает быстрее находить ответы на поставленные задачи, что, несомненно, полезно в современном, быстро меняющемся мире. Помимо саморазвития, они так же помогают с пользой провести время.
Логические игры незаменимы для развития детей школьного и дошкольного возрастов, но так же актуальны и интересны взрослому человеку. Практически все логические игры имеют ярко выраженную математическую направленность, вследствие чего, могут быть решены методом комбинаторного анализа.
В данной работе приводится пример решения логической игры «Быки и коровы».
Эта, простая на первый взгляд, игрушка, однако заставит вас, напрячь серое вещество – это шедевр времяубивания на лекциях, уроках, работе или дома. Правила просты.
В классическом варианте игра рассчитана на двух игроков, каждый из которых задумывает и записывает тайное 4-значное число с неповторяющимися цифрами. Игрок, который начинает игру по жребию, делает первую попытку отгадать число. Попытка — это 4-значное число с неповторяющимися цифрами, сообщаемое противнику. Противник сообщает в ответ, сколько цифр угадано без совпадения с их позициями в тайном числе (то есть количество коров) и сколько угадано вплоть до позиции в тайном числе (то есть количество быков).
«Быки» – это те цифры вашего числа, расположение которых поразрядно совпадает с цифрами загаданного числа;
«Коровы» - это те цифры вашего числа, которые присутствуют в загаданном числе, но находятся в другом месте, (в другом разряде, на другой позиции).
Рассмотрим пример: Загадано число «2308».
В числе присутствуют цифры - 2, 3, 0, 8;
На ваши попытки его угадать, ответом будет следующее:
1. «1234» – 0б, 2к («коровы» цифры 2 и 3, так как они присутствуют в загаданном числе, но находятся не на своих местах);
2. «5678» – 1б, 0к («бык» это цифра 8, находится на 4-й позиции, т.е. на месте);
3. «2380» – 2б, 2к (2,3 - быки, 8,0 - коровы, 2 и 3 на местах, 8,0 не на местах ).
и т.д.
В среднем, пытливому уму требуется от 6 до 8 попыток, чтобы отгадать любое 4-хзначное число.
Стоит заметить, что игра, о которой идет речь, представляют собой весьма интересный объект для исследования на компьютере. Достаточно сказать, что в написании программы для «Быков и коров» участвовал один из крупнейших в мире специалистов в области программирования американец Д. Кнут. В нашей стране ряд результатов в этой области был получен группой студентов кафедры кибернетики МИСиС под руководством доцента М. Гендлера.
Основная задача, привлекающая математиков и программистов, состоит в нахождении оптимального алгоритма, то есть такой стратегии игры, при которой количество шагов для достижения максимально результата (получения 4 быков) будет минимальным.
На сегодняшний день существует несколько вариантов для решения этой задачи. Один из них представлен в работе А. Словеснова «Оптимальный алгоритм в игре быки и коровы», в которой он доказывает, что существует алгоритм, следую которому можно отгадать число, сделав не более 7, но и не менее 6 ходов.
Алгоритм заключается в переборе комбинаций, начиная с 0123, 1245, 2456 и.т.д., пытаясь найти ход с максимальной результативностью. Данная схема позволяет проверить практически все цифры на различных позициях, и по подсказкам (быкам и коровам) провести анализ и отгадать число.
Но данный алгоритм предназначен для случая, когда на первом месте в загаданной четырехзначной комбинации может стоять «0, что является одной из разновидностей игры. Но все же вернемся к классическому варианту.
В правилах сказано: «…Каждый из игроков задумывает и записывает тайное 4-хзначное число…», а число не может начинаться с 0, следовательно, данный алгоритм не будет столь результативен, если вообще может быть применен, в классической игре, тем более, если игра реализуется в компьютерной программе, где правила ввода число и проверочных комбинаций строго обозначены.
В ходе решения данной задачи мной был разработан алгоритм, позволяющий угадать число за максимум 8-9 шагов, а в частных случаях и за 5-7.
Заключается он в следующем.
Начинаем перебор с комбинации «1234», каждый следующий шаг меняем последнюю цифру на следующую по порядку за ней, т.е после «1234» будет комбинация «1235» и.т.д. По изменению числа «коров» мы с легкостью определяем цифры, участвующие в записи числа, ну а уж если появляется «бык», то и узнаем одну из конечных позиций. Когда станут известны все 4 коровы остается только подобрать выигрышную комбинацию. Сделав анализ предыдущих шагов, данная процедура займет максимум 2 шага.
Рассмотрим работу данного алгоритма на примере: пусть загадано число 2876.
Начинаем перебор:
|
1234 |
1 к, 0 б |
|
1235 |
1 к, 0 б |
|
1236 |
1 к, 1 б |
|
1237 |
2 к, 0 б |
|
1238 |
2 к, 0 б |
Итак, сделав всего 5 ходов, мы определили 3 цифры участвующие в записи числа: 6 (счетчик быков изменился, а значит, данная цифра присутствует в числе на той же позиции), 7 (счетчик коров изменился), 8 (мы не меняли цифры ни в одной из позиций, кроме последней, следовательно, данная цифра присутствует в числе).
Осталось найти последнюю цифру и определить число. Мы знаем, что «6» стоит в числе на последнем месте и что последняя корова скрывается в комбинации «123».
Начинаем простой перебор и, анализируя предыдущие шаги, делаем следующие. В итоге получаем следующий результат:
|
1786 |
2 к, 1 б |
|
2876 |
0 к, 4 б |
Итак, на данном примере я доказала, что данный алгоритм действенный и пригодный для решения конкретно этой игры. Возможно так же применение этого алгоритма в подобных играх, основанных на комбинаторном анализе.
Библиографическая ссылка
Шарнова В.А., Горовенко Л.А. ТЕХНОЛОГИЯ ПРИМЕНЕНИЯ МЕТОДОВ КОМБИНАТОРНОГО АНАЛИЗА В ИГРАХ С УГАДЫВАНИЕМ ЧИСЛА // Международный студенческий научный вестник. – 2015. – № 5-4. ;URL: https://eduherald.ru/ru/article/view?id=13974 (дата обращения: 21.11.2024).