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

Ответ:

Задача 64. Как и задача 63, данная задача является очень важной, ведь это первое задание на построение ветки дерева игры. Для облегчения технической работы мы поместили в поле решения задачи заготовки всех необходимых полей, на которые уже поставлены все крестики и нолики из корневой позиции. Ребятам остаётся только дорисовать позиции и дерево, но вначале им придётся ответить на ряд вопросов.

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

После заполнения позиций второго уровня ребятам нужно проверить, нет ли среди этих позиций заключительных (в данном случае их нет). Далее ребята аналогично работают с вершинами второго уровня, строя вершины третьего уровня (на третьем уровне уже будут заключительные позиции) и так до четвёртого уровня. Чтобы учащимся было легче отвечать на вопросы, можно поставить над каждым уровнем дерева (или перед ним) римскую цифру I или II в зависимости от того, кто из игроков сделал ход, в результате которого получились данные позиции (или, что то же самое в этой игре, кто из игроков ставил значки).

Отметим, что в отличие от игры «камешки» мы не можем считать все листья последнего уровня (он у нас помечен значком I) позициями с выигрышем Первого, поскольку среди этих позиций могут встретиться и ничьи. Листья последнего уровня нужно тщательно проверять, хотя в данном дереве ни одна партия ничьей не заканчивается (при ответе на вопрос про число ничьих ребята должны написать нуль и в дереве никакие листья зелёным не обводить).

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

Ответ:

Задача 65. Необязательная. Здесь ребятам нужно написать программу, которая приводит Робика в определённую клетку поля и при этом заставляет его обходить стены. Если вы хотите немного усложнить задание, попросите ребят написать такую программу С, в которой будет не больше 18 команд, — это наименьшая возможная длина такой программы. Действительно, чтобы привести Робика из левого нижнего угла в правый верхний на том же поле без стен, потребуется самое меньшее 14 команд (нужно пройти 6 клеток вверх и 8 вправо). Здесь же нам приходится, как минимум, в двух местах обходить стену, т. е. идти влево или вниз (а потом возвращаться). Программ С минимальной длины много, приведём одну из них:

вправо

вправо

вверх

влево

вверх

вправо

вправо

вверх

вправо

вверх

вверх

вправо

вниз

вправо

вверх

вправо

вверх

вправо

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

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

Придётся изобретать какой-то свой способ работы. Предлагаем здесь два способа рассуждений.

Первый способ. Рассмотрим сначала второе утверждение. В мешке ровно две квадратные бусины и ровно две красные бусины. В цепочке должны стоять две «слипшиеся» пары «красная — квадратная». Есть всего два варианта таких пар:

либо

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

Остались две круглые синие. Как им найти место? Одну синюю круглую можно поставить перед парой, а другую уже поставить будет некуда. Поставим круглую синюю:

Тогда через одну после неё нужно поставить ещё одну синюю — не получается, не хватает ещё синих.

Рассмотрим второй вариант расстановки в пары красных и квадратных бусин. После пары «красная круглая — зелёная квадратная» нужно поставить (треугольную или круглую) синюю бусину. Поставим треугольную:

Оставшиеся две круглые синие поставить будет некуда. Поставим круглую:

Тогда через одну после неё должна стоять ещё одна круглая. Есть два варианта следующих двух бусин: либо вторая пара — либо две оставшиеся синие:

В первом случае оставшиеся синие бусины будет некуда поставить, во втором случае, если поставить сначала треугольную, потом круглую, всё получается:

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

Пусть последняя бусина цепочки — зелёная квадратная, тогда перед ней — красная треугольная (красная круглая здесь стоять не может, иначе первое утверждение потеряет смысл):

Осталось пять бусин и пять свободных мест, снова начинаем пробовать различные варианты. При этом быстро выясняется, что круглые бусины не могут стоять на четвёртом и пятом местах, иначе становится ложным первое утверждение. Значит, три круглые бусины должны стоять на первых трёх местах. Но тут приходим к противоречию. Если красная бусина первая или вторая в этой тройке, то за ней обязательно должна идти квадратная (что не получается); если же красная бусина последняя, то она вторая после круглой, а вторая после круглой должна быть синей. Делаем вывод: последняя бусина цепочки Щ не зелёная квадратная. Аналогично приходим к противоречию, если последняя бусина синяя треугольная.

Пусть последняя бусина цепочки синяя квадратная. Тогда перед ней стоит красная треугольная (см. выше).

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

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

Решение задачи предполагает большое количество сложных рассуждений. Как приведённые здесь рассуждения помогут вам при работе над этой задачей с детьми? Какие-то отдельные идеи вполне могут помочь при индивидуальной работе с учеником, который совсем запутался и не знает, что делать дальше, или начал решать, но зашёл в тупик. Если вы видите, что он упорно выбирает варианты, которые заведомо не приведут к правильному ответу, порассуждайте вместе с ребёнком, почему именно так быть не может. В зависимости от того, какие идеи высказывает ученик и в чём ошибается, наметьте возможные стратегии решения и понаблюдайте, что он делает дальше. Так, по принципу горячо — холодно вы вместе будете понемногу подбираться к искомой цепочке.