kopilkaurokov.ru - сайт для учителей

Создайте Ваш сайт учителя Курсы ПК и ППК Видеоуроки Олимпиады Вебинары для учителей

Разработка задание ОГЭ по теме: "Графы. Поиск путей".

Нажмите, чтобы узнать подробности

Данную разработку можно использовать на уроках информатики, на факультативах при подготовке к ОГЭ.

Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Наладить дисциплину на своих уроках.
Получить возможность работать творчески.

Просмотр содержимого документа
«Разработка задание ОГЭ по теме: "Графы. Поиск путей".»

Тема: Графы. Поиск путей.


На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Е

Решение:

Главную идею решения: (число дорог в город N есть сумма дорог, приводящих в города, из которых есть прямой проезд в город N), отразим на самой схеме, показывая на ней ЧИСЛО ДОРОГ, приводящих в каждый город.

  1. Последовательность очевидна: начинаем с Б и Г (городов, куда есть по 1-й дороге из А)

  1. Посчитаем дороги в В: 1 (из A)+ 1(дороги города Б)+ 1(дороги города В) = 3

  1. Аналогично посчитаем дороги в Д, И, Е, Ж:

  1. Определяем число дорог в город К, как сумму дорог в города, с которыми он связан: Д, И, Ж, Е.

  1. Ответ: 13.





























2 Тема: Графы. Поиск путей

Сегодня мы рассмотрим решение задачи 11 ГИА по информатике.

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой  дороге  можно  двигаться  только  в  одном  направлении,  указанном стрелкой. Сколько существует различных путей из города А в город К?

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

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

Итак, начнем решение с конца, т. е. с города К. Как мы видим, в город К можно приехать из городов Е, В, Г, Ж. Отобразим это графически

Шаг 1

Далее, на втором шаге определим, откуда можно добраться в города Е, В, Г, Ж. К примеру,

  • в город Е можно добраться только из города Б,

  • в город В — из городов А и Б,

  • в город Г из городов А, В и Д,

  • в город Ж из городов Г и Д.

Графически это будет выглядеть таким образом:

Шаг 2

Таким образом, мы будем продолжать до тех пор, пока каждая ветка не приведет к городу А. В итоге получится такая диаграмма — дерево:

Шаг 3

Здесь зеленым цветом я выделил конечные пункты — город А. Осталось только посчитать их количество — это и будет правильный ответ. В нашем случае их 12. Правильный ответ: 12.








Получите в подарок сайт учителя

Предмет: Информатика

Категория: Прочее

Целевая аудитория: 9 класс.
Урок соответствует ФГОС

Скачать
Разработка задание ОГЭ по теме: "Графы. Поиск путей".

Автор: Могилевская Юлия Гильфановна

Дата: 30.11.2020

Номер свидетельства: 564932


Получите в подарок сайт учителя

Видеоуроки для учителей

Курсы для учителей

ПОЛУЧИТЕ СВИДЕТЕЛЬСТВО МГНОВЕННО

Добавить свою работу

* Свидетельство о публикации выдается БЕСПЛАТНО, СРАЗУ же после добавления Вами Вашей работы на сайт

Удобный поиск материалов для учителей

Ваш личный кабинет
Проверка свидетельства