Моделирование
Что такое список?
Операции со списком
Что такое дерево?
Из чего состоит дерево?
Родители и дети
Генеалогическое дерево
Классификации
Файловая система
Арифметические выражения
Запишите выражения, соответствующие дереву:
Перебор вариантов
Дерево для двоичного кода
С помощью дерева перебора найдите все трёхзначные числа, меньшие 300, сумма цифр которых равна 6.
822.50K
Категория: ИнформатикаИнформатика

Моделирование. § 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
English     Русский Правила