Урок 59. Дерево раскрытия цепочки мешков

План урока

      1. Работа с листом определений «Дерево раскрытия цепочки мешков».
      2. Решение обязательных бумажных задач 63, 66, 67.
      3. Решение необязательных бумажных задач 68, 70.
      4. Решение компьютерных задач 427–431.

Лист определений «Дерево раскрытия цепочки мешков»

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

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

Решение обязательных бумажных задач

Задача 63. Раскрытие цепочки мешков без использования дерева предполагает сложный процесс перебора в уме. Рисование дерева, хотя и требует определенных усилий и времени, зато делает перебор видимым. Дерево есть способ статического, одновременного представления процесса, в данном случае – процесса раскрытия цепочки. После изучения листа определений полезно вернуться к задачам 57 и 58. Учащиеся вспомнят, что основная проблема, которая обсуждалась в этих задачах – как ничего не пропустить и не написать лишнего. Хорошо, если учащиеся сами скажут, что дерево раскрытия цепочки мешков – универсальный способ решения данной проблемы, и объяснят почему. Все появляющиеся возможности мы сразу изображаем на дереве, поэтому ничего не теряем.

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

Вторую часть задачи – «раскрась бусины в цепочках мешка…» – можно считать задачей на повторение.
Ответ:

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

Задача 67. В мешке есть одинаковые слова, значит, в одном из мешков цепочки V (или в нескольких) должны быть одинаковые буквы. Необходимо понять, в каком мешке они лежат. Скорее всего, ребята не будут так глубоко в это вдумываться и пойдут по привычному пути: напишут в первом мешке цепочки букву П, во втором – И, в третьем – Р, в четвертом – О, в пятом – Г. Проблемы возникнут лишь в том случае, если в шестом мешке учащийся напишет только четыре буквы: Е, А, И, У. Попросите его раскрыть полученную цепочку. Тогда ребенок поймет, что букв в последнем мешке должно быть столько же, сколько слов в ⊗V, и допишет недостающие буквы. Возможна и другая крайность – учащийся напишет в какой-то из мешков (может быть, и не в шестой) лишние буквы. Совет тот же, попросите его раскрыть цепочку и обсудите, почему цепочек в мешке оказалось гораздо больше, чем нужно.

Решение необязательных бумажных задач

Задача 68. Не все окна заполняются однозначно, да и сами мешки, которые получатся, возможно, будут разными.
Однозначно заполняются окна в четырех словах:

Остальные слова делятся на группы в соответствии с количеством букв, идущих перед НИБУДЬ.
Три буквы (КЕМ-, КТО-, ЧЕЙ-, ЧЕМ-, ЧТО-):

Четыре буквы (КОГО-, КОМУ-, КУДА-, ЧЕГО-, ЧЕМУ-):


Пять букв (КАКОЙ-, КОГДА-):


Шесть букв (ОТЧЕГО-, ПОЧЕМУ-):


Когда мы все выписали, шестибуквенные слова восстанавливаются однозначно, для двух пятибуквенных есть два варианта. Среди четырехбуквенных слов КОМУ- и КОГО- восстанавливаются однозначно, а для пары ЧЕГО-/ЧЕМУ- есть два варианта. Вариантов заполнения трехбуквенных есть довольно много.

Если кто-то запутался совсем, то попросите найти его в мешке слово, определяющееся однозначно, например, КАК-НИБУДЬ или ОТКУДА-НИБУДЬ (первое и второе слова сверху). Глядя на то, как ученик работает, вы легко поймете, в чем причина ошибок. Скорее всего, ребенок забыл, что дефис – отдельный символ и должен занимать при заполнении окон отдельную бусину. Посоветуйте такому ученику сначала заполнить все окна, соответствующие дефисам (перед частицей НИБУДЬ), а затем приступить к дальнейшей работе.

Задача 70. Ответ: первое и второе утверждения ложны, третье – истинно.

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

Задача 427. Задача на закрепление нового листа определений, аналогичная бумажной задаче 63. В случае дефицита времени слабым детям можно ее пропустить или наоборот, решить эту задачу, а задачу 63 решить дома.

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

Задача 429. Знакомая ребятам задача на отработку конструкции повторения для Робота (см. комментарии к компьютерным задачам 416, 423).

Задача 430. Еще одна задача на построение дерева раскрытия цепочки мешков. Элементами мешков здесь являются буквы, но алгоритм от этого нисколько не меняется. На первом уровне должны находиться две буквы из первого мешка – А и Б. У каждой из них будет лишь одна следующая, поскольку во втором мешке лежит лишь одна буква – буква В. У каждой буквы В второго уровня будет три следующие – буквы Г, Д и Е. Так дети будут двигаться от первого уровня до последнего, пока все окна не окажутся заполненными. При этом сильным детям заранее будет ясно, что все листья этого дерева – буквы И, ведь в последнем мешке всего одна буква.

Задача 431. Необязательная.
Ответ: МОНЕТА – НЕМОТА
             ПРАВО – ПОВАР
             ЛОСЁНОК – ОСЛЁНОК
             КОЛОСОК – ОСКОЛОК

Урок 60. Дерево раскрытия цепочки мешков

План урока

      1. Решение обязательных бумажных задач 64, 65, 71, 77.
      2. Решение компьютерных задач 432–436.
      3. Решение необязательных бумажных задач 73, 74.

Решение обязательных бумажных задач

Задача 64. Большинство ребят уже понимают закономерности операции раскрытия цепочки мешков. Например то, что на первом, третьем и четвертом месте всех цепочек мешка будут стоять одни и те же буквы (К, Ш, К). Кроме того, учащиеся смогут посчитать, сколько цепочек должно быть в мешке. Если при решении предыдущей задачи подобные вопросы обсуждались, то проблем не возникнет, если нет – обсудите их здесь. Итак, должно получиться шесть цепочек, поэтому в мешке ⊗Y можно сделать сразу шесть заготовок типа К–...–Ш–К–...

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

Теперь дописываем последние буквы (А, Е или И) к цепочкам так, чтобы все они стали разными (в данном случае одинаковых цепочек в мешке быть не должно).
Ответ:      КАШКА                     КОШКА
                  КАШКИ                     КОШКИ
                  КАШКЕ                     КОШКЕ

Задача 65. Задача содержит новую деталь – в одном из мешков все три бусины одинаковые. Главное, что должны понять ребята при решении задачи, – наличие одинаковых бусин в мешке не изменяет способа построения дерева, числа веток, листьев и т. д., а влечет лишь появление одинаковых путей. При построении дерева раскрытия цепочки мешков работает одно и то же правило: каждая бусина имеет ровно столько следующих бусин, сколько лежит в следующем по счету мешке цепочки. Раскрасив бусины в мешке ⊗Ф, ребята смогут еще раз убедиться в том, что наличие одинаковых бусин в мешках цепочки ведет к появлению одинаковых цепочек в мешке.
Ответ:


Задача 71. Тем, кто запутался, можно предложить следующие наводящие вопросы: «Сколько бусин-мешков должно получиться в цепочке?» (Две, ведь в каждом числе два знака, а при составлении числа нужно взять по одной цифре из каждого мешка.) «Что должно находиться в первом мешке?» (Цифра 2, ведь у всех чисел от 20 до 29 первая цифра одинаковая – 2.) «Какие цифры должны лежать во втором мешке, чтобы при раскрытии получить все числа от 20 до 29?» (Цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.)
Задача устанавливает еще одну связь между миром цепочек и миром чисел. В предыдущих задачах мы уже столкнулись с тем, что операция раскрытия цепочки мешков может применяться к заданию разных форм одного слова. В данной задаче мы видим аналогию этой конструкции с построением десятичных чисел.
Ответ:

Задача 77. В формулировке задания появилось отрицание: «…нет мешка с двумя одинаковыми бусинами». Это вызовет дополнительные трудности при решении. Главное – не спешить, все аккуратно отмечать и время от времени снова читать условие задачи.
Рекомендуем поставить прямо в задании рядом с каждым словом «мешок» пометку – внутренний или внешний. Получаем фразу: «Отметь галочкой мешок (внешний), в котором нет мешка (внутреннего) с двумя одинаковыми бусинами». Проверяем выполнимость этого утверждения для каждого мешка. В первом большом мешке есть мешок (второй) с двумя одинаковыми бусинами – значит, он не подходит. Аналогично проверяем утверждение для второго мешка. Убеждаемся, что в его третьем внутреннем мешке есть две одинаковые бусины; значит, он тоже не подходит. Продолжая перебор, выясняем, что условию удовлетворяет третий большой мешок. Нужно просмотреть и четвертый большой мешок – проверить, что он не удовлетворяет условию.

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

Задача 432. Задача на закрепление нового листа определений, аналогичная бумажной задаче 65. В случае дефицита времени слабым детям можно ее пропустить или наоборот, решить эту задачу, а задачу 65 решить дома.

Задача 433. Похожую задачу (компьютерную задачу 417) ребята уже решали. Эта задача немного отличается. Все слова в Словарике на одну букву, значит корневую букву вписать легко – это буква К. Дальше будем работать с каждой веткой в отдельности. Например, рассмотрим левую ветку. В ней всего два пути. Это два слова, начала которых (первые три буквы) совпадают. При этом одно слово из четырех букв, а другое – из шести. Перебирая слова из словаря, находим два подходящих слова – КИЛЬ и КИЛЬКА. Теперь аналогично работаем с правой веткой.

Задача 434. Аналогичных задач ребята решали довольно много. Однако здесь ситуация довольно затейливая. Как видите, внутренних команд в конструкции повторения довольно много, это затрудняет анализ программы с целью уменьшения перебора, а полный перебор всех клеток поля достаточно велик. Тем не менее слабые дети, скорее всего, будут перебирать все клетки или почти все. Их не нужно отговаривать, разве что вы захотите поговорить с ними о стратегии сужения круга клеток поля. Кто-то из детей все же попытается проанализировать программу. Действительно, в результате выполнения внутренних команд цикла Робот смещается по вертикали на 1 клетку вниз, а по горизонтали на 2 клетки вправо. Поскольку эти команды повторяются 4 раза, то можно отбросить 4 нижних строки и 8 правых столбцов клеток поля, что уменьшит перебор до двух клеток. Кто-то из сообразительных детей, возможно догадается выполнить целиком все внутренние команды цикла, а затем полученный рисунок разместить на поле 4 раза, учитывая положение Робота в конце каждого цикла.

Задача 435.  Эта задача явно ставит перед ребятами вопрос, над которым многие возможно еще не задумывались – вопрос об особенностях дерева раскрытия цепочки мешков. Действительно, не любое дерево может быть деревом раскрытия цепочки мешков. Во-первых, все пути такого дерева одинаковой длины. Во-вторых, все бусины одного уровня имеют одинаковые мешки следующих за ними бусин. Поэтому если кто-то из ребят вначале захочет расставить буквы в дереве наугад, а затем построить цепочку мешков, скорее всего, задачу он решить не сможет. С другой стороны, напечатать в цепочке любые буквы в любом количестве, а затем пытаться достроить дерево тоже не получится. Тем не менее, начинать лучше с цепочки, но при этом принимать во внимание структуру дерева. Итак, в дерева 2 корневые бусины. Это значит что в первом мешке цепочки ровно 2 буквы, вписываем туда две любые буквы. У каждой из этих букв ровно две следующие, значит во втором мешке цепочки также две буквы, заполняем второй мешок. Так двигаемся до конца цепочки. Теперь остается раскрыть получившуюся цепочку мешков и заполнить окна в дереве.

Задача 436. Задача на повторение листа определений «Перед каждой бусиной. После каждой бусины», аналогичная компьютерной задаче 397.

Решение необязательных бумажных задач

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

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

Урок 61. Дерево раскрытия цепочки мешков

План урока

      1. Решение обязательных бумажных задач 69, 72, 75, 80.
      2. Решение необязательных бумажных задач 76, 78, 79.
      3. Проект «Дневник наблюдения за погодой», подведение итогов за апрель.

Решение обязательных бумажных задач

Задача 69. До этого момента мы решали задачи только на построение всех объектов, удовлетворяющих какому-то условию, а затем их пересчитывали, если того требовало задание. В данном случае задача другая: провести такие рассуждения и вычисления, которые позволили бы, не рисуя дерево, сосчитать количество цепочек в мешке. Число путей дерева раскрытия цепочки мешков равно произведению чисел, равных количеству бусин в мешках исходной цепочки мешков. В данном случае 5•1•2=10 путей.

Задача 72. Идея произвольного сочетания различных слов во фразе была широко распространена еще в Средние века. (Один из ее отголосков присутствует в «Путешествиях Гулливера» и часто цитируется историками информатики.) Постройте вместе с детьми такую комбинаторную «машину», где можно будет произвольным образом выбирать подлежащее, затем сказуемое, затем дополнение и т. д., получая неожиданные эффекты.

Задача 75. Подобную задачу дети уже решали, только для двузначных, а не для трехзначных чисел. Если у кого-то возникли трудности, то отошлите его к задаче 71. Пусть вспомнит, как решал подобную задачу в прошлый раз.
Ответ:

Задача 80. В случае затруднения предложите начать с какого-нибудь одного слова, например, со слова ДЫМ.
Правильных ответов здесь довольно много, поскольку на дерево L не накладывается никаких условий, кроме того, что мешок его путей должен совпадать с мешком U. Конфигурация такого дерева может быть самая разная, в частности, подойдет и дерево, имеющее 9 корневых букв Д, где каждое слово расположено на отдельной «ветке». В таком случае дерево будет иметь 33 бусины.

Кто-то захочет экономить, нарисовав на каждом уровне вместо нескольких одинаковых бусин одну, как на деревьях на листах определений. Самое экономное дерево будет иметь 18 бусин и выглядит как на рисунке.
Обратите внимание, что на букве Ш нельзя сэкономить, придется поставить ее на третьем уровне дважды, поскольку в одном пути она является листом, а в другом – имеет следующую букву.

Ответ:

Решение необязательных бумажных задач

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

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

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

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

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

Задача 78. Напомните детям, что выражение «чтобы Робот смог выполнить программу» означает, что Робот сможет дойти до конца программы, ни разу не попытавшись выйти за границы поля. На листе определений мы писали, что, если Роботу нужно пройти через границу, он ломается.

Начав выполнять внутренние команды первого цикла, ученик понимает, что их можно выполнить два раза. После этого Робот попадает в клетку, из которой невозможно движение вверх. Значит, в первом пустом окошке нужно написать 2 (1 в конструкции повторения использовать просто бессмысленно – к чему тогда конструкция?). Аналогично анализируем следующую конструкцию повторения. Есть лишь одна клетка на текущей строке, из которой можно будет потом выполнить команды вверх и вправо хотя бы один раз. До этой клетки Робот должен сделать три шага влево, значит, во втором окне ученик пишет 3 и т. д. Таким образом получаем единственный правильный ответ – в пустые окна необходимо вписать соответственно 2, 3, 2. Остается дорисовать позицию Робота после выполнения программы, то есть убедиться, что Робот действительно сможет ее выполнить.

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

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

Можно также составить цепочку из нескольких мешков. В таком случае сначала нужно решить, какое именно слово в четырех экземплярах будет лежать в мешке ⊗К. Пусть это будет, например, слово ГУСЬ. Затем нужно решить, какая именно буква будет повторяться в мешке 4 раза – это совершенно все равно, но нужно выбрать одну. Пусть это будет первая; тогда получим такую цепочку:

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

Проект «Дневник наблюдения за погодой», подведение итогов за апрель