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 (демо ЕГЭ 2012)

Время выполнения-2 мин, уровень сложности-базовый

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


ABCDEF
A
2 4


B 2
1
7
C 4 1
3 4
D

3
3
E
7 4 3
2
F



2

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

  1. 9
  2. 10
  3. 11
  4. 12
Решение:

Изобразим с помощью графа данные таблицы. Точками обозначим населенные пункты. Там, где пункты соединены дорогой, там соединяем точки.

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

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

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

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

задача A2 ЕГЭ по информатике 2012 дороги в пункт E

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

задача A2 ЕГЭ по информатике 2012 дороги в пункты D,C,B

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

задача A2 ЕГЭ по информатике 2012 дороги в пункты С, В

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

задача A2 ЕГЭ по информатике 2012 дорога в пункт В

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

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

1-й путь: A-B-C-D-E-F=2+1+3+3+2=11

2-й путь: A-B-C-E-F=2+1+4+2=9

3-й путь: A-B-E-F=2+7+2=11

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

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

 

Rambler's Top100

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