Уроки 20–21. Дерево выполнения программ

Материалы к урокам: лист определений «Дерево выполнения программ», бумажные задачи 48–53 (1 часть), компьютерный урок «Дерево выполнения программ» (задачи 483–488), занятие 6 на Клавиатурном тренажере.
На каждом из уроков по данной теме работа с бумажным учебником интегрируется с компьютерной составляющей. На первом уроке ребята изучают новый лист определений, решают две обязательные задачи и затем переходят к работе с Клавиатором. На втором уроке ребята решают компьютерные задачи уроков и дорешивают все оставшиеся задачи из бумажного учебника.

Дерево выполнения программ

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

Здесь речь пойдет о дереве возможностей выполнения программы Роботом. Часто Робот может выполнить все четыре команды из той клетки, где он находится. Единственное, что его ограничивает – это стены, внутренние и внешние. Ясно, что Робот может выполнить команду лишь в том случае, если на пути нет стены. Если учесть, что ветвления (варианты выбора) есть и на первом, и на втором, и на третьем (и т. д.) шагах, то возникает множество вариантов возможных путей Робота. Соответственно существует множество программ заданной длины, которые Робот может выполнить из данного начального положения. Учесть все варианты нам поможет дерево. В качестве бусин дерева мы берем не сами команды, а результаты их выполнения – получившиеся позиции.

Итак, цепочка позиций – это способ представить динамический процесс в виде статичной последовательности моментальных снимков. Дерево позиций – это способ фиксировать и различные варианты развития событий.
Понятие дерева выполнения программ, как и другие понятия, относящиеся к командам и процессам их выполнения, мы даем только на примере Робота и его фиксированной системы команд. Ясно, что эти понятия можно использовать и в более общей ситуации для любых исполнителей и систем команд.

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

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

  1. Почему дерево У имеет 5 уровней?
  2. Почему корневая бусина имеет две следующие?
  3. Почему самая нижняя бусина третьего уровня имеет одну следующую?
  4. Почему не во всех листьях дерева число заштрихованных клеток одинаково? И т. п.

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

Если ребята понимают, как построено дерево У, то написание программы Г их не затруднит, ведь из корневой позиции Робот может выполнить лишь одну из двух команд – «вверх» или «влево». Вторую команду конструкции повторения можно найти перебором по дереву. Например, в первое окно мы вписали «вверх». Далее Робот может выполнить команды «вправо» или «вниз». Пробуем выполнить каждую из получившихся программ Г и убеждаемся, что на данном поле выполнима лишь одна из них.

ПОВТОРИТЬ 2 РАЗА
вверх
вниз
КОНЕЦ

Если в первом окне записать команду «влево», то получаем также лишь одну возможную программу Г.

ПОВТОРИТЬ 2 РАЗА
влево
вправо
КОНЕЦ

Задача 49. Ребята, разобравшиеся в листе определений, такую задачу решат без труда. Если у кого-то из учеников возникнет заминка, то побеседуйте с ним о возможностях выполнения команд Роботом. Понятно, что если Робот стоит на безграничном поле, то он в любой момент может выполнить любую из своих четырех команд. Но нам дано ограниченное поле сложной формы. Поэтому первый ваш наводящий вопрос может быть таким: «Какие команды может выполнить Робот в начальной позиции?» Оказывается, что лишь одну – «вниз», ведь в начальной позиции с трех сторон от Робота – стены. Значит, после корневой бусины следует лишь одна позиция. Далее можно спросить: какие команды может выполнить Робот из клетки, куда он переместился? Их три: «вправо», «вниз» и «вверх», ведь стена теперь лишь слева. Рисуем возможные позиции. Теперь для каждой из трех позиций проводим аналогичные рассуждения. Получаем следующее дерево Ш.


Задача 50. Здесь ребятам вновь придется вспомнить операцию, обратную склеиванию, и «разрезать» цепочку на 2 части. При этом необходимо обеспечить истинность утверждения в рамке. Задача упрощается тем, что в слове СТОЛОВАЯ только две одинаковые буквы, очевидно, о них и идет речь в утверждении.

Задача 51. Подобных задач, где необходимо собрать из фигурок цепочку, используя условия с конструкциями «перед каждой» и «после каждой», в 3 классе ребятам приходилось решать довольно много. Как всегда, один из способов решения таких задач – собрать цепочку из кусочков удовлетворяющих одному из условий (частичных решений). В данной задаче это получится достаточно легко, ведь отрезки цепочки не связаны между собой и нет лишних букв. Из первого утверждения появляется кусок цепочки Y – R, а из второго – кусок цепочки Q – … – W. Вообще, данную цепочку легко составить, начиная с любой Y или W. При этом нужно принимать во внимание, что Y не может быть последней бусиной в цепочке, а W не может идти в цепочке раньше третьей бусины (иначе утверждения не будут иметь смысла). В 3 классе при решении подобных задач мы советовали ребятам воспользоваться телесными объектами – вырезать фигурки с листа вырезания, сложить на столе, а уже затем соединить фигурки, данные в задании, в одну цепочку. На данном этапе мы считаем полезным для ребят некоторые действия с объектами проводить уже в уме, но если вы считаете, что для кого-то это сложно, заготовьте несколько наборов букв из этой задачи. Данная задача является также хорошим поводом повторить латинский алфавит. Спросите ребят, как называются буквы, встречающиеся в задаче, какая буква идет раньше в латинской алфавитной цепочке и т. п.

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

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


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

МОЛОКО + МОЛОКО + ТВОРОГ = 38 р.
ТВОРОГ + ТВОРОГ + МОЛОКО = 34 р.

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

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

Задачи 483 и 484. Задачи на построение дерева выполнения программ, аналогичные бумажной задаче 49. Однако компьютерные возможности позволяют выполнить подобные задачи быстрее. Брать позиции из библиотеки гораздо легче, чем вырезать, наклеивать и раскрашивать. При этом содержательно задачи не проще задачи 49. Как видите, мы умышленно дали в библиотеке позиций с избытком. Среди них много неподходящих позиций. Чтобы выделить нужные позиции ребятам необходимо разбираться в материале.

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

Задача 486. Задача на повторение темы «Все пути дерева».
Ответ: ТАЕТР ТЕКСТ ТЕКСТУРА ТЕКУЧИЙ ТЕЛО ТЕЛОК ТЕМА ТЕМП

Задача 487. Знакомая ребятам задача (см. комментарии к задачам 452, 474), предоставьте всем учащимся возможность справиться с ней самостоятельно.

Задача 488. Необязательная. Аналогичные задачи, как мы уже говорили, имеют комбинаторный характер. Однако дети, как правило, решают их методом проб и ошибок, без всякого перебора, что нередко приводит к успеху. Даже если дети в таких задачах и проводят какие-то рассуждения, то больше из соображений здравого смысла, чем классической математики. Например, в данной задаче ясно, что цвета в ходе решения совершенно равнозначны. Улиток всего 9, в каждой по 2 области. Значит можно раскрасить одну из областей (например, раковину) у трех улиток в красный цвет, у трех – в синий, у трех – в зеленый. Теперь у каждых трех улиток, у которой раковина раскрашена одинаково, нужно тело раскрасить по-разному. Тогда все фигурки будут разными.