Миннурова Азиза Ильдусовна,

учитель математики и информатики

МБОУ «Средняя общеобразовательная школа № 85 с углубленным изучением отдельных предметов» 

РТ, г. Казань

Методика решения задач по формализации и моделированию, алгоритмы их выполнения

(Задача ОГЭ)

Задание 3. Между населенными пунктами А, В, С, D, E построены дороги, протяженность которых (в километрах) приведена в таблице:

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

1. 4                      2) 5                        3)6                         4) 7

Наша цель решить данную задачу и получить какой-то конкретный ответ, так как какой-то вариант ответа соответствует нашему значению.

Задача решается достаточно просто, и мы видим, как минимум 2 способа ее решения.

Первый способ – это попытаться угадать. Допустим, вы предполагаете, что это вариант под номером 2, то есть записываете двойку. Вероятность 25% из 100. Понятно, что это крайне нерациональный вариант, поэтому так делать не рекомендуется.

Второй способ. С помощью графов.

Выясним, какая здесь имеется проблема, которая возникает в процессе решения задачи?

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

Если посмотреть на таблицу, что мы можем увидеть?

Во-первых, у нас информация симметрична относительно главной диагонали. Например, АВ дает 2, и ВА дает 2.

 Что это означает? Это означает, что у нас двусторонне движение, то есть если мы едим из А в В – это 2 км, если двигаемся из В в А тоже 2 км. Наша таблица является симметричной.

Для решения задачи будет, скорее всего, удобнее построить пятиугольник, так как у нас 5 городов, то есть каждая вершина будет соответствовать какому-то городу, а ребра, которые соединяют эти вершины, будут соответствовать наличию дороги, между соответствующими городами.

Значит, нарисуем пятиугольник и заполним вершины.

Дальше мы проводим дороги, в соответствии с той информацией, которая у нас есть в исходной таблице. Итак, соединим соответствующие населенные пункты. Смотрим на таблицу. Между А и В и между В и А есть дорога протяженностью 2 км. Запишем это.

Далее указываем дорогу между А и С и соответственно между С и А – это есть дорога протяженностью 5 км. Также пишем. Затем дорогу между А и D, и соответсвенно между D и A, между которыми есть дорога с расстоянием 1 км. Нарисуем ее.

С А у нас больше ничего не соединяется, переходим к В. В и А мы построили. В и С – 1 км. В больше ничем не соединяется. Переходим к С. С и А показали, С и В показали, остается С и D, между которыми расстояние равно 3 км. Изобразим расстояние между С и Е, протяженность между которыми равна 2 км и все. DА, DС и ЕС также построены. В итоге из табличной структуры мы получим структуру графа. По построенной схеме нам будет уже гораздо легче решить нашу задачу.

Далее мы должны найти кратчайший путь между пунктами А и Е. Сейчас мы просто перебираем возможные маршруты и потом определим самый кратчайший путь¸ который мы должны найти.

Начнем перебирать. Стартовая вершина А. Как видим из вершины А, мы можем попасть в В, из В идем в С, то есть идем по алфавиту. Понятно, что в D идти смысла нет¸ так как из D мы попадаем в А и у нас получится цикл, так что нам из пункта С нужно двигаться в пункт Е. В итоге мы достигаем конечной точки.

И сейчас мы просуммируем: А+В+С+Е=2+1+2=5.

Строим второй маршрут. Если пойдем из А в В, то потом однозначно можно идти только в С и потом только в Е. Этот вариант мы рассмотрели. Поэтому мы из А пытаемся попасть в С. А из С двигаться в D нет смысла, потому что у нас образуется цикл, поэтому идем в Е. Идти в В смысла нет, так как образуется также цикл. В итоге получится у нас такой маршрут: А+С+Е=5+2=7.

Дальше посмотрим третий вариант. АВ и АС рассмотрели. Остается АD. Из D мы можем двигаться к пункту С. Видим, что из С двигаться к В нет смысла, так как мы попадаем в А. Поэтому после С мы движемся к пункту Е. В результате получаем: А+ D

+С+Е=1+2+3=6.

Больше вариантов мы не видим, так как из А в Е мы не можем двигаться. У нас получилось три различных маршрута. Таким образом имеется 3 расстояния: 5, 6 и 7.

Наша цель была найти кратчайший путь. Мы нашли его – это 5!

Далее мы находим число 5 среди вариантов ответов, которые нам предлагают. Нам подходит второй вариант, который совпадает с нашим вариантом ответа. Далее мы пишем, ответ в котором указываем номер правильного варианта, а не значение, которое мы рассчитали.

Ответ: 2

Алгоритм выполнения задания:

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

Список литературы

1. Босова, Л.Л. Информатика [Текст]: учебник для 9 класса/ Л.Л. Босова, А.Ю. Босова. – М.: БИНОМ. Лаборатория знаний, 2013. – 184с.
2. Евич, Л.Н. Информатика и ИКТ. 9 класс. Подготовка к ОГЭ_2016. [Текст]/ Под ред. Л.Н. Евич, С.Ю. Кулабухова. – Ростов-на-Дону: Легион, 2015. – 192с.
3. Евич, Л.Н. Информатика и ИКТ. Подготовка к ЕГЭ – 2016. [Текст]/ Под ред. Л. Н. Евич, С. Д. Кулабухова. – Ростов –на –Дону: Легион, 2015. – 272 с.
4. Крылов, С.С. ЕГЭ 2016. Информатика. Тематические тестовые задания [Текст]/ С.С. Крылов, Д.М. Ушаков. – М.: Издательство «Экзамен», 2015. – 255 с.
5. Крылов, С.С. ОГЭ. Информатика и ИКТ: типовые экзаменационные варианты: 10 вариантов [Текст]/ С.С. Крылов, Т.Е. Чуркина – М.: Издательство «Национальное образование», 2015. – 144 с.
6. Угринович, Н.Д. Информатика и ИКТ [Текст]: учебник для 9 класса / Н.Д. Угинович. – 6-е изд. – М.: БИНОМ. Лаборатория знаний, 2012. – 295с.
7. Сайт К.Ю. Полякова «Преподавание, наука и жизнь» [Электронный ресурс]/URL: http://kpolyakov.narod.ru/school/ege.htm (дата обращения 10.02.2015)