Алгоритмизация и программирование. Язык Python

1. Алгоритмизация и программирование. Язык Python

1
Алгоритмизация и
программирование.
Язык Python
§ 41. Стек, дек, очередь
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

2. Что такое очередь?

Алгоритмизация и программирование. Язык Python, 11 класс
2
Что такое очередь?
Очередь – это линейный список,
для которого введены две
операции:
• добавление элемента в конец
• удаление первого элемента
FIFO = Fist In – First Out.
Применение:
• очереди сообщений в операционных системах
• очереди запросов ввода и вывода
• очереди пакетов данных в маршрутизаторах
•…
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

3. Заливка области

Алгоритмизация и программирование. Язык Python, 11 класс
3
Заливка области
Задача. Рисунок задан в виде матрицы A, в которой
элемент A[y][x] определяет цвет пикселя на
пересечении строки y и столбца x. Перекрасить в цвет
2 одноцветную область, начиная с пикселя (x0,y0).
0 1 2 3 4
0 1 2 3 4
0 0 1 0 1 1
0 0 2 0 1 1
1 1 1 1 2 2
(1,2)
1 2 2 2 2 2
2 0 1 0 2 2
2 0 2 0 2 2
3 3 3 1 2 2
3 3 3 1 2 2
4 0 1 1 0 0
4 0 1 1 0 0
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

4. Заливка: использование очереди

Алгоритмизация и программирование. Язык Python, 11 класс
4
Заливка: использование очереди
добавить в очередь точку (x0,y0)
color = цвет начальной точки
while очередь не пуста:
взять из очереди точку (x,y)
if A[y][x] == color:
A[y][x] = новый цвет
добавить в очередь точку (x-1,y)
добавить в очередь точку (x+1,y)
добавить в очередь точку (x,y-1)
добавить в очередь точку (x,y+1)
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

5. Заливка

Алгоритмизация и программирование. Язык Python, 11 класс
5
Заливка
Подготовка:
YMAX = len(A)
XMAX = len(A[0])
NEW_COLOR = 2
y0 = 0
x0 = 1
# начать заливку отсюда
color = A[y0][x0] # цвет начальной точки
Элементы очереди – координаты:
(x, y)
Q = []
Q.append ( (x0,y0) )
кортеж
!
добавить
начальную точку
Кортеж – неизменяемая последовательность
элементов (как список, но нельзя изменять)!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

6. Заливка (основной цикл)

Алгоритмизация и программирование. Язык Python, 11 класс
6
Заливка (основной цикл)
пока очередь не пуста
while len(Q) > 0:
x, y = Q.pop(0)
if A[y][x] == color:
перекрасить
A[y][x] = NEW_COLOR
if x > 0:
Q.append( (x-1,y)
if x < XMAX-1: Q.append( (x+1,y)
if y > 0:
Q.append( (x,y-1)
if y < YMAX-1: Q.append( (x,y+1)
с проверкой
выхода за
границы
К.Ю. Поляков, Е.А. Ерёмин, 2014
?
)
)
)
)
Что можно улучшить?
http://kpolyakov.spb.ru

7. Очередь: статический массив

Алгоритмизация и программирование. Язык Python, 11 класс
7
Очередь: статический массив
голова
Head
Tail
хвост
0
N-1
1
2
3
4
Удаление элемента:
Head
5
Tail
0
N-1
1
2
3
4
Добавление элемента:
Head
5
Tail
0
N-1
2
3
4
не двигаем элементы
К.Ю. Поляков, Е.А. Ерёмин, 2014
5
6
нужно знать размер
http://kpolyakov.spb.ru

8. Очередь: статический массив

Алгоритмизация и программирование. Язык Python, 11 класс
8
Очередь: статический массив
Замыкание в кольцо:
Tail
Head
1
7
N
8
9
1
Очередь заполнена:
Tail
2
3
4
5
Head
1
7
6
N
8
9
10 11 12
Очередь пуста:
1
2
3
4
5
6
Tail Head
1
N
!
Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2014
http://kpolyakov.spb.ru

9. Что такое дек?

Алгоритмизация и программирование. Язык Python, 11 класс
9
Что такое дек?
Дек – это линейный список, в котором можно добавлять и
удалять элементы как с одного, так и с другого конца.
Моделирование:
• массив (список)
изменяющегося размера
•collections.deque
добавить в начало
удалить с начала
К.Ю. Поляков, Е.А. Ерёмин, 2014
import collections
d = collections.deque()
d.append(1)
d.appendleft(0)
d.pop()
d.popleft()
http://kpolyakov.spb.ru