Уроки 34–36. Дерево игры. Ветка из дерева игры

Материалы к урокам: лист определений «Дерево игры. Ветка из дерева игры», бумажные задачи 1–16 (2 часть), компьютерный урок «Дерево игры. Ветка из дерева игры» (задачи 520–523), занятия 9 и 10 на Клавиатурном тренажере.

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

Дерево игры. Ветка дерева игры

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

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

Ветка из дерева игры – это, как вы понимаете, фрагмент, часть дерева игры. Важно, что ветка дерева игры имеет одну корневую бусину – какую-то позицию игры и все возможные следующие позиции после этой корневой – до конца игры (до заключительных позиций). Таким образом, ветка дерева игры – это не любая часть дерева игры, а только такая, которая включает все возможные варианты завершения игры, начиная с некоторой позиции, т. е. в ветке нет «оборванных веточек и листьев».

Решение бумажных задач

Задача 1. Очень важно, чтобы с этой задачей справились все ребята. Не жалейте на нее времени, тем более что учащиеся здесь встретятся с некоторыми новыми моментами, на которые нужно обратить внимание.

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

Если вы видите, что кто-то из учеников не знает, с чего начать, можно помочь ему следующими вопросами: «Какие ходы может сделать Первый из начальной позиции?», «Какие позиции при этом могут получиться?», «Какие ходы может сделать Второй из возможных позиций второго уровня (4 и 5)?», «Какие позиции могут при этом получиться?» и т. д. Если вы видите, что учащийся не отвечает на эти вопросы, возможно, стоит вместе разобраться, как построено дерево G на с. 3. Чтобы при построении дерева не запутаться, перебирая возможные позиции, лучше располагать все бусины, следующие за некоторой бусиной, в определенном порядке, например, сверху вниз по убыванию числа камешков в позициях.

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

Есть и другие варианты для красивого расположения дерева в окне. Можно начать строить дерево с самого длинного пути, разместив его приблизительно по диагонали, начав примерно с середины первого уровня и закончив наверху последнего уровня. Затем следует пририсовывать к каждой из бусин нарисованного пути следующие бусины, начиная с конца. Так появляется одна (самая большая) ветка. Затем на оставшемся месте следует разместить остальные ветки.

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

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

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


Задача 2. Необязательная. Здесь интересно выслушать не только ответ, но и объяснения ребят, которые, скорее всего, не уместятся на отведенной строке. Если у вас нет возможности поговорить со всеми, кто решил эту задачу, объедините их в небольшие группы (по 2–4 человека) и попросите выслушать друг друга. Затем вы можете поговорить только с одним представителем от каждой группы. Тем, кто взялся за задачу, но запутался в ней, можно предложить такие вопросы: «Может ли человек, говорящий «Я лжец», быть рыцарем?» (Почему?), «Может ли такой человек быть лжецом?» (Почему?) Так постепенно ребята начнут понимать, что никто из жителей острова не скажет о себе «Я лжец».

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

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

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

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

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

Задача 4. Необязательная. Здесь для кого-то из ребят может оказаться сложным понять, что требуется сделать в задаче. На самом деле все не так уж и сложно – последние бусины цепочки L должны совпадать с позициями одного из путей дерева С, но не любого, поскольку длина цепочки L задана. Мы надеемся, что к настоящему моменту ребята понимают связь между длиной цепочки партии, числом ходов и выигрышем определенного игрока. Например, в цепочке L – 9 позиций, значит, сделано 8 ходов и партия закончилась выигрышем Второго. Теперь ясно, что последней бусиной искомой цепочки может быть любой лист дерева С, расположенный на третьем уровне. Теперь осталось перенести в цепочку L позиции пути дерева С, ведущего в этот лист, и придумать начало партии (позиции до корневой бусины).

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

Изобразив дерево В, ребята должны нарисовать цепочки игр, в которых выигрывает определенный игрок. Подобные задания ребята выполняли и раньше (см. задачи 19, 31, 56 части 1). Здесь важно, чтобы ребята использовали именно дерево В. Для начала следует пометить уровни дерева В в зависимости от того, кто из игроков сделал ход (I или II). Тогда все листья, помеченные I – это заключительные позиции партий, в которых выиграл Первый, а все листья, помеченные II – это заключительные позиции партий, в которых выиграл Второй. Итак, на первый и второй вопросы ответ утвердительный, осталось в каждом окне нарисовать подходящую цепочку партии.
Ответ:

Задача 6. Необязательная. Ребятам уже встречались задачи, где, кроме целых клеток, исходная фигурка содержит половинки клеток. Отличие данной задачи в том, что фигура содержит нечетное число целых клеток (7), а значит, одну из целых клеток ребятам придется резать на половинки. Найти такую клетку можно при помощи перебора.
Ответ:

Задача 7. В этой задаче учащиеся должны быстро прийти к уже знакомой им идее полного перебора и начать методически резать цепочку на две части (ведь требуется построить цепочку цепочек длины 2). Неплохо, если они выберут какую-нибудь разумную стратегию: например, начнут с левого конца и будут двигаться, добавляя по одной бусине. Можно лишь отметить, что мы требуем здесь наличия предпоследней бусины у первой цепочки (значит, ее длина больше 1) и четвертой бусины у второй (значит, длина второй больше 3). Отсюда видно, что перебор совсем невелик – всего три варианта, пары следующей длины: (2, 6) (3, 5), (4, 4). При этом условию задачи удовлетворяет только второй вариант:

Задача 8. Необязательная. Возможно, кто-то из ребят вспомнит, что два одинаковых пути появляются в дереве в том случае, если у них на каждом уровне или одинаковые бусины, или общая бусина. Поэтому все листья, следующие за каждой одной бусиной второго уровня дерева Ф, должны быть различны. Значит, учитывая информацию, содержащуюся в таблице, за верхней и нижней бусинами второго уровня должны следовать красный и желтый листы, а за средней – красный, желтый и синий. Теперь оставшиеся 6 бусин нужно раскрасить в соответствии с таблицей в красный и желтый цвета так, чтобы начала всех путей (цепочки из первых двух бусин) были различны. Таким образом, нам подходят следующие три начала: красная – красная, красная – желтая и желтая – красная.

Скорее всего, ребята будут решать задачу методом проб и ошибок. Пробы можно осуществлять, помечая на бусинах карандашом цвета первыми буквами (К, Ж, С). Это не будет наглядно, зато в случае ошибки решение легко поправить. Если вы хотите сдвинуть кого-то «с мертвой точки», то попросите его для начала раскрасить бусины средней ветки, причем начиная с листьев. Далее можно обсудить полученный результат и дать возможность учащемуся закончить решение самостоятельно.

Задача 9. Несложная задача на раскрытие цепочки мешков. Все ребята должны уметь на данном этапе выполнять подобные задания самостоятельно, а также уметь отвечать на вопросы: «Сколько цепочек будет в мешке?», «Сколько бусин будет в каждой из цепочек?», «Будут ли в мешке одинаковые цепочки? Почему?»

Задача 10. Необязательная. Эта задача предназначена в основном для сильных учеников. Естественно, алгебраическим путем она решается очень быстро (например, с помощью уравнения). Однако, четвероклассники необходимыми для этого знаниями не обладают и могут дойти до ответа лишь логическим путем. Это потребует от них смекалки и мастерства. В этой задаче проще всего подтолкнуть учащегося к решению методом проб и ошибок или методом перебора. Например, предложите взять любой возраст дедушки и посчитать, сколько лет будет вместе дедушке и внучке. Пусть деду 50 лет, тогда внучке 50 месяцев (т. е. 4 года и 2 месяца), а вместе им 54 года и 2 месяца. Итак, возраст деда 50 лет нам не подходит – в сумме получается слишком мало. Возьмем возраст деда 80 лет (а внучке 80 месяцев), тогда вместе им 86 лет и 8 месяцев – это слишком много. Таким образом, дедушке больше 50 лет, но меньше 80. Этот интервал можно сокращать в ходе следующих проб, пока мы не дойдем до ответа. У кого-то из разумных детей может в ходе проб родиться одно дополнительное соображение – вместе деду и внучке 65 лет (целое число), значит, возраст внучки в месяцах должен делиться на 12 (быть равным целому числу лет). В таком случае в нашем интервале (от 50 до 80) подходящих чисел окажется всего 2.
Ответ: дедушке 60 лет.

Задача 11. В этой задаче мы начинаем готовить ребят к проекту «Стратегия победы». Для успешной работы с проектом необходимо: во-первых, уметь строить дерево игры, во-вторых, уметь это дерево анализировать. Отметим, что обычно при анализе дерева мы рассматриваем каждую отдельную позицию с точки зрения одного игрока – того, который должен делать ход (ведь именно он решает, как ему лучше пойти, чтобы выиграть). Просматривая дерево, мы пытаемся ответить на вопросы: «Какой ход игрока наверняка приведет его к победе, т. е. при любых дальнейших ходах противника?», «Какой ход наверняка приведет к проигрышу, а какой может дать и тот и другой исход?» Так и в жизни: нашим детям необходимо, с одной стороны, представлять все возможные выходы из данной ситуации, а с другой – оценивать вероятность выигрыша в каждой из них для себя и окружающих. Только в этом случае можно успешно обходить все рифы и мели. Например, ученик, обдумывая, когда выйти из дома, должен хорошо представлять себе: если он придет в школу за 15 минут до начала занятий, то наверняка не опоздает и его день начнется нормально; если влетит через 15 минут после звонка, то наверняка его день начнется с замечания в дневнике; если же войдет в школу со звонком, то возможно и то и другое в зависимости от ситуации (скорости бега до кабинета, возможной встречи с директором, настроения учителя и т. п.).

В задаче 11 ветка дерева игры в Ползунок уже построена. Нужно проанализировать дерево и ответить на вопросы задания. Сначала найдем и пометим (например, обведем) все заключительные позиции, в которых выигрывает Второй. Для удобства можно предварительно написать над каждым уровнем позиций I или II в зависимости от того, кто сделал последний ход, и найти все заключительные позиции, над которыми написано II. Видим, что таких позиций три.
Теперь рассмотрим по очереди последствия каждого из ходов А, Б и В Второго игрока. Пусть Второй сделал ход А. Как будет развиваться партия дальше? У Первого есть только один вариант следующего хода, и очередной ход Второго тоже один. Партия при этом заканчивается – Второй выиграл. Кажется, мы уже знаем ответ на первый вопрос задачи. Действительно, при ходе А дальнейшее развитие партии ясно, и выигрывает обязательно Второй. Осталось только убедиться, что это единственный ответ ходы Б и В нам не подходят.

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

Итак, ответ на первый вопрос – ход А, ответ на второй вопрос – ход Б.

Задача 12. Необязательная. Чтобы найти правильный ответ в данной задаче, нужно понять характер зависимости между величинами (число работников, время работы и ее объем). Для уяснения ситуации можно задать затрудняющемуся ребенку наводящие вопросы:

  1. За 2 часа 6 землекопов выроют больше или меньше ям, чем 3 землекопа? (Во сколько раз?)
  2. Сколько ям выроют 6 землекопов за 2 часа?
  3. За 6 часов 6 землекопов выроют больше или меньше ям, чем за 2 часа? (Во сколько раз?)

Ответ: 18 ям.

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


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

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

Задача 14. Необязательная. Здесь ребятам впервые придется разрезать фигуру больше, чем на две части. Как и раньше, в подобных задачах поможет подсчет клеток в фигуре, а затем в каждой из частей. Так ребята выясняют, что каждая из частей должна состоять из трех клеток. Если предположить, что все клетки целые (это в данном случае самое естественное), то вариантов форм для частей всего два – три клетки в ряд и три клетки «углом», причем в первом случае решение не выстраивается. Теперь методом проб и ошибок можно пытаться по-разному разместить 3 клетки «углом» в данной фигуре и найти ответ.
Ответ:


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

Задача 16. Необязательная. Построение дерева D – задача, знакомая ребятам, вряд ли здесь потребуется ваша помощь. Если кто-то все же затрудняется, используйте комментарии к задачам 1 и 5. Заметим, что дерево D – ветка дерева В из задачи 5. Мы пометили задачу как необязательную из-за второго задания, которое является, скорее, пропедевтическим. Второе задание вплотную подводит ребят к понятию выигрышной стратегии, которое будет рассматриваться дальше. Впоследствии мы будем говорить, что игрок имеет выигрышную стратегию, если он, следуя определенному правилу, может выиграть в любом случае, как бы ни играл противник. В данной задаче исход всей игры может быть предопределен первым ходом Первого. Так, если Первый на первом ходу возьмет 4 камешка, то обязательно выиграет Второй, если 3 камешка – обязательно выиграет Первый, если 1 – может выиграть как Первый, так и Второй. Таким образом, Первый, чтобы обязательно выиграть, должен взять 3 камешка. Цепочка, соответствующая такому ходу Первого: 5–2–1–0.

Решение компьютерных задач


Задача 520. В этой задаче нужно достроить ветку дерева игры в Ползунок из данной позиции. Для начала нужно выяснить, кто делает ход из корневой позиции. Оказывается – Первый, поскольку на поле в корневой позиции поровну красных и зеленых отрезков. Первый может сделать из корневой позиции 3 разных хода. Один из них приведет партию к заключительной позиции. Значит рисуем соответствующий ход там, где обозначен лист. Два других хода рисуем на позициях справа и слева от него и сразу же рисуем эти же ходы на следующих позициях. После этого дорисовываем позиции третьего уровня – соединяем зеленым последнюю возможную пару точек. Теперь все заключительные позиции третьего уровня помечаем зелеными галочками, а заключительную позицию второго уровня – красной галочкой.

Задача 521. В этой задаче нужно достроить ветку дерева игры в Сим из данной позиции. Аналогичная задача есть и бумажном учебнике (см. комментарии к бумажной задаче 13). При дефиците времени одну из этих задач можно пропустить или задачу 521 решить в классе, а задачу 13 предложить детям на дом.

Задача 522. Знакомая детям задача на построение дерева игры в Камешки (см. комментарии к бумажным задачам 1 и 5).

Задача 523. Как обычно, компьютерные возможности позволяют построить ветку из дерева игры гораздо быстрее, чем на бумаге. Так инструментально эта задача гораздо проще, чем бумажная задача 3. Что касается содержательной стороны, данная задача имеет свои сложности. Например, в библиотеке кроме нужных для решения содержатся еще лишние позиции. В корневой позиции имеется 3 пустые клетки, значит у нее будет 3 следующие позиции. Но в библиотеке 6 позиций с двумя пустыми клетками. Выбираем из них подходящие нам позиции и размещаем их в дереве и проверяем, нет ли среди них заключительных. Одна позиция оказывается заключительной, а для остальных снова ищем следующие позиции. Так продолжаем работу, пока ветка не будет построена. Затем выбираем заключительные позиции Первого и заключительные позиции Второго.