Урок 55. Повторение, подготовка к теме «Дерево всех слов данной длины»

Материалы к уроку: бумажные задачи 54–62 (2 часть).

Данный урок целиком посвящен решению бумажных задач. Следующая тема, «Дерево всех слов данной длины» (из букв данного мешка) во многом опирается на уже пройденный материал. Поэтому перед тем, как начинать новую тему, нам необходимо повторить некоторые темы и задачи из курса 3 класса. Речь идет о построении мешка всех путей дерева и, наоборот, о построении дерева по мешку его путей. Этому и посвящено большинство задач на с. 30–33 учебника.

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

Задача 54. Здесь ребятам предстоит построить дерево по мешку его путей. Вообще-то таких деревьев существует много, но в данной задаче уже имеется заготовка, которая вынуждает ребят строить самое «экономное» дерево – дерево с минимальным числом бусин. Понятно, что нельзя вписывать бусины в дерево L наугад.

Можно заметить, что из одной корневой бусины берут начало 3 пути, из другой – 4. Необходимо решить, где записать букву С, а где – П (руководствуясь числом слов в мешке, начинающихся на каждую из этих букв). Дальше в двух ветках можно разместить два самых длинных слова ПОРТ и СОРТ. После этого остальные слова можно просто «пристраивать», исходя из букв, уже имеющихся в дереве. В дереве есть два пути, которые можно поменять местами: ПАР и ПАН. Если кто-то из ребят спросит, в каком порядке лучше ставить бусины, следующие после А (Р и Н), предложите им руководствоваться алфавитным порядком, именно так мы стараемся упорядочивать в деревьях буквы.
Ответ:


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


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

В задаче 56 пока не требуется построить все объекты – дерево уже построено, нужно просто выписать все его пути. Данное в задаче дерево У – это дерево построения всех слов длины 3 из мешка букв (А, В и С). Пути этого дерева – не осмысленные слова, а наборы из трех букв, что может несколько затруднить работу.
Ответ:


Задача 57. В отличие от задачи 56 здесь уже дан мешок, содержащий все возможные цепочки длины 4, составленные из 0 и 1. Требуется по этому мешку построить дерево.

Ясно, что все бусины дерева Q – числа 1 или 0. Можно заметить также, что в мешке R нет одинаковых путей, значит, корневые бусины разные (0 и 1) и все бусины, следующие за бусиной каждого уровня (кроме листьев), разные (на самом деле их всегда две – 0 и 1).

Дерево, которое дети рисуют в этой задаче, очень знаменитое, наверное, самое знаменитое из деревьев, как и похожие на него деревья другой высоты и с другими бусинами вместо 0 и 1, например черной и белой бусинами. Это дерево называется полным двоичным (или бинарным) деревом высоты 4. Можно построить такое же дерево высоты 3 или 5 и т. д.

Задача для вас: сколько имеется путей в дереве высоты 5? А в дереве высоты 7?

Как вы, вероятно, слышали, в компьютере информация хранится в виде цепочек нулей и единиц. В задаче дети выписывают все такие цепочки длины 4.

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

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


Тогда легко выделить соседние части, прилегающие к первым двум.


Оставшиеся три части укладываются уже однозначно.


Задача 59. Продолжаем предварительное обсуждение темы «Дерево всех слов данной длины» (из букв данного мешка).
Итак, нужно построить дерево М, мешок путей которого задан.

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

Сначала несколько обычных технических советов. Как и всегда, с подобной задачей лучше работать карандашом, иначе потом будет трудно исправить ошибки. Детям, которые не смогли сразу сориентироваться, посоветуйте выписать все слова из мешка F на небольших карточках (или просто кусочках бумаги) и рассортировать их на столе. Сначала нужно будет тщательно проверить, все ли слова выписаны на карточки и нет ли в них ошибок. Впрочем, самым слабым вы можете подготовить такой комплект карточек заранее и просто выдать в готовом виде. Если кто-то сам догадается изготовить для себя такие карточки, замечательно!

Теперь несколько содержательных советов. Конечно, дерево М удобнее строить, начиная от корневых бусин и продвигаясь постепенно к листьям. В ходе работы можно обсуждать вопрос, почему за данной бусиной следуют 3 (или 2) бусины и т. д. Последовательность «вкладывания» слов в дерево может быть различной. Можно, например, просто наугад брать любое слово и помещать его в дерево. Но при такой стратегии может возникнуть неприятность, если, скажем, первые буквы слов СТО и СОТ мы поместим в разных квадратиках. Поэтому учащиеся должны как-то дойти до мысли, что все слова, начинающиеся с С, должны начинаться с одной корневой бусины. Такое решение может возникнуть у них случайно или оказаться принятым из каких-то неясных, интуитивных соображений. Все это неплохо, надо лишь убедиться, что ответ действительно верный. Хорошо, если в обсуждениях на тему данной задачи возникнет слово (и понятие) возможность, в данном случае – «какие есть возможности для следующих букв» и т. п.

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

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


Осталось проверить, что мешок F действительно является мешком всех путей дерева М, т. е. пометить попарно листья дерева и слова мешка. Удобно по ходу заполнения дерева помечать (например, подчеркивать) слова, соответствующие появившимся путям дерева. Тогда, закончив заполнять окна, ребята уже будут знать ответ на вопрос, действительно ли мешок F – мешок всех путей дерева М.

Ответы на вопросы задачи 59 не должны вызвать затруднений – они даны, скорее, для самоконтроля. Ответы на третий и четвертый вопросы должны совпадать, как и ответы на первые два вопроса. Но интересно порассуждать с ребятами, что проще – убедиться в отсутствии двух одинаковых слов в мешке или в отсутствии двух одинаковых путей в дереве. Если заполнение дерева шло осознанно (а особенно, если пути построенного дерева упорядочены), то ребята сразу скажут, что двух одинаковых путей там нет, и объяснят почему. Действительно, если пути выходят из разных корневых бусин, то естественно отличаются друг от друга (первой буквой), а если из одной, то у них различны либо вторые буквы, либо третьи.

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

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

Тем ребятам, которые быстро справились с задачей, можно предложить подсчитать, сколько существует слов длины 4, составленных из данных букв, и подумать, как можно быстро выписать все такие слова, имея мешок F и дерево М (таких слов будет тоже 24 – нужно просто дописать в конце каждого слова мешка F ту букву из данных четырех, которой в этом слове нет).

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

Задача 61. Необязательная. Как и в других подобных задачах, здесь проще сначала составить цепочку мешков, исходя из того, какие буквы встречаются на соответствующих местах в словах мешка ⊗D.


Теперь, раскрыв цепочку мешков D, можно дописать в мешок недостающие слова НОРЫ, НОРЕ, ПОРА, ПОРУ.

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

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