Методы программирования. Громов Ю.Ю - 52 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

52
Для входных данных (36), вводимых по порядку слева направо, по
окончании алгоритма таблица FATHER получит следующее заполнение:
FATHER
5 0 2 2 0 8 2 2 8 ,
1 2 3 4 5 6 7 8 9
что представляет лес, изображённый на рис. 24.
Рис. 24. Лес, определяющий разбиение (37)
Рассмотрим ещё одно важное практическое приложение, исполь-
зующее понятие дерева при анализе вычислительных алгоритмов. В нём
решается задача определения, сколько раз выполняется каждый шаг не-
которого алгоритма при однократном его исполнении. Применение де-
ревьев позволяет в этой задаче определить независимые неизвестные и
даёт систематический метод их обнаружения.
Пусть алгоритм представлен блок-схемой, изображённой на рис. 25.
В ней блоки обозначают шаги алгоритма, буква или цифра внутри блока –
сколько раз должен быть выполнен этот шаг за один проход алгоритма.
Стрелки указывают возможные переходы между блоками.
Рис. 25. Блок-схема алгоритма
5
1
6 9
2
8
3 4 7
A
B
C
D
C
1
E
F
G
Начало Конец
S
R
P
H
Q
L
K
J
e
1
e
2
e
3
e
4
e
5
e
6
e
7
e
8
e
9
e
10
e
11
e
12
e
13
e
14
e
15
e
16
e
17
e
18
e
19
e
20
e
21
e
22
e
23
e
24
e
25
e
26
e
27

Страницы