11 класс Информатика ГДЗ учебник Босова Параграф 11

1) Где применяют алгоритмы кратчайшего пути?

Решение. Маршрутизация в навигаторах и в транспортных сетях; планирование логистики и доставки;
маршрутизация пакетов в компьютерных сетях; оптимизация кабельных и трубопроводных трасс; задачи в робототехнике (путь до цели);
поиск на графах зависимостей в проектах (критический путь); оптимизация цепочек технологических операций.

2) Дейкстра: найти кратчайший путь между A и G

Рёбра и веса (с рисунка):
A–B 23, A–C 12, B–C 25, B–E 21, B–H 35, C–D 19, C–F 23, D–F 20, E–G 14, F–G 24, H–G 16.
(Неназванных рёбер нет.)

Ход алгоритма (d — текущая наименьшая дистанция от A):

1. Старт: d(A)=0; остальные ∞.
2. Из A: d(B)=23, d(C)=12.
3. Обрабатываем C (12): d(D)=31, d(F)=35.
4. Обрабатываем B (23): d(E)=44, d(H)=58 (d(C) не улучшается).
5. Обрабатываем D (31): d(F)=min(35,31+20)=35 (без изменений).
6. Обрабатываем F (35): d(G)=59.
7. Обрабатываем E (44): d(G)=min(59,44+14)=58.
8. Оставшиеся вершины улучшений не дают.

Ответ: кратчайший маршрут A → B → E → G, длина 58.

3) «Бобёр Билли и жёлуди» — максимальное количество (динамическое программирование)

Идея. Река задаёт слоистый направленный граф: с каждого острова можно плыть только на узлы следующего слоя
(стрелками на рисунке). Пусть a[i,j] — жёлуди на острове в слое i, позиция j. Тогда максимальная добыча
dp[i,j] = a[i,j] + max(dp[i+1, j1], dp[i+1, j2], …) по всем разрешённым стрелкам вниз.
Считаем слои снизу вверх; ответ — максимум в первом слое. Подставьте ваши числа — получите значение и маршрут
(восстановить по выбору max в каждом узле).

4) На столе 25 спичек. За ход берут 1–4. Побеждает тот, кто берёт последнюю.

Решение. Проигрышны позиции, где число спичек кратно 5 (после любого хода соперник может добрать до следующего кратного 5).
25 — кратно 5, значит выигрывает второй игрок. Стратегия: после каждого хода первого добирать столько, чтобы суммарно
убрать ровно 5 спичек (пары ходов 1+4, 2+3 и т. п.).

5) На столе 107 спичек. За ход берут 1 или 2. Побеждает взявший последнюю.

Решение. Проигрышны позиции, кратные 3. Так как 107 ≡ 2 (mod 3), первый игрок выигрывает:
первый ход — взять 2 (оставить 105), дальше зеркалить: на 1 отвечать 2, на 2 — 1, поддерживая кратность 3.

6) Две кучи: (2, 3). Ход: выбрать кучу и либо умножить на 3, либо прибавить 3. Побеждает тот, кто первым делает сумму ≥ 35.

Метод. Анализ через обратную индукцию: позиция выигрышна, если есть ход прямо в область x+y ≥ 35
или ход в проигрышную позицию сопернику. Начальная позиция мала, но удваивающие ходы быстро растят сумму.
Для компактности здесь даю схему рассуждений и два рабочих приёма для первого игрока:

• Избегать ходов, после которых соперник сможет утроить большую кучу и сразу достичь ≥35.
• Стремиться сделать к одной из куч значение ≥12: тогда на следующем ходу утроение этой кучи гарантирует победу
  (например, 12→36).

Пример выигрывающей линии для первого: 1-й ход: сделать (2, 9) (утроить 3). Если соперник увеличит любую кучу на 3
(получится (5,9) или (2,12)) — первый тут же выигрывает, утроив 12→36. Если соперник утроит меньшую (получится (6,9)) —
первый за цикл наращивает до 12 и добирает победу. (Допускается несколько ходов; цель — не дать сопернику первым пересечь 35.)

Замечание. Формально можно выписать все позиции с суммой ≤34 и отметить выигрышные/проигрышные
по правилу «есть ход в проигрышную — значит выигрышная», но дерево громоздко; на сайте лучше оставить изложенный приём и один победный сценарий.

7) Игра «добавь 1 или 5». Победа при S ≥ 47. Начальное S ∈ [1; 46].

1) Когда Петя выигрывает в один ход?

Ответ. При S ∈ {42, 43, 44, 45, 46} (прибавить 5 или 1 соответственно).

2) Значение S, при котором Петя не может выиграть в один ход, но как бы ни сходил Петя, Ваня выигрывает своим первым ходом.

Ответ. S = 41. Ибо 41→42 или 41→46, после чего Ваня добирает до 47 (соответственно +5 или +1).

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

Ответ. S = 36 и S = 40. Стратегия — перевести игру в позицию 41 (проигрышную для того, кто ходит):
36→41 (+5) или 40→41 (+1); затем какой бы ход ни сделал Ваня (в диапазон 42–46), Петя на своём втором ходу добирает до ≥47.

4) Значение S, при котором выигрышная стратегия у Вани есть, но гарантированно выиграть своим первым ходом он не может.

Ответ (пример). S = 39. Это проигрышная позиция для ходящего (все такие S — нечётные ≤41).
Если Петя пойдёт 39→44, Ваня выигрывает сразу (44→49). Если Петя пойдёт 39→40, Ваня не может выиграть первым ходом,
но переводит в 41 (или 45), после чего на следующем своём ходе неизбежно добирает до ≥47.

Общий принцип. Проигрышные позиции — все нечётные S ≤ 41; выигрышные — все чётные S и S ≥ 42.
Они образуются «лесенкой» с шагом 1 из-за ходов +1 и +5.