Я по быкам-коровам делал приложеньку ещё в 90-е на Delphi и в алгоритме ориентировался на решение задачи методом минимакса, думаю, это приблизительно то же самое, что и в вашем подходе.
Суть такая. После хода N у нас есть некая информация P(N), исходя из которой мы знаем, что загадано одно из X(N) чисел.
Делаем перебор всех возможных вариантов ходов - их всего 10 * 9 * 8 *7 - N. Для каждого варианта хода внутри устраиваем второй цикл по X(N) - среди всех возможных загаданных чисел, и для каждого числа получаем какой-то ответ в предположении, что загадано оно, на основе которого у нас уже есть информация Px(N+1). Для этой информации вычисляем сколько останется загаданных чисел - X(N+1). Берем максимум из этих чисел во внутреннем цикле. Таким образом для каждого возможного хода мы знаем наихудший в рамках этого алгоритма вариант - сколько останется вероятных кандидатов на верный ответ. Ну и естественно по внешнему циклу выбираем такой ход, для которого это число минимально.
Доказать, что это оптимальная стратегия, я не берусь, но вероятно, очень близко к тому. Вот какой она делала второй ход в ответ на 0б 1к, я за давностью лет позабыл.
А нидерландское zondek (навес от солнца) перекочевало в русское "зонтик", ассимилировалось, со временем "-ик" стало восприниматься как приставка и получилось русское "зонт".
Я по быкам-коровам делал приложеньку ещё в 90-е на Delphi и в алгоритме ориентировался на решение задачи методом минимакса, думаю, это приблизительно то же самое, что и в вашем подходе.
Суть такая. После хода N у нас есть некая информация P(N), исходя из которой мы знаем, что загадано одно из X(N) чисел.
Делаем перебор всех возможных вариантов ходов - их всего 10 * 9 * 8 *7 - N. Для каждого варианта хода внутри устраиваем второй цикл по X(N) - среди всех возможных загаданных чисел, и для каждого числа получаем какой-то ответ в предположении, что загадано оно, на основе которого у нас уже есть информация Px(N+1). Для этой информации вычисляем сколько останется загаданных чисел - X(N+1). Берем максимум из этих чисел во внутреннем цикле. Таким образом для каждого возможного хода мы знаем наихудший в рамках этого алгоритма вариант - сколько останется вероятных кандидатов на верный ответ. Ну и естественно по внешнему циклу выбираем такой ход, для которого это число минимально.
Доказать, что это оптимальная стратегия, я не берусь, но вероятно, очень близко к тому. Вот какой она делала второй ход в ответ на 0б 1к, я за давностью лет позабыл.
А нидерландское zondek (навес от солнца) перекочевало в русское "зонтик", ассимилировалось, со временем "-ик" стало восприниматься как приставка и получилось русское "зонт".
Систематическая ошибка выжившего