Анимация_препроцессинга_и_алгоритма

Август 9, 2022

Главная
Разное
Анимация_препроцессинга_и_алгоритма

Содержание

2. 1 Кол-во детей у #1: Поле для логов запуска алгоритма 2 2 3 Кол-во детей у
3. 1 Кол-во детей у #1: Поле для логов запуска алгоритма Визуализация алгоритма – шаг 0. Выделение
4. 1 Кол-во детей у #1: Поле для логов запуска алгоритма Шаг 1 – свап u и
5. 1 Шаг 2 – Подъем u до достижения глубины вершины v, по степеням двойки, начиная со
6. 1 Шаг 2 – Когда подъем закончился, вершину u красим в тот же цвет, что и
7. 1 2 4 5 6 7 9 8 10 u v 11 13 3 12 13
8. 1 2 4 5 6 7 9 8 10 u v 11 13 3 12 13
10. Скачать презентацию

Слайд 2

1
Кол-во детей у #1:
Поле для логов запуска алгоритма
2
2
3
Кол-во детей у

#2:

Кол-во детей у #3:

Препроцессинг

Слайд 3

1
Кол-во детей у #1:
Поле для логов запуска алгоритма
Визуализация алгоритма –

шаг 0. Выделение u, v

Кол-во детей у #2:

Кол-во детей у #3:

Слайд 4

1
Кол-во детей у #1:
Поле для логов запуска алгоритма
Шаг 1 –

свап u и v, если нужен для того, чтобы глубина u была не меньше глубины v

Кол-во детей у #2:

Кол-во детей у #3:

Слайд 5

1
Шаг 2 – Подъем u до достижения глубины вершины v, по

степеням двойки, начиная со старшей.
При каждом присваивании новая вершина u красится в желтый цвет, буква u перемещается к ней, а старая вершина красится в цвет остальных вершин. Старая и новая вершины и соединены стрелкой желтого цвета, подписанной длиной прыжка (1, 2, 4 и тд)

Слайд 6

1
Шаг 2 – Когда подъем закончился, вершину u красим в тот

же цвет, что и v

Слайд 7

1
2
4
5
6
7
9
8
10
u
v
11
13
3
12
13
15
14
Шаг 3. Поиск общего предка. Начинается одновременный параллельный подъем вершин u

и v двоичными прыжками (некоторые из них неудачные). Прыжки идут с шагом степеней двойки, от большей к меньшей. Выше корня не поднимаемся.
Если прыжок на степень двойки из вершин u, v попадает в одну и ту же вершину, прыжок считается неудачным. Иначе удачным.
А) Анимация неудачных прыжков: вершина, куда был прыжок, подсвечивается красным цветом, а также рисуются стрелки от вершин u и v до этой вершины красным цветом. Рядом со стрелками пишется длина прыжка, в данном случае 16.

Слайд 8

1
2
4
5
6
7
9
8
10
u
v
11
13
3
12
13
15
14
Шаг 3. Поиск общего предка.
Б) Анимация удачных прыжков: вершины, куда были

прыжки, подсвечивается зеленым цветом, буквы u, v передвигаются к ним, а также рисуются стрелки от старых вершин u и v до новых зеленым цветом. Рядом со стрелками пишется длина прыжка, в данном случае 4.