Как решать задание 3 ЕГЭ по информатике

Задание 3

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

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

П1

П1

П2

П2

П3

П3

П4

5

5

П4

4

П5

П5

4

П6

7

П6

7

8

8

9

9

10

10

2

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 и F (при условии, что передвигаться можно только по построенным дорогам).

A

A

B

B

C

C

4

D

D

4

5

E

5

E

9

F

9

F

12

12

3

3

16

16

7

7

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

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

A

A

B

C

D

4

E

F

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

A

B

B

5

5

C

C

6

D

D

6

E

4

4

E

6

F

6

F

20

6

6

20

2

2

7

7

4

4

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

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

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

A

A

B

C

5

D

6

4

E

F

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

A

B

B

C

3

C

3

D

6

6

D

E

E

2

2

F

F

G

G

7

7

28

28

2

2

18

7

7

18

3

12

3

12

5

5

1

1

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

Строим граф

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

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

Ответ: 18

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

Задание: На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

П1

П1

П2

П2

П3

45

П3

45

П4

П4

П5

10

10

П5

П6

П6

40

40

П7

П7

15

15

55

55

60

60

20

20

35

35

55

55

  45

45

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите. какова длина дороги из пункта В в пункт Е. В ответе запишите целое число — так, как оно указано в таблице.

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

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

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

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

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

П1

П1

П2

П2

П3

П3

45

45

П4

П4

10

10

П5

П5

40

40

П6

П6

П7

П7

55

55

15

15

60

60

20

20

35

35

55

55

  45

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:40

10:35

11:40

10:45

12:00

Пояснение. Путешественник не может уехать раньше того, как он пришёл, т. е. рань­ше 8-00. Заметим, что есть пря­мой рейс из посёлка ЛЕС­НОЕ в ПО­ЛЕ­ВОЕ с при­бы­ти­ем в 11:45.

Но можно по­ехать с пересадкой: ЛЕСНОЕ-ЛУГОВОЕ (9-20 — 10-30), затем ЛУГОВОЕ-ПОЛЕВОЕ (10-40 — 11-40), причём на пе­ре­сад­ку у пу­те­ше­ствен­ни­ка есть 10 минут.

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

Определите самое ран­нее время, когда пу­те­ше­ствен­ник смо­жет ока­зать­ся в пунк­те ПО­ЛЕ­ВОЕ со­глас­но этому расписанию.

1) 10:30

2) 11:25

3) 11:40

4) 11:45

Транспортная фирма осуществляет грузоперевозки разными видами транспорта между четырьмя городами: ЧЕРЕПОВЕЦ, МОСКВА, КУРСК, ПЕРМЬ. Стоимость доставки грузов и время в пути указаны в таблице:

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

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

Москва

Москва

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

Пермь

Курск

Москва

100

Время в пути

70

30

Череповец

Пермь

50

Москва

Череповец

10

15

100

Пермь

Череповец

69

140

Череповец

Москва

80

Курск

Курск

50

15

100

Пермь

Курск

Курск

80

60

Москва

Курск

Череповец

30

40

10

100

Череповец

80

90

100

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

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

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

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

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

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

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

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

A

A

B

B

C

4

4

C

D

D

E

6

E

6

3

F

3

F

6

6

4

4

2

2

5

5

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

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

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

2

1

3

4

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

Источники:

Сайт БУ Информатик http://infbu.ru /

Сайт Сдам ЕГЭ https :// inf-ege.sdamgia.ru