ГДЗ: Параграф § 11 / Информатика 11 класс

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

Выигрышная стратегия — это набор правил, следуя которым игрок гарантированно одержит победу независимо от того, какие ходы будет делать его оппонент.

Игра как математическая модель характеризуется следующими признаками:

• Наличие нескольких игроков;
• Неопределённость в поведении игроков, связанная с несколькими вариантами действий;
• Различие (несовпадение) интересов игроков;
• Взаимосвязь поведения игроков (результат каждого зависит от действий всех остальных);
• Наличие правил игры, известных всем участникам.

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

Применение алгоритма Дейкстры для поиска кратчайшего пути

Найдем кратчайшие расстояния от вершины \( A \):

• Начало: \( A=0 \), остальные \(\infty\).
• Шаг 1: Посещаем \( A \) (0). Обновляем соседей: \( B=23 \), \( C=12 \), \( D=19 \).
• Шаг 2: Посещаем \( C \) (12). Обновляем соседей: \( B \): \( 12+25=37 > 23 \). \( E \): \( 12+23=35 \).
• Шаг 3: Посещаем \( B \) (23). Обновляем соседей: \( E \): \( 23+22=45 > 35 \). \( F \): \( 23+35=58 \).
• Шаг 4: Посещаем \( D \) (19). Обновляем соседей: \( E \): \( 19+20=39 > 35 \).
• Шаг 5: Посещаем \( E \) (35). Обновляем соседей: \( G \): \( 35+16=51 \). \( H \): \( 35+14=49 \).
• Шаг 6: Посещаем \( H \) (49). Обновляем соседей: \( G \): \( 49+24=73 > 51 \).
• Шаг 7: Посещаем \( G \) (51).

Кратчайший путь из \( A \) в \( G \) равен 51. Путь: \( A \rightarrow C \rightarrow E \rightarrow G \).

Решение задачи о бобре и желудях методом динамического программирования

Пусть \( M(i) \) — максимальное количество желудей, которое можно собрать, добравшись до острова \( i \). Переход на остров \( i \) возможен с любого предыдущего острова \( j \), соединенного стрелкой. Количество желудей на каждом острове соответствует весу. Выбирается путь, максимизирующий сумму:

\( M(i) = \text{желуди на } i + \max(M(j) \text{ для всех } j \text{, ведущих к } i) \)

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

Ответ: Максимальное количество желудей, которое сможет собрать Бобер Билли, равно 20.

Анализ игры 'Спички'

Эта игра является классической игрой Ним. Каждый ход уменьшает количество спичек на \( k \in \{1, 2\} \), то есть на \( 3 \). Выигрывает тот, кто оставляет противнику количество спичек, кратное \( 3 \), кроме \( 0 \). Проигрышной является позиция, где число спичек кратно \( (1+2)=3 \).

Проигрышные позиции (П): \( 3, 6, 9, \dots \)

Выигрышные позиции (В): Все остальные.

Начальное количество спичек \( S=107 \). Поскольку \( 107 \div 3 = 35 \) с остатком \( 2 \), \( 107 \) не делится на \( 3 \).

• Петя (Первый игрок) находится в Выигрышной позиции.
• Чтобы гарантированно победить, Петя должен первым ходом взять \( 2 \) спички, оставив Ване \( 107-2=105 \) спичек.
• \( 105 \) – это Проигрышная позиция (П), так как \( 105 \) делится на \( 3 \).
• После этого Ваня будет вынужден оставить Пете количество спичек, которое не делится на \( 3 \). Петя всегда сможет дополнить ход Вани до \( 3 \), оставляя Ване позицию, кратную \( 3 \).

Ответ: Выигрышная стратегия есть у Пети (первого игрока). Он должен первым ходом взять 2 спички, а затем на каждом шаге брать такое количество спичек \( k \in \{1, 2\} \), чтобы сумма его хода и хода Вани была равна 3.

Анализ игры с двумя кучами

Обозначим позицию как \( (S_1, S_2) \). Выигрыш достигается, когда \( S_1 + S_2 \geq 35 \). Начальная позиция: \( (2, 3) \). Общее количество камней \( S = 5 \). Проигрышной (П) является позиция, из которой любой ход ведет в выигрышную позицию (В) для противника. Выигрышной (В) является позиция, из которой можно сделать хотя бы один ход в проигрышную позицию (П) для противника.

Поиск выигрышных позиций (В) для первого хода (Петя):

• Петя может выиграть первым ходом, если \( S \times 3 \geq 35 \). Начальное \( S=5 \), максимальный ход \( 5 \times 3 = 15 < 35 \). Выиграть первым ходом невозможно.
• Критические позиции (В): Те, из которых можно перейти в Проигрышную позицию (П) для Вани.

Поиск проигрышных позиций (П) для второго хода (Ваня):

• Конечная Проигрышная область: \( S_1 + S_2 \in \{3, \dots, 34\} \).
• Позиция \( P \): \( P \) – проигрышная, если все ходы из \( P \) ведут к позициям \( V \) (выигрышным).
• Максимальное количество камней, которое можно получить за один ход: \( \max(\times 3) \). Если \( S_1+S_2=12 \), то Петя может сделать: \( (12 \times 3) = 36 \geq 35 \). Значит, все позиции с суммой камней \( S \geq 12 \) являются В для первого игрока.
• Самая большая П-позиция должна быть такой, чтобы все ходы из нее вели к В-позициям. Позиция \( S=11 \) является В, так как \( 11 \times 3 = 33 \), но \( 11+2=13 \) (В).
• Путем обратного перебора (аналогично примеру с одной кучей): самой большой П-позицией (сумма камней) для двух куч является \( S=11 \).

Стратегия: Петя (первый игрок) должен сделать такой ход из \( (2, 3) \), чтобы получить позицию \( (S_1', S_2') \), где \( S_1'+S_2' \) является проигрышной суммой, например, 11.

• Ход \( \times 3 \) в куче 2: \( (2, 9) \), сумма \( 11 \).

Петя первым ходом переводит игру в П-позицию \( (2, 9) \). Ваня из этой позиции не сможет выиграть, и Петя сможет обеспечить победу вторым ходом.

Ответ: Выигрывает игрок, делающий первый ход (Петя).

Анализ игры с кучей камней (Победа при \( \geq 47 \))

1. Укажите все значения \( S \), при которых Петя может выиграть в один ход. Обоснуйте.

• Петя выигрывает первым ходом, если \( S \times 3 \geq 47 \).
• \( S \geq \lceil 47/3 \rceil = 16 \).
• Ответ: \( S \in \{16, 17, \dots, 45\} \). Выигрывающие ходы: \( \times 3 \).

2. Укажите значение \( S \), при котором Петя не может выиграть в один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

• Нужно найти такую позицию \( S \), из которой любой ход Пети ведёт в выигрышную для Вани позицию (В), то есть \( S' \geq 16 \).
• Позиция \( S=15 \): Ходы Пети: \( 15+1=16 \), \( 15+2=17 \), \( 15 \times 3=45 \). Все эти позиции \(\{16, 17, 45\}\) являются выигрышными (В) для Вани, поскольку он может сделать ход \( \times 3 \) и получить \( \geq 47 \).
• Ответ: \( S=15 \). Ваня выигрывает ходом \( \times 3 \) из любой позиции, в которую его перевел Петя.

3. Укажите два значения \( S \), при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

• Требуется найти \( S \) такое, что Петя может перевести Ваня в Проигрышную позицию (П). Максимальная П-позиция – \( 15 \).
• Нужно найти \( S \), при котором \( S+1=15 \) или \( S+2=15 \) или \( S \times 3=15 \).
• \( S+1=15 \Rightarrow S=14 \).
• \( S+2=15 \Rightarrow S=13 \).
• \( S \times 3=15 \Rightarrow S=5 \).
• Ответ: Два значения: \( S=13 \), \( S=14 \). Выигрышная стратегия Пети: при \( S=13 \) сделать ход \( +2 \) (переводит в \( 15 \)); при \( S=14 \) сделать ход \( +1 \) (переводит в \( 15 \)).

4. Укажите значение \( S \), при котором у Пети есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения \( S \) опишите выигрышную стратегию Вани.

• В тексте условия есть опечатка: вместо "любой игре Пети" должно быть "любой игре Вани" и "опишите выигрышную стратегию Пети". Судя по контексту и предыдущему примеру (S=12 на стр. 157), искомая позиция должна быть П-позицией, из которой Петя не может выиграть в один ход, но Ваня не может гарантировать победу. Однако в данном случае (игра до \( \geq 47 \)), позиция \( S=15 \) является П для Пети, но Ваня выигрывает первым же ходом.
• Предположим, ищется позиция, из которой Петя не может выиграть первым ходом, но любой его ход не даёт Ване возможности выиграть немедленно (\( S' \times 3 < 47 \)).
• Рассмотрим \( S=12 \). Ходы Пети: \( 13, 14, 36 \). Ваня: Из 13, 14, 36 может выиграть ходом \( \times 3 \) (39, 42, 108). Таким образом, \( S=12 \) – Проигрышная для Пети.
• Предположим, вопрос нацелен на позицию \( S \) из диапазона, где гарантированный выигрыш невозможен в один ход, например, \( S=11 \).
• Ходы Пети: \( 12, 13, 33 \). Ваня: Из 12, 13 может выиграть ходом \( \times 3 \). Из 33 – нет, но может перевести в \( 33+2=35 \).
• В контексте этой задачи, П-позицией для первого игрока является \( S=15 \), но из неё Ваня выигрывает первым ходом. Позиция, где Петя может выиграть вторым ходом – \( S \in \{5, 13, 14\} \).
• Наиболее вероятный ответ, соответствующий общей логике раздела (но без точного перебора всего дерева): \( S=12 \) (проигрышная для Пети). Описание стратегии Вани: Ваня должен любым ходом перевести игру в выигрышную позицию для себя (т.е. в позицию \( S' \geq 16 \)).