infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи A2 (демо ЕГЭ 2013)

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

A
B
C
D
E
F
A
-
3




B
3
-
7
4
7

C

7
-

5

D

4

-
2

E

7
5
2
-
3
F




3
-

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
  1. 11
  2. 12
  3. 13
  4. 18
Решение:
Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.

задача A2 ЕГЭ по информатике 2013 граф

Нарисуем путь из пункта А в F. Начнем с конца, с пункта F. В него идет дорога из Е:

задача A2 ЕГЭ по информатике 2013 путь F-E

В пункт Е ведут дороги из B, C и D:

задача A2 ЕГЭ по информатике 2013 пути F-E-B, F-E-С, F-E-D

В пункт B ведет дорога из A, в пункт С ведет дорога из В, в пункт D ведет дорога из B:

задача A2 ЕГЭ по информатике 2013 пути F-E-B-A, F-E-C-B, F-E-D-B

В пункт В ведет дорога из А:

задача A2 ЕГЭ по информатике 2013 пути F-E-C-B-A, F-E-D-B-A

Видим, что из А в F ведет 3-и пути. Надо найти кратчайший путь из трех. Добавим в граф значение расстояний между пунктами:

задача A2 ЕГЭ по информатике 2013 кратчайший путь

1-й путь: A−B−E−F=3+7+3=13

2-й путь: A−B−C−E−F=3+7+5+3=18

3-й путь: A−B−D−E−F=3+4+2+3=12

Получили кратчайший путь: A−B−D−E−F. Его длина равна 12.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В, 2012-2015. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта