Задать вопрос
9 февраля, 01:26

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

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

+1
Ответы (1)
  1. 9 февраля, 03:43
    0
    Попытка поиска выигрышной стратегии может быть сделана при помощи метода, получившего название "бэкрекинг" (backtracking - обратное прослеживание).

    Рассматриваем финальную позицию для второго студента. У него должно оставаться от 1 до 4 карточек, чтобы он мог их все забрать и не оставить карточек первому студенту. Следовательно, у первого студента должно быть ровно 5 карточек. Забрав от 1 до 4 карточек, он оставит второму студенту как раз требуемое количество карточек.

    Чтобы у первого студента осталось 5 карточек, второй студент должен иметь от 6 до 9 карточек, т. е. первый студент для этого должен делать выбор из 10 карточек.

    И так далее. Выигрышная стратегия второго студента состоит в том, чтобы предоставлять первому студенту количество карточек, кратное 5.

    Но исходное количество карточек равно 20; это число кратно 5, следовательно второй студент всегда выигрывает, применяя описанную стратегию (она же - алгоритм).
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «Чтобы получить зачет по очень сложному предмету двум студентам нужно в сумме ответить на 20 вопросов. Выбор вопросов происходит так: на ...» по предмету 📘 Информатика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы
Похожие вопросы по информатике
укажите истинное высказывание (отметьте точкой) алгоритм всегда представляет собой некоторую последовательность вычислений алгоритм может представлять собой некоторую последовательность вычислений, а может последовательность действий
Ответы (1)
Правила игры "Оставь сопернику последнюю спичку" позволяют игроку за один раз забрать одну, две или три спички. Сколько спичек на первом ходу должен взять игрок, чтобы он в дальнейшем имел выигрышную стратегию, если в игре 10 спичек? 1.1 2.2 3.3
Ответы (1)
1) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза.
Ответы (1)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Ответы (1)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в четыре раза.
Ответы (1)