Моделирование. Списки и деревья. Графы

1. Моделирование

13.12.2021
Моделирование
Списки и деревья. Графы
Дома:
1) §16, 17
2) РЭШ Урок №2 «Графы»:
Видеоурок (конспект)
Тренировочные задания
Контрольные задания В1 и В2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Оптимальный маршрут (стр. 113)

Моделирование, 9 класс
2
Оптимальный маршрут (стр. 113)
Из
Березовое
Березовое
Лесное
Полевое
Осиновое
Лесное
Осиновое
Березовое
Лесное
Полевое
В
Лесное
Осиновое
Березовое
Лесное
Полевое
Осиновое
Лесное
Полевое
Полевое
Осиновое
Отправл.
07:30
11:50
12:50
13:20
14:00
14:20
14:40
16:00
16:10
17:40
Прибытие
10:00
14:10
15:20
14:40
17:15
15:30
15:50
17:50
17:30
19:55
Березовое: 8:00
Полевое
17:50 П
16:00
Б 07:30
11:50
10:00 Л
14:00
14:10 О
14:40
К.Ю. Поляков, Е.А. Ерёмин, 2018
17:15 П
15:50 Л 16:10
17:30 П
http://kpolyakov.spb.ru

3. Что такое дерево?

Моделирование, 9 класс
3
Что такое дерево?
директор
Уровень 1
Уровень 2
Уровень 3
главный инженер
Петров
Иванов
Фомин
Дерево – это структура
данных, которая служит
моделью многоуровневой
структуры (иерархии).
главный бухгалтер
Алексеева
Сидорова
лист лист
лист
лист
лист
Лес – это несколько деревьев.
корень
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Из чего состоит дерево?

Моделирование, 9 класс
4
Из чего состоит дерево?
A – корень
D, E, F, G – листья
A
рёбра
B
D
E
C
F
B, C – промежуточные
узлы
G
Путь — это последовательность узлов, где каждый
следующий связан с предыдущим.
Высота дерева — это наибольшая длина пути от
корня дерева к листу.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Родители и дети

Моделирование, 9 класс
5
Родители и дети
Родитель – сын: между ними есть ребро.
B – родитель для D и E
D и E – сыновья для B
A
B
D
C
E
F
G
Предок – потомок: между ними есть путь.
A и B – предки для D и E
B, D и E – потомки для A
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

6. Кратчайший путь (перебор)

Моделирование, 9 класс
6
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
Ответ: 7
http://kpolyakov.spb.ru

7. Задача

Моделирование, 9 класс
7
Задача
Между населёнными пунктами A, B, C, D, E построены дороги,
протяжённость которых (в километрах) приведена в таблице (см.
рисунок). Определите длину кратчайшего пути между пунктами A и
Е, проходящего через пункт С. Передвигаться можно только по
дорогам, протяжённость которых указана в таблице.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

8. Задача

Моделирование, 9 класс
8
Задача
Определите длину кратчайшего пути между пунктами
A и Е, проходящего через пункт С.
A
1
B
С
6
С
D
4
D
3
3
3
5
6
С
6
3
3
D
4
1
2
3
С
9
2
E
К.Ю. Поляков, Е.А. Ерёмин, 2018
8
Ответ: 8
http://kpolyakov.spb.ru

9. Количество путей из А в Ж

Моделирование, 9 класс
9
Количество путей из А в Ж
Б
1
Д
1+1+1=3
1
А
1
1+1+1+1+3=7
Ж
Г
В
!
1
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Задача

Моделирование, 9 класс
10
Задача
На рисунке — схема дорог, связывающих города А, Б, В,
Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из города А в город К,
проходящих через город В?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Задача

Моделирование, 9 класс
11
Задача
А К через В
Решение:
1) вычеркнем те дороги,
которые минуют город В:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Задача

Моделирование, 9 класс
12
Задача
А К через В
Решение:
К= Д+Е+Ж = 2+4+4 = 10
1
2
2
10
4
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
4
Ответ: 10
http://kpolyakov.spb.ru

13. Задача

Моделирование, 9 класс
13
Задача
На рисунке — схема дорог, связывающих города А, Б, В,
Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в
одном направлении, указанном стрелкой. Сколько
существует различных путей из города А в город К,
проходящих через город Д?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Задача

Моделирование, 9 класс
14
Задача
А К через Д?
Решение:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

15. Задача

Моделирование, 9 класс
15
Задача
А К через Д?
Решение:
К= Ж + И = 6+3 = 9
3
1
2
6
3
9
3
Ответ: 9
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru