Метод решета в игре «Быки и коровы»

[ok34]

Очень интересно. Немного не разобрался в функции «pr», но прочитав статью в википедии «метод „Решето Эратосфена“ стало понятней.
PS а игрушка занятная! Меня компьютер пару раз победил!

[sl4mmer]

>не столь известная логическая игра
угу, учитывая что 99% программистов писали реализацию игры еще в школе=)

[sl4mmer]

А алгоритм действительно хорош.

[TheHorse]

1.

Var A:array[1..Pmax] of Post;

Это лишнее, не нужно хранить в памяти константы, которые легко посчитать:

function getA(i : integer): Post;
begin
   result[4] = (i - 1) mod 10;
   result[3] = (i - 1) div 10 mod 10;
   result[2] = (i - 1) div 100 mod 10;
   result[1] = (i - 1) div 1000 mod 10;
end;

Тут мне пришлось брать (i — 1), потому что вы начинаете с 1, а не с 0, что имхо не очень правильно.

2. Обязательно прочитайте про то, как должен выглядеть код, про всякие нотации. Ваш код сложно читать.

3. В самой статье, я так и не понял ничего про применения метода решета. Не хватает формально написанного алгоритма, и примера, который доведет игру до конца.

P. S. Поздравляю с автоматом.

[allswell]

вы правы, благодарю за замечания.

[petropavel]

Подход стандартный.

Но в нем самое главное — выбор очередного хода. От этого зависит за сколько ходов программа будет угадывать комбинацию. У вас за сколько? И как выбирается очередной ход?

[allswell]

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

[petropavel]

И как — наверно за пять-шесть ходов отгадывал?

Насколько я помню (давненько я не брал в руки шашек) — случайный выбор дает шесть. Кстати вон и ниже так пишут. Но можно получить пять, если выбирать комбинацию, которая как можно сильнее ограничивает множество решений. То есть для разных комбинаций и разных ответов множество возможных решений уменьшается по-разному. И в наших интересах выбрать ход, который уменьшает его как можно больше.

[allswell]

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

[mik]

Школа, турбо паскаль, 286. Изобретенный алгоритм — это было откровение. Тут же написанный перебор всех вариантов — за сколько ходов будет отгадано. Два варианта выбора — первое допустимое или случайное. Случайное, насколько помню, давало чуть меньшее среднее число попыток, но все равно они оставались на уровне 5-6.
Недавнее время, fallout 3. Взлом компьютеров по тому же самому алгоритму.

[sl4mmer]

>Недавнее время, fallout 3.
Вы тоже писали себе утилиту для взлома компов?=)

[mik]

Нет, в голове, но тем самым методом :)

[shock_one]

Конечно возможно перебор и перестановки всячески оптимизировать, например перебирать поочередно с двух концов — «1111», «0000», «2222», «9999»...

Какая же это опимизация, если вероятность «выпадения» любого числа одинакова?

[allswell]

ребенок поиграет с ним два раза и поймет, что он каждый раз начинает с 1,2,3… и загадает например 9876.
… конечно и с поочередными попытками так же можно догадаться и составить число из средних. вы правы. нужно рандомизировать

[Athari]

Меня забавляет объяснение неиспользования алгоритма угадывания за 7 ходов — «слишком много ветвления». Лолшто? И за сколько шагов ваш алгоритм угадывает?

[allswell]

сами поиграйте и увидите. а тот алгоритм не использовал, тк нисколько не интересно переписывать алгоритм из кучи кейзов и условий

[Stvad]

Играем иногда в универе в эту игру (правда с несколько модифицированными правилами):) к даному алгоритму приходишь интуитивно игр после пяти;) а вот с выбором максимально эффективного следующего хода уже сложнее…

[3dm]

Объясните пожалуйста про переменные bk и kr в фунции pr. А именноусловия x

[boh]

Не совсем по теме, но как забавно смотрится меню «Файл»! Как будто в нём действительно собраны операции для работы с файлами, а не кнопка выход. И это ни в коем случае не упрёк в ваш адрес.

[allswell]

требования преподавателя:) есть еще кнопка «пауза»…

[bazeyvit]

Только что написал программу, используя этот метод решета.
Вероятно, я чего-то не понял, но у меня крайне редко случаются ситуации, когда нет ни одного попадания, так что программа работает практически на генераторе случайных чисел.

[Survei]

А есть какой-то алгоритм для поиска в уме?