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

Август 7, 2022

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

Содержание

2. Что такое очередь? Очередь – это линейный список, для которого введены две операции: • добавление элемента
3. Заливка области Задача. Рисунок задан в виде матрицы A, в которой элемент A[y][x] определяет цвет пикселя
4. Заливка: использование очереди добавить в очередь точку (x0,y0) color = цвет начальной точки while очередь не
5. Заливка YMAX = len(A) XMAX = len(A[0]) NEW_COLOR = 2 y0 = 0 x0 = 1
6. Заливка (основной цикл) while len(Q) > 0: x, y = Q.pop(0) if A[y][x] == color: A[y][x]
7. Очередь: статический массив нужно знать размер не двигаем элементы голова хвост Удаление элемента: Добавление элемента:
8. Очередь: статический массив Замыкание в кольцо: Очередь заполнена: Очередь пуста:
10. Скачать презентацию

Слайд 2

Что такое очередь?
Очередь – это линейный список, для которого введены две

операции:
• добавление элемента в конец
• удаление первого элемента

FIFO = Fist In – First Out.

Применение:

очереди сообщений в операционных системах
очереди запросов ввода и вывода
очереди пакетов данных в маршрутизаторах
…

Слайд 3

Заливка области
Задача. Рисунок задан в виде матрицы A, в которой элемент

A[y][x] определяет цвет пикселя на пересечении строки y и столбца x. Перекрасить в цвет 2 одноцветную область, начиная с пикселя (x0,y0).

(1,2)

Слайд 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)

Слайд 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) )

кортеж

добавить начальную точку

Слайд 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) )

пока очередь не пуста

перекрасить

с проверкой выхода за границы

Слайд 7