Программирование на языке Python
Программирование на языке Python
Что такое массив?
Что такое массив?
Массивы в Python: списки
Генераторы списков
Добавление элементов
Удаление элементов
Ввод массива с клавиатуры
Ввод массива с клавиатуры
Вывод массива на экран
Как обработать все элементы массива?
Как обработать все элементы массива?
Заполнение случайными числами
Перебор элементов
Подсчёт количества нужных элементов
Сумма элементов массива
Перебор элементов
Задачи
Задачи
Программирование на языке Python
Поиск в массиве
Поиск в массиве
Поиск в массиве
Задачи
Задачи
Задачи
Максимальный элемент
Максимальный элемент и его номер
Максимальный элемент и его номер
Задачи
Задачи
Реверс массива
Реверс массива
Циклический сдвиг элементов
Срезы в Python
Срезы в Python – отрицательные индексы
Срезы в Python – шаг
Задачи
Задачи
Отбор нужных элементов
Отбор нужных элементов
Особенности работы со списками
Копирование списков
Задачи
Задачи
Программирование на языке Python
Что такое сортировка?
Метод пузырька (сортировка обменами)
Метод пузырька
Метод пузырька
Метод пузырька
Метод пузырька
Задачи
Метод выбора (минимального элемента)
Метод выбора (минимального элемента)
Метод вставок (insertion sort)
Метод вставок (insertion sort)
Задачи
Задачи
Сортировка слиянием
Сортировка слиянием
Сортировка слиянием
Сортировка слиянием
Быстрая сортировка (QuickSort)
Быстрая сортировка (QuickSort)
Сравнение алгоритмов сортировки
Быстрая сортировка «на месте»
Быстрая сортировка
Быстрая сортировка
Быстрая сортировка
Быстрая сортировка
Быстрая сортировка
Сортировка в Python
Сортировка в Python – на месте
Задачи
Задачи
Задачи
Программирование на языке Python
Двоичный поиск
Двоичный поиск
Двоичный поиск
Двоичный поиск
Задачи
Задачи
Задачи
Программирование на языке Python
Символьные строки
Символьные строки
Символьные строки
Задачи
Задачи
Задачи
Сравнение строк
Сравнение строк
Операции со строками
Операции со строками
Операции со строками
Удаление и вставка символов
Стандартные функции
Поиск в строках
Пример обработки строк
Пример обработки строк
Пример обработки строк
Задачи
Задачи
Задачи
Преобразования «строка» – «число»
Задачи
Задачи
Задачи
Строки в процедурах и функциях
Замена подстроки
Замена всех экземпляров подстроки
Замена всех экземпляров подстроки
Замена всех экземпляров подстроки
Замена всех экземпляров подстроки
Задачи
Задачи
Задачи
Рекурсивный перебор
Рекурсивный перебор
Рекурсивный перебор
Рекурсивный перебор + счётчик
Рекурсивный перебор + условие
Рекурсивный перебор + условие (функция)
Задачи
Задачи
Сортировка строк
Задачи
Задачи
Задачи
Программирование на языке Python
Что такое матрица?
Создание матриц
Создание матриц
Ввод матрицы с клавиатуры
Вывод матриц
Простые алгоритмы
Задачи
Задачи
Задачи
Перебор элементов матрицы
Перестановка строк и столбцов
Выделение строк и столбцов
Задачи
Задачи
Программирование на языке Python
Какие бывают файлы?
Принцип сэндвича
Ввод данных
Вывод данных в файл
Чтение неизвестного количества данных
Чтение неизвестного количества данных
Чтение неизвестного количества данных
Задачи
Обработка массивов
Обработка массивов
Обработка массивов
Задачи
Обработка строк
Чтение данных из файла
5.66M
Категория: ПрограммированиеПрограммирование

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

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

1
Программирование
на языке Python
§ 62. Массивы
§ 63. Алгоритмы обработки массивов
§ 64. Сортировка
§ 65. Двоичный поиск
§ 66. Символьные строки
§ 67. Матрицы
§ 68. Работа с файлами
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

2
Программирование
на языке Python
§ 62. Массивы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
3
Что такое массив?
? Как ввести 10000 переменных?
Массив – это группа переменных одного типа,
расположенных в памяти рядом (в соседних ячейках) и
имеющих общее имя. Каждая ячейка в массиве имеет
уникальный номер (индекс).
Надо:
• выделять память
• записывать данные в нужную ячейку
• читать данные из ячейки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
4
Что такое массив?
! Массив = таблица!
A
массив
0
1
5
10
A[0]
A[1]
НОМЕР
элемента массива
(ИНДЕКС)
22
15
15
3
4
20
25
ЗНАЧЕНИЕ
A[2]
A[3]
A[4]
элемента массива
НОМЕР (ИНДЕКС)
элемента массива: 2
A[2]
ЗНАЧЕНИЕ
элемента массива: 15
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
5
Массивы в Python: списки
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]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
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]
from random import randint случайные
числа
A = [ randint(20,100)
for x in range(10)]
A = [ i for i in range(100)
if isPrime(i) ]
условие
отбора
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7. Добавление элементов

Алгоритмизация и программирование, язык Python, 10 класс
7
Добавление элементов
A = [1, 2, 3]
в конец списка
x = 5
append ( x+3 ) # [1, 2, 3, 8]
A.append
Метод – операция, которую
можно применить к списку.
A = [1, 2, 3]
A.insert
insert ( 1, 35 ) # [1, 35, 2, 3]
?
В начало?
A.insert ( 0, 90 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
A[1]
A = [90] + A
http://kpolyakov.spb.ru

8. Удаление элементов

Алгоритмизация и программирование, язык Python, 10 класс
8
Удаление элементов
A = [1, 2, 3]
x = A.pop ( 1 )
# x = 2, A = [1, 3]
удалить A[1]
A = [1, 2, 3]
x = A.pop () # x = 3, A = [1, 2]
удалить последний
A = [11, 29, 37, 45]
A.remove( 37 ) # A = [11, 29, 45]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
9
Ввод массива с клавиатуры
Создание массива:
N = 10
A = [0]*N
Ввод с клавиатуры:
for i in range(N):
print ( f"A[{i}]=",
sep = "", end = "" )
A[i] = int( input() )
sep = ""
end = ""
не разделять
элементы
A[0] = 5
A[1] = 12
A[2] = 34
A[3] = 56
A[4] = 13
не переходить на
новую строку
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
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]
или так:
s = input().split() # ["1","2","3","4","5"]
A = list( map(int, s) ) # [1,2,3,4,5]
построить
список
К.Ю. Поляков, Е.А. Ерёмин, 2018
применить int ко
всем элементам s
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
11
Вывод массива на экран
Как список:
print ( A )
[1, 2, 3, 4, 5]
В строчку через пробел:
for i in range(N):
print ( A[i], end = " " )
или так:
for x in A:
print ( x, end = " " )
или так:
print ( *A )
К.Ю. Поляков, Е.А. Ерёмин, 2018
1 2 3 4 5
1 2 3 4 5
print (1, 2, 3, 4, 5)
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
12
Как обработать все элементы массива?
Создание массива:
N=5
A = [0]*N
Обработка:
# обработать A[0]
# обработать A[1]
# обработать A[2]
# обработать A[3]
# обработать A[4]
? 1) если N велико (1000, 1000000)?
2) при изменении N программа не должна меняться!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
13
Как обработать все элементы массива?
Обработка с переменной:
Обработка в цикле:
i=0
# обработать A[i]
i += 1
# обработать A[i]
i += 1
# обработать A[i]
i += 1
# обработать A[i]
i += 1
# обработать A[i]
i=0
while i < N:
# обработать A[i]
i += 1
Цикл с переменной:
for i in range(N):
# обработать A[i]
i += 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
14
Заполнение случайными числами
from random import randint
N = 10
A = [0]*N
for i in range(N):
A[i] = randint(20,100)
или так:
from random import randint
N = 10
A = [ randint(20,100)
for x in range(N)]
К.Ю. Поляков, Е.А. Ерёмин, 2018
случайные
числа
[20,100]
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
15
Перебор элементов
Общая схема (можно изменять A[i]):
for i in range(N):
... # сделать что-то с A[i]
for i in range(N):
A[i] += 1
Если не нужно изменять A[i]:
for x in A:
... # сделать что-то с x
x = A[0], A[1], ..., A[N-1]
for x in A:
print ( x )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

16. Подсчёт количества нужных элементов

Алгоритмизация и программирование, язык Python, 10 класс
16
Подсчёт количества нужных элементов
Задача. В массиве записаны данные о росте
баскетболистов. Сколько из них имеет рост больше
180 см, но меньше 190 см?
? Как решать?
Python:
180 < x < 190
count = 0
for x in A:
if 180 < x and x < 190:
count += 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17. Сумма элементов массива

Алгоритмизация и программирование, язык Python, 10 класс
17
Сумма элементов массива
summa = 0
for x in A:
if 180 < x < 190:
summa += x
print ( summa )
или так:
print ( sum(A) )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
18
Перебор элементов
Среднее арифметическое:
count = 0
summa = 0
for x in A:
if 180 < x < 190:
count += 1
summa += x
print ( summa/count )
среднее
арифметическое
или так:
отбираем нужные
B = [ x for x in A ]
if 180 < x < 190]
print ( sum(B)/len(B) )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
19
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

20. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
20
Задачи
«C»: Заполните массив из N элементов случайными числами
в интервале [1,N] так, чтобы в массив обязательно вошли
все числа от 1 до N (постройте случайную перестановку).
Пример:
Массив:
3 2 1 4 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

21
Программирование
на языке Python
§ 63. Алгоритмы обработки
массивов
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
22
Поиск в массиве
Найти элемент, равный X:
i=0
while A[i] != X:
i += 1
print ( f"A[{i}]={X}" )
? Что плохо?
i=0
while i < N and A[i] != X:
i += 1
Что если такого нет?
if i < N:
print ( f"A[{i}]={X}" )
else:
print ( "Не нашли!" )
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
23
Поиск в массиве
Вариант с досрочным выходом:
номер найденного
элемента
nX = -1
for i in range ( N ):
if A[i] == X:
nX = i
досрочный
break
выход из цикла
if nX >= 0:
print ( f"A[{nX}]={X}" )
else:
print ( "Не нашли!" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
24
Поиск в массиве
Варианты в стиле Python:
for i in range ( N ):
if A[i] == X:
print ( f"A[{i}]={X}" )
break
else:
print ( "Не нашли!" )
если не было досрочного выхода из цикла
if X in A:
nX = A.index(X)
print ( f"A[{nX}]={X}" )
else:
print ( "Не нашли!" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

25. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
25
Задачи
«A»: Заполните массив случайными числами в интервале
[0,5]. Введите число X и найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

26. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
26
Задачи
«B»: Заполните массив случайными числами в интервале
[0,5]. Определить, есть ли в нем элементы с
одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

27. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
27
Задачи
«C»: Заполните массив случайными числами. Определить,
есть ли в нем элементы с одинаковыми значениями, не
обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
28
Максимальный элемент
M = A[0]
for i in range(1,N):
if A[i] > M:
M = A[i]
print ( M )
? Если range(N)?
Варианты в стиле Python:
M = A[0]
for x in A:
if x > M:
M=x
? Как найти его номер?
M = max ( A )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
29
Максимальный элемент и его номер
M = A[0]; nMax = 0
for i in range(1,N):
if A[i] > M:
Что можно улучшить?
M = A[i]
nMax = ii
print ( f"A[{nMax}]={M}" )
?
! По номеру элемента можно найти значение!
nMax = 0
for i in range(1,N):
if A[i] > A[nMax]
A[nMax]:
nMax = i
print ( f"A[{nMax}]={ A[nMax] }" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
30
Максимальный элемент и его номер
Вариант в стиле Python:
номер заданного
M = max(A)
элемента (первого из…)
nMax = A.index(M)
print ( f"A[{nMax}]={M}" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

31. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
31
Задачи
«A»: Заполнить массив случайными числами и найти
минимальный и максимальный элементы массива и их
номера.
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5
«B»: Заполнить массив случайными числами и найти два
максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

32. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
32
Задачи
«C»: Введите массив с клавиатуры и найдите (за один проход)
количество элементов, имеющих максимальное
значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
33
Реверс массива
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//2
N ):
поменять местами A[i] и A[N-1-i]
? Что плохо?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
34
Реверс массива
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()
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
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
12
5
8
15
34
40
23
7
«Простое» решение:
? Почему не до N?
? Что плохо?
c = A[0]
for i in range(N-1):
A[i] = A[i+1]
A[N-1] = c
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

36. Срезы в Python

Алгоритмизация и программирование, язык Python, 10 класс
36
Срезы в Python
0
1
2
3
N-4
N-3
N-2
N-1
7
12
5
8
18
34
40
23
! Последний элемент не входит в срез!
A[1:3]
A[2:3]
A[:3]
[12, 5]
[5]
A[0:3]
[7, 12, 5]
с начала
A[3:N-2]
A[3:]
[8,…,18,34]
A[3:N]
до конца
A[:]
[8,…,18,34,40,23]
копия массива
[7,12,5,8,…,18,34,40,23]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
37
Срезы в Python – отрицательные индексы
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]
A[1:N-1]
A[-4:-2]
A[N-4:N-2]
К.Ю. Поляков, Е.А. Ерёмин, 2018
[12,5,8,…,18,34,40]
[18, 34]
http://kpolyakov.spb.ru

38. Срезы в Python – шаг

Алгоритмизация и программирование, язык Python, 10 класс
38
Срезы в Python – шаг
0
1
2
3
4
5
6
7
8
7
12
5
8
76
18
34
40
23
шаг
A[1:6:2]
A[::3]
A[8:2:-2]
A[::-1]
[12, 8, 18]
[7, 8, 34]
[23, 34, 76]
[23,40,34,18,76,8,5,12,7]
реверс!
К.Ю. Поляков, Е.А. Ерёмин, 2018
A.reverse()
http://kpolyakov.spb.ru

39. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
39
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

40. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
40
Задачи
«C»: Заполнить массив случайными числами в интервале [100,100] и переставить элементы так, чтобы все
положительные элементы стояли в начала массива, а
все отрицательные и нули – в конце. Вычислите
количество положительных элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
41
Отбор нужных элементов
Задача. Отобрать элементы массива 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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
42
Отбор нужных элементов
Задача. Отобрать элементы массива A,
удовлетворяющие некоторому условию, в массив B.
Решение в стиле Python:
перебрать все
элементы A
B = [ x for x in A ]
if x % 2 == 0 ]
если x – чётное
число
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
43
Особенности работы со списками
A = [1, 2, 3]
B=A
A
B
[1, 2, 3]
A[0] = 0
A = [1, 2, 3]
B = A[:]
[0, 2, 3]
A
[0, 2, 3]
B
[1, 2, 3]
копия массива A
A
[1, 2, 3]
B
[1, 2, 3]
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
A[0] = 0
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
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[0][0] = 0
A
«Глубокое» копирование:
D = copy.deepcopy(C)
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
[1,2,3]
B
[4,5,6]
C
[A,B]
D
[A,B]
A
B
0
[1,2,3]
[4,5,6]
! Влияет на C и D!
C
[A,B] A
B
D
[ , ]
[1,2,3]
[4,5,6]
[1,2,3]
[4,5,6]
http://kpolyakov.spb.ru

45. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
45
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

46. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
46
Задачи
«C»: Заполнить массив случайными числами и отобрать в
другой массив все числа Фибоначчи. Используйте
логическую функцию, которая определяет, является ли
переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

47
Программирование
на языке Python
§ 64. Сортировка
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
48
Что такое сортировка?
Сортировка – это расстановка элементов массива в
заданном порядке.
…по возрастанию, убыванию, последней цифре, сумме
делителей, по алфавиту, …
Алгоритмы:
• простые и понятные, но неэффективные для больших
массивов
время
работы
▫ метод пузырька
▫ метод выбора
• сложные, но эффективные
▫ «быстрая сортировка» (QuickSort)
N
▫ сортировка «кучей» (HeapSort)
▫ сортировка слиянием (MergeSort)
▫ пирамидальная сортировка
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
49
Метод пузырька (сортировка обменами)
Идея: пузырек воздуха в стакане воды поднимается со
дна вверх.
Для массивов – самый маленький («легкий» элемент
перемещается вверх («всплывает»).
1-й проход:
4
4
4
4
1
5
5
5
1
4
2
2
1
5
5
1
1
2
2
2
3
3
3
3
3
К.Ю. Поляков, Е.А. Ерёмин, 2018
• сравниваем два соседних
элемента; если они стоят
«неправильно», меняем
их местами
• за 1 проход по массиву
один элемент (самый
маленький) становится на
свое место
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
50
Метод пузырька
2-й проход:
3-й проход:
4-й проход:
1
1
1
1
1
1
1
1
1
4
4
4
2
2
2
2
2
2
5
5
2
4
4
4
3
3
3
2
2
5
5
5
3
4
4
4
3
3
3
3
3
5
5
5
5
сортировки массива из N элементов нужен
! Для
N-1 проход (достаточно поставить на свои места
N-1 элементов).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
51
Метод пузырька
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]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
Метод пузырька
52
от N-2 до 0 шаг -1
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]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
53
Метод пузырька
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]
? Как написать метод «камня»?
? Как сделать рекурсивный вариант?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

54. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
54
Задачи
«A»: Напишите программу, в которой сортировка выполняется
«методом камня» – самый «тяжёлый» элемент
опускается в конец массива.
«B»: Напишите вариант метода пузырька, который
заканчивает работу, если на очередном шаге внешнего
цикла не было перестановок.
«С»: Напишите программу, которая сортирует массив по
убыванию суммы цифр числа. Используйте функцию,
которая определяет сумму цифр числа.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
55
Метод выбора (минимального элемента)
Идея: найти минимальный элемент и поставить его на
первое место.
for i in range(N-1):
найти номер nMin минимального
элемента из A[i]..A[N]
if i != nMin:
поменять местами A[i] и A[nMin]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
56
Метод выбора (минимального элемента)
for i in range(N-1):
nMin = i
for j in range(i+1,N):
if A[j] < A[nMin]:
nMin = j
if i!= nMin:
A[i], A[nMin] = A[nMin], A[i]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

57. Метод вставок (insertion sort)

Алгоритмизация и программирование, язык Python, 10 класс
57
Метод вставок (insertion sort)
Идея: освобождаем место для нового элемента, сдвигая
те, которые должны стоять после него.
1
5
1
1
1
4
1
key
5
4
4
2
4
key
5
2
3
2
key
4
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
3
1
2
4
3
5
3
3
3
1
2
3
4
key
5
http://kpolyakov.spb.ru

58. Метод вставок (insertion sort)

Алгоритмизация и программирование, язык Python, 10 класс
58
Метод вставок (insertion sort)
Идея: освобождаем место для нового элемента, сдвигая
те, которые должны стоять после него.
все N!
for i in range(N):
key = A[i]
j=i
while j > 0 and A[j-1] > key:
A[j] = A[j-1]:
j -= 1
сдвиг всех,
которые
A[j] = key
больше key
ставим key
на место
! Устойчивая сортировка!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

59. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
59
Задачи
«A»: Массив содержит четное количество элементов.
Напишите программу, которая сортирует первую
половину массива по возрастанию, а вторую – по
убыванию. Каждый элемент должен остаться в «своей»
половине.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

60. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
60
Задачи
«B»: Напишите программу, которая сортирует массив и
находит количество различных чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
«C»: Напишите программу, которая сравнивает число
перестановок элементов при использовании сортировки
«пузырьком» и методом выбора. Проверьте ее на разных
массивах, содержащих 1000 случайных элементов,
вычислите среднее число перестановок для каждого
метода.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

61. Сортировка слиянием

Алгоритмизация и программирование, язык Python, 10 класс
61
Сортировка слиянием
Слияние отсортированных массивов:
A
6
34
67
B
44
55
78
С
6
34
44
82
98
55
67
78
82
98
Na = len(A); Nb = len(B)
пока оба массива
iA = iB = 0; C = []
непустые
while iA < Na and iB < Nb:
if A[iA] <= B[iB]:
C.append(A[iA]); iA += 1
else:
C.append(B[iB]); iB += 1
C = С + A[iA:] + B[iВ:]
добавить остаток
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

62. Сортировка слиянием

Алгоритмизация и программирование, язык Python, 10 класс
62
Сортировка слиянием
def mergeSort( A ):
выход из
if len(A) <= 1: return
рекурсии
mid = len(A) // 2
L = A[:mid]
R = A[mid:]
рекурсивные
mergeSort(L)
вызовы
mergeSort(R)
слияние
C = merge(L, R)
for i in range(len(A)):
A[i] = C[i]
копируем
? Почему нельзя A = C?
К.Ю. Поляков, Е.А. Ерёмин, 2018
результат в
массив A
http://kpolyakov.spb.ru

63. Сортировка слиянием

Алгоритмизация и программирование, язык Python, 10 класс
63
Сортировка слиянием
Процедура слияния:
def merge( A, B ):
Na = len(A); Nb = len(B)
iA = iB = 0; C = []
while iA < Na and iB < Nb:
if A[iA] <= B[iB]:
C.append(A[iA]); iA += 1
else:
C.append(B[iB]); iB += 1
C = С + A[iA:] + B[iВ:]
return C
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

64. Сортировка слиянием

Алгоритмизация и программирование, язык Python, 10 класс
64
Сортировка слиянием
работает быстро
нужен дополнительный массив
«Разделяй и властвуй» (divide and conquer):
1) задача разбивается на несколько подзадач
меньшего размера;
2) эти подзадачи решаются с помощью
рекурсивных вызовов того же (или другого)
алгоритма;
3) решения подзадач объединяются, и
получается решение исходной задачи.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
65
Быстрая сортировка (QuickSort)
разделение
I: < X
Ч.Э.Хоар
II: = X
III: > X
! Эти части нужно так же отсортировать!
? Как лучше выбирать X?
Медиана – такое значение X, что слева и справа от него
в отсортированном массиве стоит одинаковое число
элементов (долго искать …).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
66
Быстрая сортировка (QuickSort)
B1: < X
BX: = X
B2: > X
import random
Где рекурсия?
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
? Что плохо?
http://kpolyakov.spb.ru

67. Сравнение алгоритмов сортировки

Алгоритмизация и программирование, язык Python, 10 класс
67
Сравнение алгоритмов сортировки
N
Метод
пузырька
Метод
выбора
Сортировка
слиянием
Быстрая
сортировка
1000
0,08 с
0,05 с
0,006 с
0,002 с
5000
1,8 с
1,3 с
0,033 с
0,006 с
15000
17,3 с
11,2 с
0,108 с
0,019 с
~ N2
T
~ N log N
N
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

68. Быстрая сортировка «на месте»

Алгоритмизация и программирование, язык Python, 10 класс
68
Быстрая сортировка «на месте»
Шаг 1: выбрать некоторый элемент массива X
Шаг 2: переставить элементы так:
A[i] <= X
A[i] >= X
при сортировке элементы не покидают « свою область»!
Шаг 3: так же отсортировать две получившиеся области
Разделяй и властвуй (англ. divide and conquer)
78
6
82
67
55
44
34
? Как лучше выбрать X?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
69
Быстрая сортировка
Разделение:
1) выбрать любой элемент массива (X=67)
44
78
44
78
53
82
67
6
95
L
L
R
R
2) установить L = 0, R = N-1
3) увеличивая L, найти первый элемент A[L],
который >= X (должен стоять справа)
4) уменьшая R, найти первый элемент A[R],
который <= X (должен стоять слева)
5) если L<=R то поменять местами A[L] и A[R]
и перейти к п. 3
иначе стоп.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
70
Быстрая сортировка
78
L
6
82
67
55
44
34
R
34
6
82
L
67
55
44
R
78
34
6
44
67
L
55
R
82
78
34
6
44
55
R
67
L
82
78
! L > R : разделение закончено!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
71
Быстрая сортировка
Основная программа:
N=7
A = [0]*N
# заполнить массив
массив
начало
конец
qSort( A, 0, N-1 ) # сортировка
# вывести результат
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
72
Быстрая сортировка
массив
начало
конец
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
на 2 части
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
73
Быстрая сортировка
Случайный выбор элемента-разделителя:
from random import randint
def qSort ( A, nStart, nEnd ):
...
X = A[randint(L,R)]
...
или так:
from random import choice
def qSort ( A, nStart, nEnd ):
...
X = choice ( A[L:R+1] )
...
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
74
Сортировка в Python
По возрастанию:
B = sorted( A )
алгоритм
Timsort
По убыванию:
B = sorted( A, reverse = True )
По последней цифре:
def lastDigit ( n ):
return n % 10
B = sorted( A, key = lastDigit )
или так:
B = sorted( A, key = lambda x: x % 10 )
«лямбда»-функция
(функция без имени)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
75
Сортировка в Python – на месте
По возрастанию:
A.sort()
По убыванию:
A.sort ( reverse = True )
По последней цифре:
def lastDigit ( n ):
return n % 10
A.sort ( key = lastDigit )
или так:
lambda x:
x: xx %% 10
10 )
A.sort( key = lambda
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

76. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
76
Задачи
«A»: Массив содержит четное количество элементов.
Напишите программу, которая сортирует по возрастанию
отдельно элементы первой и второй половин массива.
Каждый элемент должен остаться в «своей» половине.
Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

77. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
77
Задачи
«B»: Напишите программу, которая сортирует массив и
находит количество различных чисел в нем. Используйте
алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

78. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
78
Задачи
«C»: Напишите программу, которая сравнивает число
перестановок элементов при использовании сортировки
«пузырьком», методом выбора и алгоритма быстрой
сортировки. Проверьте ее на разных массивах,
содержащих 1000 случайных элементов, вычислите
среднее число перестановок для каждого метода.
«D»: Попробуйте построить массив из 10 элементов, на
котором алгоритм быстрой сортировки c с выбором
среднего элемента показывает худшую эффективность
(наибольшее число перестановок). Сравните это
количество перестановок с эффективностью метода
пузырька (для того же массива).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

79
Программирование
на языке Python
§ 65. Двоичный поиск
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
80
Двоичный поиск
X=7
1
1
1
2
2
2
3
3
3
4
4
5
5
5
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
4
X<8
1. Выбрать средний элемент A[c] и
сравнить с X.
2. Если X == A[c], то нашли (стоп).
3. Если X < A[c], искать дальше в
первой половине.
4. Если X > A[c], искать дальше во
второй половине.
К.Ю. Поляков, Е.А. Ерёмин, 2018
X>4
X>6
6
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
81
Двоичный поиск
X = 44
A[0]
6
34
44
L
67
78
82
с
6
34
L
с
6
34
L
6
55
A[N-1] A[N]
34
44
55
R
67
78
82
R
44
55
с
R
44
55
L
67
78
82
67
78
82
R
! L = R-1 : поиск завершен!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
82
Двоичный поиск
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 ( f"A[{L}]={X}" )
else:
print ( "Не нашли!" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
83
Двоичный поиск
Число сравнений:
N
линейный
поиск
двоичный
поиск
2
2
2
16
16
5
1024
1024
11
1048576
1048576
21
скорость выше, чем при линейном поиске
нужна предварительная сортировка
? Когда нужно применять?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

84. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
84
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

85. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
85
Задачи
«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 не встречается.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

86. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
86
Задачи
«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.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

87
Программирование
на языке Python
§ 66. Символьные строки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
88
Символьные строки
Начальное значение:
! Строка – это
s = "Привет!"
последовательность
символов!
Вывод на экран:
print ( s )
print ( s[5] )
print ( s[-2] )
0
1
2
3
4
5
6
П
р
и
в
е
т
!
s[len(s)-2]
s[0] s[1] s[2] s[3] s[4] s[5] s[6]
Длина строки:
n = len ( s )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
89
Символьные строки
Ввод с клавиатуры:
s = input ( "Введите имя: " )
Изменение строки:
s[4] = "a"
! Строка – это неизменяемый объект!
... но можно составить новую строку:
s1 = s + "a"
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
90
Символьные строки
Задача: заменить в строке все буквы "а" на буквы "б".
! Строка – это неизменяемый объект!
s = input( "Введите строку:" )
s1 = ""
# строка-результат
for c in s:
перебрать все
символы в строке
if c == "а":
c = "б"
s1 = s1 + c
добавить символ к
print ( s1 )
строке-результату
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

91. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
94
Сравнение строк
print( "Введите 2 строки:" )
s1 = input()
s2 = input()
if s1 == s2:
print( s1, "=", s2 )
elif s1 < s2:
print( s1, "<", s2 )
else:
print( s1, ">", s2 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

92. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
95
Сравнение строк
А
Б
CP-1251 192 193
UNCODE 1040 1041
...
...
...
Ё
168
1025
...
...
...
Ю
Я
222 223
1070 1071
а
б
CP-1251 224 225
UNCODE 1072 1073
...
...
...
ё
184
1105
...
...
...
ю
я
254 255
1102 1103
5STEAM < STEAM < Steam < steam
steam < ПАР < Пар < пАр < пар < парк
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

93. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
96
Операции со строками
Объединение (конкатенация) :
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
97
Операции со строками
Срезы:
s = "0123456789"
s1 = s[:8]
# "01234567"
от начала строки
s = "0123456789"
s1 = s[3:]
# "3456789"
до конца строки
s1 = s[::-1]
# "9876543210"
реверс строки
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
98
Операции со строками
Срезы с отрицательными индексами:
s = "0123456789"
s1 = s[:-2]
# "01234567"
N-2
s = "0123456789"
s1 = s[-6:-2]
N-6
# "4567"
N-2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
99
Удаление и вставка символов
! Строка – это неизменяемый объект!
Удаление:
s = "0123456789"
s1 = s[:3] + s[9:]
"012"
"9"
# "0129"
Вставка:
s = "0123456789"
s1 = s[:3] + "ABC" + s[3:]
"012ABC3456789"
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
100
Стандартные функции
Верхний/нижний регистр:
s = "aAbBcC"
s1 = s.upper()
s2 = s.lower()
# "AABBCC"
# "aabbcc"
Проверка на цифры:
s = "abc"
print ( s.isdigit() )
s1 = "123"
print ( s1.isdigit() )
# False
# True
… и много других.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
101
Поиск в строках
s = "Здесь был Вася."
n = s.find ( "с" )
# n = 3
if n >= 0:
print ( "Номер символа", n )
else:
print ( "Символ не найден." )
! Находит первое слева вхождение
подстроки!
Поиск с конца строки:
s = "Здесь был Вася."
n = s.rfind ( "с" )
К.Ю. Поляков, Е.А. Ерёмин, 2018
# n = 12
http://kpolyakov.spb.ru

99. Удаление и вставка символов

Алгоритмизация и программирование, язык Python, 10 класс
102
Пример обработки строк
Задача: Ввести имя, отчество и фамилию. Преобразовать их к
формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.
Алибабаевич Хрюндиков
Алгоритм:
• найти первый пробел и выделить имя
Хрюндиков
• удалить имя с пробелом из основной строки
• найти первый пробел и выделить отчество
• удалить отчество с пробелом из основной строки
• «сцепить» фамилию, первые буквы имени и фамилии,
точки, пробелы…
Хрюндиков В.А.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
103
Пример обработки строк
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
104
Пример обработки строк
Решение в стиле Python:
print ( "Введите имя, отчество и фамилию:" )
s = input()
fio = s.split()
s = fio[2] + " " + fio[0][0] + "." + fio[1][0] + "."
print ( s )
Василий Алибабаевич Хрюндиков
fio[0]
fio[1]
К.Ю. Поляков, Е.А. Ерёмин, 2018
fio[2]
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
108
Преобразования «строка» – «число»
Из строки в число:
s = "123"
N = int ( s )
s = "123.456"
X = float ( s )
# N = 123
# X = 123.456
Из числа в строку:
N = 123
s = str ( N )
s = "{:5d}".format(N)
# s = "123"
# 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"
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
109
Задачи
«A»: Напишите программу, которая вычисляет сумму трех
чисел, введенную в форме символьной строки. Все числа
целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60
«B»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
только знаки «+» или «–»). Выражение вводится как
символьная строка, все числа целые.
Пример:
Введите выражение:
12-3+45
Ответ: 54
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
110
Задачи
«C»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/»). Выражение вводится как
символьная строка, все числа целые. Операция «/»
выполняется как целочисленное деление.
Пример:
Введите выражение:
12*3+45
Ответ: 81
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

105. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
111
Задачи
«D»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/») и круглых скобок. Выражение
вводится как символьная строка, все числа целые.
Операция «/» выполняется как целочисленное деление
(div).
Пример:
Введите выражение:
2*(3+45)+4
Ответ: 100
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

106. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
112
Строки в процедурах и функциях
Задача: построить функцию, которая возвращает первое
слово в предложении.
? Что плохо?
def firstWord( s ):
p = s.strip()
s.find( ' ' )
s
if p < s[:p]
0:
return
return s
else:
return s[:p]
Однажды весною, в час…
Однажды весною, в час…
Однажды
word = firstWord( s )
print( word )
К.Ю. Поляков, Е.А. Ерёмин, 2018
Однажды
http://kpolyakov.spb.ru

107. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
113
Замена подстроки
Задача: построить функцию, которая заменяет в строке s
все вхождения слова-образца wOld на слово-замену
wNew.
пока слово wOld есть в строке s
удалить слово wOld из строки
вставить на это место слово wNew
? Что плохо?
wOld: "12"
wNew: "A12B"
К.Ю. Поляков, Е.А. Ерёмин, 2018
зацикливание
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
114
Замена всех экземпляров подстроки
wNew
wOld
а) res
s
s
б) res
wNew
в) res
s
г) res
s
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

109. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
115
Замена всех экземпляров подстроки
s = "12.12.12"
s = replaceAll ( s, "12", "A12B" )
print( s )
рабочая строка s
"12.12.12"
".12.12"
".12"
""
К.Ю. Поляков, Е.А. Ерёмин, 2018
результат res
""
"A12B"
"A12B.A12B"
"A12B.A12B.A12B"
http://kpolyakov.spb.ru

110. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
116
Замена всех экземпляров подстроки
def replaceAll ( s, wOld, wNew ):
lenOld = len(wOld)
res = ""
искать образец
while len(s) > 0:
p = s.find ( wOld )
если не нашли
if p < 0:
взять начало
return res + s
перед образцом
if p > 0: res = res + s[:p]
res = res + wNew
добавить
слово-замену
if p+lenOld >= len(s):
s = ""
строка кончилась
else:
s = s[p+lenOld:]
взять «хвост»
return res
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

111. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
117
Замена всех экземпляров подстроки
Встроенная функция:
s = "12.12.12"
s = s.replace( "12", "A12B" )
print ( s )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
118
Задачи
«A»: Напишите функцию, которая отсекает всю часть строки
после первого слова.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

113. Замена подстроки

Алгоритмизация и программирование, язык Python, 10 класс
119
Задачи
«B»: Напишите функцию, которая заменяет расширение
файла на заданное новое расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
120
Задачи
«C»: Напишите функцию, которая заменяет во всей строке все
римские числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся
очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной
выпуск 11 классов.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
121
Рекурсивный перебор
Задача. В алфавите языка племени «тумба-юмба»
четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести
на экран все слова, состоящие из L букв, которые
можно построить из букв этого алфавита.
перебор L-1
символов
Ы
?
?
?
Ш
?
?
?
Ч
?
?
?
0
?
?
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
задача для слов длины
L сведена к задаче для
слов длины L-1!
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
122
Рекурсивный перебор
перебор L символов
w[0]="Ы"
# перебор последних L-1 символов
w[0]="Ш"
# перебор последних L-1 символов
w[0]="Ч"
# перебор последних L-1 символов
w[0]="О"
# перебор последних L-1 символов
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
123
Рекурсивный перебор
алфавит
слово
нужная
длина слова
def TumbaWords ( A, w, L ):
if len(w) == L:
слово полной длины
print ( w )
return
по всем символам
алфавита
for c in A:
TumbaWords ( A, w + c, L )
# основная программа
TumbaWords ( "ЫШЧО", "", 3 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

118. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
124
Рекурсивный перебор + счётчик
count = 0
def TumbaWords ( A, w, L ):
global count
будем менять глобальную
if len(w) == L:
print ( w )
count += 1
переменную
увеличение
счётчика
return
for c in A:
TumbaWords ( A, w + c, L )
TumbaWords ( "ЫШЧО", "", 3 )
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

119. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
125
Рекурсивный перебор + условие
count = 0
def TumbaWords ( A, w, L ):
global count
if len(w) == L:
if not "ОО" in w:
условие
отбора
print ( w )
count += 1
return
for c in A:
TumbaWords ( A, w + c, L )
TumbaWords ( "ЫШЧО", "", 3 )
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

120. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
126
Рекурсивный перебор + условие (функция)
def valid ( s ):
if not "ОО" in w:
return True
else:
return False
return not "ОО" in w
def TumbaWords ( A, w, L ):
global count
if len(w) == L:
if valid(w):
условие
отбора
print ( w )
count += 1
return
for c in A:
TumbaWords ( A, w + c, L )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
127
Задачи
«A»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых вторая
буква «Ы». Подсчитайте количество таких слов.
«B»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, стоящие рядом.
Подсчитайте количество таких слов.
Программа не должна строить другие слова, не
соответствующие условию.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
128
Задачи
«C»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, не обязательно
стоящие рядом.
Программа не должна строить другие слова, не
соответствующие условию.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
129
Сортировка строк
aS = []
# пустой список строк
print ( "Введите строки для сортировки:" )
while True:
s1 = input()
if s1 == "": break
aS.append ( s1 ) # добавить в список
aS.sort()
# сортировка
print ( aS )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

124. Рекурсивный перебор + счётчик

Алгоритмизация и программирование, язык Python, 10 класс
130
Задачи
«A»: Вводится 5 строк, в которых сначала записан порядковый
номер строки с точкой, а затем – слово. Вывести слова в
алфавитном порядке.
Пример:
Введите 5 строк:
1. тепловоз
2. арбуз
3. бурундук
4. кефир
5. урядник
Список слов в алфавитном порядке:
арбуз, бурундук, кефир, тепловоз, урядник
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

125. Рекурсивный перебор + условие

Алгоритмизация и программирование, язык Python, 10 класс
131
Задачи
«B»: Вводится несколько строк (не более 20), в которых сначала
записан порядковый номер строки с точкой, а затем –
слово. Ввод заканчивается пустой строкой. Вывести
введённые слова в алфавитном порядке.
Пример:
Введите слова:
1. тепловоз
2. арбуз
Список слов в алфавитном порядке:
арбуз, тепловоз
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

126. Рекурсивный перебор + условие (функция)

Алгоритмизация и программирование, язык Python, 10 класс
132
Задачи
«C»: Вводится несколько строк (не более 20), в которых сначала
записаны инициалы и фамилии работников фирмы. Ввод
заканчивается пустой строкой. Отсортировать строки в
алфавитном порядке по фамилии.
Пример:
Введите ФИО:
А.Г. Урядников
Б.В. Тепловозов
В.Д. Арбузов
Список в алфавитном порядке:
В.Д. Арбузов
Б.В. Тепловозов
А.Г. Урядников
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

127. Задачи

133
Программирование
на языке Python
§ 67. Матрицы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

128. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
134
Что такое матрица?
нолик
нет знака
A
0
1
2
0
-1 0
1
крестик
1
-1 0
1
строка 1,
столбец 2
2
0
1 -1
A[1][2]
? Как закодировать?
Матрица — это прямоугольная таблица, составленная
из элементов одного типа (чисел, строк и т.д.).
Каждый элемент матрицы имеет два индекса –
номера строки и столбца.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
135
Создание матриц
! Матрица – это список списков!
A = [[-1, 0, 1],
[-1, 0, 1],
[0, 1, -1]]
перенос на другую
строку внутри скобок
или так:
A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]
! Нумерация элементов с нуля!
A[0][0] A[0][1] A[0][2]
A[1][0] A[1][1] A[1][2]
A[2][0] A[2][1] A[2][2]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

130. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
136
Создание матриц
Нулевая матрица:
N=3
M=2
row = [0]*M
A = [row]*N
A
0
row
0
0
1
1
2
A[0][0] = 1
а правильно так:
A = []
for i in range(N):
A.append ( [0]*M )
A
0
0
1
0
1
0
0
0
0
2
A[0][0] = 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

131. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
137
Ввод матрицы с клавиатуры
Данные на входе:
N
M
3 4
1 2 3 4
5 6 7 8
9 10 11 12
Программа:
N, M = map( int, input().split() )
A = []
for i in range(N):
row = [int(x) for x in input().split()]
A.append( row )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

132. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
138
Вывод матриц
print ( A )
[[1, 12, 3], [4, 5, 146], [7, 118, 99]]
def printMatrix ( A ):
for row in A:
for x in row:
print ( f"{x:4d}", end = "" )
print ()
1 12
3
4
5 146
7 118 99
К.Ю. Поляков, Е.А. Ерёмин, 2018
? Зачем форматный вывод?
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
139
Простые алгоритмы
Заполнение случайными числами:
import random
Вложенный цикл!
for i in range(N):
for j in range(M):
A[i][j] = random.randint ( 20, 80 )
print ( f"{A[i][j]:4d}", end = "" )
print()
!
Суммирование:
s=0
for i in range(N):
for j in range(M):
s += A[i][j]
print ( s )
К.Ю. Поляков, Е.А. Ерёмин, 2018
s=0
for row in A:
s += sum(row)
print ( s )
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
140
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
141
Задачи
«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в
виде матрицы. Преобразовать рисунок в черно-белый по
следующему алгоритму:
1) вычислить среднюю яркость пикселей по всему рисунку
2) все пиксели, яркость которых меньше средней, сделать
черными (записать код 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 255 255
255 255
0
0
255
0
0
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
142
Задачи
«С»: Заполните матрицу, содержащую N строк и M столбцов,
натуральными числами по спирали и змейкой, как на рисунках:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
143
Перебор элементов матрицы
Главная диагональ:
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]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

138. Вывод матриц

Алгоритмизация и программирование, язык Python, 10 класс
144
Перестановка строк и столбцов
2-я и 4-я строки:
A[2], A[4] = A[4], A[2]
0
1
2
3
4
2-й и 4-й столбцы:
for i in range(N):
A[i][2], A[i][4] = A[i][4], A[i][2]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
145
Выделение строк и столбцов
1-я строка:
R = A[1][:]
R = A[1]
? Почему плохо?
2-й столбец:
C = []
for row in A:
C.append(row[2])
или так:
C = [ row[2] for row in A ]
главная диагональ:
D = [ A[i][i] for i in range(N) ]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

140. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
146
Задачи
«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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

141. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
147
Задачи
«B»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните отражение рисунка сверху вниз:
1
2
3
7
8
9
4
5
6
4
5
6
7
8
9
1
2
3
«С»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните поворот рисунка вправо на 90 градусов:
1
2
3
7
4
1
4
5
6
8
5
2
7
8
9
9
6
3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

142. Задачи

148
Программирование
на языке Python
§ 68. Работа с файлами
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
149
Какие бывают файлы?
файлы
текстовые
«plain text»:
• для чтения человеком
• текст, разбитый на строки;
• из специальных символов
только символы перехода
на новую строку
двоичные
• любые символы
• рисунки, звуки, видео, …
12
123
1234
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
150
Принцип сэндвича
хлеб
начинка
хлеб
файловые переменныеуказатели
открыть файл
работа с файлом
закрыть файл
по умолчанию – на
чтение (режим "r")
Fin = open ( "input.txt" )
Fout = open ( "output.txt", "w" )
# здесь работаем с файлами
Fin.close()
"r" - чтение
Fout.close()
"w" – запись
"a" – добавление
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
151
Ввод данных
Fin = open( "input.txt" )
Чтение строки:
s = Fin.readline()
# "1 2"
Чтение строки и разбивка по пробелам:
s = Fin.readline().split()
# ["1","2"]
Чтение целых чисел:
s = Fin.readline().split()
a, b = int(s[0]), int(s[1])
# ["1","2"]
или так:
a, b = [int(x) for x in s]
или так:
a, b = map( int, s )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

146. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
152
Вывод данных в файл
a=1
b=2
Fout = open( "output.txt", "w" )
Fout.write ( f"{a} + {b} = {a+b}\n" )
Fout.close()
! Все данные преобразовать в строку!
a=1
b=2
Fout = open( "output.txt", "w" )
print( f"{a} + {b} = {a+b}", file = Fout )
Fout.close()
не надо
"\n"
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

147. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
153
Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
пока не конец файла
прочитать число из файла
добавить его к сумме
Fin = open ( "input.txt" )
sum = 0
если конец файла,
while True:
вернёт пустую строку
s = Fin.readline()
if not s: break
sum += int(s)
Fin.close()
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
154
Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
sum = 0
Fin = open ( "input.txt" )
lst = Fin.readlines()
for s in lst:
прочитать все строки в
sum += int(s)
список строк
Fin.close()
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

149. Какие бывают файлы?

Алгоритмизация и программирование, язык Python, 10 класс
155
Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
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)
! Не нужно закрывать файл!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
156
Задачи
«A»: Напишите программу, которая находит среднее
арифметическое всех чисел, записанных в файле в
столбик, и выводит результат в другой файл.
«B»: Напишите программу, которая находит минимальное и
максимальное среди чётных положительных чисел,
записанных в файле, и выводит результат в другой файл.
Учтите, что таких чисел может вообще не быть.
«C»: В файле в столбик записаны целые числа, сколько их –
неизвестно. Напишите программу, которая определяет
длину самой длинной цепочки идущих подряд одинаковых
чисел и выводит результат в другой файл.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

151. Ввод данных

Алгоритмизация и программирование, язык Python, 10 класс
157
Обработка массивов
Задача. В файле записаны в столбик целые числа.
Вывести в другой текстовый файл те же числа,
отсортированные в порядке возрастания.
? В чем отличие от предыдущей задачи?
сортировки нужно удерживать все элементы в
! Для
памяти одновременно.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
158
Обработка массивов
Ввод массива:
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()
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
159
Обработка массивов
Вывод результата:
Fout = open ( "output.txt", "w" )
Fout.write ( str(A) )
[1, 2, 3]
Fout.close()
или так:
for x in A:
Fout.write ( str(x)+"\n" )
1
2
3
или так:
for x in A:
Fout.write ( f"{x:4d}" )
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
2
3
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
160
Задачи
«A»: В файле в столбик записаны числа. Отсортировать их по
возрастанию последней цифры и записать в другой файл.
«B»: В файле в столбик записаны числа. Отсортировать их по
возрастанию суммы цифр и записать в другой файл.
Используйте функцию, которая вычисляет сумму цифр
числа.
«C»: В двух файлах записаны отсортированные по возрастанию
массивы неизвестной длины. Объединить их и записать
результат в третий файл. Полученный массив также
должен быть отсортирован по возрастанию.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
161
Обработка строк
Задача. В файле записано данные о собаках: в каждой
строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка
Вывести в другой файл сведения о собаках, которым
меньше 5 лет.
пока не конец файла Fin
прочитать строку из файла Fin
разобрать строку – выделить возраст
если возраст < 5 то
записать строку в файл Fout
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

156. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
162
Чтение данных из файла
Чтение одной строки:
s = Fin.readline()
Разбивка по пробелам:
data = s.split()
Выделение возраста:
sAge = data[1]
age = int ( sAge )
Кратко всё вместе:
s = Fin.readline()
age = int ( s.split()[1] )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
163
Обработка строк
Полная программа:
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()
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
164
Обработка строк
или так:
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 )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
165
Задачи
«A»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл фамилии и имена тех учеников,
которые получили больше 80 баллов.
«B»: В предыдущей задаче добавить к полученному списку
нумерацию, сократить имя до одной буквы и поставить
перед фамилией:
П. Иванов
И. Петров
...
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

160. Задачи

Алгоритмизация и программирование, язык Python, 10 класс
166
Задачи
«C»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл данные учеников, которые
получили больше 80 баллов. Список должен быть
отсортирован по убыванию балла. Формат выходных
данных:
П. Иванов 98
И. Петров 96
...
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
167
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
168
Источники иллюстраций
1.
2.
3.
www.mcdonalds.com
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
English     Русский Правила