Задание № 3

Спецификация контрольных измерительных материалов единого государственного экзамена по информатике и ИКТ

Практика

Т.к.теории по данному вопросу практически нет, то перейдем сразу к практике.

1. Разберем примеры заданий из ЕГЭ прошлый лет.

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

1) 12
2) 13
3) 14
4) 16

Решать данное задание можно и устно, перебирая все возможные передвижения по сетке таблицы из исходного пункта к конечному, например:

В данном случае, длина пути между пунктами A и F равна 2 + 3 + 9 = 14. И так далее.

Можно еще выписывать найденные пути (АВDF = 14, и т.д.) и выбирать из них самый короткий.

Но решая таким образом, легко сделать ошибку - пропустить какой-либо путь. Поэтому я рекомендую решать такое задание полным перебором всех возможных перемещений из пункта А, составляя дерево.

Начало дерева (из пункта А можно попасть в пункты B, C, D и F):

Первый вариант пути найден - 16.

Продолжим построение.

На этом этапе построения мы видим, что до пункта D можно добраться двумя путями и что путь через пункт В короче (2 + 3 = 5), поэтому в дальнейшем мы будем развивать именно эту ветвь дерева.

Продолжим построение.

Здесь также присутствует новый путь до пункта D, но он длиннее 5, поэтому его не будем рассматривать.

Продолжим построение.

Из пункта D можно попасть в 5 пунктов, но путь в пункты A, B и С - это движение назад, поэтому остается только два пункта E и F. При этом мы нашли второй вариант пути - 2 + 3 + 9 = 14.

Продолжим построение.

Находим последний вариант - 2 + 3 + 4 + 3 = 12. Он и является самым коротким.

Ответ: 1.

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

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

Это задание отличается только тем, что нет вариантов ответов, а решается точно также.

Можете себя проверить (ответ - 23).

Внимание: есть задания, в которых включено дополнительное условие, например, что нельзя проезжать через какой-либо пункт и др. Такие ветки дерева также надо отсекать.

2. Очень хорошо разобраны решения заданий ЕГЭ на сайте К.Полякова ( )

3. И, в заключение, рекомендую пройти онлайн-тест по заданию №5 (В5) на сайте К.Полякова (выбрать ) или на сайте ege.yandex.ru (

Такой тип задач встречается под номером 3 в тексте ОГЭ по информатика.

Пример 1

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

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

Решение:

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

4. Новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

5. Новый маршрут из D – в E (длина пути 3):

6. Новый маршрут из E – в F (длина пути 2):

7. Нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

8. Попробуем перечислить возможные маршруты из А в Е:

• А – В – Е длина 9
• А – В – С – Е длина 7
• А – В – C – D – Е длина 9
• А –C – Е длина 8
• А –C – B – Е длина 12
• А –C – D – Е длина 10

9. Из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

10. Таким образом, правильный ответ - 9.

Пример 2

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

Определите длину кратчайшего пути между пунктами A и Е. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
1) 4
2) 5
3) 6
4) 7

Решение:

1. Построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B, C и D (длины путей соответственно 2, 5 и 1)

2. Для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее. Например, ВА=АВ=2. Если нижняя часть таблицы отличается от верхней, то строим отдельный маршрут. В задачах, как правило, таблица симметрична.

3. Из вершины В можно проехать в вершину C (длина пути 1):

4. Из вершины C можно проехать в вершины D, E (длины путей 3 и 2):

5. Нужно проехать из А в Е, по схеме видим, что в любой из таких маршрутов входит ребро СE длиной 2; таким образом, остается найти оптимальный маршрут из A в С

Попробуем составить все возможные варианты маршрутов из точки А в точку С:

А-С = 5
А-В-С = 3
А-D-С = 4

Видно, что самый короткий маршрут от А до С это маршрут А-В-С. Добавляем последнее ребро С-Е, получим длину маршрута А-В-С-Е = 3 + 2 = 5. Это второй вариант ответа.

Ответ: 2

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

Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.

Решение (1 способ, перебор вариантов):

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

нам нужно найти все пути, которые проходят через 6 и более пунктов, считая начальный и конечный; то есть между A и Z должно быть не менее 4 промежуточных пункта

начнем с перечисления всех маршрутов из А, которые проходят через 2 пункта; по таблице видим, что из A можно ехать в B, C и Z; количество пунктов на маршруте будем записывать сверху:

1. маршрут AZнас не интересует, хотя он и пришел в конечный пункт, он проходит меньше, чем через 6 пунктов (только через 2!); здесь и далее такие «неинтересные» маршруты из A в Z будем выделять серым фоном

   теперь ищем все маршруты, проходящие через 3 пункта; из B можно ехать только в C, а из С – в D и Z:

3. строим следующий уровень только для тех маршрутов, которые ещё не пришли в Z:

4. следущие два уровня дают «интересные» маршруты, проходящие через 6 или 7 пунктов:

на последней схеме зелёным фоном выделены «интересные» маршруты, их всего 6; красным фоном отмечены маршруты, в которых получился цикл – они дважды проходят через один и тот же пункт; такие маршруты запрещены и мы далее их не рассматриваем

1. можно было нарисовать схему возможных маршрутов в виде дерева:

Решение (2 способ, через построение графа, М.В. Кузнецова)

Общее число пунктов 7. Есть дороги, последовательно связывающие все 7 пунктов, значит 1-й путь: ABCDEFZ.

Есть 3 дороги, которые позволяют «проехать мимо» соседнего пункта (ACидёт «мимо»B,DF– мимоE,…), значит, есть 3 способа проехать через 6 пунктов (AC DEFZ,ABCDF Z,ABCDEZ ).

…

Есть одна «обратная дорога», позволяющая изменить порядок прохождения пунктов – FE. Эта дорога при наличии дорогиDF, идущей «мимо» Е, создает дополнительные маршруты: один через 7 пунктовABCDFE Zи один через 6 пунктовAC DFE Z.

Вывод: общее число дорог, соответствующих условию: 1+3+2=6

Представляю решение 3 задания ОГЭ-2016 по информатике из проекта демоверсии. По сравнению с демоверсией 2015 года, 3 задание не изменилось. Это задание на умение анализировать формальные описания реальных объектов и процессов (формализация описания реальных объектов и процессов, моделирование объектов и процессов).

Скриншот 3 задания.

Задание:

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

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

1) 4
2) 5
3) 6
4) 7

На основании таблицы, которая дана в задании, строим граф. Из пункта А можно попасть в пункты В, С и D, а из них — в C, D, E и т.д. Не забываем, что нам нужно именно в пункт E (некоторые варианты можно сразу отбросить, т.к. дорога до пункта Е по ним будет однозначно длинной). Затем подсчитаем длину пути по каждому маршруту и выберем наименьший из них.

ABCE=2+1+2=5
ACE=5+2 =7
ADCE=1+3+2=6

В нашем случае это маршрут АВСЕ (2+1+2=5) .