Задача 103. Задача на понимание нового листа определений. Если вы видите, что кто-то выписывает цепочки, которые путями дерева D не являются, попросите его ещё раз разобрать примеры листа определений и внимательно прочитать текст. В дереве D всего пять путей — БУМ, БУР, МИГ, МИР и МИФ, все они различны, и любые три в данном случае являются ответом.
Задача 104. Такие деревья вполне осмысленны с точки зрения современной лингвистики. В дереве J всего шесть путей, учащиеся могут выписать любые четыре из них. По завершении этой работы ребята должны проверить, что все пути разные, поскольку в условии имеются в виду, конечно, разные пути.
ДЕТИ ЛЕТОМ КУПАЮТСЯ
ДЕТИ ЛЕТОМ ЗАГОРАЮТ
ДЕТИ ЛЕТОМ ИГРАЮТ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА КОНЬКАХ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА ЛЫЖАХ
ДЕТИ ЗИМОЙ КАТАЮТСЯ НА САНКАХ
Задача 105. Задача требует от ребят более глубокого понимания того, что такое путь дерева. Дети могут заметить, что некоторые пути дерева (выходящие из разных корневых вершин) совершенно не связаны между собой, т. е. вершины, которые принадлежат одному пути, не принадлежат другому. Совершенно иной будет ситуация, когда два пути выходят из одной корневой вершины.
Восстановление дерева по коду Прюфера
В этом случае корневая вершина определяет начало сразу нескольких путей, которые из неё выходят. Так, например, прогуливая школу, ученик определяет несколько возможных сценариев дальнейшего развития событий, связанных между собой и неприятных. Эти сценарии никак не связаны с развитием событий в том случае, если бы он пошёл в школу.
Скорее всего, ребята начнут решать задачу методом проб и ошибок, ставя различные знаки в различные окна и проверяя условия. Здесь постепенно и начнёт формироваться идея связи. В ходе экспериментов ребята начнут понимать, что нельзя поставить в корневую вершину, из которой берут начало четыре пути, ни знак приоритета, ни знак сервиса.
Действительно, в этом случае мы задаём сразу четыре пути, и тогда путей в дереве потом просто не хватит. Если же мы поставим в эту вершину запрещающий знак, дальше решение достраивается само собой — во все следующие за ней вершины мы ставим также запрещающие знаки, за той из них, что не является листом, тоже ставим запрещающие знаки. Итак, первое условие выполнено — есть четыре разных пути, все знаки в которых запрещающие. При этом все оставшиеся пути, оказывается, никак не связаны между собой, их можно строить по отдельности: три из знаков приоритета, один из знаков сервиса. Количество знаков на листе вырезания в данной задаче также не накладывает никаких дополнительных ограничений.
Задачу можно рассматривать как хороший повод продолжить знакомство со знаками дорожного движения. С дорожными знаками дети уже работали при решении задачи 5. В комментарии к этой задаче мы советовали обсудить с ребятами смысл данных знаков и поговорить о них. Теперь можно продолжить эту работу на другом наборе дорожных знаков. Ниже мы приводим информацию об использованных в задаче дорожных знаках.
семейное дерево
Задача 106. Задача на повторение листа определений «Перед каждой бусиной. После каждой бусины». Нетрудно догадаться, что в результате раскраски в цепочке появятся одинаковые последовательности цветов: зелёный — жёлтый — синий — красный.
Задача 107. Это первая задача на новую тему, где требуется не просто выписать какие-нибудь пути дерева, а найти путь, удовлетворяющий определённым условиям. Эту работу будут затруднять особенности дерева G. Во-первых, оно достаточно большое, во-вторых, слишком много одинаковых вершин на одном уровне (в том числе все корневые вершины одинаковые).
Задание (а) включает также новую деталь — словосочетание «путь длины 2»: путь — это цепочка, а что такое длина цепочки, ребятам известно, значит, речь идёт просто о цепочке длины 2. Найти её не слишком сложно, так как деревья мы всегда рисуем по уровням (и ребят приучаем к тому же). Поэтому достаточно найти на втором уровне хотя бы один лист и пометить путь, который в него ведёт (это слово КУ).
Найти путь КРОНА оказывается сложнее. Здесь ребята, скорее всего, воспользуются методом перебора, просматривая пути один за другим до тех пор, пока не найдут нужный. Кто-то может догадаться, что КРОНА — путь длины 5, значит, его последняя вершина находится на пятом уровне. Последняя вершина этого пути — А, значит, остаётся найти на последнем уровне все вершины А (таких оказывается всего 4) и проверить все пути, идущие в эти листья.
Задание (в) самое сложное. Если ребята в первых двух заданиях могли случайно наткнуться на решение, то здесь без перебора обойтись трудно. Учитывая второе утверждение, можно вести перебор только путей длины 5 (по листьям последнего уровня), но и такой перебор будет достаточно большим. Поэтому предоставьте ребятам достаточно времени для выполнения этого задания.
Возможно, сообразительные ребята, не склонные к выполнению рутинной работы, придумают нечто, чтобы отсечь часть вариантов. Это очень хорошо, но не стоит требовать этого от всех. Например, нетрудно догадаться, что последняя буква искомого пути не может быть гласной, иначе первое утверждение потеряет смысл. Тогда перебор по возможным буквам последнего уровня уже гораздо меньше, их всего 5. При этом обнаруживается только два подходящих слова — КРОЛЬ и КРЕСТ.
Задача 108 (необязательная). Это задача на склеивание цепочек, но языковая составляющая её настолько велика, что формально решить её невозможно. Перебрать все слова русского языка невозможно, значит, перебор будет лишь дополнять различные языковые соображения ребят и простое угадывание. Поэтому не стоит требовать от всех ребят решения. Если вы видите, что у кого-то задача совсем не идёт — просто предложите ученику другую задачу.
Решений здесь много, например, в качестве результатов склеивания подойдут слова: ТЕПЛОВОЗ, ПОЙМАЛ, ПАРАД, КОРАБЛИК. Проще всего построить решение, имея в виду, что все предлоги и союзы тоже являются словами русского языка.
Задача 109. В этой задаче дети узнают, что склеивать можно не только две, но и любое число цепочек. Несмотря на простоту задачи, проследите, чтобы все дети с ней справились — в дальнейшем ребят ожидает ещё много задач на одновременное склеивание нескольких цепочек.
Задача 110. Задача представляет собой комбинацию двух типов задач, с которыми ребята по отдельности уже встречались. Первый — вписать в программу пропущенные команды, когда начальная позиция и позиция Робика после выполнения программы известны. Второй — найти начальное и конечное положения Робика на поле, если даны программа и её результат.
Здесь учащимся предстоит сделать и то и другое. Прежде всего стоит определить начальное положение Робика на поле. Это можно сделать разумным перебором, ставя Робика в любую закрашенную клетку и начиная выполнять команды. Оказывается, не выходя за пределы закрашенных клеток, три начальные команды программы можно выполнить только из одной клетки.
Теперь уже нетрудно восстановить пропущенные команды — влево, влево. Лучше всего по окончании этой работы ещё раз проверить себя — выполнить получившуюся программу из найденного начального положения на запасном поле из листа вырезания. Проконтролируйте также, чтобы ребята не забыли отметить положение Робика на поле до и после выполнения программы.
Задача 111. По сути, это задача, обратная задаче 109. Здесь нужно выполнить «разрезание» цепочки на три части так, чтобы получившиеся цепочки удовлетворяли некоторым условиям. Первое задание выполнить проще. Для этого достаточно посчитать число букв в слове КАНАРЕЙКА и разделить его на три. Второе задание можно выполнить с помощью несложных рассуждений или перебора.
Большинство детей справится с этим заданием с помощью хаотичного просматривания или простого угадывания.
Задача 112 (необязательная). При решении задачи можно применить обычную тактику — перебирать все возможные пары фигурок, каждый раз проверяя, можно ли из одной фигурки сделать другую, раскрасив лишь один квадратик. Однако условие задачи подводит к идее, позволяющей существенно уменьшить перебор.
То, что нужно закрасить лишь в одной фигурке один квадратик, подсказывает использовать в решении инвариант — число квадратиков, закрашенных в фигурках. Число закрашенных квадратиков в фигурках соответственно равно 8, 6, 8, 8, 7 и 9 (перечисляем фигурки слева направо). Исходя из этого, можно существенно сократить количество рассматриваемых вариантов.
Ответ: нужно в пятой (считая слева) фигурке закрасить верхний левый угол в жёлтый цвет, и она станет такой же, как третья.
Задача 113. Задача даёт возможность сформировать у детей понимание того, откуда в дереве берутся одинаковые пути. Путь — это цепочка, значит, нужно найти две одинаковые цепочки. Задачу можно решить, сравнивая каждую цепочку с каждой, но в случае, если цепочки — пути одного дерева, у такого перебора появляются свои особенности.
Скорее всего, ребята начнут хаотично сравнивать пути, проглядывая дерево слева направо, сверху вниз и т. п. Однако в ходе такой работы у детей постепенно начнёт формироваться понимание, где и что нужно искать (а также где искать не нужно). Во-первых, станет ясно, что одинаковыми могут быть лишь те пути, которые выходят из одной корневой вершины или из двух одинаковых корневых вершин.
Например, нет смысла сравнивать крайний правый путь и крайний левый: ведь уже первые вершины этих цепочек разные. Таким образом, дерево К можно разделить на две части и искать пары одинаковых путей в каждой части отдельно. Одинаковые пути могут выходить из синей квадратной бусины или из двух оставшихся одинаковых треугольных синих бусин. Это облегчает задачу — из большого дерева мы получили два небольших. Искать стало проще.
Если возникнет вопрос, как пометить два одинаковых пути, попросите сделать это так же, как в задаче 107.
Задача имеет два решения: два пути, которые соответствуют красным круглым бусинам-листьям шестого уровня: пятой и восьмой слева и два пути, которые соответствуют красным круглым бусинам шестого уровня: второй и третьей слева.
Задача 114 (необязательная). Предоставьте ребятам возможность самостоятельно найти для себя подсказку: латинский алфавит есть в учебнике на второй странице обложки. Формирование умения сориентироваться и найти необходимую информацию — одна из основных задач курса, даже если ребята работают пока в пределах одного учебника.
Ответ: истинные утверждения — третье и пятое, остальные ложные.
Задача 115 (необязательная). Задача на повторение листа определений «Цепочка цепочек». Некоторую трудность может вызвать третье утверждение (в совокупности со вторым): ребята, скорее всего, просто не задумывались над тем, что пустая цепочка тоже может быть словом, в котором нет ни одной буквы.
Компьютерный проект «Определение дерева по веточкам и почкам» (только для компьютерного варианта изучения курса)
Практическая цель проекта — определение названия дерева по побегу в осенне-зимний период с помощью электронного определителя.
Методическая цель проекта — обучение использованию бинарного дерева для классификации видов растений, продолжение обучения поиску объекта по описанию, знакомство с биологическими понятиями на основе информатических (формальных) критериев.
Источник: studopedia.su
Информатика 4 класс Тетрадь проектов Семенов Рудченко
На сайте Учебник-Школа.ком ученик найдет электронные учебники ФГОС и рабочие тетради в формате pdf (пдф). Данные книги можно бесплатно скачать для ознакомления, а также читать онлайн с компьютера или планшета (смартфона, телефона).
Информатика 4 класс Тетрадь проектов Семенов Рудченко — 2014-2015-2016-2017 год: Читать онлайн (cкачать в формате PDF) — Щелкни!
Пояснение: Для скачивания книги (с Гугл Диска), нажми сверху справа — СТРЕЛКА В ПРЯМОУГОЛЬНИКЕ 
. Затем в новом окне сверху справа — СТРЕЛКА ВНИЗ 
. Для чтения — просто листай колесиком страницы вверх и вниз.
Текст из книги:
Источник: uchebniki-shkola.com
Урок 26
Деревья
Практическая работа №10
«Схемы, графы и деревья» (задания 6 — 8).
Проверочная работа
Деревья
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).
Например, иерархическую структуру имеет школа, потому что в ней установлены следующие отношения подчиненности: директор — заместители директора – учителя — ученики.
Иерархическую структуру имеют системы, элементы которых связаны отношением «входит в состав».
На рисунке ниже изображен граф иерархической системы, представляющий состав прикладного программного обеспечения (ПО) компьютера.
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка — обозначенный ею объект входит в один класс верхнего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один ко многим». Вершины, не имеющие порожденных вершин, называются листьями.
Древовидными являются схемы отношений «является разновидностью», используемые для наглядного представления классификации объектов:
Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:
Родственные связи между членами семьи удобно изображать с помощью схемы, называемой генеалогическим или родословным деревом. На рисунке ниже показана родословная Романовых. Здесь корень дерева находится снизу. Изображать дерево отношений можно в любом направлении — это дело вкуса разработчика модели.
По иерархическому принципу организована система хранения файлов во внешней памяти.
Вы знаете, что по определенному признаку (принадлежность, назначение, содержимое, время создания и т. д.) файлы целесообразно объединять в папки. Папки, в свою очередь, могут вкладываться в другие папки и т. д. Главная (корневая) вершина этой иерархии соответствует определенному устройству внешней памяти.
Для того чтобы найти файл в иерархической файловой структуре, можно указать путь к файлу. В путь к файлу входят записываемые через разделитель «» логическое имя диска и последовательность имен вложенных друг в друга папок, в последней из которых находится нужный файл.
Например, пути к файлам можно записать так:
С:ПроектыИстория
С:ПроектыИнформатика
С:Рисунки
Путь к файлу вместе с именем файла называют полным именем файла.
Примеры полных имен файлов:
Операционная система позволяет получить на экране компьютера изображение файловой системы в виде дерева:
Использование графов при решении задач
Графы удобно использовать при решении некоторых классов задач.
Задача 1
Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.
Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмем произвольную точку плоскости О.
На первый стул можно посадить любого из трех учеников — обозначим их А, В и С. На схеме это соответствует трем ветвям, исходящим из точки О:
Посадив на первый стул ученика А, на второй стул можно посадить ученика В или С. Если же на первый стул сядет ученик В, то на второй можно посадить А или С. А если на первый стул сядет С, то на второй можно будет посадить А или В. Это соответствует на схеме двум ветвям, исходящим из каждой вершины первого уровня:
Очевидно, что третий стул в каждом случае займет оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на из предыдущих ветвей.
Выпишем все пути от вершин первого уровня к вершинам третьего уровня: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.
Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трех человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3 * 2 * 1 = 6.
Задача 2
Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трех дорог старого ворона и вот какие советы от него услышал:
1. иди сейчас по правой тропинке;
2. на следующей развилке не выбирай правую тропинку;
3. на третьей развилке не ходи по левой тропинке.
Пролетавший мимо голубь шепнул Ивану-царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?
Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» ребрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией:
Коротко о главном
Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная — ребром. Линия, выходящая из некоторой вершины и входящая в нее же, называется петлей. Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией — весом вершины или ребра (дуги).
Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью. Цепь, начальная и конечная вершины которой совпадают, называется циклом. Разновидность графа, содержащая циклы, называется сетью.
Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчиненности, называются иерархическими системами (системами с иерархической структурой).
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.
Вопросы и задания
1. Определите сказку, для которой следующий граф определяет отношения между персонажами.
(Курочка Ряба)
2. С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.
(Решение:
а) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься также по 3-м (3 варианта). В итоге имеем: 3 • 3 = 9 вариантов.
б) Вверх можно подняться по 3-м тропинкам (3 варианта), спуститься только по оставшимся 2-м (2 варианта). В итоге имеем: 3 • 2 = 6 вариантов)
3. Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?
(Решение:
Число размещений 4-х элементов по 3: A = 4 • (4-1) • (4-2) • (4-3) = 4 • 3 • 3 • 1 = 24
Ответ: 24 чисел)
4. Для составления цепочек используются бусины, помеченные буквами: А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором — любая гласная, если первая буква согласная, и любая согласная, если первая гласная.
На третьем месте – одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?
(Решение:
а) Первая бусинка А, тогда на втором месте может быть 3 варианта бусинок и на третьем месте тоже 3 варианта. Получаем 3 • 3 = 9 вариантов;
б) Первая бусинка С, тогда на втором месте возможны 2 варианта (2 гласные) и на третьем тоже 2 варианта (Д, Е). Получаем 2 • 2 = 4 варианта;
в) Первая бусинка Е, тогда на втором месте возможны 3 варианта (3 согласные), а на третьем место — 2 варианта (С, Д) Получаем 3 • 2 = 6 вариантов;
В итоге получаем: 9 + 4 + 6 = 19 вариантов
Ответ: 19 вариантов)
5. В центре дальнего леса находилась большая поляна — самое удивительное место в Стране малышей. На ней были три колодца: один — с газировкой, второй — с молоком, третий — с морсом. Когда-то три друга Фантик, Грибок и Дружок — построили на поляне домики и целое лето жили в лесу. Другим малышам нравилось приходить к ним в гости, попить молока, газировки или морса, погулять по лесным тропинкам. Но однажды бывшие друзья поссорились, и каждый из них решил проложить собственные дорожки к колодцам так, чтобы они не пересекались с дорожками соседей.
Подумайте, почему Знайка, к которому коротышки обратились за помощью, предложил им помириться.
(Задача не имеет решения. Нельзя провести тропинки так, чтобы они не пересекались).
Проверочная работа
Вариант 1
1. Решите задачу табличным способом.
В кафе встретились три друга: художник Черняев, рыбак Беленьков и таксист Рыжиков. «Замечательно, что у одного из нас белые, у другого черные, а у третьего рыжие волосы, но ни у кого цвет волос не соответствует фамилии», – заметил черноволосый. «Ты прав», – сказал Рыжиков. Какого цвета волосы у каждого из друзей.
2. Пользуясь диаграммой работоспособности в течение рабочей недели, отметьте только истинные высказывания:
1. самая высокая работоспособность в понедельник;
2. работоспособность в среду ниже работоспособности в четверг;
3. работоспособность во вторник и четверг одинакова;
4. самый непродуктивный день — суббота;
5. работоспособность заметно снижается в пятницу;
6. самая высокая работоспособность в среду;
7. пик работоспособности – в пятницу;
8. всю неделю работоспособность одинаковая.
3. Для выполнения задания постройте дерево.
Запишите все возможные двузначные числа, при записи которых используются цифры 2, 8 и 5.
4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 4.
Б) вводится число 5
Вариант 2
1. Решите задачу табличным способом.
Три ученицы – Липкина, Яблонева и Черемухина – посадили около школы три дерева: черемуху, яблоню и липу. Причем не одна из них не посадила то дерево, от которого произошла ее фамилия. Узнайте, какое дерево посадила каждая из девочек, если известно, что Липкина посадила не яблоню.
2. Пользуясь диаграммой работоспособности в течение рабочей недели, отметьте только ложные высказывания:
1. самая высокая работоспособность в понедельник;
2. работоспособность в среду ниже работоспособности в четверг;
3. работоспособность во вторник и четверг одинакова;
4. самый непродуктивный день — суббота;
5. работоспособность заметно снижается в пятницу;
6. самая высокая работоспособность в среду;
7. пик работоспособности – в пятницу;
8. всю неделю работоспособность одинаковая.
3. Для выполнения задания постройте дерево.
Запишите все возможные двузначные числа, при записи которых используются цифры 1, 7 и 4.
4. Какое число получится в результате работы этой блок-схемы, если
А) вводится число 6.
Б) вводится число 5
Практическая работа №10
«Схемы, графы и деревья» (задания 6 — 8)
Задание 6. Наши конкурсы
Работы участников школьных конкурсов по информационным технологиям записаны на диске, файловая структура которого имеет вид:
Средствами текстового процессора Word создайте соответствующую схему.
Сохраните результат работы в собственной папке в файле с именем Конкурсы.
Задание 7. Царство животных
1. Составьте схему но следующему описанию:
Близкие виды объединяются в один род. Например: ворона, ворон, галка и грач объединены в род Ворон. Близкие роды объединяются в семейства: род Ворон, род Сорока, род Сойка, род Кедровка объединены в семейство Вороновые. В свою очередь, близкие семейства объединяются в отряды. Так, семейство Синицевые, семейство Вороновые, семейство Ласточковые принадлежат отряду Воробьинообразные.
Близкие отряды составляют класс. Так, отряд Воробьинообразные, отряд Совообразные, отряд Гусеобразные принадлежат к классу Птицы. Близкие классы объединены в типы. Так, класс Птицы, класс Амфибии, класс Млекопитающие входят в тип Хордовые. В настоящее время выделяют до 25 различных типов животных.
Все они объединены в царство Животные.
2. Сохраните результат работы в собственной папке в файле с именем Животные.
Задание 8. Творческое задание
Придумайте сами пример объектов, отношения между которыми можно представить с помощью схемы. Создайте соответствующую схему в программе Microsoft Word. Сохраните результат работы в собственной папке в файле с именем Идея5.
Источник: xn—-7sbbfb7a7aej.xn--p1ai