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

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

Задача 87. Необязательная. Данная задача — сказочный аналог игры «камешки». В переводе на игровой язык она будет выглядеть так: «В начальной позиции 9 камешков, за один ход игрок может брать 1, 2 или 3 камешка. Найдите выигрышную стратегию для Первого». В данной игре выигрышную стратегию одинаково удобно искать с опорой как на числовую линейку, так и на дерево. Мы предлагаем детям построить дерево, поскольку хотим, чтобы они описали выигрышную стратегию пошагово, а это удобнее делать по дереву. Чтобы детям было легче сформулировать ответ, мы предлагаем шаблон, в который ребята должны вставить только числа. Главная сложность этой задачи в том, что дерево будет достаточно большим. Ребятам лучше заранее спланировать его на черновике, чтобы потом правильно разместить в окне.

Задача 88. Необязательная. В курсе 2 класса ребятам приходилось решать довольно много подобных задач, где необходимо собрать из фигурок цепочку, используя условия с конструкциями «перед каждой» и «после каждой». Как всегда, один из способов решения такой задачи — собрать цепочку из кусочков, удовлетворяющих одному из условий (частичных решений). Из первого утверждения появляется кусок цепочки R — Y, а из второго — кусок цепочки W — … — … — Q. Эти два частичных решения легко скомбинировать и между собой, получается цепочка W — R — Y — Q. Из данного набора таких цепочек можно построить две. Оставшиеся буквы можно выстроить в цепочку, используя только второе утверждение.

Задача 89. Задача на повторение операции склеивания мешков, аналогичная задаче 81.

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

Задача 91. Необязательная. Решение — в быстром поиске в мешке слова с очередной второй буквой (А, Б, В, Г...). Задача решается однозначно, даже если не обращать внимания на словарный порядок. Но с учетом словарного порядка она решается гораздо быстрее.

Уроки «Дерево вычисления»

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

Примерно так же, в виде дерева, можно представить процесс приготовления кулинарных блюд, где постепенное соединение ингредиентов по парам или группам (и их последующее смешивание, варка, жарка и пр.) приводит на каждом шаге к появлению одного полуфабриката, а в итоге — к появлению некоторого блюда. Аналогично можно представить процесс сборки различных механизмов и т. п.

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

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

Решение задач 92—104 из учебника

Задачи 92 и 93. Впервые в курсе встречаются задания, которые несут вычислительную нагрузку. Естественно, кому-то из ребят это понравится, кому-то нет. Для учителя такие задания могут стать хорошим поводом для организации интегрированных уроков с уроками математики — занятий на отработку вычислительных навыков. В дальнейшем подобные задания можно использовать на уроках математики для упражнений в устном счёте. Мы старались, чтобы вычисления, необходимые при решении подобных задач, были нетрудными: основная нагрузка задания состоит не в том, чтобы вычислить значение выражения, а в том, чтобы научиться правильно работать с деревом вычисления.

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

Заметим, что в вычислении значения выражения по дереву ошибиться в порядке действий гораздо сложнее, чем в примере. Действительно, ребенок просто не сможет по дереву начать с того действия, которое нужно выполнить позже, так как в соответствующих вершинах пусто, а все те действия, которые можно выполнить сразу (в вершинах есть нужные числа), на самом деле допускают различный порядок выполнения. Так, например, в дереве Т можно сначала выполнить действия с числами 24 и 10, затем с числами 96 и 84, а можно поступить наоборот. В дереве S можно сначала выполнить действия с числами 46 и 14, а затем с числами 80 и 16 либо наоборот. Если кто-то из ребят спросит вас о последовательности действий, то обсуждать это лучше в индивидуальном порядке. С сильным ребёнком можно обсудить общее правило порядка вычисления по дереву. Оно несложное: сначала выполняются действия предпоследнего уровня (на последнем уровне всегда только листья, и там ничего вычислять не нужно), затем предыдущего и т. д., пока мы не дойдём до корневой вершины. Причём если на одном уровне находится несколько действий, то порядок их выполнения может быть любым (порядок не влияет на результат). Для слабого ребёнка при этом опора на правила порядка действий может оставаться единственной возможностью найти правильный ответ в примере, поэтому его не стоит запутывать. Если такой ребёнок вас спросит, в какой последовательности надо выполнять действия на одном уровне, то можно сказать, что, как обычно, слева направо.

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

Ответ:

Задачи 94 и 95. Эти задачи сложнее задач 92 и 93, здесь надо заполнить не только цветные окна в дереве, но и белые: расставить числа, входящие в пример. Например, на предпоследнем уровне дерева К есть два зелёных окна, значит, две следующие за каждым из них вершины должны участвовать в сложении. Но в примере два сложения в скобках. Чтобы разобраться, какие числа вписывать в какие белые окна, полезно посмотреть, что с результатами сложений будет происходить дальше, — обратить внимание на цвет окон второго уровня. Вы, наверное, увидите, что некоторые дети впишут числа в листья быстро, почти не задумываясь. Это не случайно, так как мы стараемся выстраивать листья в дереве слева направо, так же как числа в записи примера.