Подготовка к ЕГЭ по информатике

Задание 3

Задание 1. Тип заданий 3: поиск пути

Задание: На рисунке справа схема дорог между населенными пунктами изображена в виде графа. В

таблице содержатся сведения о длинах этих дорог.

П1

П2

П3

П4

П5

П6

П1

5

7

П2

4

8

П3

5

4

9

П4

10

2

П5

7

8

9

10

П6

2

Таблицу и схему дорог построили независимо друг от друга, т. е. нумерация пунктов в таблице никак не связана с

буквенными обозначениями на графе. Определите, какова длина дороги из пункта D в пункт E. В ответе запишите

целое число, как оно указано в таблице.

Решение:

Нам не известно, каким пунктам на графе соответствуют пункты таблицы. Но мы можем это определить.

Обратите внимание на пункт F графа. Это единственный пункт, из которого выходит только один путь. Значит в

таблице это П6.

Из F путь ведёт в Е, значит по таблице мы можем определить, что пункт Е — это П4.

Теперь посмотрим на пункт D графа. Это единственный пункт, из которого ведут четыре пути. Соответственно в

таблице пункт D это П5.

Нам нужно определить расстояние между пунктами D и E, то есть между П4 и П5. Из таблицы видно, что расстояние

между ними равно 10.

Ответ: 10

Задание 2. Тип заданий 3: поиск пути.

Задание: Между населенными пунктами A, B, C, D, E, F построены дороги. Протяженность дорог

приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги между пунктами нет.

A

B

C

D

E

F

A

4

9

B

5

12

C

4

5

3

D

16

7

E

9

12

3

16

F

7

Определите длину кратчайшего пути между пунктами

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

по построенным дорогам).

Решение: Не все понимают, как работать с таблицей. Давайте разберемся.

Возьмем первую строку:

A

B

C

D

E

F

A

4

9

Это дороги из пункта А. Строка показывает, что из него ведут пути в пункт С и в пункт E, и длина путей 4

и 9 соответственно.

Для решения отобразим все пути на графе и на рёбрах графа отобразим расстояние между пунктами:

1. Из пункта А пути ведут в C и в E:

2. Из пункта B пути ведут в C и в E:

3. Из пункта С пути ведут в A, B, E. Пути в пункты A и B у нас уже обозначены, осталось отобразить путь в

Е:

4. Из пункта D пути ведут в E и в F:

Пути из пункта E и пункта F уже отображены. Осталось посчитать длину кратчайшего пути:

То есть длина кратчайшего пути равна 4+3+16+7=30

Ответ: 30

Задание 3. Тип заданий 3: поиск пути.

Задание: Между населенными пунктами A, B, C, D, E, F построены дороги. Протяженность дорог

приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги между пунктами нет.

A

B

C

D

E

F

A

5

6

4

20

B

5

6

C

6

6

D

4

6

6

2

7

E

2

4

F

20

7

4

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

можно только по построенным дорогам).

Решение: Не все понимают, как работать с таблицей. Давайте разберемся.

Возьмем первую строку:

A

B

C

D

E

F

A

5

6

4

20

Это дороги из пункта А. Строка показывает, что из него ведут пути в пункты B, C, D, F, и длина путей 5, 6,

4, 20 соответственно.

Для решения отобразим все пути на графе и на рёбрах графа отобразим расстояние между пунктами.

1. Из пункта А пути ведут в B, C, D, F:

2. Из пункта B пути ведут в пункты A и D. Путь в A уже отмечен, отметим путь в пункт D:

3. Из С пути ведут в пункты А и D. Путь в А уже

отмечен, отметим путь в пункт D:

4. Из пункта D пути ведут в A, B, C, E, F. Пути в A, B и

C уже отмечены, отобразим пути в пункты Е и F:

5. Из пункта E пути ведут в D и в F. Путь в D уже

добавлен, отобразим путь в пункт F:

Из пункта F пути ведут в A, D и E, все они на графе уже отображены. Остаётся посчитать кратчайший

путь:

4+2+4=10

Ответ: 10

Задание 4. Тип заданий 3: поиск пути.

Задание: Между населенными пунктами A, B, C, D, E, F, G построены дороги. Протяженность дорог

приведена в таблице. Если в таблице числа отсутствуют, значит прямой дороги между пунктами нет.

A

B

C

D

E

F

G

A

3

6

28

B

3

2

C

6

2

7

18

D

7

2

7

12

E

2

3

5

F

7

3

1

G

28

18

12

5

1

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

только по построенным дорогам).

Строим граф

Найдем в графе кратчайший путь:

Посчитаем длину: 3+2+7+2+3+1=18

Ответ: 18

Задание 5. Тип заданий 3: поиск пути.

Задание: На рисунке справа схема дорог Н-ского района изображена в виде графа, в

таблице содержатся сведения о длинах этих дорог (в километрах).

П1

П2

П3

П4

П5

П6

П7

П1

45

10

П2

45

40

55

П3

15

60

П4

10

40

20

35

П5

15

55

П6

55

60

20

55

45

П7

35

45

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице

никак не связана с буквенными обозначениями на графе. Определите. какова длина дороги из пункта В в

пункт Е. В ответе запишите целое число — так, как оно указано в таблице.

Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.

Решение: Чтобы найти расстояние между пунктами В и Е необходимо определить, какой пункт таблицы

соответствует пункту В карты, а какой — пункту Е карты.

Обратите внимание на граф. Пункт В — единственный, из которого выходит пять дорог. По таблице видно,

что это П6. То есть П6 таблицы — это пункт В на графе.

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

видно, что пунктом В графа может быть только П4.

Таким образом, мы должны определить расстояние между П6 и П4 в таблице, что очень легко сделать:

П1

П2

П3

П4

П5

П6

П7

П1

45

10

П2

45

40

55

П3

15

60

П4

10

40

20

35

П5

15

55

П6

55

60

20

55

45

П7

35

45

Ответ: 20

Поиск определённого маршрута по таблице. Задания для тренировки.

1. В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и

столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется

условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из

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

пункт маршрут должен проходить не более одного раза.

1

2

3

4

1) 1

2) 2

3) 3

4) 4

Ответ: 3

Путешественник пришел в 08:00 на авто­станцию по­селка ЛЕС­НОЕ и увидел следующее распи

сание авто­бусо­в:

Отправление из

Прибытие в

Время отправления

Время прибытия

Лесно­е

Озерно­е

07:45

08:55

Луго­во­е

Лесно­е

08:00

09:10

По­лево­е

Лесно­е

08:55

11:25

По­лево­е

Луго­во­е

09:10

10:10

Лесно­е

По­лево­е

09:15

11:45

Озерно­е

По­лево­е

09:15

10:30

Лесно­е

Луго­во­е

09:20

10:30

Озерно­е

Лесно­е

09:25

10:35

Луго­во­е

По­лево­е

10:40

11:40

По­лево­е

Озерно­е

10:45

12:00

Определите само­е раннее время, ко­гда путеше

ственник смо­жет о­казать­ся в пункте ПОЛЕВОЕ

со­гласно­ это­му расписанию.

1) 10:30

2) 11:25

3) 11:40

4) 11:45

Пояснение. Путешественник не

может уехать раньше того, как он

пришёл, т. е. раньше 8-00.

Заметим, что есть прямой рейс из

посёлка ЛЕСНОЕ в ПОЛЕВОЕ с при

бытием в 11:45.

Но можно поехать с пересадкой:

ЛЕСНОЕ-ЛУГОВОЕ (9-20 — 10-30),

затем ЛУГОВОЕ-ПОЛЕВОЕ (10-40 —

11-40), причём на пересадку у путе

шественника есть 10 минут.

Следовательно, правильный ответ

3.

Транспо­ртная фирма о­существляет грузо­перево­зки разными видами транспо­рта между

четырь­мя го­ро­дами: ЧЕРЕПОВЕЦ, МОС­КВА, КУРС­К, ПЕРМЬ. С­то­имо­сть­ до­ставки грузо­в и время

в пути указаны в таблице:

Пункт отправления

Пункт назначения

Стоимость (у. е.)

Время в пути

Мо­сква

Пермь­

100

70

Мо­сква

Курск

30

10

Мо­сква

Черепо­вец

50

15

Пермь­

Мо­сква

100

69

Черепо­вец

Пермь­

140

80

Черепо­вец

Мо­сква

50

15

Черепо­вец

Курск

100

80

Курск

Пермь­

60

40

Курск

Мо­сква

30

10

Курск

Черепо­вец

100

80

Курск

Черепо­вец

90

100

Определите маршрут наибо­лее дешево­го­ варианта до­ставки груза из ЧЕРЕПОВЦА в ПЕРМЬ.

Если таких маршруто­в неско­ль­ко­, в о­твете укажите наибо­лее выго­дный по­ времени вариант.

1) ЧЕРЕПОВЕЦ – ПЕРМЬ

2) ЧЕРЕПОВЕЦ – КУРС­К – ПЕРМЬ

3) ЧЕРЕПОВЕЦ – МОС­КВА – ПЕРМЬ

4) ЧЕРЕПОВЕЦ – МОС­КВА – КУРС­К – ПЕРМЬ

Варианты 1 и 4 имеют одинаково минимальную стоимость

140 (140 < 150 < 160), но вариант 4 более выгоден по

времени 65 < 80.

Правильный ответ указан под номером 4.

Между населёнными пунктами A, B, C, D, E, F по­стро­ены до­ро­ги, про­тяжённо­сть­ ко­то­рых

приведена в таблице. (Отсутствие числа в таблице о­значает, что­ прямо­й до­ро­ги между

пунктами нет.)

A

B

C

D

E

F

A

4

B

4

6

3

6

C

6

4

D

3

2

E

6

4

2

5

F

5

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

мо­жно­ то­ль­ко­ по­ по­стро­енным до­ро­гам).

Кратчайший путь­ равен 14.

В таблице приведена сто­имо­сть­ перево­зо­к между со­седними железно­до­ро­жными станциями.

Укажите схему, со­о­тветствующую таблице.

2

1

4

3

Правиль­ный о­твет указан по­д но­меро­м 4.