Не, ну вы издеваетесь!!! И тут не успела!
Сидела, голову ломала, а все зря....
Думала, хоть в личку кинут ответ....
Блин.
Логическая задача
Модераторы: Азарапетыч, Администрация
- Atson
- Литератор-любитель
- Сообщения: 371
- Зарегистрирован: 15 апр 2007, 21:02
- Пол: Мужской
- Откуда: планета K-pax
team55 совершенно верно отмечает, что трактовки оптимальности могут быть разные. Специально не стал уточнять. Думаю, реально стоит рассматривать 2 - наиболее быстрый гарантированный выигрыш и наименьшее мат. ожидание количества необходимых ходов.
Но проблема еще и в термине "алгоритм". Полный перебор всех случаев (типа, как Dendr предлагает), конечно, даст такой алгоритм. Хотелось бы, однако, иметь некоторое решающее правило на каждом ходу по возможности простое. Не исключая при этом необходимости компьютерного обсчета, но только в рамках этого "хода", потому как обсчитывать все до конца довольно тяжко. Варианты растут в геометрической прогрессии.
Проблема тут в том, что меньшее количество оставшихся возможных вариантов не гарантирует возможность более быстрого отгадывния (и об этом уже было в некотором виде здесь написано). Иначе можно было бы выбирать ход по принципу минимакса (для задачи 1).
Но проблема еще и в термине "алгоритм". Полный перебор всех случаев (типа, как Dendr предлагает), конечно, даст такой алгоритм. Хотелось бы, однако, иметь некоторое решающее правило на каждом ходу по возможности простое. Не исключая при этом необходимости компьютерного обсчета, но только в рамках этого "хода", потому как обсчитывать все до конца довольно тяжко. Варианты растут в геометрической прогрессии.
Проблема тут в том, что меньшее количество оставшихся возможных вариантов не гарантирует возможность более быстрого отгадывния (и об этом уже было в некотором виде здесь написано). Иначе можно было бы выбирать ход по принципу минимакса (для задачи 1).
зайчатки интеллекта
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Да уж... переборы - дело хорошее, но все больше от удачи зависит. Ну, например, при том же первом ходе ответ 0б1к помогает мало. Даже мешает. И как делать второй ход - непонятно вдвойне.
А иногда стратегия и тактика могут завести в такие дебри...
Пример - вот сейчас разгадывал число.
1) 1234 1б1к
Предположил, что 1 - "бык", 3 - "корова", составил их в новое число: убрал 2 и 4, добавил 5 и 6.
2) 1356 1б1к
Опять-таки, гипотезе не противоречит. Но 3 - до сих пор "корова", а 5 и 6 в таком случае - нет в ответе.
3) 1783 1б1к
Все ясно... 3 - не "корова". Но 1 - до сих пор может быть "быком". Еще раз проверяем.
4) 1475 0б1к
Ну, все ясно: 1 - не "бык". Плохо? Ан нет. Повезло, наверное.
Анализируя, можно сделать вывод, что у нас только три варианта:
2736, 6384, 8253
И снова тактика... За три хода мы однозначно вычислим ответ. А за два можно? Можно!
5) 6920 0б2к
Две "коровы", следовательно, первое из чисел. (если бы была одна "корова", то третье, если один "бык", то второе - проверьте!)
И действительно:
6) 2736 4б0к
Опять же повторю - повезло, что ответы были такими.
Хм... а интересная задача - зная заданное число, определить, за сколько минимум ходов его можно разгадать. Не "рандомом", конечно, а пользуясь стратегией "равноценности".
Стратегия "равноценности":
Цифры последовательно, ход за ходом, разбиваются на группы, и у каждой группы свои свойства. Все цифры в группе считаются равноценными. При комплектации следующего хода из цифр нескольких групп, используются всегда наименьшие цифры каждой группы. (По заданному типу, например: 1<2<..<9<0) Путано - на примерах это показать проще.
Например, если есть группы: 1-2-5, 3-7-8-0, 4-6-9. И мы решили брать две цифры из 2-й группы, и по одной из остальных, имеем право брать только 1,3,7,4. И уже дальше переставлять их по местам, пользуясь тактикой.
Соответственно, если мы решим эту задачу для произвольно выбранного числа. Например: 8561 можно решить за (условно) 5 ходов. Далее - можно попытаться составить программу, которая, собственно, перебрав все числа, выдаст минимум ходов.
...
Написал и подумал. А ведь минимум - не есть оптимум... Хм. Можно ли создать программу, которая умеет играть в "Быки-коровы"?
А иногда стратегия и тактика могут завести в такие дебри...
Пример - вот сейчас разгадывал число.
1) 1234 1б1к
Предположил, что 1 - "бык", 3 - "корова", составил их в новое число: убрал 2 и 4, добавил 5 и 6.
2) 1356 1б1к
Опять-таки, гипотезе не противоречит. Но 3 - до сих пор "корова", а 5 и 6 в таком случае - нет в ответе.
3) 1783 1б1к
Все ясно... 3 - не "корова". Но 1 - до сих пор может быть "быком". Еще раз проверяем.
4) 1475 0б1к
Ну, все ясно: 1 - не "бык". Плохо? Ан нет. Повезло, наверное.
Анализируя, можно сделать вывод, что у нас только три варианта:
2736, 6384, 8253
И снова тактика... За три хода мы однозначно вычислим ответ. А за два можно? Можно!
5) 6920 0б2к
Две "коровы", следовательно, первое из чисел. (если бы была одна "корова", то третье, если один "бык", то второе - проверьте!)
И действительно:
6) 2736 4б0к
Опять же повторю - повезло, что ответы были такими.
Хм... а интересная задача - зная заданное число, определить, за сколько минимум ходов его можно разгадать. Не "рандомом", конечно, а пользуясь стратегией "равноценности".
Стратегия "равноценности":
Цифры последовательно, ход за ходом, разбиваются на группы, и у каждой группы свои свойства. Все цифры в группе считаются равноценными. При комплектации следующего хода из цифр нескольких групп, используются всегда наименьшие цифры каждой группы. (По заданному типу, например: 1<2<..<9<0) Путано - на примерах это показать проще.
Например, если есть группы: 1-2-5, 3-7-8-0, 4-6-9. И мы решили брать две цифры из 2-й группы, и по одной из остальных, имеем право брать только 1,3,7,4. И уже дальше переставлять их по местам, пользуясь тактикой.
Соответственно, если мы решим эту задачу для произвольно выбранного числа. Например: 8561 можно решить за (условно) 5 ходов. Далее - можно попытаться составить программу, которая, собственно, перебрав все числа, выдаст минимум ходов.
...
Написал и подумал. А ведь минимум - не есть оптимум... Хм. Можно ли создать программу, которая умеет играть в "Быки-коровы"?
- Лазков Йончер
- Белинский по натуре
- Сообщения: 46
- Зарегистрирован: 05 дек 2006, 22:37
- Пол: Мужской
- Откуда: Москва
- Контактная информация:
- dP
- Графоман со стажем
- Сообщения: 720
- Зарегистрирован: 12 апр 2005, 18:26
- Пол: Мужской
- Откуда: Санкт-Петербург
- Контактная информация:
Когда-то я прочесывал инет на тему оптимального алгоритма. Насколько я помню (хотя, могу и наврать - давно дело было), есть который для четырехзначного дает в среднем 4 с копейками, и есть другой, который чуть-чуть хуже, зато угадывает не более чем с шести ходов. Но это все глубокая теория. На практике я писал что-то на тему минимакса, который вполне ничего себе работает. Кстати, вариант брать первое попавшееся тоже не так плох, по сравнению с человеком, особенно на шестизнаках, где у последнего начинаются нехилые проблемы :Р
-эммм. а зачем winapi с MFC мешать?
-чтобы крышу быстрее сносило
-чтобы крышу быстрее сносило