Размещено 5 лет назад по предмету Информатика от mrakos2012

Чтобы получить зачет по очень сложному предмету двум студентам нужно в сумме ответить на 20 вопросов. Выбор вопросов происходит так: на столе разложено 20 карточек. Каждый из студентов по очереди делает свой выбор, причем за один раз можно взять от 1 до 4 карточек.

Существует примета, что тот, на ком вопросы закончатся, т.е. тот, кто не сможет взять следующую карточку, – тот зачет не сдаст. Поэтому кроме того, чтобы выучить сам предмет, студенты разрабатывают выигрышную стратегию: такую последовательность действий, которая гарантированно, не зависимо от действий второго участника, позволит завладеть последним вопросом. Возможно ли составить такую стратегию студенту, который выбирает вопросы вторым?Напишите алгоритм, подтверждающий ответ

Ответ на вопрос

Ответ на вопрос дан Аккаунт удален

Попытка поиска выигрышной стратегии может быть сделана при помощи метода, получившего название "бэкрекинг" (backtracking - обратное прослеживание).
Рассматриваем финальную позицию для второго студента. У него должно оставаться от 1 до 4 карточек, чтобы он мог их все забрать и не оставить карточек первому студенту. Следовательно, у первого студента должно быть ровно 5 карточек. Забрав от 1 до 4 карточек, он оставит второму студенту как раз требуемое количество карточек.
Чтобы у первого студента осталось 5 карточек, второй студент должен иметь от 6 до 9 карточек, т.е. первый студент для этого должен делать выбор из 10 карточек.
И так далее. Выигрышная стратегия второго студента состоит в том, чтобы предоставлять первому студенту количество карточек, кратное 5.
Но исходное количество карточек равно 20; это число кратно 5, следовательно второй студент всегда выигрывает, применяя описанную стратегию (она же - алгоритм).