Python. Обработка массива 2

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

Python

К.Ю.Поляков

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

1

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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 ( "Не нашли!" )

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

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

for i in range ( N ):

if A[i] == X:

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

else:

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

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

4

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

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

if X in A:

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

else:

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

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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
for i in range(1,N):

if A[i] >

A[nMax]:

nMax = i

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

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

7

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

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

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

(первого из…)

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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(

):

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

N//2

Что плохо?
?

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

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

0

1

2

3

N-4

N-3

N-2

N-1

12

5

8

15

34

40

23

7

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

10

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Срезы в Python

11

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

N

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

12

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

N

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

разрезы

A[1:-1]

A[1:N-1]

A[-4:-2]
[18, 34]
A[N-4:N-2]

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Срезы в Python – шаг

13

0

1

2

3

4

5

6

7

8

7

12

5

8

76

18

34

40

23

0

1

2

3

4

5

6

7

8

9

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

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 класс

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

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

15

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

Задача. Отобрать элементы массива A,

удовлетворяющие некоторому условию, в массив B.

B = [ x for x in A ]

if x % 2 == 0 ]

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

число

перебрать все

элементы A

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

Особенности работы со списками

16

A = [1, 2, 3]
B = A

[1, 2, 3]

A
B

A[0] = 0

[0, 2, 3]

A
B

A = [1, 2, 3]
B = A[:]

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

[1, 2, 3]

A

[1, 2, 3]

B

A[0] = 0

[0, 2, 3]

A

[1, 2, 3]

B

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

© К.Ю. Поляков, Е.А. Ерёмин, 2014

http://kpolyakov.spb.ru

[1,2,3]

A

[4,5,6]

B

[A,B]

C

[A,B]

D

Копирование списков

17

«Поверхностное» копирование:

import copy
A = [1, 2, 3]
B = copy.copy(A)

A = [1, 2, 3]
B = [4, 5, 6]
C = [A, B]
D = copy.copy(C)
C[0][0] = 0

[1,2,3]

A

[4,5,6]

B

0

A

Влияет на C и D!
!

«Глубокое» копирование:

D = copy.deepcopy(C)
[A,B]

C

[•,•]

D

[1,2,3]

A

[4,5,6]

B

[1,2,3]
[4,5,6]

Multiple Choice

Какой массив будет создан следующим фрагментом программы:

for i in range (2, 10, 2):

• [2, 3, 4, 5, 6, 7, 8, 9, 10]

• [2, 4, 6, 8, 10]

• [2, 4, 6, 8]

• [2, 3, 4, 5, 6, 7, 8, 9]

Multiple Choice

Чему будут равны элементы массива?

• 10 9 8 7 6 5 4 3 2 1 0

• 0 1 2 3 4 5 6 7 8 9 10

• 0 1 2 3 4 5 4 3 2 1 0

• 10 9 8 7 6 5 6 7 8 9 10

Multiple Choice

Требуется заполнить массив именно так:

X = [1 3 5 7 9 11]

Какой оператор надо поместить в тело цикла вместо многоточия?

X = [0]*6

for k in range(6):

...

• X[k] = k

• X[k] = 2*k

• X[k] = 2*k - 1

• X[k] = 2*k + 1

• X[k] = 2*(k + 1)

Multiple Choice

Задан массив X из N элементов. Какое условие надо поставить вместо многоточия, чтобы найти количество четных элементов массива в переменной S?

S = 0

for j in range(N):

if ... :

S += 1

• S // 2 == 1

• S % 2 == 0

• X[j] % 2 == 1

• X[j] % 2 == 0

• X[j] // 2 == 0