![Специальные символы с \](https://cf4.ppt-online.org/files4/slide/o/ODl3THmzNR9Z4isejSwCYFb28MLp1kBG50oXIh/slide-65.jpg "Специальные символы с \")
programmingSimilar presentations:
Алгоритмизация и программирование. Язык Python
1. Алгоритмизация и программирование. Язык Python
Целочисленные алгоритмыСтруктуры
Словари
Анализ текста на естественном языке
Стек, очередь, дек
Деревья
Графы
Динамическое программирование
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
1
2. Алгоритмизация и программирование. Язык Python
2Алгоритмизация и
программирование.
Язык Python
Целочисленные
алгоритмы
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
3. Все простые числа от 2 до N
Алгоритмизация и программирование. Язык Python, 11 класс3
Все простые числа от 2 до N
Вывести на экран все простые числа в диапазоне
от 2 до N.
включая N
N = int(input())
for i in range(2, N+1):
простое число
число :
if ii –– простое
print( i, end=" " )
? Как определить, что число простое?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
4. Все простые числа от 2 до N
Алгоритмизация и программирование. Язык Python, 11 класс4
Все простые числа от 2 до N
Вывести на экран все простые числа в диапазоне
от 2 до N.
def isPrime( x ):
count = 0
for d in range(2, x):
if x % d == 0:
count += 1
return count == 0
[2,x-1]
N = int(input())
for i in range(2, N+1):
if isPrime( i ) :
print( i, end=" " )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
5. Все простые числа от 2 до N
Алгоритмизация и программирование. Язык Python, 11 класс5
Все простые числа от 2 до N
Добавить в массив все простые числа в диапазоне
от 2 до N.
N = int(input())
P = []
for i in range(2, N+1):
if isPrime( i ):
P.append( i )
print( P )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
6. Какая сложность?
Алгоритмизация и программирование. Язык Python, 11 класс6
Какая сложность?
def isPrime( x ):
count = 0
for d in range(2, x):
if x % d == 0:
count += 1
return count == 0
N = int(input())
for i in range(2, N+1):
if isPrime( i ):
print( i, end=" " )
! O(N )!
2
К.Ю. Поляков, Е.А. Ерёмин, 2025
O(x)
O(N)
? Как ускорить?
http://kpolyakov.spb.ru
7. Небольшое ускорение
Алгоритмизация и программирование. Язык Python, 11 класс7
Небольшое ускорение
Если нашли один делитель, то число уже не простое, нет
смысла искать остальные.
def isPrime( x ):
count = 0
for d in range(2, x):
if x % d == 0:
count += 1
break
return count == 0
O(x)
? Какая сложность?
! O(N )!
2
К.Ю. Поляков, Е.А. Ерёмин, 2025
? Как ещё ускорить?
http://kpolyakov.spb.ru
8. Большое ускорение
Алгоритмизация и программирование. Язык Python, 11 класс8
Большое ускорение
x d e, d e d x
перебор до
корня
def isPrime( x ):
count = 0
for d in range(2, round(x**0.5)+1 ):
if x % d == 0:
count += 1
O( x )
break
return count == 0
Какая сложность?
O( N ) O( N N )
?
2
? Как ещё ускорить?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
9. Решето Эратосфена
Алгоритмизация и программирование. Язык Python, 11 класс9
Решето Эратосфена
22 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Алгоритм:
1) начать с k = 2
Эратосфен Киренский
2) «выколоть» все числа через k, начиная с 2k··kk
(Eratosthenes, Ερατοσθδνη)
3) перейти к следующему «невыколотому» k
(ок. 275-194 до н.э.)
<=N N , то перейти к шагу 2
4) если kk·k<=
5) напечатать все числа, оставшиеся «невыколотыми»
Новая версия – решето Аткина.
? Как улучшить?
высокая скорость, количество операций
O((N·log N)·log log N )
нужно хранить в памяти все числа от 1 до N
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
10. Решето Эратосфена
Алгоритмизация и программирование. Язык Python, 11 класс10
Решето Эратосфена
Задача. Вывести все простые числа от 2 до N.
Массив (сначала все не вычеркнуты):
N = 100
выделяем на 1
элемент больше,
A = [True]*(N+1)
чтобы начать с A[1]
Вычёркивание непростых:
k=2
while k*k <= N:
if A[k]: # если k не вычеркнуто
i = k*k # начать c k*k
while i <= N: # вычеркнуть кратные k
A[i] = False
i += k
k += 1
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
11. Решето Эратосфена
Алгоритмизация и программирование. Язык Python, 11 класс11
Решето Эратосфена
или так:
from math import sqrt
for k in range(2, int(sqrt(N))+1):
if A[k]: # если k не вычеркнуто
range(k*k, N+1,
N+1, k):
k)
for i in range(k*k,
A[i] = False
все кратные k
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
12. Решето Эратосфена
Алгоритмизация и программирование. Язык Python, 11 класс12
Решето Эратосфена
Вывод результата:
for i in range(2,N+1):
if A[i]:
print ( i )
или так:
P = [ i for i in range(2,N+1)
if A[i] ]
print ( P )
выбираем те, которые
не вычеркнуты
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
13. «Длинные» числа
Алгоритмизация и программирование. Язык Python, 11 класс13
«Длинные» числа
Ключи для шифрования: 256 битов.
Целочисленные типы данных обычно 64 битов.
? Как хранить?
Длинное число – это число, которое не помещается в
переменную одного из стандартных типов данных
языка программирования.
«Длинная арифметика» – алгоритмы для работы с
длинными числами.
! В Python длинная арифметика встроенная!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
14. «Длинные» числа
Алгоритмизация и программирование. Язык Python, 11 класс14
«Длинные» числа
A = 12345678
A
0
1
2
3
4
5
6
7
1
2
3
4
5
6
7
8
? Что плохо?
неудобно вычислять (с младшего разряда!)
неэкономное расходование памяти (одна цифра в
ячейке)
Обратный порядок элементов:
A
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
15. «Длинные» числа
Алгоритмизация и программирование. Язык Python, 11 класс15
«Длинные» числа
A = 12345678
Упаковка элементов:
A
2
1
0
12
345
678
12345678 = 12·10002 + 345·10001 + 678·10000
? На что похоже?
система счисления с
основанием 1000!
Если 4 байтовая ячейка:
от –231 = – 2 147 483 648 до 231 – 1 = 2 147 483 647.
? Какие основания можно использовать?
должны помещаться все
промежуточные результаты!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
16. Вычисление факториала
Алгоритмизация и программирование. Язык Python, 11 класс16
Вычисление факториала
Задача 1. Вычислить точно значение факториала
100! = 1·2·3·…·99·100
? Как оценить количество цифр?
201 цифра
1·2·3·…·99·100 < 100100
основание 1000000
6 цифр в ячейке 34 ячейки
Основной алгоритм:
длинное
{A} = 1
число
for k in range(2,101):
{A} *= k
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
17. Вычисление факториала
Алгоритмизация и программирование. Язык Python, 11 класс17
Вычисление факториала
основание d = 1 000 000
[A] = 12345678901734567
A
3
2
1
0
0
12345
678901
734567
734 567·3 = 2 203 701
r = перенос в A[1]
*3
остаётся в A[0]
? Как найти перенос?
s = A[0]*k
A[0] = s % d
r = s // d
? Что изменится для A[1]?
К.Ю. Поляков, Е.А. Ерёмин, 2025
s = A[1]*k + r
http://kpolyakov.spb.ru
18. Вычисление факториала
Алгоритмизация и программирование. Язык Python, 11 класс18
Вычисление факториала
Умножение «длинного» числа на k:
r=0
все разряды
for i in range(len(A)):
s = A[i]*k + r
A[i] = s % d
r = s // d
число
if r > 0:
удлиняется
A.append ( r )
Вычисление 100!:
for k in range(2,101):
{A} *= k
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
19. Вывод длинного числа
Алгоритмизация и программирование. Язык Python, 11 класс19
Вывод длинного числа
A
3
2
1
0
0
1
2
3
? Какое число?
A = 1000002000003
• вывести старший ненулевой разряд
h = len ( A )- 1
print ( A[h], end = "" )
• вывести все следующие разряды, добавляя
лидирующие нули до 6 цифр
for i in range(h-1,-1,-1):
print ( f"{A[i]:06d}", end = "" )
дополнить
нулями
К.Ю. Поляков, Е.А. Ерёмин, 2025
в6
позициях
http://kpolyakov.spb.ru
20. Квадратный корень
Алгоритмизация и программирование. Язык Python, 11 класс20
Квадратный корень
Задача. Извлечь квадратный корень из «длинного»
целого числа; если это не целое число, найти корень с
округлением «вниз» (к меньшему значению).
x* a
x0 a
Метод Герона:
! Начальное приближение –
1
a
xi xi 1
2
xi 1
любое > 0!
a 16
x0 16
x1 0,5 16 16 / 16 8,5
x2 0,5 8,5 16 / 8,5 5,19
x3 0,5 5,19 16 / 5,19 4,14
...
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
21. Квадратный корень
Алгоритмизация и программирование. Язык Python, 11 класс21
Квадратный корень
Метод Герона в целых числах:
1
a
xi xi 1
x = (x + a // x)// 2
или так:
x = (x*x + a) // (2*x)
только целые
числа!
2
xi 1
xi2 1 a
xi
2 xi 1
? Когда остановиться?
это ответ!
x* a
x0 a
! Если следующее приближение больше
предыдущего, то стоп!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
22. Квадратный корень
Алгоритмизация и программирование. Язык Python, 11 класс22
Квадратный корень
Метод Герона в целых числах:
def isqrt(a):
x = a # начальное приближение
while True:
следующее
приближение
x1 = (x*x + a)//(2*x)
if x1 >= x:
вернуть
return x
результат
x = x1
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
23. Алгоритмизация и программирование. Язык Python
23Алгоритмизация и
программирование.
Язык Python
Структуры
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
24. Зачем нужны структуры?
Алгоритмизация и программирование. Язык Python, 11 класс24
Зачем нужны структуры?
Книги в библиотеках:
• автор
символьные строки
• название
целое число
• количество экземпляров
•…
Как хранить данные?
?
Несколько массивов:
N = 100
authors = [""]*N
titles = [""]*N
count = [0]*N
...
неудобно работать
(сортировать и т.д.),
ошибки
Задачa: объединить разнотипные данные в один блок.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
25. Структуры
Алгоритмизация и программирование. Язык Python, 11 класс25
Структуры
Структура – это тип данных, который может включать в
себя несколько полей – элементов разных типов (в
том числе и другие структуры).
новый тип (класс)
данных
название типа
данных
class TBook:
pass
«пустой»
оператор
class TBook:
author = ""
title = ""
count = 0
К.Ю. Поляков, Е.А. Ерёмин, 2025
эти поля будут у
всех структур
класса TBook
http://kpolyakov.spb.ru
26. Работа со структурами
Алгоритмизация и программирование. Язык Python, 11 класс26
Работа со структурами
Создание:
B = TBook()
Заполнение:
B.author = "Пушкин А.С."
B.title = "Полтава"
создание полей
B.count = 1
точечная запись
! В Python не нужно заранее объявлять поля!
Ввод с клавиатуры:
B.author = input()
B.title = input()
B.count = int( input() )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
27. Работа со структурами
Алгоритмизация и программирование. Язык Python, 11 класс27
Работа со структурами
Обработка:
B.author = "Пушкин А.С."
fam = B.author.split()[0] # фамилия
print ( fam )
B.count -= 1
# одну книгу взяли
if B.count == 0:
print ( "Этих книг больше нет!" )
Вывод на экран:
print ( B.author, B.title + ".",
B.count, "шт." )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
28. Массив структур
Алгоритмизация и программирование. Язык Python, 11 класс28
Массив структур
Создание:
Books = [TBook()]*100
? Что плохо?
Books = []
for i in range(100):
Books.append ( TBook() )
Изменение полей:
Books[5].author = "Пушкин А.С."
Books[5].title = "Полтава"
Books[5].count = 1
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
29. Запись структур в CSV-файлы
Алгоритмизация и программирование. Язык Python, 11 класс29
Запись структур в CSV-файлы
Текстовые файлы – это файлы, в которых данные
разбиты на строки и содержат только символы,
присутствующие в тексте (английском, русском).
CSV = Comma Separated Values
Пушкин А.С.,Полтава,12
Лермонтов М.Ю.,Мцыри,8
разделитель
F = open( "library.csv", "w" )
"w" – запись
for B in Books:
"r" – чтение
F.write( B.author + "," )
"a" – добавление
F.write( B.title + "," )
F.write( str(B.count) + "\n" )
F.close()
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
30. Чтение структур из CSV-файлов
Алгоритмизация и программирование. Язык Python, 11 класс30
Чтение структур из CSV-файлов
Пушкин А.С.,Полтава,12
Лермонтов М.Ю.,Мцыри,8
по умолчанию
"r" – чтение
Books = []
for line in open( "library.csv" ) :
line = line.rstrip()
убрать "\n" в
data = line.split( "," )
конце строки
B = TBook()
B.author = data[0]
B.title = data[1]
B.count = int(data[2])
Books.append( B )
["Пушкин А.С.","Полтава","12"]
data[0]
К.Ю. Поляков, Е.А. Ерёмин, 2025
data[1]
data[2]
http://kpolyakov.spb.ru
31. Обработка структур из массива
Алгоритмизация и программирование. Язык Python, 11 класс31
Обработка структур из массива
одна
структура
массив
структур
изменение
for B in Books:
B.count += 1
if B.author == "Пушкин А.С.":
print( B.author, B.title,
B.count, "экз." )
проверка
вывод
Пушкин А.С. Полтава 12 экз.
Пушкин А.С. Сказка о царе Салтане 7 экз.
Пушкин А.С. Руслан и Людмила 5 экз.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
32. Сортировка структур
Алгоритмизация и программирование. Язык Python, 11 класс32
Сортировка структур
Ключ — это поле, по которому выполняется сортировка.
Ключ – фамилия автора:
# B – массив структур TBook
N = len(B)
for i in range(0,N-1):
for j in range(N-2,i-1,-1):
if B[j].author > B[j+1].author:
B[j], B[j+1] = B[j+1], B[j]
? Какой метод?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
33. Сортировка структур (в стиле Python)
Алгоритмизация и программирование. Язык Python, 11 класс33
Сортировка структур (в стиле Python)
Ключ – фамилия автора:
def getAuthor ( B ):
return B.author
Books.sort ( key = getAuthor )
или так:
лямбда-функция
Books.sort ( key =
lambda x:
x: x.author
x.author )
lambda
не меняя Books:
sortedBooks = sorted ( Book,
key = lambda x: x.author )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
34. Сортировка структур
Алгоритмизация и программирование. Язык Python, 11 класс34
Сортировка структур
По убыванию (обратный порядок) :
Books.sort ( reverse
reverse == True
True,
key = lambda x: x.author )
Сначала по автору, потом – по названию:
Books.sort ( key =
lambda x: (x.author, x.title) )
Сначала по количеству (по убыванию), потом –
по автору:
Books.sort ( key =
lambda x: (-x.count, x.author) )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
35. Запись структуры в двоичный файл
Алгоритмизация и программирование. Язык Python, 11 класс35
Запись структуры в двоичный файл
import pickle
B = TBook()
B.author = "Тургенев И.С."
B.title = "Муму"
B.count = 2
binary, двоичный
"wb" – запись
"rb" – чтение
F = open ( "books.dat", "wb" ) "ab" – добавление
pickle.dump ( B, F )
F.close()
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
36. Запись массива структур
Алгоритмизация и программирование. Язык Python, 11 класс36
Запись массива структур
Books = []
for i in range(10):
Books.append ( TBook() )
Сразу все:
pickle.dump ( Books, F )
По одной структуре:
файл, открытый
на запись
for B in Books:
pickle.dump ( B, F )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
37. Чтение структур из файла
Алгоритмизация и программирование. Язык Python, 11 класс37
Чтение структур из файла
Одна структура:
F = open ( "books.dat", "rb" )
B = pickle.load ( F )
print ( B.author, B.title,
B.count, sep = ", " )
F.close()
Массив структур целиком:
Books = pickle.load ( F )
Массив из N структур по одной:
for i in range(N):
Books[i] = pickle.load ( F )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
38. Чтение структур из файла
Алгоритмизация и программирование. Язык Python, 11 класс38
Чтение структур из файла
Число структур неизвестно:
Books = []
while True:
try:
B = pickle.load ( F )
Books.append ( B )
except:
break
try – попытаться выполнить следующие операторы
except – что делать в случае ошибки (исключения,
аварийной ситуации)
Исключение — это аварийная ситуация, которая делает
дальнейшие вычисления по основному алгоритму
невозможными или бессмысленными.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
39. Алгоритмизация и программирование. Язык Python
39Алгоритмизация и
программирование.
Язык Python
Словари
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
40. Что такое словарь?
Алгоритмизация и программирование. Язык Python, 11 класс40
Что такое словарь?
Задача. В файле находится список слов, среди которых
есть повторяющиеся. Каждое слово записано в
отдельной строке. Построить алфавитно-частотный
словарь: список слов в алфавитном порядке, справа
от каждого слова должно быть указано, сколько раз
оно встречается в исходном файле.
? Какая структура данных нужна?
print ( D["бегемот"] )
ключ значение
(отображение, map)
поиск не по индексу,
а по слову (ключу)
Словарь – это неупорядоченный набор элементов, в
котором доступ к элементу выполняется по ключу.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
41. Алгоритм (псевдокод)
Алгоритмизация и программирование. Язык Python, 11 класс41
Алгоритм (псевдокод)
ключ значение
слово
счётчик
? Как выбрать ключ и
значение?
создать пустой словарь
while есть слова в файле:
прочитать очередное слово
if слово есть в словаре:
увеличить на 1 счётчик
для этого слова
else:
добавить слово в словарь
записать 1 в счетчик слова
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
42. Работа со словарями в Python
Алгоритмизация и программирование. Язык Python, 11 класс42
Работа со словарями в Python
Создание:
D = {}
# пустой словарь
D = { "бегемот": 0, "пароход": 2 }
Добавление (изменение) элемента:
D["самолёт"] = 1
! Создаётся новый элемент!
D["самолёт"] += 1
ошибка, если
ключа нет
! Нужно проверить, есть ли элемент!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
43. Работа со словарями в Python
Алгоритмизация и программирование. Язык Python, 11 класс43
Работа со словарями в Python
Изменение с проверкой:
if "самолёт" in D:
D["самолёт"] += 1
else:
D["самолёт"] = 1
или так:
D["самолёт"] = D.get ( "самолёт", 0 ) + 1
получить
значение по ключу
К.Ю. Поляков, Е.А. Ерёмин, 2025
значение по
умолчанию (если
ключа нет)
http://kpolyakov.spb.ru
44. Основной цикл
Алгоритмизация и программирование. Язык Python, 11 класс44
Основной цикл
создать пустой
словарь
D = {}
for s in open ( "input.txt" ):
word = s.strip()
убрать "\n" в конце
if word:
D[word] = D.get ( word, 0 ) + 1
увеличить
счётчик слова
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
45. Вывод результата
Алгоритмизация и программирование. Язык Python, 11 класс45
Вывод результата
Получить массив всех ключей:
allKeys = D.keys()
отсортировать ключи:
sortKeys = sorted(D.keys())
или так:
sortKeys = sorted(D)
Вывод результата:
F = open ( "output.txt", "w" )
for k in sorted(D):
F.write ( f"{k}: {D[k]}\n" )
F.close()
пароход: 12
самолёт: 20
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
46. Ещё о словарях
Алгоритмизация и программирование. Язык Python, 11 класс46
Ещё о словарях
Перебор значений:
for i in D.values():
print ( i )
Перебор ключей и значений:
for k, v in D.items():
print ( k, "->", v )
список пар
(ключ, значение)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
47. Словарь и массив пар
Алгоритмизация и программирование. Язык Python, 11 класс47
Словарь и массив пар
Массив (список) пар «ключ-значение»:
A = list(D.items())
список пар
(ключ, значение)
Сортировка:
D = {"бам": 2, "там": 3}
A[0] кортеж A[1]
A =[("бам", 2), ("там", 3)]
A[0][0]
A[0][1]
for i in range(N-1):
for j in range(N-2, i-1 ,-1):
по значению!
if A[j][1] < A[j+1][1]:
A[j], A[j+1] = A[j+1], A[j]
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
48. Словарь и массив пар
Алгоритмизация и программирование. Язык Python, 11 класс48
Словарь и массив пар
Сортировка:
A.sort()
по ключам, если ключи
равны – по значениям
A.sort( key = lambda x: x[0])
по ключам
по значениям
A.sort( key = lambda x: x[1])
A.sort( key = lambda x: (x[1], x[0]))
по значениям, если они
равны – по ключам
A.sort( key = lambda x: (-x[1], x[0]))
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
49. Словарь и массив пар
Алгоритмизация и программирование. Язык Python, 11 класс49
Словарь и массив пар
Вывод массива пар
for x in A:
print( f"{x[0]}: {x[1]}" )
или так
for x in A:
print( "{}: {}".format(x[0], x[1]) )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
50. Алгоритмизация и программирование. Язык Python
50Алгоритмизация и
программирование.
Язык Python
Анализ текста на
естественном языке
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
51. Что такое анализ текста?
Алгоритмизация и программирование. Язык Python, 11 класс51
Что такое анализ текста?
Анализ текста (или интеллектуальный анализ
текста) — это компьютерная обработка текста
для извлечения какой-либо информации.
NLP = Natural Language Processing
• классификация текстов (отзывы)
• извлечение ключевых слов (упоминание
компании)
• тематическая модель документа (набор
слов классификация документа)
• удаление персональных данных
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
52. Типы NLP-программ
Алгоритмизация и программирование. Язык Python, 11 класс52
Типы NLP-программ
• на основе лингвистических моделей:
– выделение частей речи
– определение падежей и склонений
– определение смысла с учётом соседних
слов и предложений
• глубокие нейронные сети (DNN – deep
neural network)
– обучение на большом количестве примеров
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
53. Выделение шаблонов
Алгоритмизация и программирование. Язык Python, 11 класс53
Выделение шаблонов
Определить, сколько раз в строке s
встречаются подстроки «гласная + согласная».
Известная строка:
s = "АБВААБВГАБ"
print( s.count("АБ") )
шаблон
Любые строки «гласная + согласная»:
# перебирать все варианты???
print( s.count("АБ") +
s.count("АВ") +
s.count("АГ") + ... )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
54. Конечный автомат (КА)
Алгоритмизация и программирование. Язык Python, 11 класс54
Конечный автомат (КА)
КА — это модель устройства, которое может
находиться только в одном из нескольких
состояний.
Состояния автомата:
1 – ждём гласную (начало шаблона)
2 – ждём согласную
count += 1
согласная
согласная
1
2
гласная
гласная
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
55. Конечный автомат для поиска шаблона
Алгоритмизация и программирование. Язык Python, 11 класс55
Конечный автомат для поиска шаблона
s = open( "input.txt" ).read()
glas = "АЕЁИОУЫЭЮЯ"
sogl = "БВГДЖЗЙКЛМНПРСТФХЧЦШЩ"
state, count = 1, 0
for c in s:
if state == 1:
if c in glas: # переход 1-> 2
state = 2
else:
if c in sogl: # переход 2-> 1
state = 1
count += 1
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
56. Еще один пример КА
Алгоритмизация и программирование. Язык Python, 11 класс56
Еще один пример КА
В тексте встречаются коды кабинетов, которые
имею такой формат: «буква+„–”+три цифры». Буква в
номере — это A, Б или У. Нужно вывести на экран все
найденные коды кабинетов и их количество.
? Какие состояния у автомата?
Состояния автомата:
0 – ждём букву А, Б или У
1 – ждём дефис
2 – ждём первую цифру
3 – ждём вторую цифру
4 – ждём третью цифру
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
57. Еще один пример КА
Алгоритмизация и программирование. Язык Python, 11 класс57
Еще один пример КА
не А, Б, У
не «-»
0
1
А, Б
или У
цифра цифра цифра
«-»
2
3
4
!
терминальное
состояние
Состояния автомата:
0 – ждём букву А, Б или У
1 – ждём дефис
2 – ждём первую цифру
3 – ждём вторую цифру
4 – ждём третью цифру
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
58. Ещё один пример КА
Алгоритмизация и программирование. Язык Python, 11 класс58
Ещё один пример КА
room – строка с кодом кабинета
len(room)– состояние автомата
s = open( "input.txt" ).read()
room, count = '', 0
for c in s:
L = len( room )
if not room and c in "АБУ":
room = c
elif L == 1 and c == '-':
room += c
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
59. Ещё один пример КА
Алгоритмизация и программирование. Язык Python, 11 класс59
Ещё один пример КА
elif L > 1 and c in "0123456789":
room += c
if L+1 == 5: # номер получен!
print( room )
count += 1
room = ''
else:
room = ''
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
60. Регулярные выражения
Алгоритмизация и программирование. Язык Python, 11 класс60
Регулярные выражения
Регулярные выражения (англ. regex: regular
expression) — это строки, задающие шаблон
для поиска и замены фрагментов текста.
модуль для работы
с регулярными
выражениями
import re
s = "Карл у Клары украл кораллы."
if re.search( "коралл", s ):
print( "Есть коралл!" )
else: # вернёт None, если нет
print( "Нет коралла." )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
61. Как определить позицию?
Алгоритмизация и программирование. Язык Python, 11 класс61
Как определить позицию?
«моржовый»
оператор
import re
s = "Карл у Клары украл кораллы."
if m := re.search( "коралл", s ):
print( "Есть коралл!" )
print( m.span() )
# [19, 25)
p0, p1 = m.span()
print( s[p0:p1] )
# коралл
else: # вернёт None, если нет
print( "Нет коралла." )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
62. . – один любой символ
Алгоритмизация и программирование. Язык Python, 11 класс62
. – один любой символ
import re
s = "Кура кара кора икра кобура"
m = re.search( "к.ра"
"к.ра", s )
позиции
что нашли
if m:
print( m.span(), m.group() )
# (5, 9) кара
? Почему не «Кура»?
без учёта
регистра
m = re.search( "к.ра", s, re.I )
ignore case
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
63. Все совпадения с шаблоном
Алгоритмизация и программирование. Язык Python, 11 класс63
Все совпадения с шаблоном
import re
s = "Кура кара кора икра кобура"
findall ( "к.ра", s, re.I )
m = re.findall
print( m )
# ['Кура', 'кара', 'кора']
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
64. ? – 0 или 1 совпадение предыдущего
Алгоритмизация и программирование. Язык Python, 11 класс64
? – 0 или 1 совпадение предыдущего
import re
s = "Кура кара кора икра кобура"
m = re.findall( "к.?ра"
"к.?ра", s, re.I )
print( m )
# ['Кура', 'кара', 'кора', 'кра']
.? пусто или 1 любой символ
? Почему не «кобура»?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
65. * – 0 или > совпадений предыдущего
Алгоритмизация и программирование. Язык Python, 11 класс65
* – 0 или > совпадений предыдущего
+ – 1 или > совпадений предыдущего
import re
s = "Кура кара кора икра кобура"
m = re.findall( "к.*ра"
"к.*ра", s, re.I )
print( m )
# ['Кура кара кора икра кобура']
! «Жадный» поиск!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
66. Специальные символы с \
Алгоритмизация и программирование. Язык Python, 11 класс66
Специальные символы с \
\d
\D
\w
\W
\s
\S
\b
– любая цифра
– любой символ, кроме цифры
– любая буква, цифра или знак _
– любой символ, кроме букв, цифр и знаков _
– любой пробельный символ
– любой непробельный символ
– граница слова
import re
s = "Кура 123 кара 3456 кора 78910"
m = re.findall( rr"\d\d\d", s )
print( m )
# ['123', '345', '789']
! Буква r перед строкой (raw – сырой)!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
67. Снова к знакомой задаче
Алгоритмизация и программирование. Язык Python, 11 класс67
Снова к знакомой задаче
В тексте встречаются коды кабинетов, которые
имею такой формат: «буква+„–”+три цифры». Буква в
номере — это A, Б или У. Нужно вывести на экран все
найденные коды кабинетов и их количество.
import re
s = "А-213 Б-4 Б-219 Ф-215 У-514"
m = re.findall( r"[АБУ]-\d{3}"
"[АБУ]-\d{3}" , s )
print( m )
или
3 шт.
# ['А-213', 'Б-219', 'У-514']
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
68. Поиск URL
Алгоритмизация и программирование. Язык Python, 11 класс68
Поиск URL
В строке url записан URL-адрес веб-страницы. Требуется
определить адрес сайта (IP-адрес или доменное имя).
import re
url = "https://www.example.com/o/ht/qq.htm"
[^/] +/", url )
m = re.search( r"https?://[^/]
кроме /
print( m.span() ) # (0, 24)
print( m.group() )# https://www.example.com/
?
Почему плохо "https?://.+/"?
К.Ю. Поляков, Е.А. Ерёмин, 2025
«жадный
поиск»
http://kpolyakov.spb.ru
69. Группы
Алгоритмизация и программирование. Язык Python, 11 класс69
Группы
В строке s записаны адреса сайтов и веб-страниц.
Требуется выделить все адреса сайтов (IP-адреса или
доменные имена).
import re
s = "https://ex.com/news " + \
"http://192.168.0.1/arc"
m = re.findall( r"https?://([^/]+)/",
s )
([^/]+)
print( m )
группа в
# ['ex.com', '192.168.0.1'] скобках ()
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
70. Замена подстроки на другую
Алгоритмизация и программирование. Язык Python, 11 класс70
Замена подстроки на другую
Заменить форматы всех дат в строке s:
США: 01/23/2023 Россия: 23.01.2023
"(\d{2})/(\d{2})/(\d{4})"
\1
\2
"\2.\1.\3"
\3
import re
s = "Даты: 12/11/2022 и 01/23/2023."
sub
substitute – заменить
sNew = re.sub(
r"(\d{2})/(\d{2})/(\d{4})",
r"\2.\1.\3", s )
print( sNew )
# Даты: 11.12.2022 и 23.01.2023.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
71. Частотный анализ текста
Алгоритмизация и программирование. Язык Python, 11 класс71
Частотный анализ текста
Частотный анализ — это исследования частоты
появления в тексте отдельных символов, пар
символов, троек и т. д.
Загрузка файла:
s = open( "input.txt" ).read()
s = s.lower() # все строчные
Словарь из счётчиков для каждой буквы:
counters = { c: 0 for c in
"абвгдеёжзийклмнопрстуфхцчшщъыьэюя" }
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
72. Частотный анализ текста
Алгоритмизация и программирование. Язык Python, 11 класс72
Частотный анализ текста
Основной цикл: считаем количество для каждого символа
for c in s:
if c in counters:
counters[c] += 1
Относительные частоты:
total = sum( counters.values() )
for c in counters:
counters[c] /= total
Сортировка по убыванию частоты:
sortCounters = sorted( counters.items(),
key = lambda p: p[1],
reverse = True )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
73. Частотный анализ текста
Алгоритмизация и программирование. Язык Python, 11 класс73
Частотный анализ текста
Выводим первые 10 символов
for c, freq in sortCounters[:10]:
print( f"{c}: {freq:0.3f}" )
? Как найти частоты биграмм (пар символов)?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
74. Алгоритмизация и программирование. Язык Python
74Алгоритмизация и
программирование.
Язык Python
Стек, дек, очередь
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
75. Что такое стек?
Алгоритмизация и программирование. Язык Python, 11 класс75
Что такое стек?
Стек (англ. stack – стопка) – это линейный список, в
котором элементы добавляются и удаляются только с
одного конца («последним пришел – первым ушел»).
LIFO = Last In – First Out.
Системный стек:
• адреса возврата из подпрограмм
• передача аргументов подпрограмм
• хранение локальных переменных
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
76. Реверс массива
Алгоритмизация и программирование. Язык Python, 11 класс76
Реверс массива
Задача. В файле записаны целые числа. Нужно вывести
их в другой файл в обратном порядке.
while файл не пуст:
прочитать x
добавить x в стек
5
4
3
2
5
4
3
2
1
1
while стек не пуст:
вытолкнуть число из стека в x
записать x в файл
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
77. Использование списка
Алгоритмизация и программирование. Язык Python, 11 класс77
Использование списка
! Конец списка – вершина стека!
Создать стек:
stack = []
«Втолкнуть» x в стек:
stack.append ( x )
Снять элемент с вершины стек в x:
x = stack.pop()
• удалить последний элемент
• вернуть удалённый элемент как
результат функции
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
78. Инверсия массива неизвестной длины
Алгоритмизация и программирование. Язык Python, 11 класс78
Инверсия массива неизвестной длины
Чтение из файла:
stack = []
for s in open( "input.txt" ):
stack.append ( int(s) )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
79. Инверсия массива неизвестной длины
Алгоритмизация и программирование. Язык Python, 11 класс79
Инверсия массива неизвестной длины
Запись в файл (в обратном порядке):
with open ( "output.txt", "w" ) as F:
while len(stack) > 0:
while stack:
x = stack.pop()
F.write ( str(x) + "\n" )
без переменной x:
with open ( "output.txt", "w" ) as F:
while stack:
F.write ( str(stack.pop()) + "\n" )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
80. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык Python, 11 класс80
Вычисление арифметических выражений
? Как компьютер вычисляет арифметические
выражения?
(5+15)/(4+7-1) инфиксная форма (знак операции
между данными)
1920 (Я. Лукашевич): префиксная форма
(знак операции перед данными)
/ + 5 15 - + 4 7 1
/ + 5 15 - 11 1
/ + 5 15 10
/ 20 10
2
К.Ю. Поляков, Е.А. Ерёмин, 2025
не нужны скобки
первой стоит последняя
операция (вычисляем с конца)
http://kpolyakov.spb.ru
81. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык Python, 11 класс81
Вычисление арифметических выражений
(5+15)/(4+7-1)
1950-е: постфиксная форма
(знак операции после данных)
5 15 + 4 7 + 1 - /
20 4 7 + 1 - /
не нужны скобки
вычисляем с начала
20 11 1 - /
20 10 /
2
! Вычисляем с помощью стека!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
82. Использование стека
Алгоритмизация и программирование. Язык Python, 11 класс82
Использование стека
5 15 + 4 7 + 1 - /
5
5
15
5
15
20
+
4
20
4
7
4
20
7
11
20
+
1
11
20
1
10
20
-
2
/
• если число – «втолкнуть» в стек
• если операция – выполнить с верхними элементами
стека
! В стеке остается результат!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
83. Вычисление постфиксной формы
Алгоритмизация и программирование. Язык Python, 11 класс83
Вычисление постфиксной формы
data = input().split()
разбить строку
stack = []
на элементы
for x in data:
if x in "+-*/":
# если операция
op2 = int(stack.pop())
взять 2 значения
со стека
op1 = int(stack.pop())
if
x == "+": res = op1 + op2
elif x == "-": res = op1 - op2
выполнить
операцию
elif x == "*": res = op1 * op2
else:
res = op1 // op2
stack.append ( res )
результат в стек
else:
данные в стек
stack.append ( x )
print ( stack[0] )
# результат
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
84. Скобочные выражения
Алгоритмизация и программирование. Язык Python, 11 класс84
Скобочные выражения
Задача. Вводится символьная строка, в которой записано
некоторое (арифметическое) выражение,
использующее скобки трёх типов: ( ), [ ] и { }.
Проверить, правильное ли расставлены скобки.
()[{()[]}]
[()
[()}
)(
([)]
Для одного типа скобок:
счётчик
0
(
)
(
(
)
(
(
)
)
)
1
0
1
2
1
2
3
2
1
0
({[)}]
? Когда выражение правильное?
• счётчик всегда 0
! Для разных скобок
• в конце счётчик = 0
не работает!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
85. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык Python, 11 класс85
Скобочные выражения (стек)
(
(
[
(
[
(
[
(
(
[
(
)
{
[
(
{
(
{
[
(
(
{
[
(
)
[
(
}
(
]
)
• если открывающая скобка – «втолкнуть» в стек
• если закрывающая скобка – снять парную со стека
? Когда выражение правильное?
• когда встретили закрывающую скобку, на вершине
стека лежит соответствующая открывающая
• в конце работы стек пуст
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
86. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык Python, 11 класс86
Скобочные выражения (стек)
Подготовка:
pairs = {"(": ")", "[": "]", "{": "}"}
stack = []
# пустой стек
err = False
# признак ошибки
Вывод результата:
if not err:
print ( "Выражение правильное." )
else:
print ( "Выражение неправильное." )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
87. Скобочные выражения (стек)
Алгоритмизация и программирование. Язык Python, 11 класс87
Скобочные выражения (стек)
для всех символов
строки s
парную скобку
в стек
for c in s:
if c in pairs:
stack.append( pairs[c] ) если закрывающая
скобка…
elif c in pairs.values():
if not stack or c != stack.pop():
err = True
стек
не та
break
пуст
скобка
if stack: err = True
если не все скобки
закрыты
К.Ю. Поляков, Е.А. Ерёмин, 2025
? Что ещё?
http://kpolyakov.spb.ru
88. Что такое очередь?
Алгоритмизация и программирование. Язык Python, 11 класс88
Что такое очередь?
Очередь – это линейный список,
для которого введены две
операции:
• добавление элемента в конец
• удаление первого элемента
FIFO = Fist In – First Out.
Применение:
• очереди сообщений в операционных системах
• очереди запросов ввода и вывода
• очереди пакетов данных в маршрутизаторах
•…
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
89. Управление очередью
Алгоритмизация и программирование. Язык Python, 11 класс89
Управление очередью
Подготовка:
Queue = []
Добавить элемент (в конец):
Queue.append( x )
Удалить элемент (с начала):
x = Queue.pop( 0 )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
90. Управление очередью
Алгоритмизация и программирование. Язык Python, 11 класс90
Управление очередью
Queue.append( 1 )
1
Queue.append( 2 )
1
x = Queue.pop( 0 )
x
2
1
2
Queue.append( 3 )
1
2
3
Queue.append( 4 )
1
2
3
x = Queue.pop( 0 )
2
3
4
Queue.append( 5 )
2
3
4
К.Ю. Поляков, Е.А. Ерёмин, 2025
4
5
http://kpolyakov.spb.ru
91. Заливка области
Алгоритмизация и программирование. Язык Python, 11 класс91
Заливка области
Задача. Рисунок задан в виде матрицы A, в которой
элемент A[y][x] определяет цвет пикселя на
пересечении строки y и столбца x. Перекрасить в цвет
2 одноцветную область, начиная с пикселя (x0,y0).
0 1 2 3 4
0 1 2 3 4
0 0 1 0 1 1
0 0 2 0 1 1
1 1 1 1 2 2
(0,1)
1 2 2 2 2 2
2 0 1 0 2 2
2 0 2 0 2 2
3 3 3 1 2 2
3 3 3 1 2 2
4 0 1 1 0 0
4 0 1 1 0 0
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
92. Заливка: использование очереди
Алгоритмизация и программирование. Язык Python, 11 класс92
Заливка: использование очереди
добавить в очередь точку (x0,y0)
color = цвет начальной точки
while очередь не пуста:
взять из очереди точку (x,y)
if A[y][x] == color:
A[y][x] = цвет заливки
добавить в очередь точку (x-1,y)
добавить в очередь точку (x+1,y)
добавить в очередь точку (x,y-1)
добавить в очередь точку (x,y+1)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
93. Заливка
Алгоритмизация и программирование. Язык Python, 11 класс93
Заливка
Подготовка:
YMAX = len(A)
XMAX = len(A[0])
NEW_COLOR = 2
y0 = 0
x0 = 1
# начать заливку отсюда
color = A[y0][x0] # цвет начальной точки
Элементы очереди – координаты:
(x, y)
Q = []
Q.append ( (x0,y0) )
кортеж
добавить
начальную точку
! Кортеж – неизменяемая последовательность
элементов (как список, но нельзя изменять)!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
94. Заливка (основной цикл)
Алгоритмизация и программирование. Язык Python, 11 класс94
Заливка (основной цикл)
пока очередь не пуста
while len(Q) > 0:
while Q:
x, y = Q.pop(0)
if A[y][x] == color:
перекрасить
A[y][x] = NEW_COLOR
if x > 0:
Q.append( (x-1,y) )
if x < XMAX-1: Q.append( (x+1,y) )
if y > 0:
Q.append( (x,y-1) )
if y < YMAX-1: Q.append( (x,y+1) )
с проверкой
выхода за
границы
К.Ю. Поляков, Е.А. Ерёмин, 2025
? Что можно улучшить?
http://kpolyakov.spb.ru
95. Очередь: статический массив
Алгоритмизация и программирование. Язык Python, 11 класс95
Очередь: статический массив
голова
Head
Tail
хвост
0
N-1
1
2
3
4
Удаление элемента:
Head
5
Tail
0
N-1
1
2
3
4
Добавление элемента:
Head
5
Tail
0
N-1
2
3
4
не двигаем элементы
К.Ю. Поляков, Е.А. Ерёмин, 2025
5
6
нужно знать размер
http://kpolyakov.spb.ru
96. Очередь: статический массив
Алгоритмизация и программирование. Язык Python, 11 класс96
Очередь: статический массив
Замыкание в кольцо:
Tail
Head
1
7
N
8
9
1
Очередь заполнена:
Tail
2
3
4
5
Head
1
7
6
N
8
9
10 11 12
Очередь пуста:
1
1
2
3
4
5
6
Tail Head
N
! Вариант: хранить размер очереди в переменной!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
97. Что такое дек?
Алгоритмизация и программирование. Язык Python, 11 класс97
Что такое дек?
Дек – это линейный список, в котором можно добавлять и
удалять элементы как с одного, так и с другого конца.
Моделирование:
• массив (список)
изменяющегося размера
•collections.deque
добавить в начало
удалить с начала
К.Ю. Поляков, Е.А. Ерёмин, 2025
import collections
d = collections.deque()
d.append(1)
d.appendleft(0)
d.pop()
d.popleft()
http://kpolyakov.spb.ru
98. Алгоритмизация и программирование. Язык Python
98Алгоритмизация и
программирование.
Язык Python
Деревья
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
99. Что такое дерево?
Алгоритмизация и программирование. Язык Python, 11 класс99
Что такое дерево?
A
1
B
D
C
E
F
«Сыновья» А: B, C.
2
Высота дерева —
наибольшее
расстояние от
корня до листа
G
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G. «Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
100. Рекурсивные определения
Алгоритмизация и программирование. Язык Python, 11 класс100
Рекурсивные определения
1) пустая структура – это дерево
2) дерево – это корень и несколько связанных с ним
отдельных (не связанных между собой) деревьев
Двоичное (бинарное) дерево:
1) пустая структура – это двоичное дерево
2) двоичное дерево – это корень и два связанных с ним
отдельных двоичных дерева («левое» и «правое»
поддеревья)
Применение:
• поиск в большом массиве неменяющихся данных
• сортировка данных
• вычисление арифметических выражений
• оптимальное сжатие данных (метод Хаффмана)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
101. Деревья поиска
Алгоритмизация и программирование. Язык Python, 11 класс101
Деревья поиска
Ключ – это значение, связанное с узлом дерева, по
которому выполняется поиск.
6
3
1
8
4
7
9
• слева от узла – узлы с
меньшими ключами
• справа от узла – узлы с
большими или равными
ключами
O(log N)
? Сложность поиска?
К.Ю. Поляков, Е.А. Ерёмин, 2025
Двоичный поиск O(log N)
Линейный поиск O(N)
http://kpolyakov.spb.ru
102. Обход дерева
Алгоритмизация и программирование. Язык Python, 11 класс102
Обход дерева
Обойти дерево «посетить» все узлы по одному разу.
список узлов
КЛП – «корень-левый-правый» (в прямом порядке):
посетить корень
обойти левое поддерево
обойти правое поддерево
ЛКП – «левый-корень-правый» (симметричный):
обойти левое поддерево
посетить корень
обойти правое поддерево
ЛПК – «левый-правый-корень» (в обратном порядке):
обойти левое поддерево
обойти правое поддерево
посетить корень
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
103. Обход дерева
Алгоритмизация и программирование. Язык Python, 11 класс103
Обход дерева
(1+4)*(9-5)
*
+
«в глубину»
1
-
4
9
5
КЛП: * + 1 4 – 9 5
префиксная форма
ЛКП: 1 + 4 * 9 - 5
инфиксная форма
ЛПК: 1 4 + 9 5 - *
постфиксная форма
Обход «в ширину»: «сыновья», потом «внуки», …
* + - 1 4 9 5
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
104. Обход КЛП – обход «в глубину»
Алгоритмизация и программирование. Язык Python, 11 класс104
Обход КЛП – обход «в глубину»
используется вспомогательный стек
записать в стек корень дерева
while стек не пуст:
выбрать узел V с вершины стека
посетить узел V
если у узла V есть правый сын то
добавить в стек правого сына V
если у узла V есть левый сын то
добавить в стек левого сына V
? Почему сначала добавить правого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
105. Обход КЛП – обход «в глубину»
Алгоритмизация и программирование. Язык Python, 11 класс105
Обход КЛП – обход «в глубину»
(1+4)*(9-5)
*
+
4
1
*
-
9
5
5
9
+
-
1
4
-
4
-
-
9
5
*
+
1
4
–
К.Ю. Поляков, Е.А. Ерёмин, 2025
5
http://kpolyakov.spb.ru
106. Обход «в ширину»
Алгоритмизация и программирование. Язык Python, 11 класс106
Обход «в ширину»
используется вспомогательная очередь
записать в очередь корень дерева
пока очередь не пуста:
выбрать узел V из очереди
посетить узел V
если у узла V есть левый сын то
добавить в очередь левого сына V
если у узла V есть правый сын то
добавить в очередь правого сына V
? Почему сначала добавить левого сына?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
107. Обход «в ширину»
Алгоритмизация и программирование. Язык Python, 11 класс107
Обход «в ширину»
(1+4)*(9-5)
*
+
4
1
голова
очереди
*
К.Ю. Поляков, Е.А. Ерёмин, 2025
-
9
5
+
4
1
-
5
9
4
1
5
9
4
5
9
5
*
+
-
1
4
9
5
http://kpolyakov.spb.ru
108. Вспомогательные структуры
Алгоритмизация и программирование. Язык Python, 11 класс108
Вспомогательные структуры
ссылки на сыновей class TNode:
data = ""
left = None
данные
right = None
данные None None
Создание узла:
данные None None
значения по умолчанию
def node(d, L = None, R = None):
newNode = TNode()
# создаём новый узел
newNode.data = d
newNode.left = L
newNode.right = R
return newNode
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
109. Создание дерева
Алгоритмизация и программирование. Язык Python, 11 класс109
Создание дерева
*
+
1
-
4
9
5
T = node("*",
node("+", node("1"), node("4")),
node("-", node("9"), node("5"))
)
L = None, R = None
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
110. Обход дерева в глубину
Алгоритмизация и программирование. Язык Python, 11 класс110
Обход дерева в глубину
Рекурсивный:
def DFS( T ):
if not T: return
print(T.data, end=" ")
DFS(T.left)
DFS(T.right)
Без рекурсии (стек):
def DFS_stack( T ):
stack = [T]
while stack:
V = stack.pop()
print(V.data, end=" ")
if V.right: stack.append(V.right)
if V.left: stack.append(V.left)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
111. Обход дерева в ширину
Алгоритмизация и программирование. Язык Python, 11 класс111
Обход дерева в ширину
def BFS ( T ):
queue = [T]
while queue:
V = queue.pop(0)
# первый из очереди
print(V.data, end=" ")
if V.left: queue.append(V.left)
if V.right: queue.append(V.right)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
112. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык Python, 11 класс112
Вычисление арифметических выражений
? Что будет в корне дерева?
40–2*3–4*5
В корень дерева нужно поместить последнюю из
операций с наименьшим приоритетом.
-
-
40–2*3
4*5
-
-
40
*
2*3
*
40
4
К.Ю. Поляков, Е.А. Ерёмин, 2025
*
2
4
5
3
5
http://kpolyakov.spb.ru
113. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык Python, 11 класс113
Вычисление арифметических выражений
Построение дерева:
найти последнюю выполняемую операцию
if операций нет:
создать узел-лист
return
поместить операцию в корень дерева
построить левое поддерево
построить правое поддерево
! Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
114. Вычисление арифметических выражений
Алгоритмизация и программирование. Язык Python, 11 класс114
Вычисление арифметических выражений
Вычисление по дереву:
n1 = значение левого поддерева
n2 = значение правого поддерева
результат = операция(n1, n2)
! Рекурсия!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
115. Использование связанных структур
Алгоритмизация и программирование. Язык Python, 11 класс115
Использование связанных структур
Дерево – нелинейная структура динамический
массив неудобен!
данные
данные None None
class TNode:
data = ""
left = None
right = None
новый тип:
узел
К.Ю. Поляков, Е.А. Ерёмин, 2025
данные None None
Создание узла:
def node( d ):
newNode = TNode()
newNode.data = d
newNode.left = None
newNode.right = None
return newNode
http://kpolyakov.spb.ru
116. Основная программа
Алгоритмизация и программирование. Язык Python, 11 класс116
Основная программа
s = input ( "Введите выражение: " )
T = makeTree ( s )
print ( "Результат: ", calcTree(T) )
! Нужно построить makeTree и calcTree!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
117. Построение дерева
Алгоритмизация и программирование. Язык Python, 11 класс117
Построение дерева
def makeTree ( s ):
k = lastOp(s) # номер последней операции
if k < 0:
# создать лист
Tree = node ( s )
else:
# создать узел-операцию
Tree = node ( s[k] )
Tree.left = makeTree ( s[:k] )
Tree.right = makeTree ( s[k+1:] )
return Tree
вернёт ссылку на
корень нового
дерева
Рекурсия!
!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
118. Вычисление по дереву
Алгоритмизация и программирование. Язык Python, 11 класс118
Вычисление по дереву
def calcTree ( Tree ):
это число
if Tree.left == None:
(лист)
return int(Tree.data)
else:
n1 = сalcTree
calcTree ( Tree.left )
Рекурсия!
n2 = calcTree ( Tree.right )
if Tree.data == "+":
res = n1 + n2
elif Tree.data == "-": res = n1 - n2
elif Tree.data == "*": res = n1 * n2
else: res = n1 // n2
return res
!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
119. Вспомогательные функции
Алгоритмизация и программирование. Язык Python, 11 класс119
Вспомогательные функции
Приоритет операции:
def priority ( op ):
if op in "+-": return 1
if op in "*/": return 2
return 100
Номер последней операции:
def lastOp ( s ):
minPrt = 50
# любое между 2 и 100
k = -1
for i in range(len(s)):
if priority(s[i]) <= minPrt:
minPrt = priority(s[i])
k=i
Почему <=?
return k
?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
120. Двоичное дерево в массиве
Алгоритмизация и программирование. Язык Python, 11 класс120
Двоичное дерево в массиве
-
0
-
*
*
2
A[0]
A[1]
A[2]
4
5
3
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
5
6
7
8
9
10
7
8
9
10
- - * 40 *
0
1
2
3
4
- - * 40 * 4 5
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
2
- - *
0
40
1
0
1
2
3
4
5
6
- - * 40 * 4 5
A[4]
К.Ю. Поляков, Е.А. Ерёмин, 2025
A[9]
A[10]
A[i]
2 3
?
A[2*i+1]
A[2*i+2]
?
http://kpolyakov.spb.ru
121. Алгоритмизация и программирование. Язык Python
121Алгоритмизация и
программирование.
Язык Python
Графы
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
122. Что такое граф?
Алгоритмизация и программирование. Язык Python, 11 класс122
Что такое граф?
Граф – это набор вершин и связей между ними (рёбер).
Матрица смежности:
A
B
C
D
Список смежности:
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2025
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
петля
http://kpolyakov.spb.ru
123. Связность графа
Алгоритмизация и программирование. Язык Python, 11 класс123
Связность графа
Связный граф – это граф, между любыми вершинами
которого существует путь.
A
B
C
A
C
B
D
D
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
124. Дерево – это граф?
Алгоритмизация и программирование. Язык Python, 11 класс124
Дерево – это граф?
Дерево – это связный граф без циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2025
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru
125. Взвешенные графы
Алгоритмизация и программирование. Язык Python, 11 класс125
Взвешенные графы
A
12
B
8
2
C
5
6
Весовая матрица:
A
4
D
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
вес ребра
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
126. Ориентированные графы (орграфы)
Алгоритмизация и программирование. Язык Python, 11 класс126
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец), рёбра
называю дугами.
A
8
5
12
B
6
A
C
4
D
A
B
C
D
12
B
12
C
8
5
D
6
4
4
! Весовая матрица может быть несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
127. Ввод весовой матрицы
Алгоритмизация и программирование. Язык Python, 11 класс127
Ввод весовой матрицы
A
A
B
C
D
12
B
12
C
8
5
4
D
4
6
4
0 12
12 0
0 0
0 0
8
5
0
4
0
6
4
0
Для отладки (пример из условия):
N=4
W = [ [0, 12, 8, 0],
[12, 0, 5, 6],
[0, 0, 0, 4],
[0, 0, 4, 0]
]
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
128. Ввод весовой матрицы
Алгоритмизация и программирование. Язык Python, 11 класс128
Ввод весовой матрицы
A
A
B
C
D
12
B
12
C
8
5
D
4
6
4
0 12
12 0
0 0
0 0
4
8
5
0
4
0
6
4
0
Рабочий вариант:
N = int(input())
W = []
for i in range(N):
row = [ int(x)
for x in input().split() ]
W.append(row)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
129. Список смежности из весовой матрицы
Алгоритмизация и программирование. Язык Python, 11 класс129
Список смежности из весовой матрицы
A
A
B
C
D
12
B
12
C
8
5
D
6
4
2 3
1 3 4
4
3
4
Через индексы:
for i in range(N):
for j in range(N):
if W[i][j] > 0:
print( f"{j+1}", end=" " )
print() # на следующую строку
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
130. Вывод весовой матрицы
Алгоритмизация и программирование. Язык Python, 11 класс130
Вывод весовой матрицы
A
A
B
C
D
12
B
12
C
8
5
D
6
4
0 12
12 0
0 0
0 0
8
5
0
4
0
6
4
0
4
Через индексы:
for i in range(N):
for j in range(N):
print( f"{W[i][j]:2}", end=" " )
print() # на следующую строку
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
131. Вывод весовой матрицы
Алгоритмизация и программирование. Язык Python, 11 класс131
Вывод весовой матрицы
A
A
B
C
D
12
B
12
C
8
5
D
6
4
0 12
12 0
0 0
0 0
8
5
0
4
0
6
4
0
4
В стиле Python:
for row in W:
for x in row:
print( f"{x:2}", end=" " )
print() # на следующую строку
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
132. Обход графа в глубину
Алгоритмизация и программирование. Язык Python, 11 класс132
Обход графа в глубину
11
1
2
3
4
К.Ю. Поляков, Е.А. Ерёмин, 2025
10
8
5
9
6
7
http://kpolyakov.spb.ru
133. Обход графа в глубину
Алгоритмизация и программирование. Язык Python, 11 класс133
Обход графа в глубину
G = [
[2, 10, 11], # 1
[3, 8, 10], # 2
[4, 5, 8],
# 3
[5],
# 4
4
[6],
# 5
[7],
# 6
[],
# 7
[5, 6, 9],
# 8
[6, 7],
# 9
[8, 9],
# 10
[],
# 11
]
for i in range(11):
for j in range(len(G[i])):
G[i][j] -= 1
К.Ю. Поляков, Е.А. Ерёмин, 2025
11
1
2
3
10
8
5
9
6
7
http://kpolyakov.spb.ru
134. Обход графа в глубину
Алгоритмизация и программирование. Язык Python, 11 класс134
Обход графа в глубину
англ. DFS = Depth First Search
visited = [False]*len(G)
def DFS( G, v ):
if not visited[v]:
print( v+1, end=" " ) # обработали
visited[v] = True
for nxt in G[v]:
DFS( G, nxt )
Рекурсия!
DFS( G, 0 )
начать обход с
вершины 1
!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
135. Обход графа в глубину (без рекурсии)
Алгоритмизация и программирование. Язык Python, 11 класс135
Обход графа в глубину (без рекурсии)
англ. DFS = Depth First Search
def DFS_stack( G, v ):
visited = [False]*len(G)
stack = [v0]
while stack:
v = stack.pop()
if not visited[v]:
print( v+1, end=" " )
visited[v] = True
for nxt in reversed(G[v]):
stack.append( nxt )
? Если нет?
DFS_stack( G, 0 )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
136. Обход графа в ширину
Алгоритмизация и программирование. Язык Python, 11 класс136
Обход графа в ширину
4
1
2
5
8
3
6
9
7
10
11
? Когда нужно?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
137. Обход графа в глубину
Алгоритмизация и программирование. Язык Python, 11 класс137
Обход графа в глубину
англ. BFS = Breadth First Search
def BFS( G, v0 ):
visited = [False]*len(G)
queue = [v0]
while queue:
v = queue.pop(0)
print( v+1, end=" " )
for nxt in G[v]:
if not visited[nxt]:
visited[nxt] = True
queue.append( nxt )
BFS( G, 0 )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
138. Жадные алгоритмы
Алгоритмизация и программирование. Язык Python, 11 класс138
Жадные алгоритмы
Жадный алгоритм – это многошаговый алгоритм, в
котором на каждом шаге принимается решение,
лучшее в данный момент.
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
1
К.Ю. Поляков, Е.А. Ерёмин, 2025
C
7
D
8
4
1
3
E
F
5
http://kpolyakov.spb.ru
139. Жадные алгоритмы
Алгоритмизация и программирование. Язык Python, 11 класс139
Жадные алгоритмы
Задача. Найти кратчайший маршрут из А в F.
2
B
9
A
4
C
7
D
8
1
1
3
E
F
2
? Это лучший маршрут?
! Жадный алгоритм не всегда даёт наилучшее
решение!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
140. Задача Прима-Крускала
Алгоритмизация и программирование. Язык Python, 11 класс140
Задача Прима-Крускала
Задача. Между какими городами нужно проложить линии
связи, чтобы все города были связаны в одну систему
и общая длина линий связи была наименьшей?
(минимальное остовное дерево)
7
D
B
2
1
8
3
9
A
F
4
C
1
2
E
!
Алгоритм Крускала:
Лучшее решение!
• начальное дерево – пустое
• на каждом шаге добавляется ребро минимального
веса, которое ещё не входит в дерево и не
приводит к появлению цикла
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
141. Раскраска вершин
Алгоритмизация и программирование. Язык Python, 11 класс141
Раскраска вершин
2
B
9
A
4
C
7
D
8
1
1
3
E
col = [i for i in range(N)]
F
2
каждой
вершине
свой цвет
Сделать N-1 раз:
• ищем ребро минимальной длины среди всех рёбер,
концы которых окрашены в разные цвета;
• найденное ребро (iMin,jMin) добавляется в список
выбранных, и все вершины, имеющие цвет
col[jMin], перекрашиваются в цвет col[iMin].
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
142. Раскраска вершин
Алгоритмизация и программирование. Язык Python, 11 класс142
Раскраска вершин
Весовая матрица:
N=6
INF = 30000 # очень большое число
W = []
for i in range(N):
W.append ( [0]*N )
# заполнить матрицу
Вывод результата:
for edge in ostov:
print ( "(", edge[0], ",",
edge[1], ")" )
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
143. Раскраска вершин
Алгоритмизация и программирование. Язык Python, 11 класс143
Раскраска вершин
ostov = [] # список выбранных рёбер
for k in range(N-1):
minDist = INF # очень большое число
for i in range(N):
ищем ребро с
for j in range(N):
минимальным
весом
if col[i] != col[j] \
and W[i][j] < minDist:
iMin = i
jMin = j
добавить
minDist = W[i][j]
новое ребро
ostov.append ( (iMin, jMin) )
c = col[jMin]
перекраска
for i in range(N):
вершин
if col[i] == c:
col[i] = col[iMin]
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
144. Кратчайший маршрут
Алгоритмизация и программирование. Язык Python, 11 класс144
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
C
4
dist
selected
A
0
+
выбрана?
К.Ю. Поляков, Е.А. Ерёмин, 2025
D
1
B
2
C
4
1
3
F
2
E
D
Э.В. Дейкстра
E
F
кратчайшее
расстояние от A
ближайшая от A
невыбранная вершина
http://kpolyakov.spb.ru
145. Кратчайший маршрут
Алгоритмизация и программирование. Язык Python, 11 класс145
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
C
4
dist
selected
W[x,z]
X
A
0
+
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2025
D
1
B
2
+
C
4
W[z,y]
Y
1
3
F
2
E
D
9
E
Э.В. Дейкстра
F
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru
146. Кратчайший маршрут
Алгоритмизация и программирование. Язык Python, 11 класс146
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
C
4
dist
selected
W[x,z]
X
A
0
+
Z
W[x,y]
К.Ю. Поляков, Е.А. Ерёмин, 2025
D
1
B
2
+
C
4
+
W[z,y]
Y
1
3
F
2
E
D
9
E
5
Э.В. Дейкстра
F
может быть так, что
W[x,z] + W[z,y] < W[x,y]
http://kpolyakov.spb.ru
147. Кратчайший маршрут
Алгоритмизация и программирование. Язык Python, 11 класс147
Кратчайший маршрут
Алгоритм Дейкстры (1960):
7
B
2
8
9
A
C
4
dist
selected
A
0
+
B
2
+
D
3
F
D
9
8
E
5
+
Э.В. Дейкстра
2
E
1
C
4
+
1
F
7
длины кратчайших
маршрутов из A в
другие вершины
! При рассмотрении вершин F и D
таблица не меняется!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
148. Как найти сам кратчайший маршрут?
Алгоритмизация и программирование. Язык Python, 11 класс148
Как найти сам кратчайший маршрут?
B
2
C
4
A
0
D
8
9
A
dist
7
B
2
3
F
2
E
1
C
4
1
D
8
E
5
F
7
dist[D] + DF = 8 + 1 = 9
dist[E] + EF = 5 + 2 = 7
откуда
приехали в
F?
A C E F
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
149. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык Python, 11 класс149
Алгоритм Дейкстры
Весовая матрица:
N=6
W = []
for i in range(N):
W.append ( [0]*N )
# заполнить матрицу
Вспомогательные массивы:
INF = 30000
# очень большое число
selected = [False]*N # все не выбраны
dist = [INF]*N
# расстояния неизвестны
Стартовая вершина:
вершина A
start = 0
просмотрена
dist[start] = 0
V = start
# выбранная вершина
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
150. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык Python, 11 класс150
Алгоритм Дейкстры
?
Основной цикл:
Какова сложность?
minDist = 0
while minDist < INF:
O(N2)
selected[V] = True
# проверка маршрутов через вершину V
for i in range(N):
if dist[V]+W[V][i] < dist[i]:
dist[i] = dist[V] + W[V][i]
# поиск новой вершины dist[i] -> min
minDist = INF # большое число
for i in range(N):
if not selected[i] and \
dist[i] < minDist:
minDist = dist[i]
V = i
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
151. Алгоритм Дейкстры
Алгоритмизация и программирование. Язык Python, 11 класс151
Алгоритм Дейкстры
Вывод результата (маршрут 0 N-1):
пока не пришли в
V = N - 1
начальную вершину
print(V)
обратным ходом
while V != start:
for i in range(N):
if i != V and \
dist[i]+W[i][V] == dist[V]:
V = i
break
нашли вершину i, из
print(V)
которой могли прийти в
вершину V
? Она единственная?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
152. Алгоритм Флойда
Алгоритмизация и программирование. Язык Python, 11 класс152
Алгоритм Флойда
Все кратчайшие пути (из любой вершины в любую)
Идея:
K
W[i][k]
I
W[k][j]
W[i][j]
J
? Какова сложность?
O(N3)
проверить все
для всех
вершины
пар вершин
for k in range(N):
без
for i in range(N):
вершины k
for j in range(N):
if W[i][k] + W[k][j] < W[i][j]:
W[i][j] = W[i][k] + W[k][j]
путь через
вершину k
К.Ю. Поляков, Е.А. Ерёмин, 2025
? Как найти сам маршрут?
http://kpolyakov.spb.ru
153. Списки смежности
Алгоритмизация и программирование. Язык Python, 11 класс153
Списки смежности
Список смежности:
вершина 1: ( 4 )
вершина 2: ( 1, 3 )
вершина 3: ( )
вершина 4: ( 2, 3, 5 )
вершина 5: ( 3 )
2
1
3
5
4
Graph = [ [],
# фиктивный элемент
[4],
# для вершины 1
[1,3],
# ... для вершины 2
[],
# ... для вершины 3
[2,3,5], # ... для вершины 4
[3] ]
# ... для вершины 5
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
154. Списки смежности
Алгоритмизация и программирование. Язык Python, 11 класс154
Списки смежности
Задача. Составить функцию, которая находит число
путей из одной вершины в другую.
список
Основная программа:
посещённых
Graph = [[], [4], [1,3], [],
вершин
[2,3,5], [3]]
print ( pathCount (Graph, 1, 3, []) )
откуда
куда
? Зачем список посещенных вершин?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
155. Число путей: функция
Алгоритмизация и программирование. Язык Python, 11 класс155
Число путей: функция
списки
смежности
список посещённых
вершин
def pathCount ( graph, vStart, vEnd,
visited ):
if vStart == vEnd:
если уже пришли,
выход
return 1
visited.append ( vStart )
count = 0
суммируем пути
for v in graph[vStart]:
через соседние
if not v in visited:
count += pathCount ( graph, v, vEnd,
visited )
visited.pop()
return count
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
156. Задача коммивояжера
Алгоритмизация и программирование. Язык Python, 11 класс156
Задача коммивояжера
Коммивояжер (бродячий торговец) должен выйти из города 1
и, посетив по разу в неизвестном порядке города 2,3,...N,
вернуться обратно в город 1. В каком порядке надо обходить
города, чтобы путь коммивояжера был кратчайшим?
! Это NP-полная задача, которая строго решается
только перебором вариантов (пока)!
Точные методы:
большое время счета для
1) простой перебор;
больших N
2) метод ветвей и границ;
O(N!)
3) метод Литтла;
4) …
Приближенные методы:
1) метод случайных перестановок (Matlab)
не гарантируется
2) генетические алгоритмы
оптимальное
3) метод муравьиных колоний
решение
4) …
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
157. Некоторые задачи
Алгоритмизация и программирование. Язык Python, 11 класс157
Некоторые задачи
Задача на минимум суммы. Имеется N домов, в каждом из
которых живет pi жителей (i=1,...,N). Надо разместить
магазин в одном из них так, чтобы общее расстояние,
проходимое всеми жителями по дороге в магазин, было
минимальным.
Задача о наибольшем потоке. Есть система труб, которые
имеют соединения в N узлах. Один узел S является
источником, еще один – стоком T. Известны пропускные
способности каждой трубы. Надо найти наибольший поток
от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N
женщин. Каждый мужчина указывает несколько (от 0 до N)
женщин, на которых он согласен жениться. Каждая
женщина указывает несколько мужчин (от 0 до M), за
которых она согласна выйти замуж. Требуется заключить
наибольшее количество моногамных браков.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
158. Алгоритмизация и программирование. Язык Python
158Алгоритмизация и
программирование.
Язык Python
Динамическое
программирование
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
159. Что такое динамическое программирование?
Алгоритмизация и программирование. Язык Python, 11 класс159
Что такое динамическое программирование?
;
Числа Фибоначчи:
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
! Рекурсия!
.
F5
F4
F3
F3
F2
F2
F1
def Fib ( n ):
F2
F1
if n < 3:
return 1
return Fib(n-1) + Fib(n-2)
повторное вычисление тех же значений
! Запоминать то, что вычислено!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
160. Динамическое программирование
Алгоритмизация и программирование. Язык Python, 11 класс160
Динамическое программирование
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Создание массива:
F = [1]*(N+1) # чтобы начать с 1
Заполнение массива:
for i in range(3,N+1):
F[i] = F[i-1] + F[i-2]
F35: рекурсия: 58 с
дин. программирование: < 0,001 с
? Можно ли обойтись без массива?
К.Ю. Поляков, Е.А. Ерёмин, 2025
нужны только
два последних!
http://kpolyakov.spb.ru
161. Динамическое программирование
Алгоритмизация и программирование. Язык Python, 11 класс161
Динамическое программирование
Динамическое программирование – это способ
решения сложных задач путем сведения их к более
простым задачам того же типа.
B
5
2
A
1
С
D
20
30
40
ABE: 5 + 20 = 25
E
AСE: 2 + 30 = 32
ADE: 1 + 40 = 41
увеличение скорости
дополнительный расход памяти
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
162. Количество вариантов
Алгоритмизация и программирование. Язык Python, 11 класс162
Количество вариантов
Задача. Найти количество KN цепочек, состоящих из N
нулей и единиц, в которых нет двух стоящих подряд
единиц.
Решение «в лоб»:
битовые цепочки
1
2
3
N-1
N
0/1
• построить все возможные цепочки
• проверить каждую на «правильность»
? Сколько возможных цепочек?
2N
Сложность
алгоритма O(2N)
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
163. Количество вариантов
Алгоритмизация и программирование. Язык Python, 11 класс163
Количество вариантов
Задача. Найти количество KN цепочек, состоящих из N
нулей и единиц, в которых нет двух стоящих подряд
единиц.
Простые случаи:
KN = KN-1 + KN-2 = FN+2
N = 1: 0 1
K1=2
N = 2: 00 01 10 K2=3
Общий случай:
1
2
3
1
2
3
1
0
N-1
N
N-1
N
0
KN-1
KN-1 «правильных»
цепочек начинаются
с нуля!
KN-2 «правильных»
цепочек начинаются
с единицы!
KN-2
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
164. Оптимальное решение
Алгоритмизация и программирование. Язык Python, 11 класс164
Оптимальное решение
Задача. В цистерне N литров молока. Есть бидоны
объемом 1, 5 и 6 литров. Нужно разлить молоко в
бидоны так, чтобы все бидоны были заполнены и
количество используемых бидонов было
минимальным.
Перебор?
при больших N – очень долго!
«Жадный алгоритм»?
N = 10: 10 = 6 + 1 + 1 + 1 + 1
10 = 5 + 5 K = 2
K=5
! Не даёт оптимального решения!
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
165. Оптимальное решение
Алгоритмизация и программирование. Язык Python, 11 класс165
Оптимальное решение
KN – минимальное число бидонов для N литров
Сначала выбрали бидон…
1 л: KN = 1 + KN-1
5 л:
KN = 1 + KN-5
6 л: KN = 1 + KN-6
min
Рекуррентная формула:
KN = 1 + min (KN-1 , KN-5 , KN-6)
при N 6
KN = 1 + min (KN-1 , KN-5)
при N = 5
KN = 1 + KN-1
при N < 5
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
166. Оптимальное решение (бидоны)
Алгоритмизация и программирование. Язык Python, 11 класс166
Оптимальное решение (бидоны)
KN = 1 + min (KN-1 , KN-5 , KN-6)
N
KN
P
0
0
0
1
1
1
2
2
1
3
3
1
4
4
1
5
1
5
6
1
6
7
2
1
8
3
1
9
4
1
10
2
5
8
3
1
9
4
1
10
2
5
объём бидона, взятого последним
N
KN
P
0
0
0
1
1
1
2 бидона
2
2
1
3
3
1
5 + 5
К.Ю. Поляков, Е.А. Ерёмин, 2025
4
4
1
5
1
5
6
1
6
7
2
1
! Похоже на алгоритм Дейкстры!
http://kpolyakov.spb.ru
167. Количество программ
Алгоритмизация и программирование. Язык Python, 11 класс167
Количество программ
Задача. У исполнителя Утроитель есть команды:
1. прибавь 1
2. умножь на 3
Сколько есть разных программ, с помощью которых
можно из числа 1 получить число 20?
? Как решать, не выписывая все программы?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
168. Количество программ
Алгоритмизация и программирование. Язык Python, 11 класс168
Количество программ
Как получить число N:
N-1
если делится на 3!
N
3
+1
N
последняя
команда
*3
Рекуррентная формула:
KN = KN-1
KN = KN-1 + KN/3
К.Ю. Поляков, Е.А. Ерёмин, 2025
если N не делится на 3
если N делится на 3
http://kpolyakov.spb.ru
169. Количество программ
Алгоритмизация и программирование. Язык Python, 11 класс169
Количество программ
Рекуррентная формула:
если N не делится на 3
если N делится на 3
KN = KN-1
KN = KN-1 + KN/3
Заполнение таблицы:
N
KN
1
1
2
3
4
5
6
7
8
9
10
1
2
2
2
3
3
3
5
5
одна пустая!
N
KN
K2+K1
K5+K2
K8+K3
11
12
13
14
15
16
17
18
19
20
5
7
7
7
9
9
9
12
12
12
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
170. Количество программ
Алгоритмизация и программирование. Язык Python, 11 класс170
Количество программ
20
Только точки изменения:
N
KN
1
1
3
2
6
3
9
5
12
7
15
9
18
12
21
15
Программа:
K = [0]*(N+1)
K[1] = 1
for i in range(2,N+1):
K[i] = K[i-1]
if i % 3 == 0:
K[i] += K[i//3]
? Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
171. Путь Черепахи
Алгоритмизация и программирование. Язык Python, 11 класс171
Путь Черепахи
Задача. Черепаха на клетчатом поле хочет перейти из
клетки (1, 1) в клетку (N, M). За один ход она может
перейти только на одну клетку вправо или на одну
клетку вниз. Сколькими способами она может
добраться до цели?
1
1
1
1
1
2
3
4
1 1
3 4
6 10
10 20
? Сколько способов
для первой строки?
K[i][j] = K[i][j-1] + K[i-1][j]
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
172. Количество маршрутов Черепахи
Алгоритмизация и программирование. Язык Python, 11 класс172
Количество маршрутов Черепахи
Программа:
K = [[0]*M for i in range(N)]
for i in range(0,N):
K[i][0] = 1
for j in range(0,M):
K[0][j] = 1
for i in range(1,N):
for j in range(1,M):
K[i][j] = K[i-1][j]+K[i][j-1]
? Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
173. Размен монет
Алгоритмизация и программирование. Язык Python, 11 класс173
Размен монет
Задача. Сколькими различными способами можно
выдать сдачу размером W рублей, если есть монеты
достоинством pi (i=1, …, N)? В наборе есть монета
достоинством 1 рубль (p1 = 1).
Перебор?
при больших N и W – очень долго!
Динамическое программирование:
запоминаем решения всех задач меньшей
размерности: для меньших значений W и меньшего
числа монет N.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
174. Размен монет
Алгоритмизация и программирование. Язык Python, 11 класс174
Размен монет
Пример: W = 10, монеты 1, 2, 5 и 10
0
1
2
3
i
1
2
5
10
pi
0
1
1
1
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
w
базовые случаи
T[i][w] – количество вариантов для суммы
w с использованием i первых по счёту монет.
Рекуррентная формула (добавили монету pi):
при w < pi: T[i][w] = T[i-1][w] без этой монеты
при w pi: T[i][w] = T[i-1][w] + T[i][w-pi]
все варианты размена остатка
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
175. Размен монет
Алгоритмизация и программирование. Язык Python, 11 класс175
Размен монет
Пример: W = 10, монеты 1, 2, 5 и 10
0
1
2
3
1
2
5
10
0
1
1
1
1
1
1
1
1
1
2
1
2
2
2
3
1
2
2
2
4
1
3
3
3
5
1
3
4
4
6
1
4
5
5
7
1
4
6
6
8
1
5
7
7
9
1
5
8
8
10
1
6
10
11
Рекуррентная формула (добавили монету pi):
при w < pi: T[i][w] = T[i-1][w]
при w pi: T[i][w] = T[i-1][w] + T[i][w-pi]
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
176. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс176
Задача о куче
Задача. Из камней весом pi (i=1, …, N) набрать кучу
весом ровно W или, если это невозможно,
максимально близкую к W (но меньшую, чем W).
Идея: сохранять в массиве решения всех более простых
задач этого типа (при меньшем количестве камней N и
меньшем весе W).
Пример: W = 8, камни 2, 4, 5 и 7
1
2
3
4
i
2
4
5
7
pi
0
0
0
0
0
1
0
2
2
3
2
4
2
5
2
6
2
7
2
8
2
w
базовые случаи
T[i][w] – оптимальный вес, полученный для
кучи весом w из i первых по счёту камней.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
177. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс177
Задача о куче
0
1
2
3
2
4
5
7
0
0
0
0
0
1
0
0
2
2
2
3
2
2
4
2
4
5
2
4
6
2
6
7
2
6
8
2
6
Добавляем камень с весом 4:
для w < 4 ничего не меняется!
для w 4:
если его не брать: T[2][w] = T[1][w]
если его взять:
T[2][w] = 4 + T[1][w-4]
? Какой вариант выбрать?
К.Ю. Поляков, Е.А. Ерёмин, 2025
max
http://kpolyakov.spb.ru
178. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс178
Задача о куче
0
1
2
3
2
4
5
7
0
0
0
0
0
1
0
0
0
2
2
2
2
3
2
2
2
4
2
4
4
5
2
4
5
6
2
6
6
7
2
6
7
8
2
6
7
Добавляем камень с весом 5:
для w < 5 ничего не меняется!
для w 5:
если его не брать: T[3][w] = T[2][w]
если его взять:
T[3][w] = 5 + T[2][w-5]
max
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
179. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс179
Задача о куче
0
1
2
3
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
3
2
2
2
2
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
Добавляем камень с весом 7:
для w < 7 ничего не меняется!
для w 7:
если его не брать: T[4][w] = T[3][w]
если его взять:
T[4][w] = 7 + T[3][w-7]
max
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
180. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс180
Задача о куче
Добавляем камень с весом pi:
для w < pi ничего не меняется!
max
для w pi:
если его не брать: T[i][w] = T[i-1][w]
если его взять:
T[i][w] = pi + T[i-1][w-pi]
Рекуррентная формула:
при w < pi: T[i][w] = T[i-1][w]
при w pi: T[i][w] = max ( T[i-1][w],
pi+T[i-1][w-pi])
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
181. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс181
Задача о куче
? Какие камни нужно взять?
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
3
2
2
2
2
Оптимальный вес 7
К.Ю. Поляков, Е.А. Ерёмин, 2025
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
5 + 2
http://kpolyakov.spb.ru
182. Задача о куче
Алгоритмизация и программирование. Язык Python, 11 класс182
Задача о куче
? Какова сложность алгоритма?
Заполнение таблицы:
N
2
4
5
7
0
0
0
0
0
1
0
0
0
0
2
2
2
2
2
W+1
3
2
2
2
2
4
2
4
4
4
5
2
4
5
5
6
2
6
6
6
7
2
6
7
7
8
2
6
7
7
! Сложность O(N W) !
псевдополиномиальный
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
183. Алгоритмизация и программирование. Язык Python
183Алгоритмизация и
программирование.
Язык Python
Динамическое
программирование в
электронных таблицах
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
184. Числа Фибоначчи
Алгоритмизация и программирование. Язык Python, 11 класс184
Числа Фибоначчи
Задача. Вычислить 40-е число Фибоначчи F40.
1
2
3
4
5
6
A
n
B
Fn
1
2
3
4
5
1
1
=B2+B3
???
1
2
3
4
5
6
A
n
B
Fn
1
2
3
4
5
1
1
2
3
5
? В чём проблема при вычислении F ?
100
Excel-2016: до F73.
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
185. Количество путей
Алгоритмизация и программирование. Язык Python, 11 класс185
Количество путей
Задача 2. Исполнитель Кузнечик прыгает по клетчатой
ленте. Вначале Кузнечик стоит в клетке с номером 1.
За один раз он может прыгнуть вперёд на 1, 2 или 3
клетки. Найти количество возможных маршрутов
перехода Кузнечика из клетки 1 в клетку 10.
1
2
3
1
1
2
1
2
A
n
Kn
B
1
1
7
C
2
1
? Что в E2?
К.Ю. Поляков, Е.А. Ерёмин, 2025
D
3
2
E
4
4
F
5
7
G
6
13
8
H
7
24
9
I
8
44
10
J
K
9 10
81 149
=СУММ(B2:D2)
http://kpolyakov.spb.ru
186. Самая длинная цепочка
Алгоритмизация и программирование. Язык Python, 11 класс186
Самая длинная цепочка
Задача 3. Найти наибольшую длину непрерывной цепочки
положительных чисел.
1
2
3
A
15
27
13
4
5
6
–4
5
57
B
=ЕСЛИ(A1>0;1;0)
???
=ЕСЛИ(A2>0;B1+1;0)
???
1
2
3
4
5
6
A
15
27
13
–4
5
57
B
1
2
3
0
1
2
? Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
187. Наибольшая сумма
Алгоритмизация и программирование. Язык Python, 11 класс187
Наибольшая сумма
Задача 4. Найти наибольшую сумму непрерывной
цепочки чисел.
1
2
3
4
5
6
A
6
1
–8
5
–9
12
B
=???
A1
=MAX(A2;A2+B1)
???
1
2
3
4
5
6
A
6
1
–8
5
–9
12
B
6
7
–1
5
–4
12
? Где ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
188. Робот собирает монеты
Алгоритмизация и программирование. Язык Python, 11 класс188
Робот собирает монеты
Задача 5. Робот может двигаться только вправо и вниз.
Найти наибольшую сумму, которую может собрать
робот, перемещаясь из левого верхнего угла в правый
нижний.
=A1
=E1+B1
1
2
3
4
A B
63 78
10 1
25 29
C D
58
42
87
E
?
63
?
73
98
F
G
?
141
199
142
241
?
171 328
H
=E1+A2
=МАКС(F1;E2)+B2
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
189. Робот собирает монеты + стенки
Алгоритмизация и программирование. Язык Python, 11 класс189
Робот собирает монеты + стенки
Задача 5б. Робот может двигаться только вправо и вниз.
Найти наибольшую сумму, которую может собрать
робот, перемещаясь из левого верхнего угла в правый
нижний. Робот не может проходить через стенки.
1
2
3
4
A B C D
63 78 58
10 1 42
25 29 87
E
63
73
98
F
G
141 199
74
116
?
127 214
H
=E2+B2
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
190. Копирование формул
Алгоритмизация и программирование. Язык Python, 11 класс190
Копирование формул
Задача: скопировать формулу в другие ячейки, не
повредив оформление (заливку, рамки и т.п.).
1
2
3
4
A B C D
63 78 58
10 1 42
25 29 87
E
F
G
63
141 199
73 =E2+B2
98
H
? Почему нельзя
1) Выделить ячейку F2.
2) Ctrl+C или
.
3) Выделить нужные ячейки
(несколько диапазонов – при
нажатой клавише Ctrl).
4)
К.Ю. Поляков, Е.А. Ерёмин, 2025
просто «растянуть»?
http://kpolyakov.spb.ru
191. Конец фильма
Алгоритмизация и программирование. Язык Python, 11 класс191
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 174, г. Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
eremin@pspu.ac.ru
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru
192. Источники иллюстраций
Алгоритмизация и программирование. Язык Python, 11 класс192
Источники иллюстраций
1. wallpaperscraft.com
2. www.mujerhoy.com
3. www.pinterest.com
4. www.wayfair.com
5. www.zchocolat.com
6. www.russiantable.com
7. www.kursachworks.ru
8. ebay.com
9. centrgk.ru
10. www.riverstonellc.com
11. 53news.ru
12. 10hobby.ru
13. ru.wikipedia.org
14. isquared.digital
15. иллюстрации художников издательства «Бином»
16. авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2025
http://kpolyakov.spb.ru