1 of 15

Программирование на языке Python

§ 63. Алгоритмы обработки массивов

1

2 of 15

Поиск в массиве

2

Найти элемент, равный X:

i = 0

while A[i] != X:

i += 1

print ( "A[", i, "]=", X, sep = "" )

Что плохо?

?

i = 0

while i < N and A[i] != X:

i += 1

if i < N:

print ( "A[", i, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Что если такого нет?

?

i < N

Алгоритмизация и программирование, язык Python, 10 класс

3 of 15

Поиск в массиве

3

nX = -1

for i in range ( N ):

if A[i] == X:

nX = i

break

if nX >= 0:

print ( "A[", nX, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Вариант с досрочным выходом:

break

досрочный выход из цикла

номер найденного элемента

Алгоритмизация и программирование, язык Python, 10 класс

4 of 15

Поиск в массиве

4

for i in range ( N ):

if A[i] == X:

print ( "A[", i, "]=", X, sep = "" )

break

else:

print ( "Не нашли!" )

Варианты в стиле Python:

если не было досрочного выхода из цикла

if X in A:

nX = A.index(X)

print ( "A[", nX, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Алгоритмизация и программирование, язык Python, 10 класс

5 of 15

Максимальный элемент

5

M = A[0]

for i in range(1,N):

if A[i] > M:

M = A[i]

print ( M )

M = A[0]

for x in A:

if x > M:

M = x

Как найти его номер?

?

Варианты в стиле Python:

M = max ( A )

Если range(N)?

?

Алгоритмизация и программирование, язык Python, 10 класс

6 of 15

Максимальный элемент и его номер

6

M = A[0]; nMax = 0

for i in range(1,N):

if A[i] > M:

M = A[i]

nMax = i

print ( "A[", nMax, "]=", M, sep = "" )

nMax = 0

nMax = i

Что можно улучшить?

?

По номеру элемента можно найти значение!

!

nMax = 0

for i in range(1,N):

if A[i] > A[nMax]:

nMax = i

print ( "A[", nMax, "]=", A[nMax], sep = "" )

A[nMax]

Алгоритмизация и программирование, язык Python, 10 класс

7 of 15

Максимальный элемент и его номер

7

M = max(A)

nMax = A.index(M)

print ( "A[", nMax, "]=", M, sep = "" )

Вариант в стиле Python:

номер заданного элемента (первого из…)

Алгоритмизация и программирование, язык Python, 10 класс

8 of 15

Реверс массива

8

0	1	2	3		N-4	N-3	N-2	N-1
7	12	5	8		18	34	40	23

0	1	2	3		N-4	N-3	N-2	N-1
23	40	34	18		8	5	12	7

«Простое» решение:

for i in range( N ):

поменять местами A[i] и A[N-1-i]

N//2

Что плохо?

?

остановиться на середине!

Алгоритмизация и программирование, язык Python, 10 класс

9 of 15

Реверс массива

9

for i in range(N//2):

c = A[i]

A[i] = A[N-1-i]

A[N-1-i] = c

Варианты в стиле Python:

for i in range(N//2):

A[i], A[N-i-1]= A[N-i-1], A[i]

A.reverse()

Алгоритмизация и программирование, язык Python, 10 класс

10 of 15

Циклический сдвиг элементов

10

0	1	2	3		N-4	N-3	N-2	N-1
12	5	8	15		34	40	23	7

0	1	2	3		N-4	N-3	N-2	N-1
7	12	5	8		18	34	40	23

«Простое» решение:

c = A[0]

for i in range(N-1):

A[i] = A[i+1]

A[N-1] = c

Что плохо?

?

Почему не до N?

?

Алгоритмизация и программирование, язык Python, 10 класс

11 of 15

Срезы в Python

11

0	1	2	3		N-4	N-3	N-2	N-1
7	12	5	8		18	34	40	23

A[1:3]

[12, 5]

A[2:3]

[5]

A[:3]

[7, 12, 5]

A[0:3]

с начала

A[3:N-2]

[8,…,18,34]

A[3:]

[8,…,18,34,40,23]

A[3:N]

до конца

A[:]

[7,12,5,8,…,18,34,40,23]

копия массива

Последний элемент не входит в срез!

!

Алгоритмизация и программирование, язык Python, 10 класс

12 of 15

Срезы в Python – отрицательные индексы

12

0	1	2	3		N-4	N-3	N-2	N-1
7	12	5	8		18	34	40	23

-N	-N+1	-N+2	-N+3		-4	-3	-2	-1

A[1:-1]

[12,5,8,…,18,34,40]

A[1:N-1]

A[-4:-2]

[18, 34]

A[N-4:N-2]

Алгоритмизация и программирование, язык Python, 10 класс

13 of 15

Срезы в Python – шаг

13

0	1	2	3	4	5	6	7	8
7	12	5	8	76	18	34	40	23

A[1:6:2]

[12, 8, 18]

A[::3]

[7, 8, 34]

A[8:2:-2]

[23, 34, 76]

A[::-1]

[23,40,34,18,76,8,5,12,7]

реверс!

A.reverse()

шаг

Алгоритмизация и программирование, язык Python, 10 класс

14 of 15

Отбор нужных элементов

14

Простое решение:

Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.

B = []

сделать для i от 0 до N-1

если условие выполняется для A[i] то

добавить A[i] к массиву B

B = []

for x in A:

if x % 2 == 0:

B.append(x)

добавить x в конец массива B

Какие элементы выбираем?

?

Алгоритмизация и программирование, язык Python, 10 класс

15 of 15

Отбор нужных элементов

15

Решение в стиле Python:

Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.

B = [ x for x in A ]

if x % 2 == 0 ]

если x – чётное число

перебрать все элементы A

Алгоритмизация и программирование, язык Python, 10 класс