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

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

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

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

РТ, г. Казань

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

(Задача ОГЭ)

 

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

	A	B	C	D	E
A		2	5	1
B	2		1
C	5	1		3	2
D	1		3
E			2

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

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)