Урок 38. Все пути дерева

План урока

      1. Работа с листом определений «Все пути дерева».
      2. Решение обязательных бумажных задач 14–16.
      3. Решение компьютерных задач 393–397.
      4. Решение необязательной бумажной задачи 18.

Работа с листом определений «Все пути дерева»   

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

Как обычно, дети должны работать с этим листом определений самостоятельно. В конце можно спросить ребят, как построить все пути дерева – пусть сформулируют ответ в виде пошагового алгоритма, например, такого: 1. Взять лист дерева и пометить его галочкой (можно сначала карандашной). 2. Построить путь ведущий в этот лист. 3. Пометить лист жирной галочкой. 4. Взять еще не помеченный лист и т. д. Можно вообще не обсуждать данный лист определений (если, конечно, у детей не возникли вопросы). В этом случае алгоритм построения всех путей дерева вы сможете обсудить в ходе решения задач либо фронтально, либо индивидуально с теми ребятами, у которых возникли проблемы в процессе решения задачи.

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

Задача 14. Самый рациональный способ действия следующий. Находим свободный лист, двигаясь от конца, выписываем путь, ведущий в него, затем помечаем этот лист, чтобы по ошибке не выписать этот же путь еще раз. Вместо пометок можно сразу соединять лист с соответствующим путем. Хорошо пользоваться некоторой системой движения по листьям, например, перебирать их сверху вниз.
Ответ: ВАС, ВАША, ВЕК, ВЫ, ВОЛ.

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

Задача 16. Некоторые сложности могут быть связаны с толкованием третьего слова: «Депо – это место постройки и ремонта судов», так как внешне это толкование похоже на то, что написано в словаре. Можно спросить ребенка, как называется место для постройки и ремонта судов (такое толкование можно найти в нашем словаре).
Ответ: первое и четвертое утверждения истинны, остальные – ложны.

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

Задача 393. Задача, аналогичная бумажной задаче 14, но несколько сложнее, ведь здесь не 5 путей, а 8. Однако, на алгоритм работы в данном случае это никак не влияет – дети должны по прежнему перебирать листья, используя по ходу пометки и выписывать пути ведущие в них. Как и в задаче 14, здесь удобно перебирать листья по очереди сверху вниз.
Ответ: МОРЖ, МОРЯК, МОСТИК, МОСТ, МОТИВ, МОТОР, МОТ, МОХ.

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

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

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

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

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

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

Урок 39. Все пути дерева

План урока

      1. Решение компьютерных задач 398–402.
      2. Решение обязательных бумажных задач 17, 19, 20.
      3. Решение необязательных бумажных задач 24, 26.

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

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

Задача 399. Задача на повторение темы «Мешок бусин цепочки». Аналогичные задачи ребятам уже встречались и мы просили не относиться к ним слишком серьезно. Такие задачи больше относятся к области русского языка, их решение во многом зависит от того, что ребенок быстро догадался и, конечно, от словарного запаса. Однако, если рассматривать эту задачу как информатическую, то в случае, если ребенок на каком-то слове совсем застрял, нужно предложить ему сделать перебор. Конечно, он будет довольно большим, но можно надеяться, что его не придется доводить до конца. Для начала решение стоит искать среди более популярных с точки зрения языка комбинаций букв. Так в слове БАРОН две гласных и три согласных. Более вероятно, что первая буква слова – согласная. Видим, что с первой Б слов русского языка построить больше не удается. Проверяем буквы Р и Н, в результате находим слово НАБОР.
Ответ: БАРОН – НАБОР
            КУЛИЧ – ЛУЧИК
            СМОЛА – МАСЛО
            АДРЕС – СРЕДА

Задача 400. Задача на построение дерева, в которой детям снова пригодится умение анализировать и сопоставлять утверждения, делая из них правильные выводы. Так в задаче сказано, что длина каждого пути дерева меньше 4. Это значит, что в нашем дереве могут быть пути длины 1, 2 или 3, а дерево имеет не больше трех уровней. Заметим, что два уровня (или меньше) дерево иметь не может. Действительно, на каждом уровне дерева по 5 бусин, а всего в дереве 10 листьев. Но все бусины дерева не могут быть листьями. Так мы понимаем, что в нашем дереве ровно 3 уровня. Все бусины последнего (третьего) уровня – листья, поэтому размещаем на третьем уровне 5 листьев. Теперь разместим на первом и втором уровне еще 5 листьев, учитывая то, что на каждом из этих уровней должно быть по 5 бусин. Конечно, при этом необходимо помнить, что бусин первого уровня, не являющихся листьями всегда не больше, чем таких бусин второго уровня.

Задача 401. Аналогичные задачи ребятам уже встречались. Наиболее естественный совет для большинства ребят (за исключением самых сильных) – вначале выписать числа на листок, перевести их в арабскую форму записи, упорядочить полученные числа, а затем уже упорядочивать исходные числа.

Задача 402. Необязательная. Вашим ребятам, конечно, известно, что любую подобную задачу можно решить полным перебором клеток поля, запуская Робота из каждой клетки по очереди. Однако, лучше этот перебор сразу сузить, чтобы не делать слишком много напрасной работы. Так, при анализе программы сразу становится ясно, что Робот не может выполнить даже первые две команды из любой клетки двух нижних строк. Это означает, что клетка начальной позиции находится в двух верхних строках. Кроме того, Робот не сможет выполнить первые три команды из клеток последнего столбца поля. Таким образом, сразу отбрасываем довольно много вариантов, и остается проверить лишь 7 клеток поля. Конечно, анализ программы можно продолжать и отбросить еще часть клеток, но и такой перебор выполнить уже вполне реально.

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

Задача 17. Детям, которые растерялись, задайте вопрос о том, где должны быть написаны самые короткие слова. С первого взгляда на мешок слов становится ясно, что корневая бусина дерева – Б. У нее три следующие, но и у слов в мешке на втором месте также стоит Е, Л или У. Встает вопрос: какая буква должна стоять в какой бусине? Этот вопрос легко решить, посчитав количество слов в мешке с каждой из имеющихся вторых букв. Аналогично можно продолжать рассуждения до тех пор, пока все бусины дерева не будут заполнены.

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

Задача 19. В задаче нужно не полностью нарисовать мешок всех путей дерева Ю, а лишь закончить раскраску его цепочек. Однако это не облегчает нашей задачи, а только несколько изменяет ее. Здесь мы должны «узнать» каждый путь, установить соответствие между частично раскрашенными цепочками из мешка Ю и путями дерева Э. В отличие от подобных задач, которые ребята уже решали (например, № 15), пути в мешке расположены не на уровне соответствующих листьев, а в порядке возрастания числа бусин. Это дополнительно осложняет процесс «узнавания». Такое расположение цепочек в мешке, скорее всего, подтолкнет ребят искать пути, ориентируясь на их длину. Сложнее будет с путями длины 3. Особенно сложной будет ситуация с цепочками 8, 9, 10 и 11, у которых не только длина, но и первые бусины одинаковы. Однако легко увидеть, что и они определяются по дереву однозначно. Работа с такой задачей будет не только сложной, но и увлекательной, поскольку она в некотором смысле напоминает игру («угадай», «узнай»). Последнее задание дано для проверки, но кому-то, возможно, захочется ставить имена цепочек по ходу решения задачи. В этом случае число вариантов путей, из которых выбирает ребенок, будет постепенно уменьшаться: ведь на пути, около которых он поставил имя, можно уже не смотреть.

Задача 20. Несложная задача на повторение листа определений «Склеивание цепочки цепочек». Конечно, подходящих цепочек цепочек гораздо больше, чем две. В числе прочего подходят решения, где одна из цепочек – пустая.

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

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

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

Урок 40. Все пути дерева

План урока

      1. Решение компьютерных задач 403–407.
      2. Решение обязательных бумажных задач 21, 22.
      3. Решение необязательных бумажных задач 23, 25.

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

Задача 403. Это первая задача на построение дерева по мешку его путей, поэтому на нее необходимо обратить внимание. До настоящего момента ребята много раз решали задачу на построение мешка всех путей дерева и могли заметить, что этот мешок строится однозначно. Что касается обратной задачи, дело здесь обстоит совершенно иначе – разные деревья могут иметь одинаковые мешки путей. Действительно,  по мешку путей невозможно различить, следуют ли две бусины одного уровня за некоторой бусиной или же просто за двумя одинаковыми такими бусинами. Например, два пути начинаются одинаково с красной квадратной бусины, дальше в одном из них идет желтая круглая, а в другом – зеленая круглая. Это может означать, что два пути имеют общую корневую бусину, а может быть в этом дереве имеется две корневых красных квадратных бусины и каждых путь выходит из собственной корневой бусины. Такая ситуация возможна при каждом ветвлении. Поэтому если в условии задачи необходимо просто построить дерево по мешку его путей, то решений здесь существует много. Отличаться деревья будут конечно числом бусин в них. Максимальное число бусин в дереве – столько, сколько во всех путях в мешке. Такая ситуация возникнет в том случае, если каждый лист будет выходить из собственной корневой бусины, то есть каждая бусина в дереве будет иметь не больше одной следующей. Однако можно построить и другие деревья, «экономя» бусины. «Экономить» бусины – значит не ставить одинаковых бусин там, где можно обойтись одной. Например, не ставить одинаковых корневых бусин и не ставить одинаковых бусин, следующей за некоторой бусиной, заменив их одной. Если «экономить» бусины максимально, то появляется дерево с минимальным числом бусин.

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

Задача 404. Аналогичные задачи на построение цепочек ребятам уже попадались. Сложность подобных задач в том, что не удается механически сложить решение из частичных решений. Например, здесь не получается сложить решения из трех кусочков вида «баклажан - … - желтый фрукт», поскольку в цепочке должно быть ровно 7 фигурок. Поэтому приходится «сращивать» частичные решения между собой. Если «срастить» два частичных решения, то у нас получается кусочек «баклажан – баклажан – желтый фрукт – желтый фрукт». Теперь третье частичное решение к этому кусочку можно просто присоединить и в цепочке окажется как раз 7 фигурок.

Задача 405. Довольно сложная и интересная задача, связанная не только с текущим листом определений, но и с курсом математики. Наверняка, кто-то из сильных детей сможет сделать некоторые выводы из условия, проанализировав данные утверждения. Но, думаем, большинство ребят будут действовать методом проб и ошибок. Начинать, при этом удобнее с корневых бусин. В процессе многочисленных проб ребятам постепенно становится ясно, что нет смысла ставить в корневые бусины самые большие цифры, например, 8 или 9.  Тогда нам сразу становится сложно соблюсти условие, что сумма всех цифр в каждом пути равна 10. Удобнее ставить в корневые бусины маленькие цифры, тогда у нас будет больше свободы. Поскольку все пути в дереве должны быть разными, нет смысла ставить корневыми бусинами одинаковые цифры (тогда мы сразу рискуем появлением одинаковых путей). Итак, поставим в корневые бусины две разные маленькие цифры, например, 1 и 2. Теперь будем достраивать каждую ветку. Заметим, что наибольшие сложности у ребят скорее всего возникнут с самыми длинными путями, если они не продумали этот вопрос заранее. Действительно, если ребята не догадаются использовать число 0, то число 10 представляется в виде суммы разных слагаемых только одним способом – 10= 1+2+3+4. Тогда именно цифры 1, 2, 3 и 4 и будут стоять в двух самых длинных путях дерева (конечно, в разном порядке, поскольку в нашем дереве не должно быть двух одинаковых путей). Если в решении использовать ноль, то возможных вариантов становится несколько больше.

Задача 406. Аналогичные задачи ребятам уже встречались. В таких случаях каждую из пропущенных команд дети могут найти полным перебором всех возможных команд, учитывая клетки, закрашенные Роботом.
Ответ: Программа Ц: ВЛЕВО ВНИЗ ВПРАВО ВПРАВО ВНИЗ ВВЕРХ ВВЕРХ ВПРАВО ВВЕРХ ВЛЕВО ВВЕРХ ВНИЗ.

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

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

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

Задача 22. В случае ложных утверждений попросите ребят объяснить, что обозначает это слово на самом деле (появится дополнительный повод заглянуть в словарик).
Ответ: первое и третье утверждения ложны, остальные – истинны.

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

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

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