Разбор и отработка задания 3 ОГЭ по информатике.

Информатика. ЕГЭ

Задание 3

Разбор типовых задач:

№1

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

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

Задача решается преобразованием табличной модели в дерево:

Рассмотрим первую строку (столбец) таблицы. Очевидно, что из точки А мы можем попасть в точки В, С, D, F. Получим следующую схему:

Рассмотрим вторую строку (столбец) таблицы: из пункта В можно попасть в пункт А (путь АВ уже нанесен на схему и повторно рисовать его нет необходимости, т.к. это дорога «назад» и такой маршрут не будет кратчайшим). Таким образом, на схему необходимо нанести одну дорогу(из В в D, длиной 5).

Анализируя 3 строку (столбец) таблицы, добавляем на схему еще одну дорогу: из С в D длиной 2.

Анализ 4 строки (столбца) таблицы добавляет на нашу схему еще две дороги (из D в E и F), так как дороги BD, CD, AD уже присутствуют на схеме. Так как точка D на схеме нарисована 3 раза, то от каждой точки D проведем два пути: DE и DF. Получим схему

Согласно 5 строке (столбца) таблицы нанесем на схему дорогу EF:

По схеме выпишем маршруты из А в F и посчитаем их протяженность:

1. AF – 14

2. ADF – 7+8=15

3. ADEF – 7+5+1=13

4. ACDF – 4+2 +8 =14

5. ACDEF – 4+2+5+1 = 12

6. ABDF – 3+5+8 = 16

7. ABDEF – 3+5+5+1 = 14

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

№2

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

Сколько дорог между пунктами А и F имеют протяженность менее 15? Передвигаться можно только по дорогам, указанным в таблице.

Строим древовидную схему аналогично №1. Отличие от предыдущего задания заключается в том, что нас не длина кратчайшего маршрута, а количество маршрутов, длина которых удовлетворяет условию (