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

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

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

1
Программирование
на языке Python
§ 62. Массивы
§ 63. Алгоритмы обработки массивов
§ 64. Сортировка
§ 65. Двоичный поиск
К.Ю. Поляков, Е.А. Ерёмин, 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 ( "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
Ввод массива с клавиатуры
Ввод в одной строке:
A=[]
N=int(input())
for i in input().split():
A.append(int(i))
Ввод построчно:
A=[]
N=int(input())
A = [int(input("Номер %d = " % i))
for i in range(N)]
N=int(input('Введите количество чисел ='))
A=[]
for i in range (1,N+1):
A.append(int(input('Введите число =')))
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
Ввод
12
с клавиатуры и вывод массива
Ввод в одной строке и Вывод массива
n=int(input())
A=map(int,input().split(maxsplit = n))
print(n)
for y in A:
print(y, end = ' ' )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
13
Вывод массива на экран
Как список:
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

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

Алгоритмизация и программирование, язык Python, 10 класс
14
Как обработать все элементы массива?
Создание массива:
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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
16
Заполнение случайными числами
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

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

Алгоритмизация и программирование, язык Python, 10 класс
17
Перебор элементов
Общая схема (можно изменять 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

18. Этапы работы с массивом

Алгоритмизация и программирование, язык Python, 10 класс
18
Этапы работы с массивом
a=[]
n=int
(input
("Введи
кол-во
элементов
массива"))
for i in input().split(): Заполнение массива
a.append(int (i))
Вывод созданного
for y in a:
массива
print (y, end=" ")
(1 способ вывода)
print ()
for i in range (n):
Обработка массива
... # действия с a[i]
Вывод
print ()
обработанного
for i in range (n):
массива
print (a[i], end=' ‘) ( 2 способ вывода)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

19. Три способа создания массива: Заполнить один массив случайными числами, другой - введенными с клавиатуры числами, в ячейки

Алгоритмизация и программирование, язык Python, 10 класс
from random import random
N = 10
a = []
b = []
c = []
for i in range(N):
n = int(random() * 100)
a.append(n)
print("Введите числа")
for i in range(N):
n = int(input())
b.append(n)
for i in range(N):
n = a[i] + b[i]
c.append(n)
print(a)
print(b)
print(c)
К.Ю. Поляков, Е.А. Ерёмин, 2018
19
Три способа создания
массива:
Заполнить один массив
случайными числами,
другой - введенными с
клавиатуры числами,
в ячейки третьего записать
суммы соответствующих
ячеек первых двух.
Вывести содержимое
массивов на экран.
http://kpolyakov.spb.ru

20. Вывод чисел в обратном порядке

Алгоритмизация и программирование, язык Python, 10 класс
20
Вывод чисел в обратном порядке
Ввод чисел от A до B
в обратном порядке
a = int(input())
b = int(input())
a=[i for i in range
for y in a:
print(y)
(b, a-1, -1)]
print(*[i for i in range
(int(input("Введи
кол-во чисел")))]
print(*[i
for i in range(int(input()))][::-1])
[::-1])
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
21
Заполнение случайными числами
from random import randint
N = 10
A = [ randint(20,100)
for x in range(N)] [::-1]
for y in A:
print(y,end =' ')
print()
for y in A [::-1]:
print(y, end =' ‘)
К.Ю. Поляков, Е.А. Ерёмин, 2018
Вывод
случайных чисел
[20,100]
Вывод случайных
чисел
[20,100] в
обратном порядке
http://kpolyakov.spb.ru

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

Алгоритмизация и программирование, язык Python, 10 класс
22
Подсчёт количества нужных элементов
Задача. В массиве записаны данные о росте
баскетболистов. Сколько из них имеет рост больше
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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
24
Перебор элементов
Среднее арифметическое:
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

25.

Алгоритмизация и программирование, язык Python, 10 класс
25
Задан массив из натуральных чисел. Выведите его в
обратном порядке через пробел.
def print_rev(arr,k):
if k<0:
return
else:
print(arr[k],end=' ')
print_rev(arr,k-1)
a=list(map(int,input().split(' ')))
print_rev(a,len(a)-1)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
30
Максимальный элемент
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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
32
Максимальный элемент и его номер
Вариант в стиле Python:
M = max(A)
nMax = A.index(M)
print ( "A[", nMax, "]=", M, sep = "" )
номер заданного
элемента (первого из…)
К.Ю. Поляков, Е.А. Ерёмин, 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
«Простое» решение:
?
c = A[0]
for i in range(N-1):
A[i] = A[i+1]
A[N-1] = c
К.Ю. Поляков, Е.А. Ерёмин, 2018
Почему не до N?
?
Что плохо?
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
-4
-3
-2
-1
-N
-N+1 -N+2 -N+3
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,
удовлетворяющие некоторому условию, в массив 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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
41
Особенности работы со списками
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

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

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

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

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
45
Метод пузырька (сортировка обменами)
Идея: пузырек воздуха в стакане воды поднимается со
дна вверх.
Для массивов – самый маленький («легкий» элемент
перемещается вверх («всплывает»).
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

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

Алгоритмизация и программирование, язык Python, 10 класс
46
Метод пузырька
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

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

Алгоритмизация и программирование, язык Python, 10 класс
47
Метод пузырька
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

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

Алгоритмизация и программирование, язык Python, 10 класс
Метод пузырька
48
от 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

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

Алгоритмизация и программирование, язык Python, 10 класс
49
Метод пузырька
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

50.

Алгоритмизация и программирование, язык Python, 10 класс
a=[]
n=int
(input
("Введи
кол-во
массива"))
for i in input().split():
a.append(int (i))
for y in a:
print (y, end=" ")
print ()
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]
print ()
for i in range (n):
print (a[i], end=' ')
print ()
for y in a:
print (y, end=" ")
К.Ю. Поляков, Е.А. Ерёмин, 2018
50
элементов
http://kpolyakov.spb.ru

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
52
Метод выбора (минимального элемента)
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

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

Алгоритмизация и программирование, язык Python, 10 класс
53
Сортировка слиянием
Слияние отсортированных массивов:
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

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

Алгоритмизация и программирование, язык Python, 10 класс
54
Сортировка слиянием
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

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

Алгоритмизация и программирование, язык Python, 10 класс
55
Сортировка слиянием
Процедура слияния:
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

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

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
58
Быстрая сортировка (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

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

Алгоритмизация и программирование, язык Python, 10 класс
59
Сравнение алгоритмов сортировки
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

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

Алгоритмизация и программирование, язык Python, 10 класс
60
Быстрая сортировка «на месте»
Шаг 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

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

Алгоритмизация и программирование, язык Python, 10 класс
61
Быстрая сортировка
Разделение:
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

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

Алгоритмизация и программирование, язык Python, 10 класс
62
Быстрая сортировка
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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
64
Быстрая сортировка
массив
начало
конец
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

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

Алгоритмизация и программирование, язык Python, 10 класс
65
Быстрая сортировка
Случайный выбор элемента-разделителя:
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

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

Алгоритмизация и программирование, язык Python, 10 класс
66
Сортировка в 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

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

Алгоритмизация и программирование, язык Python, 10 класс
67
Сортировка в 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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс
69
Двоичный поиск
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

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

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

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

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

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

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

73.

Алгоритмизация и программирование, язык Python, 10 класс
К.Ю. Поляков, Е.А. Ерёмин, 2018
73
http://kpolyakov.spb.ru
English     Русский Rules