Презентация содержит теоретический материал, необходимый для решения задачи №3 из ОГЭ, задачи с разобранными решениями, а также ряд задач для самостоятельного решения, в которых приведены ответы. Материал может быть использован как учителями на консультациях при подготовке учащихся к экзамену, так и самими учащимися для самоподготовки.
Подготовка к ОГЭ по
информатике: задача 3
Мочалова Марина Владимировна
Учитель информатики
ГБОУ лицей №144 Калининского района
г. СанктПетербург
Содержание
1.Теория
2.Разбор решений задач
3.Задачи для
самостоятельного решения
4.Источники
память,
поскольку
нужно
Теория
Задачи данного типа можно решить путем анализа
таблицы. Но при этом существует риск ошибки: во
первых, изза невнимательности, а вовторых, может
помнить
подвести
одновременно несколько чисел – длины различных
вариантов.
Поэтому
задачи№3 является метод использования графов.
Граф это схема, в которой обозначены объекты и
связи между ними. Объекты – это вершины графа, в
нашей задаче это города, представленные в таблице.
способом решения
самым надежным
Теория
Связи между объектами (городами) это ребра графа
(поскольку не имеют строгого направления, а лишь
показывают наличие дорог).
Для решения задачи необходимо построить граф,
с их
отобразив на нем
протяженностью, данные по условию задачи в
таблице. Затем отметить начальный и конечный
пункты и рассмотреть все возможные варианты путей.
Поскольку таблица представлена в виде визуальной
картинки, это намного облегчает поиск решения и
практически исключает вероятность ошибки.
города и
дороги
Задача 1
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых
(в километрах)
приведена в таблице.
Определите длину кратчайшего пути между пунктами
A и D. Передвигаться можно только по дорогам,
указанным в таблице.
A
B
C
D
E
A
2
6
8
B
2
3
C
6
3
5
2
E
8
2
3
D
5
3
Решение
Строим граф, отмечая города и
дороги с их длинами (из таблицы).
Просматриваем все возможные
варианты путей между начальным и
конечным пунктами и выбираем
самый наименьший.
A
B
C
D
E
2
6
8
6
3
A B C D E
8
2
3
5
3
2
3
5
2
8
3
E
2
A
2
6
5
D
Ответ: 10
B
3
C
Варианты:
ABCD = 10
ACD = 11
AED = 11
AECD = 15 (данный вариант тоже стоит
рассмотреть, так как он может
оказаться самым коротким)
Задача 2
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых
(в километрах)
приведена в таблице.
Определите длину кратчайшего пути между пунктами
B и D. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
A
B
C
D
E
A
2
2
4
B
2
5
C
2
5
1
D
4
E
4
1
4
Решение
Строим граф, отмечая города и дороги
с их длинами (из таблицы).
В пункт D можно попасть только из
пункта Е, поэтому нужно найти самый
краткий путь из В в Е.
A
B
C
D
E
A
2
2
4
B
2
5
C
2
5
1
D
4
E
4
1
4
A
2
2
4
4
E
B
5
C
1
D
Ответ: 9
Варианты:
BCED = 10
BАED = 10
ВAСED = 9 (данный вариант через
бОльшее количество городов тоже
нужно рассмотреть, так как он может
оказаться самым коротким, что и
оказалось в нашей задаче)
Задача 3
Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых (в
километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами
A и E. Передвигаться можно только по дорогам,
указанным в таблице.
A
B
C
D
E
F
A
1
5
13
B
1
2
C
5
2
1
D
1
2
5
E
2
2
F
13
5
2
Решение
Строим граф, отмечая города и
дороги с их длинами (из таблицы).
Путь из А в F содержит самый
длинный отрезок AF=13, поэтому
нужно рассмотреть все остальные
варианты. A
A B C D E
A
B
1
C 5
2
D
E
2
13
F
1
2
5
2
1
1
2
5
F
13
5
2
F
2
E
13
5
2
Ответ: 6
B
2
C
1
5
1
D
Варианты:
AFE = 15
ACDE= 8
ABCDE = 6
(данный вариант через большее
количество городов тоже нужно
рассмотреть, так как он может
оказаться самым коротким, что и
оказалось)
Задача 4
В таблице отражено наличие дорог
между пятью городами: A, B, C, D и
E. Единица на пересечении строки и
столбца указывает на наличие
дороги между городами. Укажите
схему, соответствующую таблице.
A B
1
A
1
B
0
C
0
D 0
1
1
1
E
C D E
1
0
0
1
0
1
1
0
0
1
1
1
1)
2)
3)
4)
Решение
1)
2)
3)
4)
A
B
C
D
E
A
1
0
0
1
B
1
0
1
1
C D
0
0
0
1
1
1
1
0
E
1
1
0
1
Анализируем таблицу. Пункт С имеет только одну дорогу (в D).
Поэтому варианты 2) и 4) отпадают (в этих вариантах к пункту С
ведут 2 дороги).
Выбираем для рассмотрения город, в который ведут разное
количество дорог. В город Е в 1) идут 2 дороги, а в 3) – 3 дороги.
Из таблицы видно, что по условию даны 3 дороги, т.е. ответ – 3).
Можно рассмотреть город D: по таблице к нему идут 3 дороги,
это вариант 3)
Ответ: 3
Задача 5
В таблице отражено наличие дорог
между пятью городами: A, B, C, D и
E. Единица на пересечении строки и
столбца указывает на наличие
дороги между городами. Укажите
схему, соответствующую таблице.
A
B
C
D
E
A B
1
1
0
0
0
1
1
1
C D E
1
0
0
1
0
0
1
0
0
1
1
0
1)
2)
3)
4)
Решение
1)
2)
3)
4)
A
B
C
D
E
A B
1
1
0
0
0
1
1
1
C D E
1
0
0
1
0
0
1
0
0
1
1
0
Анализируем таблицу. Пункт А имеет две дороги в В и E.
Поэтому варианты 2) и 4) отпадают.
Далее выбираем для рассмотрения город, в который ведут
разное количество дорог – это город D. В город D в варианте 1)
идут 2 дороги, а в 3) – 3 дороги. По данным таблицы видно, что
по условию даны 2 дороги, т.е. правильный ответ – 1).
Для проверки можно рассмотреть город E: по таблице к нему
идут 2 дороги, это вариант 1)
Ответ: 1
Задача 6
В таблице отражено наличие дорог
между пятью городами: A, B, C, D и E.
Единица на пересечении строки и
столбца указывает на наличие дороги
между городами. Укажите схему,
соответствующую таблице.
A B
1
A
1
B
0
C
1
D 0
1
1
0
E
C D E
0
1
0
1
0
1
0
0
0
1
1
0
1)
2)
Ответ: 2)
3)
4)
Задача 7
Между населёнными пунктами A, B, C, D, E, F построены
дороги, протяжённость которых (в километрах)
приведена в таблице.
Определите длину кратчайшего пути между пунктами A
и E. Передвигаться можно только по дорогам, указанным
в таблице.
A
B
C
D
E
F
A
1
5
13
B
1
2
C
5
2
1
D
1
2
5
E
2
2
F
13
5
2
Ответ: 6
Задача 8
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена
в таблице. Определите длину кратчайшего пути между
пунктами A и Е. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
B
2
1
A
2
5
1
C
5
1
3
2
A
B
C
D
E
D
1
3
E
2
Ответ: 5
Задача 9
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах)
приведена в таблице. Определите длину кратчайшего
пути между пунктами A и Е. Передвигаться можно
только по дорогам, протяжённость которых указана в
таблице.
A
1
4
3
7
A
B
C
D
E
B
1
2
5
C
4
2
3
E
7
2
D
3
5
3
2
Ответ: 5
Задача 10
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах)
приведена в таблице. Определите длину кратчайшего
пути между пунктами A и Е. Передвигаться можно
только по дорогам, протяжённость которых указана в
таблице.
B
2
1
3
A
2
11
12
A
B
C
D
E
F
C
D
E
11
F
12
1
3
4
3
3
3
4
3
2
2
Ответ: 7
Задача 11
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена
в таблице. Определите длину кратчайшего пути между
пунктами A и F. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
B
3
C
5
4
1
A
3
5
15
A
B
C
D
E
F
F
E
15
2
6
D
4
1
2
6
Ответ: 12
Задача 12
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена в
таблице. Определите длину кратчайшего пути между
пунктами A и Е. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
B
3
2
C
4
2
1
A
B
C
D
E
F
A
3
4
15
F
15
2
2
D
E
1
6
2
6
2
Ответ: 9
Задача 13
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена
в таблице. Определите длину кратчайшего пути между
пунктами A и Е. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
A
3
5
B
3
1
C
5
1
1
A
B
C
D
E
F
F
15
6
2
D
E
1
2
6
2
2
Ответ: 7
Задача 14
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена
в таблице. Определите длину кратчайшего пути между
пунктами A и Е. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
B
3
2
3
7
C
2
3
D
3
1
A
B
C
D
E
F
A
3
15
F
15
2
E
7
3
1
2
Ответ: 7
Задача 15
Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых (в километрах) приведена
в таблице. Определите длину кратчайшего пути между
пунктами A и Е. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
A
B
C
D
E
F
A
2
3
7
15
B
2
C
3
3
5
F
15
11
4
D
7
3
5
2
11
E
2
4
Ответ: 7
Источники
• сайт К. Полякова
http://kpolyakov.spb.ru
• Е.М Зорина, М.В. Зорин. ОГЭ2018. Информатика.
Тематические тренировочные задания. Москва. АСТ. 2017
• С.С. Крылов, Т.Е. Гурина ЕГЭ2016 – типовые
экзаменационные варианты. Информатика и ИКТ. Москва.
Национальное образование. 2016
• В.Р. Лещинер. Информатика. ЕГЭ2015. Типовые тестовые
задания. Москва. Издательство «Экзамен». 2015
дороги.pptx
