Ответы пользователя по тегу Комбинаторика
  • Алгоритм автоматического поиска решений тестовых вопросов со взаимоисключающими ответами?

    cheerfulatlas
    @cheerfulatlas
    Придумался еще один немного извращенный метод, с использованием статистики.

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

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

    Плюсом подобного подхода является то, что при определении 100-го правильного ответа, вы уже будете иметь 99 готовых.

    Если вы захотите это проверить, вам придется написать некую модель, дабы не тратить производительность на работу с реальным тестом.
    Ответ написан
  • Алгоритм автоматического поиска решений тестовых вопросов со взаимоисключающими ответами?

    cheerfulatlas
    @cheerfulatlas
    Кажется, задача более практическая, чем теоретическая? Так что мое не очень математическое видение:

    Рассмотрим вариант, когда m=n
    Предположим, что тестовый набор состоит из одного вопроса. Очевидно, мы используем полный перебор.
    Если тестовый набор состоит из двух вопросов, то ответ на первый вопрос может быть получен только в случае известного ответа на второй вопрос. Исход, когда мы попадаем на неверный ответ к вопросу №2 дает 0+0 либо 0+1 баллов, что не представляет собой полезную информацию.
    Аналогично со случаем 3 и больше, ответ на третий вопрос мы можем подобрать только зная ответы на первый и второй.
    Таким образом, на практике, нам необходимо запускать наш тест, перебирая входные наборы до тех пор, пока на выходе мы не получим сумму баллов = m.

    В случае же m < n единственной и всем очевидной оптимизацией может быть не только сохранение правильных ответов в случае удачного запуска-подбора, но и использование их для подстановки при запусках для отгадывания оставшихся вопросов.
    Ответ написан