Логическая задача

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
Lemmi
Графоман со стажем
Графоман со стажем
Сообщения: 609
Зарегистрирован: 02 окт 2006, 16:32
Пол: Женский
Откуда: Шахты
Контактная информация:

Сообщение Lemmi »

Не, ну вы издеваетесь!!! И тут не успела!
Сидела, голову ломала, а все зря.... :(
Думала, хоть в личку кинут ответ....
Блин.
Все мы братья не только по крови, но и по другим анализам.

Аватара пользователя
Рыжик
Популярный автор
Популярный автор
Сообщения: 3235
Зарегистрирован: 05 фев 2007, 19:41
Пол: Мужской
Откуда: Калининград
Контактная информация:

Сообщение Рыжик »

Lemmi писал(а):Не, ну вы издеваетесь!!! И тут не успела!
Сидела, голову ломала, а все зря.... :(
Думала, хоть в личку кинут ответ....
Блин.
Ну извини, пожалуйста. :oops:
Опыт истории учит, что люди ничему не научаются на опыте истории.(с)

Аватара пользователя
Lemmi
Графоман со стажем
Графоман со стажем
Сообщения: 609
Зарегистрирован: 02 окт 2006, 16:32
Пол: Женский
Откуда: Шахты
Контактная информация:

Сообщение Lemmi »

Рыжик писал(а): Ну извини, пожалуйста. :oops:
Ну ладно :)
Все мы братья не только по крови, но и по другим анализам.

Аватара пользователя
Atson
Литератор-любитель
Литератор-любитель
Сообщения: 371
Зарегистрирован: 15 апр 2007, 21:02
Пол: Мужской
Откуда: планета K-pax

Сообщение Atson »

team55 совершенно верно отмечает, что трактовки оптимальности могут быть разные. Специально не стал уточнять. Думаю, реально стоит рассматривать 2 - наиболее быстрый гарантированный выигрыш и наименьшее мат. ожидание количества необходимых ходов.
Но проблема еще и в термине "алгоритм". Полный перебор всех случаев (типа, как Dendr предлагает), конечно, даст такой алгоритм. Хотелось бы, однако, иметь некоторое решающее правило на каждом ходу по возможности простое. Не исключая при этом необходимости компьютерного обсчета, но только в рамках этого "хода", потому как обсчитывать все до конца довольно тяжко. Варианты растут в геометрической прогрессии.
Проблема тут в том, что меньшее количество оставшихся возможных вариантов не гарантирует возможность более быстрого отгадывния (и об этом уже было в некотором виде здесь написано). Иначе можно было бы выбирать ход по принципу минимакса (для задачи 1).
зайчатки интеллекта

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Да уж... переборы - дело хорошее, но все больше от удачи зависит. Ну, например, при том же первом ходе ответ 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 ходов. Далее - можно попытаться составить программу, которая, собственно, перебрав все числа, выдаст минимум ходов.
...
Написал и подумал. А ведь минимум - не есть оптимум... Хм. Можно ли создать программу, которая умеет играть в "Быки-коровы"?

Аватара пользователя
Atson
Литератор-любитель
Литератор-любитель
Сообщения: 371
Зарегистрирован: 15 апр 2007, 21:02
Пол: Мужской
Откуда: планета K-pax

Сообщение Atson »

Можно ли создать программу, которая умеет играть в "Быки-коровы"?
Можно. У меня написана такая на VBA. Играет только не оптимально.
зайчатки интеллекта

Аватара пользователя
Лазков Йончер
Белинский по натуре
Белинский по натуре
Сообщения: 46
Зарегистрирован: 05 дек 2006, 22:37
Пол: Мужской
Откуда: Москва
Контактная информация:

Сообщение Лазков Йончер »

Ну вот, собираем все программы, коорые умеют в это играть, и устраиваем турнир... Победитель объявляется оптимальным!
Lazkov Joncer

Аватара пользователя
dP
Графоман со стажем
Графоман со стажем
Сообщения: 720
Зарегистрирован: 12 апр 2005, 18:26
Пол: Мужской
Откуда: Санкт-Петербург
Контактная информация:

Сообщение dP »

Когда-то я прочесывал инет на тему оптимального алгоритма. Насколько я помню (хотя, могу и наврать - давно дело было), есть который для четырехзначного дает в среднем 4 с копейками, и есть другой, который чуть-чуть хуже, зато угадывает не более чем с шести ходов. Но это все глубокая теория. На практике я писал что-то на тему минимакса, который вполне ничего себе работает. Кстати, вариант брать первое попавшееся тоже не так плох, по сравнению с человеком, особенно на шестизнаках, где у последнего начинаются нехилые проблемы :Р
-эммм. а зачем winapi с MFC мешать?
-чтобы крышу быстрее сносило

Ответить

Вернуться в «Задачки»