Register

OR

Do you already have an account? Login

Login

OR

Don't you have an account yet? Register

Newsletter

Submit to our newsletter to receive exclusive stories delivered to you inbox!

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

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

более месяца назад
Просмотров : 26    Ответов : 1   

Лучший ответ:

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

более месяца назад
Ваш ответ:
Комментарий должен быть минимум 20 символов
Чтобы получить баллы за ответ войди на сайт





Вы можете из нескольких рисунков создать анимацию (или целый мультфильм!). Для этого нарисуйте несколько последовательных кадров и нажмите кнопку Просмотр анимации.


Другие вопросы: