Задание 1 Вариант 1 Самостоятельная работа 8 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

ДЕРЕВО ИГРЫ
ВАРИАНТ 1
1. Петя и Вася играют в «Камешки». В начальной позиции у игроков есть кучка из 7 камешков; за один ход игрок может взять 1 или 2 камешка. Выигрывает тот, кто своим ходом забирает последний камешек (последние камешки). Постройте дерево игры по этим правилам.
Красным отмечены проигрышные ситуации, в которых выигрывает следующий игрок.

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

Получаем такие переходы:

• из $$7$$ можно перейти в $$6$$ или $$5$$;
• из $$6$$ — в $$5$$ или $$4$$;
• из $$5$$ — в $$4$$ или $$3$$;
• из $$4$$ — в $$3$$ или $$2$$;
• из $$3$$ — в $$2$$ или $$1$$;
• из $$2$$ — в $$1$$;
• позиция $$1$$ является выигрышной для текущего игрока, так как он забирает последний камешек.

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

Дерево игры:

7
├─ 6
│ ├─ 5
│ │ ├─ 4
│ │ │ ├─ 3
│ │ │ │ ├─ 2
│ │ │ │ │ └─ 1
│ │ │ │ └─ 1
│ │ │ └─ 2
│ │ │ └─ 1
│ │ └─ 3
│ │ ├─ 2
│ │ │ └─ 1
│ │ └─ 1
│ └─ 4
│ ├─ 3
│ │ ├─ 2
│ │ │ └─ 1
│ │ └─ 1
│ └─ 2
│ └─ 1
└─ 5
├─ 4
│ ├─ 3
│ │ ├─ 2
│ │ │ └─ 1
│ │ └─ 1
│ └─ 2
│ └─ 1
└─ 3
├─ 2
│ └─ 1
└─ 1

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

Ответ

Дерево игры построено для всех позиций от $$7$$ до $$1$$; выигрышной является позиция $$1$$, а проигрышные позиции — те, из которых ход ведёт к выигрышу следующего игрока.