1 of 155

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

1

2 of 155

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

§ 62. Массивы

2

3 of 155

Что такое массив?

3

Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер (индекс).

Надо:

Как ввести 10000 переменных?

?

выделять память
записывать данные в нужную ячейку
читать данные из ячейки

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

4 of 155

Что такое массив?

4

5	10	15	20	25

0	1	2	3	4

A

массив

2

15

НОМЕР �элемента массива

(ИНДЕКС)

A[0]

A[1]

A[2]

A[3]

A[4]

ЗНАЧЕНИЕ элемента массива

A[2]

НОМЕР (ИНДЕКС) �элемента массива: 2

ЗНАЧЕНИЕ �элемента массива: 15

Массив = таблица!

!

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

5 of 155

Массивы в Python: списки

5

A = [1, 3, 4, 23, 5]

Что будет?

?

A = [1, 3] + [4, 23] + [5]

[1, 3, 4, 23, 5]

A = [0]*10

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

A = list ( range(10) )

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

6 of 155

Генераторы списков

6

A =[ i for i in range(10) ]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

A =[ i*i for i in range(10) ]

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Что будет?

?

for i in range(10)

i*i

from random import randint

A = [ randint(20,100)

for x in range(10)]

randint(20,100)

A = [ i for i in range(100)

if isPrime(i) ]

if isPrime(i)

случайные числа

условие отбора

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

7 of 155

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

7

Создание массива:

Обработка:

N = 5

A = [0]*N

# обработать A[0]

# обработать A[1]

# обработать A[2]

# обработать A[3]

# обработать A[4]

1) если N велико (1000, 1000000)?

2) при изменении N программа не должна меняться!

?

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

8 of 155

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

8

Обработка с переменной:

i = 0;

# обработать A[i]

i += 1

# обработать A[i]

i += 1

# обработать A[i]

i += 1

# обработать A[i]

i += 1

# обработать A[i]

i += 1

Обработка в цикле:

i = 0

while i < N:

# обработать A[i]

i += 1

Цикл с переменной:

for i in range(N):

# обработать A[i]

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

9 of 155

Ввод массива с клавиатуры

9

Создание массива:

Ввод с клавиатуры:

N = 10

A = [0]*N

for i in range(N):

print ( "A[", i, "]=",

sep = "", end = "" )

A[i] = int( input() )

A[1] =

A[2] =

A[3] =

A[4] =

A[5] =

5

12

34

56

13

sep = ""

end = ""

не разделять элементы

не переходить на новую строку

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

10 of 155

Ввод массива с клавиатуры

10

Ввод без подсказок:

Ввод в одной строке:

A = [ int(input()) for i in range(N) ]

data = input() # "1 2 3 4 5"

s = data.split() # ["1","2","3","4","5"]

A = [ int(x) for x in s ]

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

int(input())

int(x)

или так:

s = input().split() # ["1","2","3","4","5"]

A = list( map(int, s) ) # [1,2,3,4,5]

применить int ко всем элементам s

построить список

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

11 of 155

Вывод массива на экран

11

Как список:

print ( A )

[1, 2, 3, 4, 5]

В строчку через пробел:

for i in range(N):

print ( A[i], end = " " )

1 2 3 4 5

или так:

for x in A:

print ( x, end = " " )

1 2 3 4 5

быстрее всего так:

s = [ str(x) for x in A]

print ( " ".join( s ) )

соединить через пробел

записать как строку

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

12 of 155

Заполнение случайными числами

12

from random import randint

N = 10

A = [ randint(20,100)

for x in range(N)]

randint(20,100)

случайные числа

[20,100]

from random import randint

N = 10

A = [0]*N

for i in range(N):

A[i] = randint(20,100)

или так:

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

13 of 155

Перебор элементов

13

Общая схема (можно изменять A[i]):

for i in range(N):

... # сделать что-то с A[i]

Если не нужно изменять A[i]:

for x in A:

... # сделать что-то с x

for i in range(N):

A[i] += 1

x = A[0], A[1], ..., A[N-1]

for x in A:

print ( x )

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

14 of 155

Подсчёт нужных элементов

14

Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше �180 см, но меньше 190 см?

count = 0

for x in A:

if 180 < x and x < 190:

count += 1

Как решать?

?

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

15 of 155

Перебор элементов

15

Сумма:

summa = 0

for x in A:

if 180 < x and x < 190:

summa += x

print ( summa )

print ( sum(A) )

или так:

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

16 of 155

Перебор элементов

16

Среднее арифметическое:

count = 0

summa = 0

for x in A:

if 180 < x and x < 190:

count += 1

summa += x

print ( summa/count )

среднее арифметическое

или так:

B = [ x for x in A ]

if 180 < x and x < 190]

print ( sum(B)/len(B) )

отбираем нужные

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

17 of 155

Задачи

17

«A»: Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений.

Пример:

Массив:

1 2 3 4 5

Среднее арифметическое 3.000

«B»: Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.

Пример:

Массив:

3 2 52 4 60

Ср. арифм. элементов [0,50): 3.000

Ср. арифм. элементов [50,100]: 56.000

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

18 of 155

Задачи

18

«C»: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).

Пример:

Массив:

3 2 1 4 5

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

19 of 155

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

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

19

20 of 155

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

20

Найти элемент, равный 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 класс

21 of 155

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

21

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

22 of 155

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

for i in range ( N ):

if A[i] == X:

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

break

else:

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

22

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

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

if X in A:

nX = A.index(X)

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

else:

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

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

23 of 155

Задачи

23

«A»: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X.

Пример:

Массив:

1 2 3 1 2

Что ищем:

2

Нашли: A[2]=2, A[5]=2

Пример:

Массив:

1 2 3 1 2

Что ищем:

6

Ничего не нашли.

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

24 of 155

Задачи

24

«B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом.

Пример:

Массив:

1 2 3 3 2 1

Есть: 3

Пример:

Массив:

1 2 3 4 2 1

Нет

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

25 of 155

Задачи

25

«C»: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом.

Пример:

Массив:

3 2 1 3 2 5

Есть: 3, 2

Пример:

Массив:

3 2 1 4 0 5

Нет

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

26 of 155

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

26

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

27 of 155

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

27

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

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

?

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

!

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

28 of 155

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

28

M = max(A)

nMax = A.index(M)

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

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

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

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

29 of 155

Задачи

29

«A»: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера.

Пример:

Массив:

1 2 3 4 5

Минимальный элемент: A[1]=1

Максимальный элемент: A[5]=5

«B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.

Пример:

Массив:

5 5 3 4 1

Максимальный элемент: A[1]=5

Второй максимум: A[2]=5

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

30 of 155

Задачи

30

«C»: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение.

Пример:

Массив:

3 4 5 5 3 4 5

Максимальное значение 5

Количество элементов 3

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

31 of 155

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

31

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

32 of 155

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

32

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

33 of 155

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

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

33

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-1?

?

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

34 of 155

Срезы в Python

34

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

35 of 155

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

35

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:-1]

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

разрезы

A[1:N-1]

A[-4:-2]

[18, 34]

A[N-4:N-2]

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

36 of 155

Срезы в Python – шаг

36

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

37 of 155

Задачи

37

«A»: Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент.

Пример:

Массив:

1 2 3 4 5 6

Результат:

6 1 2 3 4 5

«B»: Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.

Пример:

Массив:

1 2 3 4 5 6

Результат:

3 2 1 6 5 4

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

38 of 155

Задачи

38

«C»: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.

Пример:

Массив:

20 -90 15 -34 10 0

Результат:

20 15 10 -90 -34 0

Количество положительных элементов: 3

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

39 of 155

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

39

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

Задача. Отобрать элементы массива 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 класс

40 of 155

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

40

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

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

B = [ x for x in A ]

if x % 2 == 0 ]

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

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

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

41 of 155

Задачи

41

«A»: Заполнить массив случайными числами в интервале �[-10,10] и отобрать в другой массив все чётные отрицательные числа.

Пример:

Массив А:

-5 6 7 -4 -6 8 -8

Массив B:

-4 -6 -8

«B»: Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.

Пример:

Массив А:

12 13 85 96 47

Массив B:

13 47

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

42 of 155

Задачи

42

«C»: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.

Пример:

Массив А:

12 13 85 34 47

Массив B:

13 34

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

43 of 155

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

43

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

44 of 155

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

[1,2,3]

A

[4,5,6]

B

[A,B]

C

[A,B]

D

44

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

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[1][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]

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

45 of 155

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

§ 64. Сортировка

45

46 of 155

Что такое сортировка?

46

Сортировка – это расстановка элементов массива в заданном порядке.

…по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …

Алгоритмы:

простые и понятные, но неэффективные для больших массивов

метод пузырька
метод выбора

сложные, но эффективные

«быстрая сортировка» (QuickSort)
сортировка «кучей» (HeapSort)
сортировка слиянием (MergeSort)
пирамидальная сортировка

время

работы

N

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

47 of 155

Метод пузырька (сортировка обменами)

47

Идея: пузырек воздуха в стакане воды поднимается со дна вверх.

Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

4
5
2
1
3

4
5
2
1
3

4
5
1
2
3

1
4
5
2
3

сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-й проход:

4
1
5
2
3

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

48 of 155

Метод пузырька

48

1
4
5
2
3

1
4
5
2
3

1
4
2
5
3

2-й проход:

3-й проход:

1
2
4
5
3

1
2
3
4
5

1
2
4
5
3

4-й проход:

1
2
3
4
5

1
2
3
4
5

1
2
4
3
5

Для сортировки массива из N элементов нужен �N-1 проход (достаточно поставить на свои места N-1 элементов).

!

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

49 of 155

Метод пузырька

49

1-й проход:

сделать для j от N-2 до 0 шаг -1

если A[j+1]< A[j] то

# поменять местами A[j] и A[j+1]

2-й проход:

сделать для j от N-2 до 1 шаг -1

если A[j+1]< A[j] то

# поменять местами A[j] и A[j+1]

1

единственное отличие!

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

50 of 155

Метод пузырька

50

1-й проход:

for j in range(N-2, -1 ,-1):

if A[j+1]< A[j]:

# поменять местами A[j] и A[j+1]

2-й проход:

for j in range(N-2, 0 ,-1):

if A[j+1]< A[j]:

# поменять местами A[j] и A[j+1]

0

единственное отличие!

от N-2 до 0 шаг -1

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

51 of 155

Метод пузырька

51

for i in range(N-1):

for j in range(N-2, i-1 ,-1):

if A[j+1] < A[j]:

A[j], A[j+1] = A[j+1], A[j]

i-1

Как написать метод «камня»?

?

Как сделать рекурсивный вариант?

?

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

52 of 155

Задачи

52

«A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.

«B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.

«С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

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

53 of 155

Метод выбора (минимального элемента)

53

Идея: найти минимальный элемент и поставить его на первое место.

for i in range(N-1):

найти номер nMin минимального � элемента из A[i]..A[N]

if i != nMin:

поменять местами A[i] и A[nMin]

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

54 of 155

Метод выбора (минимального элемента)

54

for i in range(N-1):

if i!= nMin:

A[i], A[nMin] = A[nMin], A[i]

nMin = i

for j in range(i+1,N):

if A[j] < A[nMin]:

nMin = j

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

55 of 155

Задачи

55

«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.

Пример:

Массив:

5 3 4 2 1 6 3 2

После сортировки:

2 3 4 5 6 3 2 1

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

56 of 155

Задачи

56

«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем.

Пример:

Массив:

5 3 4 2 1 6 3 2 4

После сортировки:

1 2 2 3 3 4 4 5 6

Различных чисел: 5

«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

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

57 of 155

Быстрая сортировка (QuickSort)

57

Ч.Э.Хоар

Идея: выгоднее переставлять элементы, который находятся дальше друг от друга.

6	5	4	3	2	1

1	5	4	3	2	6

1	2	4	3	5	6

1	2	3	4	5	6

Для массива из N элементов нужно всего N/2 обменов!

!

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

58 of 155

Быстрая сортировка

58

Шаг 2: переставить элементы так: �

при сортировке элементы не покидают « свою область»!

Шаг 1: выбрать некоторый элемент массива X

A[i] <= X	A[i] >= X

Шаг 3: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

78	6	82	67	55	44	34

Как лучше выбрать X?

?

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

59 of 155

Быстрая сортировка

59

Разделение:

выбрать любой элемент массива (X=67)

установить L = 1, R = N
увеличивая L, найти первый элемент A[L], �который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], �который <= X (должен стоять слева)
если L<=R то поменять местами A[L] и A[R] � и перейти к п. 3� иначе стоп.

78	6	82	67	55	44	34

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

60 of 155

Быстрая сортировка

60

78	6	82	67	55	44	34
L						R

34	6	82	67	55	44	78
		L			R

34	6	44	67	55	82	78
			L	R

34	6	44	55	67	82	78
			R	L

L > R : разделение закончено!

!

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

61 of 155

Быстрая сортировка

61

N = 7

A = [0]*N

# заполнить массив

qSort( A, 0, N-1 ) # сортировка

# вывести результат

Основная программа:

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

62 of 155

Быстрая сортировка

62

def qSort ( A, nStart, nEnd ):

if nStart >= nEnd: return

L = nStart; R = nEnd

X = A[(L+R)//2]

while L <= R:

while A[L] < X: L += 1

while A[R] > X: R -= 1

if L <= R:

A[L], A[R] = A[R], A[L]

L += 1; R -= 1

qSort ( A, nStart, R )

qSort ( A, L, nEnd )

qSort ( A, nStart, R )

qSort ( A, L, nEnd )

рекурсивные вызовы

while A[L] < X: L += 1

while A[R] > X: R -= 1

разделение на 2 части

массив

начало

конец

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

63 of 155

Быстрая сортировка

63

Случайный выбор элемента-разделителя:

from random import randint

def qSort ( A, nStart, nEnd ):

...

X = A[randint(L,R)]

...

X = A[randint(L,R)]

или так:

from random import choice

def qSort ( A, nStart, nEnd ):

...

X = choice ( A[L:R+1] )

...

X = choice ( A[L:R+1] )

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

64 of 155

Быстрая сортировка

64

В стиле Python:

from random import choice

def qSort ( A ):

if len(A) <= 1: return A

X = random.choice(A)

B1 = [ b for b in A if b < X ]

BX = [ b for b in A if b == X ]

B2 = [ b for b in A if b > X ]

return qSort(B1) + BX + qSort(B2)

рекурсивные вызовы

Что плохо?

?

окончание рекурсии

Asort = qSort( A )

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

65 of 155

Быстрая сортировка

65

N	метод� пузырька	метод� выбора	быстрая сортировка
1000	0,09 с	0,05 с	0,002 с
5000	2,4 с	1,2 с	0,014 с
15000	22 с	11 с	0,046 с

Сортировка массива случайных значений:

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

66 of 155

Сортировка в Python

66

B = sorted( A )

алгоритм Timsort

По возрастанию:

B = sorted( A, reverse = True )

По убыванию:

reverse = True

По последней цифре:

def lastDigit ( n ):

return n % 10

B = sorted( A, key = lastDigit )

key = lastDigit

или так:

B = sorted( A, key = lambda x: x % 10 )

lambda x: x % 10

«лямбда»-функция

(функция без имени)

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

67 of 155

Сортировка в Python – на месте

67

A.sort()

По возрастанию:

A.sort ( reverse = True )

По убыванию:

reverse = True

По последней цифре:

def lastDigit ( n ):

return n % 10

A.sort ( key = lastDigit )

key = lastDigit

или так:

A.sort( key = lambda x: x % 10 )

lambda x: x % 10

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

68 of 155

Задачи

68

«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.

Пример:

Массив:

5 3 4 2 1 6 3 2

После сортировки:

2 3 4 5 6 3 2 1

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

69 of 155

Задачи

69

«B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки.

Пример:

Массив:

5 3 4 2 1 6 3 2 4

После сортировки:

1 2 2 3 3 4 4 5 6

Различных чисел: 5

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

70 of 155

Задачи

70

«C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

«D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

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

71 of 155

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

§ 65. Двоичный поиск

71

72 of 155

Двоичный поиск

72

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

X = 7

X < 8

8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4

X > 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6

X > 6

Выбрать средний элемент A[c] и сравнить с X.
Если X == A[c], то нашли (стоп).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

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

73 of 155

Двоичный поиск

73

A[0]						A[N-1]	A[N]
6	34	44	55	67	78	82

L

R

с

6	34	44	55	67	78	82

L

с

R

X = 44

6	34	44	55	67	78	82

L

с

R

6	34	44	55	67	78	82

L

R

L = R-1 : поиск завершен!

!

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

74 of 155

Двоичный поиск

74

L = 0; R = N # начальный отрезок

while L < R-1:

c = (L+R) // 2 # нашли середину

if X < A[c]: # сжатие отрезка

R = c

else: L = c

if A[L] == X:

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

else:

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

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

75 of 155

Двоичный поиск

75

N	линейный поиск	двоичный поиск
2	2	2
16	16	5
1024	1024	11
1048576	1048576	21

скорость выше, чем при линейном поиске

нужна предварительная сортировка

Когда нужно применять?

?

Число сравнений:

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

76 of 155

Задачи

76

«A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

2

Число 2 найдено.

Количество сравнений: 2

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

77 of 155

Задачи

77

«B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

4

Число 4 встречается 2 раз(а).

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

14

Число 14 не встречается.

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

78 of 155

Задачи

78

«C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

Введите число X:

12

Число 12 найдено.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

Введите число X:

11

Число 11 не найдено. Ближайшее число 12.

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

79 of 155

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

§ 66. Символьные строки

79

80 of 155

Символьные строки

80

Начальное значение:

Вывод на экран:

print ( s )

s = "Привет!"

Длина строки:

n = len ( s )

print ( s[5] )

0	1	2	3	4	5	6
П	р	и	в	е	т	!
s[0]	s[1]	s[2]	s[3]	s[4]	s[5]	s[6]

Строка – это

последовательность

символов!

!

print ( s[-2] )

s[len(s)-2]

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

81 of 155

Символьные строки

81

Ввод с клавиатуры:

s = input ( "Введите имя: " )

Изменение строки:

s[4] = "a"

Строка – это неизменяемый объект!

!

... но можно составить новую строку:

s1 = s + "a"

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

82 of 155

Символьные строки

82

s = input( "Введите строку:" )

s1 = "" # строка-результат

for c in s:

if c == "а":

c = "б"

s1 = s1 + c

print ( s1 )

Задача: заменить в строке все буквы "а" на буквы "б".

перебрать все символы в строке

добавить символ к строке-результату

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

83 of 155

Задачи

83

«A»: Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные).

Пример:

Введите строку:

ааббААББссСС

Результат:

ббааББААссСС

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

84 of 155

Задачи

84

«B»: Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.

Пример:

Введите строку:

Вася пошел гулять

Найдено слов: 3

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

85 of 155

Задачи

85

«C»: Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.

Пример:

Введите строку:

Вася пошел гулять

Самое длинное слово: гулять, длина 6

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

86 of 155

Операции со строками

86

Объединение (конкатенация) :

s1 = "Привет"

s2 = "Вася"

s = s1 + ", " + s2 + "!"

"Привет, Вася!"

Срезы:

s = "0123456789"

s1 = s[3:8] # "34567"

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

разрезы

0	1	2	3	4	5	6	7	8	9

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

87 of 155

Операции со строками

87

Срезы:

s = "0123456789"

s1 = s[:8] # "01234567"

от начала строки

s = "0123456789"

s1 = s[3:] # "3456789"

до конца строки

s1 = s[::-1] # "9876543210"

реверс строки

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

88 of 155

Операции со строками

88

Срезы с отрицательными индексами:

s = "0123456789"

s1 = s[:-2] # "01234567"

N-2

s = "0123456789"

s1 = s[-6:-2] # "4567"

N-2

N-6

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

89 of 155

Операции со строками

89

Вставка:

s = "0123456789"

s1 = s[:3] + "ABC" + s[3:]

Удаление:

s = "0123456789"

s1 = s[:3] + s[9:] # "0129"

"012"

"9"

"012ABC3456789"

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

90 of 155

Стандартные функции

90

Верхний/нижний регистр:

s = "aAbBcC"

s1 = s.upper() # "AABBCC"

s2 = s.lower() # "aabbcc"

Проверка на цифры:

s = "abc"

print ( s.isdigit() ) # False

s1 = "123"

print ( s1.isdigit() ) # True

… и много других.

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

91 of 155

Поиск в строках

91

s = "Здесь был Вася."

n = s.find ( "с" ) # n = 3

if n >= 0:

print ( "Номер символа", n )

else:

print ( "Символ не найден." )

Находит первое слева вхождение подстроки!

!

s = "Здесь был Вася."

n = s.rfind ( "с" ) # n = 12

Поиск с конца строки:

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

92 of 155

Пример обработки строк

92

Задача: Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы».

Пример:

Введите имя, отчество и фамилию:

Василий Алибабаевич Хрюндиков

Результат:

Хрюндиков В.А.

Алгоритм:

найти первый пробел и выделить имя
удалить имя с пробелом из основной строки
найти первый пробел и выделить отчество
удалить отчество с пробелом из основной строки
«сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

Алибабаевич Хрюндиков

Хрюндиков

Хрюндиков В.А.

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

93 of 155

Пример обработки строк

93

print ( "Введите имя, отчество и фамилию:" )

s = input()

n = s.find ( " " )

name = s[:n] # вырезать имя

s = s[n+1:]

n = s.find ( " " )

name2 = s[:n] # вырезать отчество

s = s[n+1:] # осталась фамилия

s = s + " " + name[0] + "." + name2[0] + "."

print ( s )

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

94 of 155

Пример обработки строк

94

print ( "Введите имя, отчество и фамилию:" )

s = input()

fio = s.split()

s = fio[2] + " " + fio[0][0] + "." + fio[1][0] + "."

print ( s )

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

Василий Алибабаевич Хрюндиков

fio[2]

fio[1]

fio[0]

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

95 of 155

Задачи

95

«A»: Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы.

Пример:

Введите фамилию, имя и отчество:

Иванов Петр Семёнович

П.С. Иванов

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

96 of 155

Задачи

96

«B»: Ввести адрес файла и «разобрать» его на части, разделенные знаком "/". Каждую часть вывести в отдельной строке.

Пример:

Введите адрес файла:

C:/Фото/2013/Поход/vasya.jpg

C:

Фото

2013

Поход

vasya.jpg

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

97 of 155

Задачи

97

«C»: Напишите программу, которая заменяет во всей строке одну последовательность символов на другую.

Пример:

Введите строку:

(X > 0) and (Y < X) and (Z > Y) and (Z <> 5)

Что меняем: and

Чем заменить: &

Результат

(X > 0) & (Y < X) & (Z > Y) & (Z <> 5)

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

98 of 155

Преобразования «строка» – «число»

98

Из строки в число:

s = "123"

N = int ( s ) # N = 123

s = "123.456"

X = float ( s ) # X = 123.456

Из числа в строку:

N = 123

s = str ( N ) # s = "123"

s = "{:5d}".format(N) # s = " 123"

X = 123.456

s = str ( X ) # s = "123.456"

s = "{:7.2f}".format(X) # s = " 123.46"

s = "{:10.2e}".format(X) # s = " 1.23e+02"

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

99 of 155

Задачи

99

«A»: Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые.

Пример:

Введите выражение:

12+3+45

Ответ: 60

«B»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые.

Пример:

Введите выражение:

12-3+45

Ответ: 54

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

100 of 155

Задачи

100

«C»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление.

Пример:

Введите выражение:

12*3+45

Ответ: 81

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

101 of 155

Задачи

101

«D»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление (div).

Пример:

Введите выражение:

2*(3+45)+4

Ответ: 100

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

102 of 155

Строки в процедурах и функциях

102

Задача: построить процедуру, которая заменяет в строке s все вхождения слова-образца wOld на слово-замену wNew.

пока слово wOld есть в строке s

удалить слово wOld из строки

вставить на это место слово wNew

Что плохо?

?

wOld: "12"

wNew: "A12B"

зацикливание

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

103 of 155

Замена всех экземпляров подстроки

103

s

res

б)

wNew

s

res

в)

s

res

г)

wOld

res

s

а)

wNew

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

104 of 155

Замена всех экземпляров подстроки

104

рабочая строка s	результат res
"12.12.12"	""
".12.12"	"A12B"
".12"	"A12B.A12B"
""	"A12B.A12B.A12B"

s = "12.12.12"

s = replaceAll ( s, "12", "A12B" )

print( s )

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

105 of 155

Замена всех экземпляров подстроки

105

def replaceAll ( s, wOld, wNew ):

lenOld = len(wOld)

res = ""

while len(s) > 0:

p = s.find ( wOld )

if p < 0:

res = res + s

return

if p > 0: res = res + s[:p]

res = res + wNew

if p+lenOld >= len(s):

s = ""

else:

s = s[p+lenOld:]

return res

добавить слово-замену

строка кончилась

взять «хвост»

взять начало перед образцом

искать образец

если не нашли

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

106 of 155

Замена всех экземпляров подстроки

106

s = "12.12.12"

s = s.replace( "12", "A12B" )

print ( s )

Встроенная функция:

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

107 of 155

Задачи

107

«A»: Напишите функцию, которая отсекает всю часть строки после первого слова.

Пример:

Введите строку: Однажды в студёную зимнюю пору...

Первое слово: Однажды

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

108 of 155

Задачи

108

«B»: Напишите функцию, которая заменяет расширение файла на заданное новое расширение.

Пример:

Введите имя файла: qq

Введите новое расширение: tmp

Результат: qq.tmp

Пример:

Введите имя файла: qq.exe

Введите новое расширение: tmp

Результат: qq.tmp

Пример:

Введите имя файла: qq.work.xml

Введите новое расширение: tmp

Результат: qq.work.tmp

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

109 of 155

Задачи

109

«C»: Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.

Пример:

Введите строку:

В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.

Результат:

В 2013 году в школе 123 состоялся очередной выпуск 11 классов.

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

110 of 155

Рекурсивный перебор

110

Задача. В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита.

Ы	?	?	?

перебор L-1 �символов

Ш	?	?	?

Ч	?	?	?

0	?	?	?

задача для слов длины К сведена к задаче для слов длины L-1!

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

111 of 155

Рекурсивный перебор

111

перебор L символов

w[0]="Ы"

# перебор последних L-1 символов

w[0]="Ш"

# перебор последних L-1 символов

w[0]="Ч"

# перебор последних L-1 символов

w[0]="О"

# перебор последних L-1 символов

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

112 of 155

Рекурсивный перебор

112

# основная программа

TumbaWords ( "ЫШЧО", "", 3 );

def TumbaWords ( A, w, L ):

if len(w) == L:

print ( w )

return

for c in A:

TumbaWords ( A, w + c, L )

нужная длина слова

слово полной длины

по всем символам алфавита

алфавит

слово

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

113 of 155

Задачи

113

«A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов.

«B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов.�Программа не должна строить другие слова, не соответствующие условию.

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

114 of 155

Задачи

114

«C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. �Программа не должна строить другие слова, не соответствующие условию.

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

115 of 155

Сравнение строк

115

пар

парк

Пар

?

Сравнение по кодам символов:

	A	B	...	Y	Z
CP-1251	65	66	...	89	90
UNCODE	65	66	...	89	90

	a	b	...	y	z
CP-1251	97	98	...	121	122
UNCODE	97	98	...	121	122

	0	1	...	8	9
CP-1251	48	49	...	56	57
UNCODE	48	49	...	56	57

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

116 of 155

Сравнение строк

116

	А	Б	...	Ё	...	Ю	Я
CP-1251	192	193	...	168	...	222	223
UNCODE	1040	1041	...	1025	...	1070	1071

	а	б	...	ё	...	ю	я
CP-1251	224	225	...	184	...	254	255
UNCODE	1072	1073	...	1105	...	1102	1103

5STEAM < STEAM < Steam < steam

steam < ПАР < Пар < пАр < пар < парк

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

117 of 155

Сортировка строк

117

aS = [] # пустой список строк

print ( "Введите строки для сортировки:" )

while True:

s1 = input()

if s1 == "": break

aS.append ( s1 ) # добавить строку в список

aS.sort() # сортировка

print ( aS )

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

118 of 155

Задачи

118

«A»: Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке.

Пример:

Введите 5 строк:

1. тепловоз

2. арбуз

3. бурундук

4. кефир

5. урядник

Список слов в алфавитном порядке:

арбуз, бурундук, кефир, тепловоз, урядник

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

119 of 155

Задачи

119

«B»: Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке.

Пример:

Введите слова:

1. тепловоз

2. арбуз

Список слов в алфавитном порядке:

арбуз, тепловоз

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

120 of 155

Задачи

120

«C»: Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии.

Пример:

Введите ФИО:

А.Г. Урядников

Б.В. Тепловозов

В.Д. Арбузов

Список в алфавитном порядке:

В.Д. Арбузов

Б.В. Тепловозов

А.Г. Урядников

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

121 of 155

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

§ 67. Матрицы

121

122 of 155

Что такое матрица?

122

	0	1	2
0	-1	0	1
1	-1	0	1
2	0	1	-1

Как закодировать?

?

Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца.

нет знака

нолик

крестик

строка 1, столбец 2

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

123 of 155

Создание матриц

123

A = [[-1, 0, 1],

[-1, 0, 1],

[0, 1, -1]]

Матрица – это список списков!

!

перенос на другую строку внутри скобок

A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]

или так:

Нумерация элементов с нуля!

!

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

124 of 155

Создание матриц

124

N = 3

M = 2

row = [0]*M

A = [row]*N

Нулевая матрица:

0
1
2

0	0

row

A

A[0][0] = 1

1

а правильно так:

A = []

for i in range(N):

A.append ( [0]*M )

0
1
2

0	0

A

A[0][0] = 1

0	0

0	0

1

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

125 of 155

Вывод матриц

125

print ( A )

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

def printMatrix ( A ):

for row in A:

for x in row:

print ( "{:4d}".format(x), end = "" )

print ()

1 2 3

4 5 6

7 8 9

Зачем форматный вывод?

?

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

126 of 155

Простые алгоритмы

126

Заполнение случайными числами:

import random

for i in range(N):

for j in range(M):

A[i][j] = random.randint ( 20, 80 )

print ( "{:4d}".format(A[i][j]),

end = "" )

print()

Суммирование:

s = 0

for i in range(N):

for j in range(M):

s += A[i][j]

print ( s )

Вложенный цикл!

!

s = 0

for row in A:

s += sum(row)

print ( s )

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

127 of 155

Задачи

127

«A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы.

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 11

40 12 35 15

Максимальный элемент A[2,2]=87

Минимальный элемент A[3,4]=11

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

128 of 155

Задачи

128

«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:

вычислить среднюю яркость пикселей по всему рисунку
все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255)

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 11

40 12 35 15

Средняя яркость 37.88

Результат:

0 0 255 255

0 255 0 255

255 255 0 0

255 0 0 0

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

129 of 155

Задачи

129

«С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:

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

130 of 155

Перебор элементов матрицы

130

Главная диагональ:

for i in range(N):

# работаем с A[i][i]

Побочная диагональ:

for i in range(N):

# работаем с A[i][N-1-i]

Главная диагональ и под ней:

for i in range(N):

for j in range( i+1 ):

# работаем с A[i][j]

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

131 of 155

Перестановка строк и столбцов

131

2-я и 4-я строки:

A[2], A[4] = A[4], A[2]

2-й и 4-й столбцы:

for i in range(N):

A[i][2], A[i][4] = A[i][4], A[i][2]

0
1
2
3
4

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

132 of 155

Выделение строк и столбцов

132

1-я строка:

R = A[1][:]

2-й столбец:

C = []

for row in A:

C.append(row[2])

R = A[i]

или так:

C = [ row[2] for row in A ]

главная диагональ:

D = [ A[i][i] for i in range(N) ]

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

133 of 155

Задачи

133

«A»: Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы.

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 30

40 12 35 65

Результат:

12 0 0 0

32 87 0 0

69 45 14 0

40 12 35 65

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

134 of 155

Задачи

134

«B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз:

1	2	3
4	5	6
7	8	9

7	8	9
4	5	6
1	2	3

«С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

1	2	3
4	5	6
7	8	9

7	4	1
8	5	2
9	6	3

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

135 of 155

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

§ 68. Работа с файлами

135

136 of 155

Как работать с файлами?

136

файлы

текстовые

двоичные

«plain text»:

текст, разбитый на строки;
из специальных символов только символы перехода на новую строку

любые символы
рисунки, звуки, видео, …

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

137 of 155

Принцип сэндвича

137

открыть файл

работа с файлом

закрыть файл

хлеб

начинка

Fin = open ( "input.txt" )

Fout = open ( "output.txt", "w" )

# здесь работаем с файлами

Fin.close()

Fout.close()

файловые переменные-указатели

"r" - чтение

"w" – запись

"a" – добавление

по умолчанию – на чтение (режим "r")

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

138 of 155

Ввод данных

138

Fin = open( "input.txt" )

s = Fin.readline() # "1 2"

Чтение строки:

Чтение строки и разбивка по пробелам:

s = Fin.readline().split() # ["1","2"]

Чтение целых чисел:

s = Fin.readline().split() # ["1","2"]

a, b = int(s[0]), int(s[1])

или так:

a, b = [int(x) for x in s]

или так:

a, b = map( int, s )

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

139 of 155

Вывод данных в файл

139

a = 1

b = 2

Fout = open( "output.txt", "w" )

Fout.write ( "{:d} + {:d} = {:d}\n".format(

a, b, a+b) )

Fout.close()

Все данные преобразовать в строку!

!

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

140 of 155

Чтение неизвестного количества данных

140

пока не конец файла

прочитать число из файла

добавить его к сумме

Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.

Fin = open ( "input.txt" )

sum = 0

while True:

s = Fin.readline()

if not s: break

sum += int(s)

Fin.close()

если конец файла, вернёт пустую строку

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

141 of 155

Чтение неизвестного количества данных

141

Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.

sum = 0

Fin = open ( "input.txt" )

lst = Fin.readlines()

for s in lst:

sum += int(s)

Fin.close()

прочитать все строки в список строк

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

142 of 155

Чтение неизвестного количества данных

142

Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.

sum = 0

with open ( "input.txt" ) as Fin:

for s in Fin:

sum += int(s)

Не нужно закрывать файл!

!

или так:

sum = 0

for s in open ( "input.txt" ):

sum += int(s)

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

143 of 155

Задачи

143

«A»: Напишите программу, которая находит среднее арифметическое всех чисел, записанных в файле в столбик, и выводит результат в другой файл.

«B»: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть.

«C»: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.

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

144 of 155

Обработка массивов

144

Задача. В файле записаны в столбик целые числа. Вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания.

В чем отличие от предыдущей задачи?

?

Для сортировки нужно удерживать все элементы в памяти одновременно.

!

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

145 of 155

Обработка массивов

145

Ввод массива:

A = []

while True:

s = Fin.readline()

if not s: break

A.append ( int(s) )

Ввод в стиле Python:

s = Fin.read().split()

A = list ( map(int, s) )

Сортировка:

A.sort()

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

146 of 155

Обработка массивов

146

Вывод результата:

Fout = open ( "output.txt", "w" )

Fout.write ( str(A) )

Fout.close()

или так:

for x in A:

Fout.write ( str(x)+"\n" )

[1, 2, 3]

1

2

3

или так:

for x in A:

Fout.write ( "{:4d}".format(x) )

1 2 3

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

147 of 155

Задачи

147

«A»: В файле в столбик записаны числа. Отсортировать их по возрастанию последней цифры и записать в другой файл.

«B»: В файле в столбик записаны числа. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа.

«C»: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.

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

148 of 155

Обработка строк

148

Задача. В файле записано данные о собаках: в каждой строчке кличка собаки, ее возраст и порода:

Мухтар 4 немецкая овчарка

Вывести в другой файл сведения о собаках, которым меньше 5 лет.

пока не конец файла Fin

прочитать строку из файла Fin

разобрать строку – выделить возраст

если возраст < 5 то

записать строку в файл Fout

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

149 of 155

Чтение данных из файла

149

Чтение одной строки:

s = Fin.readline()

Разбивка по пробелам:

data = s.split()

Выделение возраста:

sAge = data[1]

age = int ( sAge )

Кратко всё вместе:

s = Fin.readline()

age = int ( s.split()[1] )

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

150 of 155

Обработка строк

150

Fin = open ( "input.txt" )

Fout = open ( "output.txt", "w" )

while True:

s = Fin.readline()

if not s: break

age = int ( s.split()[1] )

if age < 5:

Fout.write ( s )

Fin.close()

Fout.close()

Полная программа:

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

151 of 155

Обработка строк

151

lst = Fin.readlines()

for s in lst:

age = int ( s.split()[1] )

if age < 5:

Fout.write ( s )

или так:

for s in open ( "input.txt" ):

age = int ( s.split()[1] )

if age < 5:

Fout.write ( s )

или так:

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

152 of 155

Задачи

152

«A»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:

<Фамилия> <Имя> <Количество баллов>

Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов.

«B»: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией:

П. Иванов

И. Петров

...

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

153 of 155

Задачи

153

«C»: В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:

<Фамилия> <Имя> <Количество баллов>

Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных:

П. Иванов 98

И. Петров 96

...

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

154 of 155

Конец фильма

154

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

eremin@pspu.ac.ru

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

155 of 155

Источники иллюстраций

155

www.mcdonalds.com
иллюстрации художников издательства «Бином»
авторские материалы

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