Моделирование. § 16. Списки и деревья

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

1
Моделирование
§ 16. Списки и деревья
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Что такое список?

Моделирование, 9 класс
2
Что такое список?
Список – последовательность элементов, в которой
важен порядок их расположения.
П
О
Л
И
предыдущий
Г
Л
О
Т
следующий
Список как модель:
слово = список букв, текст = список абзацев
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Операции со списком

Моделирование, 9 класс
3
Операции со списком
• замена элемента
• удаление элемента
• вставка нового элемента
?
Какие операции на
каждом шаге?
КРАН КОАН КОРН КОРО КОРОН КОРОНА
?
Более короткие варианты?
Операция
Замена гласной буквы на гласную или
согласной на согласную.
Замена гласной на согласную или согласной
на гласную.
Вставка или удаление буквы.
?
Цена
1
2
5
СКАНЕР ПРИНТЕР с наименьшей стоимостью?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

Моделирование, 9 класс
6
Родители и дети
Родитель – сын: между ними есть ребро.
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

7. Генеалогическое дерево

Моделирование, 9 класс
7
Генеалогическое дерево
Иванов А.Б.
Иванова Д.А.
внуки
Иванов К.А.
Иванов C.К.
К.Ю. Поляков, Е.А. Ерёмин, 2018
Семёнова М.А.
Семёнов C.C.
дети
Семёнов А.C.
http://kpolyakov.spb.ru

8. Классификации

Моделирование, 9 класс
8
Классификации
Хищные
Псообразные
Псовые
Енотовые
Медвежьи
Кошкообразные
Кошачьи
Гиеновые
Мангустовые
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9. Файловая система

Моделирование, 9 класс
9
Файловая система
Документы
Тексты
Фотографии
Доходы.doc Расходы.odt Отдых.txt Папа.jpg
Мама.gif
Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Арифметические выражения

Моделирование, 9 класс
12
Перебор вариантов
Составить все двухбуквенные слова, которые можно
записать с помощью алфавита {A, Б, В}.
пустое дерево
Б
A
В
БВ
A
Б
В
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
Б
В
A
Б
В
http://kpolyakov.spb.ru

11. Запишите выражения, соответствующие дереву:

Моделирование, 9 класс
13
Дерево для двоичного кода
А
0
?
Б
11
В
Г
Д
101 110 111
Можно однозначно
декодировать?
0
А
0
0
Условие Фано: ни одно из
кодовых слов не совпадет
с началом другого
кодового слова.
!
1
1
В
1
Б
0
Г
1
Д
тогда однозначно
декодируется!
Все буквы должны быть в листьях!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Перебор вариантов

Моделирование, 9 класс
14
С помощью дерева перебора найдите
все трёхзначные числа, меньшие 300,
сумма цифр которых равна 6.
Сколько чисел вы нашли?
К.Ю. Поляков, Е.А. Ерёмин, 2018
11
http://kpolyakov.spb.ru

13. Дерево для двоичного кода

Моделирование, 9 класс
15
Перебор вариантов
Разведчик выяснил, что ключ к замку от сейфа
состоит из трёх символов, причём могут
использоваться буквы из алфавита {A, B, C, D}. Две
одинаковые буквы не могут стоять рядом. Рядом с
буквой D обязательно должна стоять буква A. Если в
ключе есть буква B, то там не может быть буквы C.
?
Сколько возможных ключей?
К.Ю. Поляков, Е.А. Ерёмин, 2018
14
http://kpolyakov.spb.ru

14. С помощью дерева перебора найдите все трёхзначные числа, меньшие 300, сумма цифр которых равна 6.

Моделирование, 9 класс
16
Задача
Сообщения, содержат буквы А, Б, В, Г; используется
двоичный код, для которого выполняется условие
Фано. Известны кодовые слова: А: 111, Б: 0, В: 100.
Найдите кратчайшее кодовое слово для буквы Г, при
котором код будет допускать однозначное
декодирование. Если таких кодов несколько, укажите
код с наименьшим числовым значением.
Используйте дерево.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru