Информатика как найти карта

Добрый день! Сегодня посмотрим, как «бороться» с 4 заданием из ОГЭ по информатике 2023.

Четвёртное задание из ОГЭ по информатике достаточно простое, хотя и может показаться кому-то скучным.

Рассмотрим простой пример из тренировочных заданий для 4 задания.

Задача (Стандартная)

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

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

Решение:

Расставим точки, которые символизируют города, примерно по кругу.

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

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

Теперь найдём самый короткий путь из A в C.

Можно сразу попасть из A в C по прямой дороге за 8. Если пойдём через пункт D, то придём в город C за 7. Через город B так же можно прийти за 7 километров.

Но мы видим, что длина дороги из D в B равна 1. Попытаемся эту дорогу использовать при составлении маршрута. Получим путь: A-D-B-C. Получается 3+1+2=6. Это и есть искомый кратчайший путь.

Ответ: 6

Задача (C обязательным узлом)

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

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

Решение:

Расставим точки по кругу. Точка С — это обязательный пункт.

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

Теперь можно начать искать кратчайший путь от A до E, проходящего через C.

Найдём кратчайший путь до точки С. Это и есть путь A-C. Он равен 5.

От С до E можно добраться разными путями:

C-E = 8
C-D-E = 2 + 5 = 7
C-B-E = 4 + 3 = 7

Это и есть самый короткий путь.

В ответе напишем путь: A-C-D-B-E = 5 + 6 = 11.

Ответ: 11

Задача (Закрепление)

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

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

Решение:

Расставим точки А, B, С, D, E, F по кругу.

Теперь в соответствии с таблицей соединим эти города, указав числа возле линий. Стараемся сделать рисунок, как можно более понятным, применяем разные цвета.

Получилась наглядная карта городов. Оценив все пути от пункта A до пункта F, определяем, что самый короткий путь будет 4 + 3 + 4 + 3 = 14.

Ответ: 14.

ЕГЭ по информатике 2022 — Задание 13 (Лёгкое!)

Сегодня разберём одно из самых лёгких заданий из ЕГЭ по информатике — задание 13. Вы с похожим типом задач могли встретится на экзамене в 9 классе по информатике.

Приступим к практическим тренировкам решения 13 задания ЕГЭ по информатике 2022.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение:

Нужно подсчитать количество путей от начальной точки А до конечной точки К.

Будем использовать специальную технику для решения 13 задания из ЕГЭ по информатике 2022

Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б «перетекает» 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку «перетекает» 1 из А.

В точку В входят две стрелки. Значит, в точку В «втекает» сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.

И продолжаем в том же духе.

Число в конечной точке показывает правильный ответ!

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?

Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.

Основная техника же решения будет такой же, как и в прошлой задаче.

Продолжаем отработку 13 задания ЕГЭ по информатике 2022

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

Такая же задача, как и предыдущие две, только здесь, при построении путей, мы не должны проходить через точку E.

Зачеркнём те дороги, которые поведут наши пути через пункт E.

Далее, применим старый метод, который использовали ранее.

Рассмотрим задачу, которая была на реальном экзамене по информатике в этом году.

Задача (ЕГЭ по информатике, 2020, Москва)

На рисунке — схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?

Решение:

В этой задаче отличается вопрос от привычного нахождения количества путей. Здесь нужно найти наибольшую длину пути из начального пункта в конечный.

Возле начальной точки ставим число 0.

Смотрим сколько входит в узел стрелок. Выбираем стрелку, которая идёт из узла с наибольшим числом. При переходе по стрелочке добавляем 1.

Число, которое получится возле конечной точки и будет ответом. В этой задачке стрелок получилось 7, это и будет ответ.

Источник

Как считать схему дорог по информатике

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Начнем считать количество путей с конца маршрута – с города К. N_K — количество различных путей из города А в город K, N — общее число путей.

В «K» можно приехать из Е, Ж, З или И, поэтому N = N_К = N_Е + N_Ж + N _З + N_И (1)

Преобразуем первые вершины:

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Начнем считать количество путей с конца маршрута – с города Ж. N_X — количество различных путей из города А в город X, N — общее число путей.

В «Ж» можно приехать из Е, К, З или В, поэтому N = N_Ж = N_Е + N_К + N _З + N_В (1)

N = N_Ж = 3 + 8 + 3 + 5 + 1 + 2 + 1 + 1 = 24.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Начнем считать количество путей с конца маршрута – с города Ж. N_X — количество различных путей из города А в город X, N — общее число путей.

В «Ж» можно приехать из Е, К, З, В или Б, поэтому N = N_Ж = N_Е + N_К + N _З + N_В + N_Б (1)

Преобразуем первые вершины с учетом значений вторых:

N = N_Ж = 13 + 12 + 5 + 2 + 1 = 33

Источник

9 задание ОГЭ информатика

ОГЭ по информатике 9 задания объяснение

Поиск количества путей

• Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

9 задание как решать

Подробный видеоразбор по ОГЭ 9 задания:

Рассмотрено 3 задачи. Перемотайте видеоурок на решение нужной задачи.

Решение задания 9.1:

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?

• Решим задание с конца. Т.е. так как траектория поиска путей от А до Н, то мы будем рассматривать сначала город Н.
• В город Н можно попасть из трех городов — C, D и G; запишем это так:
• Теперь аналогично рассмотрим города C, D и G:

Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:

Решение задания 9.2. Сборник Ушакова Д.М., 2018 г. ВАРИАНТ 2:

На карту нанесены 4 города (A, B, C и D).
Известно, что:
между городами A и C — три дороги,
между городами C и B — две дороги,
между городами A и B — две дороги,
между городами C и D — две дороги,
между городами B и D — четыре дороги.
По каждой из этих дорог можно ехать в обе стороны.

Сколькими различными способами можно проехать из A в D, посещая каждый город не более одного раза?

• Построим все возможные ветви для движения из города A. Будем выполнять произведение количества дорог для каждой ветви, так как движение возможно в обе стороны:
• Полученные результаты для каждого способа движения из города A в город D следует сложить:

Решение задания 9.3. Демонстрационный вариант огэ по информатике 2022 г.:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К, проходящих через город В?

Поскольку нас интересуют пути, проходящие через город В, то вычеркнет те дороги, которые минуют город В:

Как видим, таких дорог получилось две — Б->Д и А->Г. Учтем это при дальнейших расчетах.

Решим задание с конца. Т.е. так как траектория поиска путей — от А до K, то мы будем рассматривать сначала город K.

В город K можно попасть из трех городов — Д, E и Ж; запишем это так:

Теперь аналогично рассмотрим города Д, Е и Ж:

Далее, рассмотрим каждый город, дойдя до первого — города А. Для него существует только одни путь. Также, для городов, выходящих только из города А, тоже существует только 1 путь. Таким образом имеем:

Поскольку нас интересуют пути, проходящие через город В, то вычеркнет те дороги, которые минуют город В:

Построим дерево, расположив его для удобства горизонтально:

Уберем пути, в которых отсутствует город В:

Подсчитаем количество оставшихся путей следования до города К, их 10 .

Источник

Задача №15. Графы. Поиск количества путей.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Источник

Как считать схему дорог по информатике

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт В?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

Е = Д = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Примечание. Необходимо найти количество различных путей из города А в город К, не проходящих через город В.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт Е?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

И = В + Г = 5 (Е не учитываем, поскольку путь не должен проходить через город Е).

Примечание. Необходимо найти количество различных путей из города А в город К, не проходящих через город Е.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт И?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

К = И = 10. (Е не учитываем, поскольку путь должен проходить через И)

Примечание. Необходимо найти количество различных путей из города А в город Л, проходящих через город И.

Количество путей из пункта А в пункт Л, проходящих через пункт И, равно произведению количества путей из пункта А в пункт И В и количества путей из пункта И в пункт Л.

Найдем количество путей из пункта А в пункт И:

Из пункта И в пункт Л есть только один путь И — К — Л.

Тогда количество путей из пункта А в пункт Л, проходящих через пункт И, равно 10 · 1 = 10.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, проходящих через пункт Е?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

К = Е = 10. (И и В не учитываем, поскольку путь должен проходить через город Е).

Л = К + Е = 20. (Д и Ж не учитываем, поскольку путь должен проходить через город Е).

Примечание. Необходимо найти количество различных путей из города А в город Л, проходящих через город Е.

Количество путей из пункта А в пункт Л, проходящих через пункт Е, равно произведению количества путей из пункта А в пункт Е и количества путей из пункта Е в пункт Л.

Найдем количество путей из пункта А в пункт Е:

Найдем количество путей из пункта Е в пункт Л (при этом Е — исходный пункт):

Тогда количество путей из пункта А в пункт Л, проходящих через пункт Е, равно 10 · 2 = 20.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Л, не проходящих через пункт Е?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

И = Г = 3 (Е не учитываем, поскольку путь не должен проходить через город Е).

К = И = 3 (Е не учитываем, поскольку путь не должен проходить через город Е).

Л = Д + Ж + К = 3 + 3 + 3 = 9 (Е не учитываем, поскольку путь не должен проходить через город Е).

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Д?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

Е = Д = 3 (В и Г не учитываем, поскольку путь должен проходить через город Д).

Примечание. Необходимо найти количество различных путей из города А в город К, проходящих через город Д.

Количество путей из города А в город К, проходящих через город Д, равно произведению количества путей из города А в город Д и количества путей из города Д в город К.

Найдем количество путей из города А в город Д:

Найдем количество путей из города Д в город К (при этом Д — исходный пункт):

Тогда количество путей из города А в город К, проходящих через город Д, равно 3 · 3 = 9.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

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

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

Е = Г = 3 (В и Д не учитываем, поскольку путь должен проходить через город Г).

Примечание. Необходимо найти количество различных путей из города А в город К, проходящих через город Г.

Количество путей из города А в город К, проходящих через город Г, равно произведению количества путей из города А в город Г и количества путей из города Г в город К.

Найдем количество путей из города А в город Г:

Найдем количество путей из города Г в город К (при этом Г — исходный пункт):

Тогда количество путей из города А в город К, проходящих через город Г, равно 3 · 3 = 9.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город Е?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

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

Ж = Е = 3. (В и Г не учитываем, поскольку в этих вершинах не проходим через Е).

Примечание. Необходимо найти количество различных путей из города А в город П, проходящих через город Е.

Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город Е. Тогда количество путей из города А в город П, проходящих через город Е, равно произведению количества путей из города А в город Е, количества путей из города Е в город Ж и количества путей из города Ж в город П.

Найдем количество путей из города А в город Е:

Из города Е в город Ж есть только один путь.

Найдем количество путей из города Ж в город П (при этом Ж — исходный пункт):

Тогда количество путей из города А в город П, проходящих через город Е, равно 3 · 1 · 7 = 21.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город В?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

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

Ж = В = 3. (Е и Г не учитываем, поскольку в этих вершинах не проходим через В).

Примечание. Необходимо найти количество различных путей из города А в город П, проходящих через город В.

Заметим, что путь из города А в город П обязательно должен проходить через город Ж. По условию задачи путь должен также проходить через город В. Тогда количество путей из города А в город П, проходящих через город В, равно произведению количества путей из города А в город В, количества путей из города В в город Ж и количества путей из города Ж в город П.

Найдем количество путей из города А в город В:

Из города В в город Ж есть только один путь.

Найдем количество путей из города Ж в город П (при этом Ж — исходный пункт):

Тогда количество путей из города А в город П, проходящих через город В, равно 3 · 1 · 7 = 21.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город П, проходящих через город М?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

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

Л = М = 17 (Ж и К не учитываем, поскольку путь должен проходить через М).

П = Л + М = 34 (К не учитываем, поскольку путь должен проходить через М).

Примечание. Необходимо найти количество различных путей из города А в город П, проходящих через город М.

Количество путей из города А в город П, проходящих через город М, равно произведению количества путей из города А в город М и количества путей из города М в город П.

Найдем количество путей из города А в город М:

Найдем количество путей из города М в город П (при этом М — исходный пункт):

Тогда количество путей из города А в город П, проходящих через город М, равно 17 · 2 = 34.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К, не проходящих через пункт В?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

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

Г = А = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Д = Б = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Е = Г + Д = 2 (В не учитываем, поскольку путь не должен проходить через город В).

Примечание. Необходимо найти количество различных путей из города А в город К, не проходящих через город В.

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город К, не проходящих через пункт В?

Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х. При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

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

Г = А = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Д = Б = 1 (В не учитываем, поскольку путь не должен проходить через город В).

Е = Г + Д = 2 (В не учитываем, поскольку путь не должен проходить через город В).

Примечание. Необходимо найти количество различных путей из города А в город К, не проходящих через город В.

Источник

Лабораторная
работа № 3

Тема: Работа
с конструктором карт Яндекса в рамках проведения демонстрационного экзамена

Цель
работы: освоение технологии работы с конструктором карт Яндекс,
формирование компетенции «Социальная работа».

Перечень
средств обучения: методические материалы по выполнению лабораторной
работы, персональный компьютер, программное обеспечение

Краткие теоретические сведения

С
помощью Конструктора карт вы сможете создать карту со своими объектами:

Это может быть, например, схема проезда до вашего дома, дачи
или офиса.

На карте вы сможете нарисовать:

• метки —
  подъезды, пункты встречи и т. д.
• линии —
  улицы, маршруты, границы и т. д.
• многоугольники
  (в том числе с внутренним контуром) — дома, коттеджные поселки, озера
  и т. д.

Если у вас есть почта на Яндексе, вы можете перейти на сервис и
сразу приступать к созданию карты. Нажмите кнопку «Создать карту».

Первым делом называем и задаем описание своей карты (не
обязательно; но так будет удобнее, особенно если карт будет несколько). Затем
приступаете к редактированию карты. На карте вы можете:

Как нарисовать схему проезда
на Яндекс.Картах

Вернемся к примеру. Нам нужно указать путь от станции метро до
нашего офиса. Находим нужную станцию на карте, затем выбираем инструмент
«Линии» и просто рисуем путь мышкой. Затем мы можем настроить внешний вид
линии: толщину, прозрачность, цвет. Как видите, конструктор сразу подсчитал,
сколько метров нужно пройти.

Затем предлагаю поставить еще и метку, указывающую на офис.
Выбираем инструмент «Метки», и ставим метку, просто кликнув мышкой в нужном
месте. Затем настраиваем метку: пишем описание, выбираем цвет и тип.

Нажимаем «Сохранить и продолжить».

Дальше указываем тип карты:

— Интерактивная – можно увеличить, уменьшить, полноценно
взаимодействовать с картой;

— Статичная – будет на сайте в виде простой картинки. Подойдет в
том случае, если вы знаете, что у вашей ЦА в основном медленное соединение.

Лучше, конечно же, использовать интерактивную карту.

ЯНДЕКС.КАРТА С НЕСКОЛЬКИМИ
АДРЕСАМИ

Точно так же создаем новую карту, называем
и пишем описание. Затем выбираем инструмент «Метки». Ставим метку в нужном
месте и настраиваем.

Это
будет указание на первый офис (магазин, салон, филиал). Теперь нужно указать
еще и второй. Все делаем точно так же, только выбираем другой цвет для этой
метки – чтобы различать.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.       
Что такое Яндекс Конструктор карт и для чего он необходим?

2.       
Какие элементы создаются в конструкторе?

3.       
Назовите типы карт.

ПРАКТИЧЕСКОЕ
ЗАДАНИЕ

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

Задание
1. На
Рабочем столе создать папку с именем ПСО 20 1_9, в папке
создать Документ Microsoft Word с именем Отчет_Лабораторная
работа № 3

Задание
2. Запустите
браузер и откройте сервис https://yandex.ru/map-constructor/

Задание
3.

—
найдите свой район/населенный пункт.

—
создайте новую карту, назовите ее любым именем

—
в описании укажите «Карта социальных объектов района …»

(сделайте скриншот и поместите его в
документ Отчет_ЛР3)

Задание
4.
С помощью инструмента «Многоугольники» очертите границы вашего района, уровень
прозрачности – 100. Назовите фигуру «Наш район». (сделайте скриншот и поместите его в документ Отчет_ЛР3).

Задание 5. Укажите на карте нужный дом с помощью инструмента «Метки»,
выберите иконку для метки и назовите ее «Наш дом», используя регион, адрес и
номер дома, где находится участник Демонстрационного экзамена.  (сделайте скриншот и поместите его в
документ Отчет_ЛР3).

Задание
6.
Укажите предложенные Вами организации для оказания социальной помощи гражданину
и подпишите, какую помощь здесь может получить ваш сосед. Для каждого типа организаций
рекомендуется выбирать определенный цвет и иконку. (сделайте скриншот и поместите его в документ Отчет_ЛР3).

Задание 7. С помощью инструмента «Линии» нарисуйте оптимальный маршрут
до центра социального обслуживания, укажите его длину в метрах и среднее время,
за которое его можно пройти. (сделайте
скриншот и поместите его в документ Отчет_ЛР3).

Задание 8. С помощью инструмента «Линии» создайте линии маршрутов от дома
до указанных Вами социальных объектов с указанием их длины и времени на дорогу.
Цвета маршрутов желательно выбирать в соответствии с выбранным цветом иконок
организаций различных видов (сделайте
скриншот и поместите его в документ Отчет_ЛР3).

Задание 9. Нажмите кнопку «Сохранить» внизу экрана, распечатайте карту.

СОДЕРЖАНИЕ ОТЧЕТА

Отчет
по результатам выполнения лабораторной работы должен содержать:

1.       
Краткий
конспект

2.       
Название
работы.

3.       
Цель
работы.

4.       
Контрольные
вопросы

5.       
Результаты
выполнения задания.

6.       
Ответ
на контрольные вопросы

7.       
Вывод
по работе.

Поиск оптимального маршрута по таблице

Учитель информатики

Хирьянова В.А.

МОУ «Ропшинская школа»

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

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

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

• полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания
• чаще всего используется взвешенный граф , где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки

B

2

A

4

C

7

B

E

2

A

1

4

C

7

E

B

2

4

A

1

4

C

D

3

7

E

B

2

4

A

3

1

4

C

D

3

7

E

B

2

2

4

A

F

3

1

4

C

D

3

7

B

E

2

2

4

F

A

3

1

4

C

D

3

• таким образом, остается найти оптимальный маршрут из A в F
• попробуем перечислить возможные маршруты из А в F:
• А – В – Е – F длина 11
• А – В – С – Е – F длина 9
• А – В – C – D – Е – F длина 11
• А –C – Е – F длина 10
• А –C – B – Е – F длина 14
• А –C – D – Е – F длина 12

• Ответ: А – В – С – Е – F длина 9