Уроки 18–19. Робот. Цепочка выполнения программы

Материалы к урокам: лист определений «Робот. Цепочка выполнения программы», бумажные задачи 39–47 (1 часть), компьютерный урок «Цепочка выполнения программы» (задачи 478–482), занятие 5 на Клавиатурном тренажере.

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

Цепочка выполнения программы

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

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

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

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

Задачи 39–40. По характеру выполняемых действий это задачи знакомые – задача 39 на выполнение программы, а задача 40 на написание программы. Поэтому для их выполнения достаточно понимания того, что такое цепочка выполнения программы.
Ответ (к задаче 39):


Ответ (к задаче 40):

вверх
влево
вправо
вверх
вправо

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

Задача 42. Это одновременно упражнение на закрепление нового листа определений «Робот. Цепочка выполнения программы» и задание на выполнение программы для Робота с неизвестным начальным положением (подобные задачи уже были раньше). Главное здесь – определить, из какой клетки начал движение Робот. Для этого можно воспользоваться одним из подходов, знакомых нам еще из 3 класса: либо последовательно проверять все клетки поля, как возможные начальные положения, отбрасывая при этом неподходящие (например, вычеркивая их), либо выполнить программу на клетчатой основе и заштрихованную Роботом фигуру поместить в поле. Поскольку в данном случае поле – прямоугольник, то второй подход делает решение задачи совсем простым. Поэтому второй подход можно посоветовать слабому ученику, если он запутался. Остальных детей лучше, как всегда, «отпустить в самостоятельное плавание».

Особенностью данной задачи является прямоугольное поле, значит, возможность, например, горизонтального движения Робота не зависит от вертикального движения. Поэтому можно отдельно устанавливать начальное положение по командам вверх-вниз и вправо-влево. Например, цепочка команд по вертикали «вниз, …, вверх,…, вверх, ..., вниз» позволяет сделать вывод, что в начальный момент Робот находился на второй строке. А цепочка команд по горизонтали «..., влево, ..., вправо,…, вправо, вправо,…» говорит о том, что Робот начал движение в клетке второго столбца. Теперь задача становится совсем простой – надо вырезать с листа вырезания и наклеить в цепочку столько полей, сколько команд в программе (ведь одно поле для начальной позиции уже есть), и раскрасить клетки.
Ответ:


Задача 43 – несложная, но полезная. Она приводит к необходимости выполнить операцию, обратную склеиванию цепочек. Решений у данной задачи, конечно, много. Поэтому мы не будем приводить здесь возможные варианты ответа. Тем детям, кто справился с решением этой задачи очень быстро, можно предложить нарисовать цепочку-решение заданной длины (например, длины 7 или 12) или попросить выяснить, является ли решением нарисованная вами цепочка.

Задача 44. Необязательная. В ходе решения этой задачи ребята повторяют понятие уровни дерева. Однако наиболее сложным здесь оказывается обеспечить истинность утверждения в рамке, ведь бусины из мешков A, B, C, D можно просто нарисовать сразу на соответствующих уровнях.

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

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


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

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

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

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


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


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


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

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

Задача 479. Самый первый шаг в решении этой задачи – выяснить положение Робота в начальной позиции. Это оказывается не слишком сложно, поскольку среди закрашенных клеток имеется лишь одна, из которой можно выполнить две команды «вправо». После того как нужная клетка найдена, задача становится аналогичной бумажной задаче 39.

Задача 480. Задача на повторение деревьев и «древесной» лексики. Аналогичных задач в курсе 3 класса ребята решали достаточно. Подходящих решений здесь довольно много. На четвертом уровне дерева всего две бусины – два листа. На третьем уровне в силу первого утверждения может быть по 3 или 4 бусины, ведь на каждом уровне должно быть по два листа, а также должны быть бусины, предыдущие перед листами 4 уровня. Однако на третьем уровне все бусины синие, а разных синих бусин у нас всего три. Поэтому на третьем уровне ровно 3 бусины. Это означает, что на втором уровне бусины может быть от трех до пяти.

Задача 481. Как видите, путей в дереве гораздо меньше, чем слов в Словарике. Чтобы понять, какие слова будут в дереве, нужно определить сначала корневые буквы. Ясно, что это не П и не Н, поскольку на эти буквы слов слишком мало. Значит корневые бусины – буквы М и С. Чтобы понять, где какая буква, заметим, что в одной из веток все слова должны иметь две общие начала, состоящие из двух букв. В словаре у нас имеется 4 слова на МА. Так мы находим место для корневой буквы М. Дальше достроить пути дерева оказывается несложно.

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