Чтобы получить зачет по сложному предмету двум студентам нужно в сумме ответить на 20 вопросов. выбор вопросов происходит так: на столе разложено 20 карточек. каждый из студентов по очереди делает свой выбор, причем за один раз можно взять от 1 до 4 карточек. существует примета, что тот, на ком вопросы закончатся, т.е. тот, кто не сможет взять следующую карточку, – тот зачет не сдаст. поэтому кроме того, чтобы выучить сам предмет, студенты разрабатывают выигрышную стратегию: такую последовательность действий, которая гарантированно, не зависимо от действий второго участника, позволит завладеть последним вопросом. возможно ли составить такую стратегию студенту, который выбирает вопросы вторым? напишите алгоритм, ответ

илона590 илона590    3   21.06.2019 22:40    0

Ответы
Жекон124 Жекон124  17.07.2020 10:47
Попытка поиска выигрышной стратегии может быть сделана при метода, получившего название "бэкрекинг" (backtracking - обратное прослеживание).
Рассматриваем финальную позицию для второго студента. У него должно оставаться от 1 до 4 карточек, чтобы он мог их все забрать и не оставить карточек первому студенту. Следовательно, у первого студента должно быть ровно 5 карточек. Забрав от 1 до 4 карточек, он оставит второму студенту как раз требуемое количество карточек.
Чтобы у первого студента осталось 5 карточек, второй студент должен иметь от 6 до 9 карточек, т.е. первый студент для этого должен делать выбор из 10 карточек.
И так далее. Выигрышная стратегия второго студента состоит в том, чтобы предоставлять первому студенту количество карточек, кратное 5.
Но исходное количество карточек равно 20; это число кратно 5, следовательно  второй студент всегда выигрывает, применяя описанную стратегию (она же - алгоритм).
ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика