Кратчайший путь егэ - Помощь в подготовке к экзаменам и поступлению

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

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

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

	A	B	C	D	E	F	G
A		5		12			25
B	5			8
C				2	4	5	10
D	12	8	2
E			4				5
F			5				5
G	25		10		5	5

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

Источник: Демонстрационная версия ЕГЭ—2015 по информатике.

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

	A	B	C	D	E	F
A		2	4	8		16
B	2			3
C	4			3
D	8	3	3		5	3
E				5		5
F	16			3	5

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

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

	A	B	C	D	E	F	G
A		2		6
B	2		5	3
C		5		1			8
D	6	3	1		9	7
E				9			5
F				7			7
G			8		5	7

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

	A	B	C	D	E	F	G
A		2		6
B	2		5	2
C		5		4			8
D	6	2	4		2	7
E				2			5
F				7			7
G			8		5	7

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

Пройти тестирование по этим заданиям

Источник

Урок посвящен тому, как решать 1 задание ЕГЭ по информатике

Содержание:

Объяснение заданий 1 ЕГЭ по информатике
- Структурирование информации и информационные модели
- Поиск кратчайшего пути (перебор)
Решение заданий 1 ЕГЭ по информатике

1-я тема характеризуется, как:
— задания базового уровня сложности,
— требуется использование специализированного программного обеспечения — нет,
— время выполнения – примерно 3 минуты,
— максимальный балл — 1

Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

До ЕГЭ 2021 года — это было задание № 3 и задание № 7 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Как и в большинстве простых заданий, основные ошибки происходят из-за торопливости и невнимательности»

ФГБНУ «Федеральный институт педагогических измерений»

* Некоторые изображения страницы взяты из материалов презентации К. Полякова

Структурирование информации и информационные модели

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

Структурирование информации — это установление главных элементов в информационных сообщениях и установление связей между ними.

Структурирование выполняется с целью облегчения восприятия и поиска информации.

Структурирование возможно при помощи следующих структур (информационных моделей):

множество:

перечисление элементов, собранных по характерному признаку;

Вася, Петя, Коля
1, 17, 22, 55

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

линейный список

Важна упорядоченность следования элементов.

таблица

В таблицах выделяются объекты (отдельные записи таблиц) и свойства (названия столбцов или названия строк):

дерево или иерархия объектов

Уровни в дереве

Рассмотрим родственные отношения в дереве:

«Сыновья» А: B, C.

«Родитель» B: A.

«Потомки» А: B, C, D, E, F, G.

«Предки» F: A, C.

Корень – узел без предков (A).
Лист – узел без потомков (D, E, F, G).
Высота – наибольшее расстояние от корня до листа (количество уровней).

файловая система (иерархия)

Допустим, на жестком диске компьютера имеются следующие папки (каталоги) с файлами:

Получим дерево:

графы

Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:

Граф – это набор вершин и связей между ними, называющихся рёбрами:

Граф, отображающий дороги между поселками

матрица и список смежности

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

Связный граф

Дерево – это связный граф без циклов (замкнутых участков).

Дерево — связный граф без циклов

взвешенные графы и весовая матрица

У взвешенных графов указан «вес ребра»:

Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Весовая матрица

Поиск кратчайшего пути (перебор)

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

В заданиях ЕГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.

Егифка ©:

Решение заданий 1 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

1_3: Решение 1 задания ЕГЭ по информатике:

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

	A	B	C	D	E	F
A		7	3
B	7		2	4	1
C	3	2		7	5	9
D		4	7		2	3
E		1	5	2		7
F			9	3	7

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

Подобные задания для тренировки

✍ Решение:

Для решения задачи используем построение дерева с подсчетом значений для каждой ветви (протяженности дорог).
При движении от корня дерева (А) вниз будем иметь в виду, что:
рассматривать вершины, которые уже есть в текущей «ветви», — не нужно,
если получаемое число (суммарная протяженность дорог) превышает какое-либо из найденных вариантов от A до F, то дальше эту ветвь можно не рассматривать.
В итоге получим дерево:

Самый короткий путь: A -> C -> B -> E -> D -> F = 11

Результат: 11

Видеоразбор задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_4: Решение 1 задания ЕГЭ по информатике:

	A	B	C	D	E	F
A		3	7		6
B	3			4	4
C	7			5		9
D		4	5			5
E	6	4				8
F			9	5	8

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

✍ Решение:

Решим задание при помощи построения дерева, вершиной которого является отправной пункт — A. На ребрах дерева будем записывать числа — результат протяженности пути до конкретной вершины.

Кратчайший путь: A -> B -> D -> F = 12

Результат: 12

1_5: Решение 1 задания ЕГЭ по информатике:

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

	A	B	C	D	E	F	Z
A		3		5			14
B			2				8
C		2					7
D					1	4	4
E						1	5
F			12		1		9
Z

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

* в учебниках 2018 года задания 2 и 3 поменяли местами: теперь 2 — Поиск кратчайшего пути, а 3 — Алгебра логики

✍ Решение:

Для решения будем использовать дерево:

Розовым отмечены неподходящие маршруты, а голубым — подходящие.
Заметим, что после 4-го уровня сверху, все варианты будут подходить.

Результат: 6

1_2: 1 задание:

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

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

Подобные задания для тренировки

✍ Решение:

Посчитаем сколько ребер у каждой вершины:

A -> 3 (В Г Д)
Б -> 1 (В)
В -> 4 (А Б Г Е)
Г -> 4 (А В Д К)
Д -> 2 (А Г)
Е -> 1 (В)
К -> 1 (Г)

Три ребра имеет только одна вершина — А, поэтому только А может соответствовать П3.
Уникальное значение количества ребер имеет также вершина Д, — два ребра. В таблице вершине Д будет соответствовать П4.
Вершины Г и В имеют по 4 ребра. Рассмотрим матрицу, в ней 4 числа соответствуют пунктам П2 и П5.
С пунктом Д пересекается только вершина Г (Г -> 4 (А В Д К)). В весовой матрице с вершиной Д пресекается П5. Значит вершина Г соответствует П5.
В П5 на пересечении с П3 находится число 6.

Результат: 6

Подробное решение данного 1 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_1: ЕГЭ по информатике:

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

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

✍ Решение:

Рассмотрим граф и посчитаем количество ребер из каждой вершины:

А - > 2 ребра (Г, В)
В - > 4 ребра (А, Г, К, Д)
Г - > 4 ребра (А, В, К, Д)
Б - > 2 ребра (Г, К)
К - > 5 ребер (Б, Г, В, Д, Е)
Е - > 2 ребра (К, Д)
Д - > 3 ребра (В, К, Е)

Мы выделили вершины, с уникальным числом ребер: 3 ребра соответствует только вершине Д, а 5 ребер соответствует только вершине К.
Рассмотрим таблицу и найдем те строки или столбцы, в которых 5 значений и 3 значения: Это П2 и П4.
Получаем П2 соответствует Д, а П4 соответствует К. На пересечении находится цифра 20.

Результат: 20

Кроме того, Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:
📹 YouTube здесь
📹 Видеорешение на RuTube здесь

1_6: Разбор 1 задания ЕГЭ:

На рисунке изображена схема дорог Н-ского района, в таблице звездочкой обозначено наличие дороги из одного населенного пункта в другой, отсутствие звездочки означает, что такой дороги нет. Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер.

	1	2	3	4	5	6	7	8
1			*	*			*
2			*	*				*
3	*	*
4	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам D и E на схеме? В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Подобные задания для тренировки

✍ Решение:

Для начала найдем уникальные вершины — у которых уникальное число ребер: это A (2 ребра) и H (6 ребер). В таблице им соответствуют номера 3 и 4:

	1	2	A	H	5	6	7	8
1			*	*			*
2			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

По схеме находим, что смежными вершинами для A являются B и G. В таблице определяем соответствующие им цифры — 1 и 2. Поскольку по заданию они нас не интересуют, обозначим их вместе:

	B,G	B,G	A	H	5	6	7	8
B,G			*	*			*
B,G			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
7	*			*	*
8		*		*		*

У обеих вершин B и G смежными являются уже известные A и H и, кроме того, вершины F и C. По первому столбцу или первой строке находим, что F или C будет соответствовать цифра 7, а по второй строке — цифра 8. Обозначим их в таблице:

	B,G	B,G	A	H	5	6	F,C	F,C
B,G			*	*			*
B,G			*	*				*
A	*	*
H	*	*			*	*	*	*
5				*		*	*
6				*	*			*
F,C	*			*	*
F,C		*		*		*

В результате получаем, что искомым вершинам — D и E — соответствуют цифры 5 и 6. Поскольку не имеет значения, какой именно цифре должна соответствовать та или иная вершина, то в ответе просто запишем эти цифры в порядке возрастания.

Результат: 56

Источник

Автор — Лада Борисовна Есакова.

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

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

Моделирование — это построение моделей, предназначенных для изучения и объектов, процессов или явлений.

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

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

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

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

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

1. Поиск графа, соответствующего таблице

Пример 1.

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

Решение:

Сравним значения таблицы и схем:

Согласно таблице вершина A должна быть связана с вершинами B (значение 4) и D (значение 5). Т.е. AB=4, AD=5. На схеме значения указаны около соответствующего ребра. Сразу отбрасываем 1),2),3) схемы, т.к. на них AD не равно 5.

Для уверенности проверим все остальные ребра схемы 4): BC=3, BD=6, что совпадает со значениями таблицы. Правильная схема 4).

Ответ: 4

2. Анализ информации в таблице и графе

Пример 2.

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

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

Решение:

На графе из вершины В выходит 5 ребер, значит в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6.

На графе из вершины Е выходит 4 ребра, значит в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4.

Таким образом, нам нужно найти расстояние между П6 и П4. Согласно таблице оно равно 20.

Ответ: 20

3. Поиск информации в таблице по условию

Пример 3.

Между четырьмя местными аэропортами: ЛУГОВОЕ, ДЯТЛОВО, НИКИТИНО и ОРЕХОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Путешественник оказался в аэропорту ЛУГОВОЕ в полночь. Определите самое раннее время, когда он может попасть в аэропорт ОРЕХОВО. Считается, что путешественник успевает совершить пересадку в аэропорту, если между временем прилета в этот аэропорт и временем вылета проходит не менее часа.

1) 12:05 2) 12:50 3)12:55 4) 13:30

Решение:

Можно, конечно, решить эту задачу просто глядя на таблицу и перебирая подходящие варианты, но есть риск ошибиться или пропустить нужную строчку. Поэтому рекомендую нарисовать дерево всех возможных путей из аэропорта ЛУГОВОЕ в ОРЕХОВО:

Средняя ветка не подходит, т.к. между прилетом в аэропорт ДЯТЛОВО (11:15) и вылетом из ДЯТЛОВО в ОРЕХОВО (12:00) интервал меньше часа.

Из оставшихся двух выбираем раннее время прилета: 12:55.

Ответ: 3

4. Выбор таблицы по условию

Пример 4.

В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

Решение:

По каждой из схем построим дерево с корнем в точке C и листьями в точке B. При этом нам не нужно строить дерево полностью. Как только найдена ветка с протяженностью больше 6, делаем вывод, что таблица не удовлетворяет указанному условию:

Таблицы 1), 2) и 4) отвергаем уже при анализе первой ветки дерева.

В таблице 3) две ветки вообще не приведут в B, а две другие имеют суммарную длину, не превышающую 6.

Ответ: 3

5. Поиск кратчайшего пути по таблице

Пример 5.

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

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

1) 13 2) 16 3) 19 4) 21

Решение:

При решении этой задачи тоже не следует полагаться на простой визуальный анализ таблицы. Чтобы избежать ошибок, построим дерево с корнем в вершине A и листьями в вершине Z. При этом нам не нужно выписывать все ветки. Второй путь из A в С (AC=6) длиннее первого (ABC=5), значит и весь маршрут через него будет длиннее.

Второй путь из C в E (CE=10) длиннее первого (CDE=6), значит и весь маршрут через него будет длиннее.

Нам остается сложить длины всех отрезков и выбрать маршрут с наименьшей длиной.

Это верхняя ветка дерева с длиной 16.

Ответ: 2

Спасибо за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №3. Таблицы и схемы, поиск оптимального маршрута по таблице и по расписанию.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из данного раздела.

Публикация обновлена:
09.03.2023

Источник

Привет! Начинаем новый видеокурс по подготовке к ЕГЭ по информатике 2022.

В этой статье будет разобрано задание 1.

Рассмотрим типовые задачи из первого задания ЕГЭ по информатике 2022.

Задача (Разминочная)

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

Решение:

Здесь мы можем легко найти точку К. Только эта точка имеет две дороги. Смотрим построчно таблицу и получаем, что точка К — это 2 пункт (только во второй строчке два числа).

У К два соседа. Один пятерной город (точка В), а другой это точка Д. Точка В — это пункт 6. Значит, точка Д — это пункт 3 (второе число во второй строке ведёт к пункту 3).

Точка Д связана помимо тех, о которых мы уже говорили, с точкой Г. Посмотрим в третьей строчке таблице, какой пункт у точки Г. Это пункт 1.

Нам нужно найти расстояние между Г и Д. Посмотрим, какое число находится на пересечении пунктов 1 и 3. Получается число 4. Это и есть наш ответ.

Ответ: 4

Отличное начало для подготовки к ЕГЭ по информатике 2022.

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

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

Решение:

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

Её легко найти в таблице. Это пункт П2. В таблице в этой строчке два числа. А если мы пойдём по соседям П2, мы придём в П1 и П3, это тройные города (имеют по три дороги).

У города Б один сосед является двойным! Давайте выберем город Б из двух вариантов: П1 и П3 (соседи Б).

Проверяем соседей в начале у П1. У этого города есть в соседях двойной город — это П4. Значит, П1 — это и есть город Б.

Уже два нужных нам города, которые есть в вопросе задачи, мы вычислили.

Найдём число, которое находится на пересечении П1 и П2 (между городами Б и В). Получается число 16. Это и есть ответ.

Ответ: 16

Решим задачу из немного другого типа, который стал модным в ЕГЭ по информатике 2022.

Задача (Частичная неопределённость)

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

Решение:

В этой задаче в таблице вместо конкретной длины показан сам факт дороги (или её отсутствие) между городами.

Определим «особую точку». Это точка F, т.к. только эта точка имеет 6 дорог, а остальные имеют меньше дорог. Цифра 3 — это точка F.

Определим точки C и E. Это легко сделать, т.к. эти точки соединяются с точкой F и имеют по 2 дороге. По две дороге имеют цифры 4 и 5. Мы точно не можем узнать, где конкретно C, а где E. Просто знаем, что именно эти цифры занимают данные буквы. Цифры 5 и 4 соединяются помимо F (3) c цифрами 1 и 2. Значит, цифры 1 и 2 — это точки D и B (или B и D).

B и D соединены кроме точки F (3) и «двойных» точек, рассмотренных ранее, с нашими искомыми точками G и A. Из таблицы видно, что точки G и A — это цифры 6 и 7 (или 7 и 6 ).

Данная задача отличается тем, что приходится действовать в условиях не полной определённости. Тем не менее, мы нашли искомые цифры для букв G и A, просто не знаем их точный порядок.

Нам в ответе нужно записать эти цифры в порядке возрастания. Ответ будет 67.

Ответ: 67.

Задача (Классическая)

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите сумму длин дорог из пункта А в пункт Б и из пункта З в Е. В ответе запишите только целое число.

Решение:

Снова задача на частичную неопределённость.

Найдём город Г. Это пункт П4. Эта точка является двойной, и у неё два соседа являются тройными городами.

П4 связана с П3 и П5, значит, на этих позициях размещаются точки В и Д. Точно, где какая точка мы не сможем определить, т.к. структура симметричная, но предположим, что П3 — В, а П5 — Д.

Пункты П3 и П5 связаны кроме тех, о которых уже говорили, с пунктами П6 и П2. Тогда, по нашему предположению, П6 — Б, П2 — Е.

Аналогично находим, что П1 — точка А, П7 — точка З.

Тогда по нашему предположению ответ будет 13+10=23. Если бы мы предположение сделали неправильно, то слагаемые поменялись бы 10+13=23. Сумма остаётся такой же!

Ответ: 23

Задача (Кратчайший путь)

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

Решение:

Будем решать методом дерева!

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

Берём строку A. От неё идёт три дороги. Рисуем их.

Далее рассматриваем точку B (1 ветку). Назад в A нет смысла идти. В C тоже не рисуем, потому что во второй ветке будем рассматривать эту точку, и в неё можно будет попасть из A не за 10, а за 9 км. Для D рисуем. Для E так же есть более короткий вариант (3 ветка), поэтому не рисуем. Для F рисуем.

Для точки D (в 1 ветке) точки B и C нет смысла рассматривать. Рисуем только от D до F.

Рассмотрим вторую ветку (точку C). В точки A, B, D нет смысла идти, т.к. эти точки мы рассматривали в более выгодных вариантах уже. Так же не рисуем и до точки E, потому что в третьей ветке можно в E попасть быстрее.

Проанализируем последнюю ветку (точку E). Назад в A нет смысла идти. В пункт B можно добраться быстрее по первой ветке. Если пойдём в C, то суммарная длина до C будет 9, а подобный вариант мы рассмотрели во второй ветке. До F рисуем.

И дерево готово! Самый кратчайший путь от A до F получается A-E-F, и длина его равна 17.

Ответ: 17

Задача (нестандартная)

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

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

Решение:

Тяжело определить разницу между пунктами К и Д (структура симметричная). Но у нас есть подсказка, что от пункта K до В длина не превышает 29 км.

Отметим те строчки бордовой галочкой, которые претендуют на точку К (строчки с тремя числами). А те строчку, которые претендуют на точку В, зелёной галочкой (строчки, где два числа).

Проверяем строчку П4. Первое число 32 точно не подходит. Второе число 15, оно ведёт в П5. Если перейдём на строчку П5, то там есть более-менее подходящие число 12, чтобы в сумме 15+12=27 получалось меньше, чем 29. Но это число 12 не ведёт в точку с двумя дорогами (на строчку с зелёной галочкой). Получается, что второе число 15 в строке П4 тоже не подходит. Третье число 16 ведёт на строчку П6, и дальше нет вариантов, чтобы сумма была меньше 29.

Значит, П4 не является точкой К. Следовательно, точкой К является П5.

И путь до двойной точки: П5—П6—П2. Длина в этом случае равна 12+15 = 27.

Значит, точка П6 — это E, а П2 — это В.

Длина дороги между П6 и П2 равна 15, это и будет ответ.

Ответ: 15

Источник

1. Вспоминай формулы по каждой теме

2. Решай новые задачи каждый день

3. Вдумчиво разбирай решения

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

Заметим, что количество путей в город Е является суммой путей в города Ж, Г и Д. Количество путей в город Ж — сумма путей в города Г и Б. Таким образом получаем:

Г = Б + В

Д = Г + В

Ж = Б + Г

Е = Ж + Г + Д

Заметим, что в пункты Б и В можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

Ответ: 8

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

Заметим, что количество путей в город Ж является суммой путей в города Д, Г и Е. Количество путей в город Г — сумма путей в город В, Б и Е. Таким образом получаем:

Г = Б + В + Е

Д = В + Г

Ж = Д + Г + Е

Заметим, что в пункты Б, В и Е можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

Ответ: 8

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

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

Найдём все варианты маршрутов из A в E и выберем самый короткий.

Из пункта A можно попасть в пункты B, D.

Из пункта B можно попасть в пункты C, D.

Из пункта C можно попасть в пункты D, E.

A—B—C—E: длина маршрута 7 км.

A—D—B—C—E: длина маршрута 9 км.

A—D—C—E: длина маршрута 6 км.

Самый короткий путь: A—D—C—E. Длина маршрута 6 км.

Ответ: 6

Геральт спешит выручить Цири из плена Кагыра. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Геральта до Цири (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Найдём все варианты маршрутов из И в М и выберем самый короткий.

Из пункта И можно попасть в пункты А, Б, Г, М.

Из пункта Г можно попасть в пункты И, М.

Из пункта В можно попасть в пункты А, Б.

Из пункта Б можно попасть в пункты В, И, М.

И—А—В—Б—М: длина маршрута 7 км.

И—Б—М: длина маршрута 4 км.

И—Г—М: длина маршрута 7 км.

И—М: длина маршрута 8 км.

Самый короткий путь: И—Б—М. Длина маршрута 4 км. Самый короткий участок этого пути равен 1 км.

Ответ: 1

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.

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

Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.

Ответ: 13

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

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

В К можно приехать из Е, В, Г или Ж, поэтому N = NК = NЕ + NВ + N Г + NЖ (*).

Аналогично:

NЕ = NБ + NВ = 1 + 2 = 3;

NЖ = NД = 1;

NВ = NА + NБ = 1 + 1 = 2;

NГ = NА + NД = 1 + 1 = 2;

NД = NА = 1;

NБ = NА = 1.

Подставим в формулу (*): N = 3 + 2 + 2 + 1 = 8.

Ответ: 8

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

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

Проанализируем некоторые возможные маршруты.

Маршрут B—D—E, длина 11 км.

Маршрут B—C—D—E, длина 10 км.

Маршрут B—С—D—A—E, длина 9 км.

Любые другие маршруты будут длиннее маршрута B—С—D—A—E. Самый короткий путь: B—С—D—A—E. Длина маршрута 9 км.

Ответ: 9

Курс Глицин. Любовь, друзья, спорт и подготовка к ЕГЭ

Источник

Расписания и пути

Типы только для начальной подготовки (не нужно тренировать для экзамена):

Длина пути ( 14 )

Устаревшие типы (нажмите, чтобы раскрыть)

Найти количество путей ( 4 )

Длина пути ( 14 )

1746 ege1 Длина пути