Как найти короткую дорогу информатика - Исправление недочетов и поиск решений вместе с Examum.ru

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

Содержание:

Объяснение 4 задания ОГЭ по информатике
- Поиск кратчайшего пути (перебор)
ОГЭ информатика разбор задания 4
- Актуальное
- Тренировочные

4-е задание: «Формальные описания реальных объектов и процессов»
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

* до 2020 г — это задание № 3 ОГЭ

Графы

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

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

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

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

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

Связный граф

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

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

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

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

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

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

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

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

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

ОГЭ информатика разбор задания 4

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

Перемотайте видеоурок на решение заданий, если не хотите слушать теорию.

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

Актуальное

Рассмотрим, как решать 4 задание по информатике ОГЭ.

Разбор задания 4.5. Демонстрационный вариант ОГЭ 2022 г ФИПИ:

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

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

✍ Решение:

Построим дерево протяженности дорог, на ветвях будем отображать протяженность. Учтем, что каждая ветвь, должна включить узел пересечения с С:

Ответ: 8

Разбор задания 4.6

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

	A	B	C	D	E	F
A		5	8	4	1
B	5		3		3	4
C	8	3		2		15
D	4		2		4	12
E	1	3		4		7
F		4	15	12	7

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

✍ Решение:

Найдём все варианты маршрутов из A в F, проходящих через пункт С, и выберем самый короткий.
Пройдемся по таблице построчно слева-направо сверху-вниз:

A—B—C—D—E--F: длина маршрута 25 км.
A—B—C—D--F: длина маршрута 29 км.
A—B—C--F: длина маршрута 28 км.
  пропустим B:
A—C--F: длина маршрута 23 км.
A—C—D—E--F: длина маршрута 20 км.
 пропустим и D:
A—C—E--F: длина маршрута 16 км.
 пропустим и E:
A—C—D--F: длина маршрута 24 км.
A—C--F: длина маршрута 23 км.
 поменяем следование маршрута, исключая пункты с большим числом км:
A—C—B--F: длина маршрута 15 км.
A—D—С—B--F: длина маршрута 13 км.

Самый короткий путь: A—D—С—B--F. Длина маршрута 13 км.
Примечание 1: Заметим, что по условию задачи дважды передвигаться по любой из дорог нельзя. Если бы по дороге можно было передвигаться дважды, то был бы другой результат.
Примечание 2: Такое задание лучше решать методом построения полного дерева без повтора пунктов — это практически исключит «потерю» какой-то ветви.

Ответ: 13

Тренировочные

Разбор задания 4.1:

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

	A	B	C	D	E
A		2	7		4
B	2
C	7			3	5
D			3		3
E	4		5	3

✍ Решение:

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

1 схема:

A: B(2), C(7), E(4) 
B: A(2), C(4)

Здесь уже можно остановиться, т.к. для вершины B по схеме два ребра, 
а по таблице одно значение (B->A=2 )

2 схема:

A: B(2), C(7), E(4) 
B: A(2)
C: A(7), D(5), E(3) 

Здесь уже можно остановиться, т.к. для вершины C стоимость по схеме 
и по таблице различается: по схеме C->D = 5, 
а по таблице на пересечении C и D цифра 3.

3 схема:

A: B(2), C(7), E(4) 
B: A(2)
C: A(7), D(3), E(5)
D: C(3), E(3)
E: A(4), C(5), D(3)

Данные на схеме полностью совпадают с табличными!

Схема 3 полностью соответствует таблице.

Ответ: 3

Разбор задания 4.2:

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

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

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

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

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

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

✍ Решение:

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

1 таблица:

A: B(3), E(2), F(2) 

Здесь уже можно остановиться, т.к. для станции A по схеме два ребра у вершины А, 
а по таблице уже три значения

2 таблица:

A: B(3), F(2) 
B: A(3), C(3), E(5), F(4)
C: B(3), D(2), E(5) 
D: C(2), E(3)
F: A(2), B(4)

Данные на схеме полностью совпадают с табличными!

Таблица 2 полностью соответствует схеме.

Ответ: 2

Разбор задания 4.3:

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

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

	A	B	C	D	E	F
A			3	4
B			4	2		2
C	3	4			4
D	4	2
E			4			2
F		2			2

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

	A	B	C	D	E	F
A		2		3
B	2		5		5
C		5				3
D	3				3
E		5		3		2
F			3		2

✍ Решение:

Для каждой из таблиц построим дерево перевозок, на ветвях будем отображать суммарную стоимость:

1 таблица:

По дереву 1-й таблицы видно, что каждая из ветвей в результате возвращает сумму большую 8. То есть таблица 1 соответствует искомому результату.

Ответ: 1

Разбор задания 4.4:

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

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

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

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

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

✍ Решение:

Решать такое задание лучше с помощью дерева:

Среди приведенных ответов кратчайший путь, равный 6 км, находится под номером 2.

Ответ: 2

Источник

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

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

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

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

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

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

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

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

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

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. Таблицы и схемы, поиск оптимального маршрута по таблице и по расписанию.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.

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

Источник

Добрый день! Сегодня посмотрим, как «бороться» с 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

Видим длину BD = 1. Попытаемся использовать эту дорогу!

C-D-B-E = 2 + 1 + 3 = 6

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

В ответе напишем путь: 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.

Источник

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

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

Тип 4 № 3

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

	A	B	C	D	E
A		1
B	1		2	2	7
C		2			3
D		2			4
E		7	3	4

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

Тип 4 № 23

	A	B	C	D	E
A		5	3
B	5		1	4
C	3	1		6
D		4	6		1
E				1

Тип 4 № 43

	A	B	C	D	E
A		3	7
B	3		2		8
C	7	2		4
D			4		1
E		8		1

Тип 4 № 63

	A	B	C	D	E
A		1
B	1		4	2	8
C		4			4
D		2			4
E		8	4	4

Тип 4 № 83

	A	B	C	D	E
A		4	7
B	4		1	5
C	7	1		3
D		5	3		1
E				1

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

Источник

Рассмотрим решение задачи 3 ГИА 2013 по информатике

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

	A	B	C	D	E	F
A		3	5			15
B	3		3
C	5	3		5	2
D			5			3
E			2			7
F	15			3	7

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

1) 9 2) 11 3) 13 4) 15

Решение

Для удобства отобразим табличные данные в виде графа

Решение задачи 2 ГИА по информатике

Теперь переберем все возможные пути из A в F:

A-B-C-E-F = 3+3+2+7 = 15

A-B-C-D-F = 3+3+5+3 = 14

A-C-E-F = 5+2+7 = 14

A-C-D-F = 5+5+3 = 13

ну и A-F = 15

Как видно, кратчайший вариант A-C-D-F = 13км. Правильный ответ 3.

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

Дополнение (ГИА 2014)

Для более качественной подготовки к ГИА по информатике рассмотрим решение задачи 3 ГИА 2014 по информатике (демоверсия ФИПИ 2014)

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

	A	B	C	D	E
A		2	5	1
B	2		1
C	5	1		3	2
D	1		3
E			2

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

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

Решение:

Для удобства предлагаю поступить так же, как и при решении задачи ГИА 2013 года и отобразить таблицу в виде графа. Для этого на листе расставляем точки — населенные пункты. В соответствии с таблицей соединяем их и подписываем расстояния.

Задача 3 ГИА 2014 по информатике

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

A-B-C-E = 2+1+2 = 5

A-C-E = 5+2 = 7

A-D-C-E = 1+3+2 = 6

Как видим, минимальное расстояние — 5 километров (маршрут A-B-C-E). Правильный ответ 2.

Рассмотрим решение задачи из диагностической работы ГИА по информатике 19 декабря 2013 года

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

ИНФ90301 задача 3

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

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

Решение:

Преобразуем таблицу в граф для удобства.

граф к задаче 3

Осталось перебрать все маршруты из A в B и посмотреть их длину:

A-C-D-B = 8+1+4 = 13

A-C-E-B = 8+3+1 = 12

A-D-B = 10+4 = 14

A-D-C-E-B = 10+1+3+1 = 15

Как видим, минимальный по длине маршрут A-C-E-B, который составляет 12 километров. Правильный ответ 2.

Автор:

Источник