Информатика (стр. 13 )

Задача 67. Задача на повторение понятий «перед каждой бусиной», «после каждой бусины». В ответе должно получиться слово КАРТОШКА.

Задача 68. Первое, что требуется в этой задаче, — осуществить полный перебор всех возможных ходов Первого и все эти ходы (их четыре, как подсказывает картинка) изобразить. Дальше нужно посмотреть, какие из получившихся позиций заключительные. Оказывается, что заключительных позиций из этих четырёх три и во всех трёх соответствующих партиях Первый проиграл. Для оставшейся четвёртой позиции в соответствии с условием задачи нужно найти все возможные варианты хода Второго и нарисовать все получающиеся позиции. Когда мы это сделаем, то окажется, что во всех позициях третьего уровня Второй проиграл, так что игра закончена.

Ответ:

Задача 69. В ходе решения подобных задач устанавливается связь между веткой дерева игры и отдельными партиями игры. Для начала ребятам необходимо понять, как связано дерево Н с цепочкой Q. Должны выполняться два условия: окончание цепочки Q — это путь дерева Н и число отрезков в заключительной позиции пути дерева Н должно соответствовать заданной длине цепочки Q. Ребята к настоящему моменту должны понимать: если в цепочке 9 бусин, значит, в партии сделано 8 ходов. Теперь ясно, что заключительными позициями партий с цепочкой Q могут быть лишь листья третьего уровня дерева Н.

Урок «Исследуем позиции на дереве игры»

К настоящему моменту ребята уже знакомы с понятием «выигрышная стратегия». Они умеют находить выигрышную стратегию для игры «камешки» с опорой на раскрашенную числовую линейку. Однако этот способ не является универсальным — с его помощью не получается найти выигрышную стратегию во всех играх с полной информацией. Причина проста: в других играх не удаётся расположить все позиции на числовой линейке, да и позиции часто не равноценны относительно двух игроков. Чтобы проанализировать все позиции большинства игр с полной информацией, необходимо построить дерево игры. В таком дереве имеются все возможные позиции игры и, начиная с листьев, эти позиции можно определить как выигрышные или проигрышные (если игра не допускает ничьей) по тем же правилам, которые были описаны на с. 27. (Если же игра допускает ничьи, то некоторые позиции будут ничейными.) Проанализировав все позиции в дереве, можно найти выигрышную стратегию для одного из игроков. Часто такую стратегию нельзя описать в виде простого правила и приходится искать различные способы, как описать её полно (для любой игры соперника), но более-менее кратко. Порой приходится описывать последовательность ходов для каждого варианта хода противника. Иногда помогают некоторые геометрические или арифметические соображения, позволяющие объединить разные позиции в группы и тем самым уменьшить объём описания стратегии. Вообще, в разных ситуациях проблема описания выигрышной стратегии может решаться по-разному. В примере на с. 45 в каждом случае вариант хода Первого единствен, поэтому выигрышная стратегия формулируется достаточно просто — одним предложением.

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

Заметим, что даже в случае игры «камешки» (которую можно проанализировать с помощью числовой линейки) анализ позиций по дереву игры может быть полезен. Особенно это актуально в том случае, когда стратегия не формулируется в виде простого правила (проигрышные позиции не подчиняются строгой закономерности). В этом случае часто приходится рассматривать разные варианты ходов противника и для каждого указывать ответный ход игрока. Это, конечно, гораздо проще сделать по дереву, где все возможные варианты ходов из каждой позиции представлены явно. Например, попробуем сформулировать выигрышную стратегию для игры, описанной на с. 44. Начальная позиция проигрышная, значит, выигрышная стратегия имеется у Второго. При этом Первый может сделать любой первый ход, и необходимо рассмотреть все варианты. По дереву видно, что если Первый на первом ходу возьмёт 1 камешек, то Второй должен взять 4 камешка и оставить Второму проигрышную позицию 2. Дальше исход игры оказывается предопределён. Если Первый на первом ходу возьмёт 3 камешка, то Второй должен взять 4 камешка и выиграть. Если Первый на первом ходу возьмёт 4 камешка, то Второй может взять любое число камешков (исход игры в обоих случаях предопределён).

Решение задач 70—75 из учебника

Задача 70. Построение дерева игры «камешки» — дело для ребят уже знакомое. Здесь интересно другое — при выполнении второго задания ребята наверняка заметят, что все проигрышные позиции находятся на уровнях с нечётными номерами, а все выигрышные — на уровнях с чётными номерами (если дети не заметят это сами, попросите их пометить уровни римскими цифрами I и II — номерами игроков, которые привели игру к этой позиции,). Это означает, что Первый не может выиграть в этой игре никогда. Соответственно Второй может играть как угодно, и выигрышная стратегия ему просто не нужна. Таким образом, Первый будет принудительно проигрывать, а Второй принудительно выигрывать. Вот почему любая партия данной игры будет разумной. Кого-то из ребят такая ситуация может смутить, поэтому приготовьтесь её прояснить. Если ребята решали задачу 42, возможно, стоит её вспомнить (а если не решали — стоит её решить, перед тем как решать задачу 70).

Ответ:

Задача 71. В этой задаче мы продолжаем готовить ребят к проекту «Стратегия победы». Для успешной работы с проектом необходимо уметь: во-первых, строить дерево игры, во-вторых, это дерево анализировать. Здесь ветка дерева уже построена. Чтобы выяснить, выигрышной или проигрышной является корневая позиция, кто из игроков обладает выигрышной стратегией из неё и в чём она заключается, необходимо, как обычно, проанализировать все позиции дерева, начиная с листьев. Для начала обведём все листья синим — это проигрышные позиции для игрока, чья очередь делать ход. Каждая позиция третьего уровня, которая не является листом, выигрышная, поскольку из неё можно сделать ход только в проигрышную позицию. Теперь проанализируем позиции второго уровня. Верхняя позиция проигрышная, поскольку все ходы из неё (а ход в данном случае один!) ведут в выигрышные позиции. Средняя позиция выигрышная, поскольку из неё существует ход в проигрышную позицию (в данном случае таких ходов два). Нижняя позиция также выигрышная, поскольку из неё существует ход в проигрышную позицию (вторую снизу позицию третьего уровня). Таким образом, корневая позиция выигрышная, поскольку из неё существует ход в проигрышную позицию (верхнюю позицию второго уровня). Значит, выигрышную стратегию из данной позиции имеет Первый. Цепочка разумной игры из корневой позиции совпадает с самым верхним путём дерева L.

Задача 72. Построение дерева D — задача, знакомая ребятам, вряд ли здесь потребуется ваша помощь. Заметим, что дерево D — ветка дерева с листа определений на с. 44. Поэтому, если кто-то затрудняется с построением дерева, попросите его ещё раз разобраться с листом определений. Все позиции, конечно, будут иметь те же цвета, что и на листе определений. В результате оказывается, что начальная позиция выигрышная, значит, выигрышную стратегию имеет Первый. У него есть возможность привести игру к одной из трёх позиций — 4, 2 и 1. При этом если он следует выигрышной стратегии, то должен сделать ход в проигрышную позицию 2. После этого исход игры определяется однозначно, и единственная разумная партия игры: 5 — 2 — 1 — 0.

Задача 73. Задача на повторение темы «Склеивание мешков цепочек», которая изучалась в курсе 2 класса. Напомним, что результатом склеивания двух мешков цепочек будет мешок, который состоит из всех цепочек, получающихся при склеивании цепочек из первого мешка с цепочками из второго мешка (к каждой цепочке из первого мешка приклеивается каждая цепочка из второго мешка). В данном случае длина каждой цепочки в мешке-результате равна 2, поэтому либо все цепочки в первом и втором мешках имеют длину 1, либо в одном из мешков лежат цепочки длины 0, а все цепочки во втором — длины 2. По условию в каждом из мешков есть непустая цепочка, значит, второй вариант исключается, остаётся только первый вариант. Ясно, что в первом мешке лежит цифра 2, а во втором — все цифры от 0 до 9. Только в этом случае при склеивании получается мешок М.

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

1. Кто должен ходить из корневой позиции?

2. Сколько у него есть возможных ходов?

3. Есть ли среди этих ходов такой, который позволит выиграть сразу?

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

Следующие ходы крестиками также возникнут естественно. Учащиеся уже понимают, почему за корневой позицией у нас шло четыре позиции, а теперь за каждой позицией — только три. Важно сформировать здесь некоторую дисциплинированность работы, привычку к систематичности. В частности, полезно, как только сделан очередной выбор, т. е. дорисована позиция в одной из позиций, передать этот выбор по цепочке, точнее, по ветке, начинающейся в данной позиции. Это потребует определённой аккуратности и сосредоточенности. Далее надо не забывать отмечать заключительные позиции — сразу рисовать стрелки и не пытаться что-то выстраивать за ними.