Урок 5. Дерево. Следующие вершины, листья. Предыдущие вершины

Урок 5. «Дерево. Следующие вершины, листья. Предыдущие вершины»

Начиная разговор о цепочках, мы упоминали о последовательности событий. Однако нам не всегда интересна простая линейная последовательность событий. Приведем несколько примеров:

– перед нами стоит возможность выбора и приходится рассматривать несколько вариантов дальнейшего хода событий: «Направо пойдешь – коня потеряешь, налево пойдешь – буйну голову сложишь, прямо пойдешь – на красавице-царевне женишься»;
– мы выбираем один из возможных объектов, но хотим потом изменить свое решение и выбрать другой;
– мы выделяем в задаче подзадачи, раздаем их участникам проекта, а потом собираем результаты для поиска одного решения.

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

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

– деревья направлены, они «растут» в одну сторону: у каждой вершины, если она не является листом, может быть несколько следующих вершин и ровно одна предыдущая, если вершина не корневая; и ни одной предыдущей у корневой вершины (такие деревья называются в информатике направленными).

Решение задач из учебника

Задача 27. Попросите детей проверить свое решение: в окне должны быть все бусины-листья дерева Ч, причем только они. Чтобы не запутаться, можно сразу помечать на дереве Ч каждый нарисованный в мешке лист.

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

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

Ответ: ложные утверждения для дерева У:

– утверждение В (предыдущая фигурка перед дельфином – белка),
– утверждение С (у жирафа три следующие фигурки – лев, лось и курица),
– утверждение Н (фигурка верблюда в дереве есть),
– утверждение G (у бегемота две следующие фигурки – волк и гусь),
– утверждение К (предыдущая фигурка перед курицей – жираф).

Остальные утверждения истинны.

Задача 30. В этой задаче проверяется, насколько хорошо ученики усвоили понятие дерево и основные свойства деревьев. Желательно эту задачу обсудить всем классом. Попросите детей сформулировать обоснования, почему каждый объект является или не является деревом, например: F не является деревом, поскольку у синей квадратной бусины две предыдущих. Это же условие нарушено и в схемах J и V. Оставшиеся две схемы являются деревьями.

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

Ответ:  

КАША
КИЛЬКА
КОМОД
КОТИК
КРЕСТ
КРУЖКА
КТО
КТО-ТО
КУСТ

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

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

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

Компьютерный урок «Дерево. Следующие вершины, листья. Предыдущие вершины», задачи 33 – 40

Задача 33. Задача на закрепление понятий «лист» и «корневая вершина». Если кто-то из детей допускает ошибки, достаточно попросить его еще раз обратиться к листу определений.

Задача 34. Здесь дети снова закрепляют понятие «лист» в ходе построения мешка всех листьев дерева. Хотя на листе определений явно не вводится понятие «мешок всех листьев дерева», но для детей оно должно быть понятно, исходя из понятий «лист» и «мешок». Как видите, листьев в дереве довольно много, и дети могут потерять какие-то из них. Чтобы этого не произошло (и в качестве проверки), можно использовать пометки. Например, можно ставить галочку около листа дерева П, как только такая же бусина оказалась в мешке, или соединять одинаковые листья в дереве и в мешке попарно.

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

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

Задача 37. В этой задаче ребята повторяют правила расстановки слов в словарном порядке. В частности, здесь ребятам будет необходимо вспомнить правило, когда одно слово является частью другого, и правило расстановки слов с дефисами.

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

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

Задача 40. Необязательная. Как видите, здесь есть два вида разных мышей – смотрящих влево и смотрящих прямо. Мышки из этих групп в любом случае будут разные, как бы мы не раскрашивали их одежду. Поэтому рассмотрим группу одинаковых мышек, например, смотрящих налево. Их будет четыре. Какие есть варианты раскраски их одежды? Либо юбка и кофта будут одинакового цвета, либо – разного. В первом случае они могут быть либо обе желтые, либо обе красные. Во втором – красной может быть юбка, а кофта желтой или наоборот. Получаем всего 4 варианта разной раскраски, что как раз совпадает с нашим числом мышей. Аналогично мы раскрасим и мышей, которые смотрят прямо.