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

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

Теперь есть два варианта: можно начинать строить дерево снизу вверх, от корня к листьям, или, наоборот, от листьев к корню. В любом случае надо работать сначала на черновике.

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

Уровень 1. В нашем случае последнее, 4-е, действие — сложение. Значит, корневая вершина должна быть помечена как результат сложения.

Уровень 2. Какие числа мы складываем в 4-м действии? Складываем два числа: одно — результат деления (2-е действие), другое — тоже результат деления (3-е действие). Поэтому на втором уровне должны находиться две вершины, помеченные как результаты деления. На рисунке мы пока для простоты поставим в окнах знаки деления и умножения, мы же работаем на черновике. При перерисовывании набело в тетрадь нужно будет эти вершины пометить так, как договорились, а в самих вершинах написать результаты действий. Вот что у нас получилось:

Уровень 3. Одна вершина второго уровня (вообще говоря, любая из двух, но правильнее — левая) у нас соответствует 2-му действию, где мы делим результат сложения (1-е действие) на 3. Поэтому следующими после этой вершины второго уровня будут «результат суммы» и 3. Вторая (правая) вершина второго уровня соответствует результату деления 72 и 8, вот почему следующие за ней вершины — 72 и 8. Данные в примере числа — всегда листья в дереве вычислений, поэтому можно сразу выпустить из них стрелки.

Уровень 4. Остались незадействованными только слагаемые 24 и 6, они расположены на четвёртом уровне и следуют после вершины-суммы третьего уровня. Построение дерева завершено.

2. От листьев к корню. Выпишем все числа данного в задаче арифметического выражения по порядку. Это будут листья дерева. Конечно, наверняка все листья не будут расположены на одном уровне. Но мы же работаем на черновике и поэтому имеем некоторую степень свободы (потом перерисуем и исправим).

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

Выполняем 2-е действие. То, что получилось сейчас, конечно, является неправильно нарисованным деревом — вершины расположены не на своих уровнях. Но исправим это потом. Сейчас для нас главное — общая структура дерева.

Выполняем 3-е действие.

Выполняем последнее, 4-е, действие, рисуем корневую вершину.

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

Осталось перерисовать дерево в тетрадь. При этом нужно не забыть соблюсти обозначения арифметических действий и заполнить дерево — вычислить значение выражения. Вычисляем значение выражения в примере, а затем сравниваем результаты (в обоих случаях должно получиться 19).

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

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

Задача 138. Необязательная. Как и в других подобных задачах, здесь можно воспользоваться методом перебора, т. е. последовательно заставлять Робика выполнять программу из разных клеток поля. Заметим, что на поле есть «изолированные» клетки, окружённые со всех сторон стенами, они в качестве начальных положений Робика не подойдут. Далее можно отбросить клетки, стартовав из которых Робик не сможет выполнить очередную команду программы. Специфику перебора подсказывает сама программа. Сначала отбрасываем все клетки, из которых Робик не может сделать два первых шага — влево, влево, и вычёркиваем их крестом.

Затем замечаем, что Робик на протяжении всей программы 4 раза выполняет команду «вниз» и только потом один раз — команду «вверх», поэтому необходимо отбросить те строчки, из клеток которых невозможно выполнить 4 команды «вниз» (это 4 нижние строчки).

Осталось 12 возможных начальных позиций. Их придется честно проверить — запустить Робика выполнять программу начиная с каждой из этих клеток. В результате получаем единственно возможное решение:

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

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

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

Задача 139. Необязательная. Больше всего данная задача напоминает задачу 128. Четыре данных в этой задаче утверждения в точности описывают мешок букв (четырёхбуквенного) слова. Таким образом, задача состоит в построении дерева всех разных слов длины 4 из букв данного мешка, причём в мешке букв есть две одинаковые буквы У. Необходимо обратить внимание учащихся на то, что все пути должны быть разными, и попросить ребят подумать, как при построении дерева можно обеспечить отсутствие одинаковых путей.

Есть прямой путь решения: построить сначала полное дерево всех слов длины 4 из букв А, З, У и У. Назовем это дерево R (оно приведено ниже). Затем, рассмотрев это полное дерево, нужно найти пары одинаковых путей (таких пар будет 12) и пометить (вычеркнуть) по одному пути из каждой такой пары. Останется ровно 12 путей, как и требуется в условии задачи. Теперь, пользуясь деревом R, нужно постараться аккуратно нарисовать искомое дерево, не рисуя зачёркнутых путей. Вычёркивать пути нужно аккуратно и внимательно — необходимо проследить, чтобы случайно не выкинуть нужные пути.

С другой стороны, рассматривая полное дерево, можно попытаться понять закономерность, как именно нужно строить дерево, чтобы в нём не оказалось одинаковых путей. Этот вопрос уже обсуждался в задаче 128. Напомним выводы, к которым мы при этом пришли: все вершины, следующие за одной вершиной, должны быть разными. Также все корневые вершины должны быть разными. Вот дерево, построенное с соблюдением этой закономерности, и мешок его путей (дерево Q и мешок J).

Несмотря на сложность этой задачи, не стоит помогать детям чрезмерно. Даже если кто-то из ребят поначалу проигнорирует условие различности путей и станет строить дерево так же, как на листе определений «Дерево всех вариантов», в конце концов он сам заметит что-то неладное. Во-первых, листьев у него будет не 12, во-вторых, выписывая цепочки, учащийся увидит, что не все они различны. Вот на этом этапе можно обсудить с таким учеником, почему появились лишние цепочки и что нужно из дерева убрать.

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