Программирование (Python). Как разрабатывают программы?

1. Программирование (Python)

1
Программирование
(Python)
§ 23. Как разрабатывают программы?
§ 24. Процедуры
§ 25. Функции
§ 19. Символьные строки
§ 20. Обработка массивов
§ 21. Матрицы (двумерные массивы)
§ 22. Сложность алгоритмов
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

2. Программирование (Python)

2
Программирование
(Python)
§ 19. Символьные строки
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

3. Что такое символьная строка?

Программирование (Python), 9 класс
3
Что такое символьная строка?
Символьная строка – это последовательность
символов.
• строка – единый объект
• длина строки может меняться во время работы
программы
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
4
Символьные строки
Присваивание:
s = "Вася пошёл гулять"
Ввод с клавиатуры:
s = input()
Вывод на экран:
print(s)
Длина строки:
n = len(s)
length – длина
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
5
Сравнение строк
?
print("Введите пароль: ")
Какой правильный
s = input()
пароль?
if s == "sEzAm":
print("Слушаюсь и повинуюсь!")
else:
print("Пароль неправильный")
? Как одна строка может быть меньше другой?
стоит раньше в отсортированном списке
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
6
Сравнение строк
s1 = "паровоз"
s2 = "пароход"
if s1 < s2:
print(s1, "<", s2)
elif s1 == s2:
print(s1, "=", s2)
else:
print(s1, ">", s2)
? Что выведет?
паровоз < пароход
первые отличающиеся
буквы
Сравниваем с начала: паровоз
пароход
! в < х!
«в»: код 1074
«х»: код 1093
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

7. Обращение к символу по номеру

Программирование (Python), 9 класс
7
Обращение к символу по номеру
print ( s[5] )
print ( s[-2] )
0
1
2
3
4
5
6
П
р
и
в
е
т
!
s[len(s)-2]
s[0] s[1] s[2] s[3] s[4] s[5] s[6]
! Символы нумеруются с нуля!
составить «кот»
s = "информатика"
kot = s[-2]+s[3]+s[-4]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

8. Посимвольная обработка строк

Программирование (Python), 9 класс
8
Посимвольная обработка строк
! Строка неизменна!
s[4] = "a"
Задача. Ввести строку и заменить в ней все буквы «э» на
буквы «е».
строим новую
строку!
sNew = ""
for i in range(len(s)
) :
range(len(s))
if s[i] == "э":
sNew += "е"
для каждого
символа строки
else:
sNew += s[i]
0
1
2
3
4
5
6
П
р
и
в
э
т
!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
len(s)-1
http://kpolyakov.spb.ru

9. Цикл перебора символов

Программирование (Python), 9 класс
9
Цикл перебора символов
sNew = ""
for c in s:
if c == "э":
sNew += "е"
else:
sNew += c
перебрать
все символы
строки
c
П
р
и
в
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
э
т
!
http://kpolyakov.spb.ru

10. Задачи

Программирование (Python), 9 класс
10
Задачи
«A»: Напишите программу, которая вводит строку,
состоящую только из точек и букв Х, и заменяет в
ней все точки на нули и все буквы X на единицы.
Пример:
Введите строку: ..X.XX.
Двоичный код: 0010110
«B»: Напишите программу, которая в символьной строке
заменяет все нули на единицы и наоборот.
Остальные символы не должны измениться.
Пример:
Введите строку: 10а01Bx1010c
Инверсия: 01a10Bx0101c
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

11. Задачи

Программирование (Python), 9 класс
11
Задачи
«С»: Введите битовую строку и дополните её последним
битом, который должен быть равен 0, если в
исходной строке чётное число единиц, и равен 1,
если нечётное (в получившейся строке должно
всегда быть чётное число единиц).
Пример:
Введите битовую строку: 01101010110
Результат: 011010101100
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
12
Операции со строками
Объединение (конкатенация) :
s1 = "Привет"
"Привет, Вася!"
s2 = "Вася"
s = s1 + ", " + s2 + "!"
Умножение:
s = "АУ"
s5 = s*5
s5 = s + s + s + s + s
АУАУАУАУАУ
? Что получим?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

13. Срезы строк (выделение части строки)

Программирование (Python), 9 класс
13
Срезы строк (выделение части строки)
s = "0123456789"
s1 = s[3:8]
# "34567"
с какого
символа
до какого
(не включая 8)
s = "0123456789"
s1 = s[:8]
# "01234567"
от начала строки
s = "0123456789"
s1 = s[3:]
# "3456789"
до конца строки
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

14. Срезы строк

Программирование (Python), 9 класс
14
Срезы строк
Срезы с отрицательными индексами:
s = "0123456789"
s1 = s[:-2]
# "01234567"
len(s)-2
s = "0123456789"
s1 = s[-6:-2]
len(s)-6
# "4567"
len(s)-2
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
15
Операции со строками
Удаление:
s = "0123456789"
s1 = s[:3] + s[9:]
"012"
"9"
"0129"
Вставка:
s = "0123456789"
s1 = s[:3] + "ABC" + s[3:]
"012"
"3456789"
"012ABC3456789"
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

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

17. Задачи

Программирование (Python), 9 класс
17
Задачи
«A»: Ввести с клавиатуры в одну строку фамилию и имя,
разделив их пробелом. Вывести первую букву имени с
точкой и потом фамилию.
Пример:
Введите фамилию и имя:
Иванов Петр
П. Иванов
«B»: Ввести с клавиатуры в одну строку фамилию, имя и
отчество, разделив их пробелом. Вывести фамилию и
инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

18. Задачи

Программирование (Python), 9 класс
18
Задачи
«C»: Ввести адрес файла и «разобрать» его на части,
разделенные знаком "/". Каждую часть вывести в
отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2015/Байкал/shaman.jpg
C:
Фото
2015
Байкал
shaman.jpg
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
19
Преобразования «строка» «число»
Из строки в число:
s = "123"
N = int ( s )
s = "123.456"
X = float ( s )
# N = 123
# X = 123.456
Из числа в строку:
N = 123
s = str ( N ) # s = "123"
s = f"{N:5}" # s = " 123"
X = 123.456
s = str (X )
# s = "123.456"
s = f"{X:7.2f}" # s = " 123.46"
s = f"{X:10.2e}" # s = " 1.23e+02"
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

20. Задачи

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

21. Задачи

Программирование (Python), 9 класс
21
Задачи
«C»: Напишите программу, которая вычисляет сумму
произвольного количества чисел, введенную в форме
символьной строки. Все числа целые.
Пример:
Введите выражение:
12+3+45+10
Ответ: 70
«D»: Напишите программу, которая вычисляет выражение,
содержащее целые числа и знаки сложения и вычитания.
Пример:
Введите выражение:
12+134–45–17
Ответ: 84
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

22. Программирование (Python)

22
Программирование
(Python)
§ 23. Как разрабатывают
программы
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

23. Этапы разработки программ

Программирование (Python), 9 класс
23
Этапы разработки программ
I. Постановка задачи
Документ: техническое задание.
II. Построение модели
исходные данные
модель
результаты
Формализация: запись модели в виде формул (на
формальном языке).
III. Разработка алгоритма и способа
хранения данных
«Алгоритмы + структуры данных = программы»
(Н. Вирт)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

24. Этапы разработки программ

Программирование (Python), 9 класс
24
Этапы разработки программ
IV. Кодирование
Запись алгоритма на языке программирования.
алгоритм
кодирование
программный
код
V. Отладка
Поиск и исправление ошибок в программах:
• синтаксические – нарушение правил языка
программирования
• логические – ошибки в алгоритме
могут приводить к отказам – аварийным ситуациям
во время выполнения (run-time error)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

25. Этапы разработки программ

Программирование (Python), 9 класс
25
Этапы разработки программ
VI. Тестирование
Тщательная проверка программы во всех режимах:
• альфа-тестирование – внутри компании
(тестировщики)
• бета-тестирование – (доверенные) пользователи
VII. Документирование
Технические писатели
VIII. Внедрение и сопровождение
• обучение пользователей
• исправление найденных ошибок
• техподдержка
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

26. Методы проектирования программ

Программирование (Python), 9 класс
26
Методы проектирования программ
«Сверху вниз» (последовательное уточнение)
Задача
Подзадача 1
1.1
1.2
Подзадача 2
2.1
2.2
Подзадача 3
2.3
3.1
3.2
30-40 строк каждая
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

27. Методы проектирования программ

Программирование (Python), 9 класс
27
Методы проектирования программ
«Сверху вниз» (последовательное уточнение)
сначала задача решается «в целом»
легко распределить работу
легче отлаживать программу (всегда есть
полный работающий вариант)
в нескольких подзадачах может потребоваться
решение одинаковых подзадач нижнего уровня
быстродействие не известно до последнего
этапа (определяется нижним уровнем)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

28. Методы проектирования программ

Программирование (Python), 9 класс
28
Методы проектирования программ
«Снизу вверх» (восходящее)
Задача
Подзадача 1
1.1
1.2
Подзадача 2
2.1
2.2
Подзадача 3
2.3
3.1
3.2
библиотека функций
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

29. Методы проектирования программ

Программирование (Python), 9 класс
29
Методы проектирования программ
«Снизу вверх» (восходящее)
нет дублирования
сразу видно быстродействие
сложно распределять работу
сложнее отлаживать (увеличение числа связей)
плохо видна задача «в целом», может быть
нестыковка на последнем этапе
!
Почти всегда используют оба подхода!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

30. Отладка программы

Программирование (Python), 9 класс
30
Отладка программы
Программа решения квадратного уравнения
ax 2 bx c 0
from math import sqrt
print("Введите a, b, c: ")
a = float(input())
float – преобразовать в
b = float(input())
вещественное число
c = float(input())
D = b*b - 4*a*a
x1 = (-b+sqrt(D))/2*a
x2 = (-b-sqrt(D))/2*a
print("x1=", x1, " x2=", x2, sep="")
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

31. Тестирование

Программирование (Python), 9 класс
31
Тестирование
Тест 1. a = 1, b = 2, c = 1.
Ожидание:
x1=-1.0 x2=-1.0
Реальность:
x1=-1.0 x2=-1.0
Тест 2. a = 1, b = – 5, c = 6.
x1=3.0 x2=2.0
x1=4.791 x2=0.209
Найден вариант, когда программа работает неверно.
Ошибка воспроизводится!
Возможные причины:
• неверный ввод данных
• неверное вычисление дискриминанта
• неверное вычисление корней
• неверный вывод результатов
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
D b 2 4ac
b D
x1, 2
2a
http://kpolyakov.spb.ru

32. Отладочная печать

Программирование (Python), 9 класс
32
Отладочная печать
Идея: выводить все промежуточные результаты.
a = float(input())
b = float(input())
c = float(input())
print(a, b, c)
D = b*b - 4*a*a
print("D=", D)
...
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

33. Отладочная печать

Программирование (Python), 9 класс
33
Отладочная печать
Идея: выводить все промежуточные результаты.
Результат:
Введите a, b, c:
1
-5
6
1.0 -5.0 6.0
D= 21.0
D b 2 4ac 25 4 1 6 1
D = b*b - 4*a* с ;
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
! Одна ошибка найдена!
http://kpolyakov.spb.ru

34. Отладка программы

Программирование (Python), 9 класс
34
Отладка программы
Тест 1. a = 1, b = 2, c = 1.
Ожидание:
x1=-1.0 x2=-1.0
Реальность:
x1=-1.0 x2=-1.0
Тест 2. a = 1, b = – 5, c = 6.
x1=3.0 x2=2.0
x1=3.0 x2=2.0
? Программа работает верно?
Тест 3. a = 8, b = – 6, c = 1.
x1=0.5 x2=0.25
x1=32.0 x2=16.0
x1 = (-b+sqrt(D))/2*a
(2*a)
x2 = (-b-sqrt(D))/2*a
(2*a)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что неверно?
http://kpolyakov.spb.ru

35. Документирование программы

Программирование (Python), 9 класс
35
Документирование программы
• назначение программы
• формат входных данных
• формат выходных данных
• примеры использования программы
Назначение:
программа для решения уравнения
ax bx c 0
2
Формат входных данных:
значения коэффициентов a, b и c вводятся с
клавиатуры через пробел в одной строке
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

36. Документирование программы

Программирование (Python), 9 класс
36
Документирование программы
Формат выходных данных:
значения вещественных корней уравнения;
если вещественных корней нет, выводится
слово «нет»
Примеры использования программы:
2
1. Решение уравнения x 5 x 6 0
Введите a, b, c: 1 -5 6
x1=3 x2=2
2
2. Решение уравнения x x 6 0
Введите a, b, c: 1 1 6
Нет.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

37. Программирование (Python)

37
Программирование
(Python)
§ 24. Процедуры
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

38. Два типа подпрограмм

Программирование (Python), 9 класс
38
Два типа подпрограмм
Подпрограммы
Процедуры
выполняют действия
? Процедура или функция?
Функции
+ возвращают некоторый
результат
а) рисует окружность на экране
б) определяет площадь круга
в) вычисляет значение синуса угла
г) изменяет режим работы программы
д) возводит число x в степень y
е) включает двигатель автомобиля
ж) проверяет оставшееся количество бензина в баке
з) измеряет высоту полёта самолёта
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

39. Простая процедура

Программирование (Python), 9 класс
39
Простая процедура
define – определить
def printLine():
print("----------")
? Что делает?
...
вызов
printLine()
процедуры
...
какие-то
операторы
можно вызывать сколько угодно раз
нет дублирования кода
изменять – в одном месте
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

40. Линии разной длины

Программирование (Python), 9 класс
40
Линии разной длины
def printLine5():
print("-----")
? Как улучшить?
def printLine10():
print("----------")
def printLine10():
print("-"*10)
параметр
процедуры
def printLine( n ):
print("-"*n)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

41. Процедура с параметром

Программирование (Python), 9 класс
41
Процедура с параметром
Параметр – величина, от
которой зависит
работа процедуры.
def printLine( n ):
...
...
printLine(10)
...
printLine(7)
printLine(5)
printLine(3)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что делает?
Аргумент – значение
параметра при
конкретном вызове.
http://kpolyakov.spb.ru

42. Несколько параметров

Программирование (Python), 9 класс
42
Несколько параметров
символьная строка
def printLine(c, n):
print(c*n)
? Что изменилось?
? Как вызывать?
printLine( "+", 5 )
printLine( "+-+", 5 )
printLine( 5, "+" )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

43. В других языках программирования

Программирование (Python), 9 класс
43
В других языках программирования
Паскаль:
procedure printLine(c: string; n: integer);
var i: integer;
begin
for i:=1 to n do
write(c);
writeln
end;
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

44. В других языках программирования

Программирование (Python), 9 класс
44
В других языках программирования
С:
void printLine(int n)
{
int i;
for (i=1; i<=n; i++)
putchar("-");
putchar("\n");
}
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

45. Как не нужно писать процедуры

Программирование (Python), 9 класс
45
Как не нужно писать процедуры
def summa():
print(x + y)
? Что плохо?
x = 10
y = 5
summa()
def summa( x, y ):
print(x + y)
x = 10
y = 5
только x + y
summa( x, y )
не перенести в
другую программу summa( 2*x+y, 7 )
! Процедура принимает данные только
через параметры!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

46. Задачи

Программирование (Python), 9 класс
46
Задачи
«A»: Напишите процедуру, которая принимает параметр –
натуральное число N – и выводит на экран две линии из
N символов "–".
Пример:
Длина цепочки: 7
------------«B»: Напишите процедуру, которая принимает один
параметр – натуральное число N, – и выводит на
экран прямоугольник длиной N и высотой 3
символа.
Пример:
Длина прямоугольника: 7
ooooooo
o
o
ooooooo
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

47. Задачи

Программирование (Python), 9 класс
47
Задачи
«C»: Напишите процедуру, которая выводит на экран
квадрат со стороной N символов. При запуске
программы N нужно ввести с клавиатуры.
Пример:
Сторона квадрата: 5
ooooo
o
o
o
o
o
o
ooooo
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

48. Задачи

Программирование (Python), 9 класс
48
Задачи
«D»: Напишите процедуру, которая выводит на экран
треугольник со стороной N символов. При запуске
программы N нужно ввести с клавиатуры.
Пример:
Сторона: 5
o
oo
ooo
oooo
ooooo
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

49. Рекурсия

Программирование (Python), 9 класс
49
Рекурсия
Задача. Вывести на экран двоичный код натурального
числа.
def printBin( n ):
...
Алгоритм перевода через остатки:
while n!=0:
print(n % 2, end="")
n = n // 2
011
? Что получится
при n = 6?
в обратном порядке!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

50. Рекурсия

Программирование (Python), 9 класс
50
Рекурсия
Чтобы вывести двоичную запись числа n, нужно сначала
вывести двоичную запись числа (n // 2), а затем — его последнюю двоичную цифру, равную
(n % 2).
двоичная запись числа 6
110
6 % 2
двоичная запись числа 3
! Чтобы решить задачу,
нужно решить ту же
задачу
для меньшего числа!
Это и есть рекурсия!
! Чтобы понять рекурсию, нужно понять рекурсию!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

51. Рекурсивная процедура

Программирование (Python), 9 класс
51
Рекурсивная процедура
def printBin( n ):
printBin(n // 2)
print(n % 2, end = "")
вызывает сама себя!
Рекурсивная процедура — это процедура, которая
вызывает сама себя.
printBin(6)
printBin(3)
? Что получится? printBin(6)
printBin(1)
printBin(0)
printBin(0)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
бесконечные вызовы
? Как исправить?
http://kpolyakov.spb.ru

52. Рекурсивная процедура

Программирование (Python), 9 класс
52
Рекурсивная процедура
def printBin( n ):
if n > 1:
printBin(n // 2)
print(n % 2, end="")
получится?
? Что
printBin(6)
printBin(6)
printBin(3)
printBin(1)
рекурсия
заканчивается!
110
print(1 % 2)
print(3 % 2)
print(6 % 2)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

53. Процедура с основной программой

Программирование (Python), 9 класс
53
Процедура с основной программой
def printBin( n ):
if n >= 1:
printBin(n // 2)
print(n % 2, end="")
x = int(input("Введите число"))
printBin( x )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

54. Задачи

Программирование (Python), 9 класс
54
Задачи
«A»: Напишите рекурсивную процедуру, которая
переводит число в восьмеричную систему.
Пример:
Введите число: 66
В восьмеричной: 102
«B»: Напишите рекурсивную процедуру, которая
переводит число в любую систему счисления с
основанием от 2 до 9.
Пример:
Введите число: 75
Основание: 6
В системе с основанием 6: 203
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

55. Задачи

Программирование (Python), 9 класс
55
Задачи
«С»: Напишите рекурсивную процедуру, которая
переводит число в шестнадцатеричную систему.
Пример:
Введите число: 123
В шестнадцатеричной: 7B
«D»: Напишите рекурсивную процедуру, которая
переводит число в любую систему счисления с
основанием от 2 до 36.
Пример:
Введите число: 350
Основание: 20
В системе с основанием 20: HA
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

56. Программирование (Python)

56
Программирование
(Python)
§ 25. Функции
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

57. Что такое функция?

Программирование (Python), 9 класс
57
Что такое функция?
Функция — это вспомогательный алгоритм, который
возвращает результат (число, строку символов и др.).
Задача. Написать функцию, которая вычисляет среднее
арифметическое двух целых чисел.
цел a, b
исходные данные
целые
def Avg(a, b):
return (a+b)/2
Avg
вещ r
результат
? Тип результата?
результат
функции
return – вернуть
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

58. Как вызывать функцию?

Программирование (Python), 9 класс
58
Как вызывать функцию?
Запись результата в переменную:
sr = Avg(5, 8)
6.5
x = 2; y = 5
sr = Avg(x, 2*y+8)
Вывод на экран:
x = 2; y = 5
sr = Avg(x, y+3)
print( Avg(12,7) )
print( sr + Avg(x,12) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Чему равно?
10
5
9.5
12
http://kpolyakov.spb.ru

59. Как вызывать функцию?

Программирование (Python), 9 класс
59
Как вызывать функцию?
Использование в условных операторах:
a = int(input())
b = int(input())
if Avg(a,b) > 5:
print("Да!")
Когда печатает «Да»?
else:
print("Нет!");
?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

60. Как вызывать функцию?

Программирование (Python), 9 класс
60
Как вызывать функцию?
Использование в циклах:
a = int(input())
b = int(input())
ввод двух чисел в
while Avg(a,b) > 0:
одной строчке
print("Нет!")
a,b = map(int, input().split())
print("Угадал!");
? Когда напечатает «Угадал»?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

61. В других языках программирования

Программирование (Python), 9 класс
61
В других языках программирования
Паскаль:
function Avg(a, b: integer): real;
begin
Avg:=(a+b)/2
Avg
end.
специальная переменная для
записи результата функции
С:
float Avg(int a, int b)
{
return (a+b)/2.0;
}
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

62. Максимум из двух (трёх) чисел

Программирование (Python), 9 класс
62
Максимум из двух (трёх) чисел
Задача. Составить функцию, которая определяет
наибольшее из двух целых чисел.
цел a, b
исходные данные
цел r
результат
Max
?
def Max(a, b):
Как с её помощью найти
if a > b:
максимум из трёх?
return a
else:
return b
def Max3(a, b, c):
return Max( Max(a,b), c )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

63. Сумма цифр числа

Программирование (Python), 9 класс
63
Сумма цифр числа
Задача. Составить функцию, которая вычисляет сумму
значений цифр натурального числа.
def sumDigits( N ):
sum = 0
# накапливаем сумму с 0
while N!=0:
d = N % 10
# выделим последнюю цифру
sum += d
# добавим к сумме
N = N // 10 # удалим последнюю цифру
return sum
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

64. Задачи

Программирование (Python), 9 класс
64
Задачи
«A»: Напишите функцию, которая вычисляет среднее
арифметическое пяти целых чисел.
Пример:
Введите 5 чисел: 1 2 3 4 6
Среднее: 3.2
«B»: Напишите функцию, которая находит количество
цифр в десятичной записи числа.
Пример:
Введите число: 751
Количество цифр: 3
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

65. Задачи

Программирование (Python), 9 класс
65
Задачи
«С»: Напишите функцию, которая находит количество
единиц в двоичной записи числа.
Пример:
Введите число: 75
Количество единиц: 4
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

66. Логические функции

Программирование (Python), 9 класс
66
Логические функции
Логическая функция — это функция, возвращающая
логическое значения (да или нет).
• можно ли применять операцию?
• успешно ли выполнена операция?
• обладают ли данные каким-то свойством?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

67. Логические функции

Программирование (Python), 9 класс
67
Логические функции
Задача. Составить функцию, которая возвращает
«True», если она получила чётное число и «False»,
если нечётное.
def Even( N ):
if N % 2 == 0:
def Even( N ):
return True
return (N % 2 == 0)
else:
return False
a = int(input("Введите число"))
if Even( a ):
print("Число чётное")
else:
print("Число нечётное")
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

68. Рекурсивные функции

Программирование (Python), 9 класс
68
Рекурсивные функции
Рекурсивная функция — это функция, которая
вызывает сама себя.
Задача. Составить рекурсивную функцию, которая
вычисляет сумму цифр числа.
? Как сформулировать решение рекурсивно?
Сумму цифр числа N нужно выразить через сумму
цифр другого (меньшего) числа.
Сумма цифр числа N равна значению последней цифры
плюс сумма цифр числа, полученного отбрасыванием
последней цифры.
sumDig(12345) = 5 + sumDig(1234)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

69. Рекурсивная функция

Программирование (Python), 9 класс
69
Рекурсивная функция
Сумма цифр числа N
последняя цифра
Вход: натуральное число N.
Шаг 1: d = N % 10
число без
Шаг 2: M = N // 10
последней цифры
Шаг 3: s = сумма цифр числа M
Шаг 4: sum = s + d
Результат: sum.
? Что забыли?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Когда остановить?
http://kpolyakov.spb.ru

70. Сумма цифр числа (рекурсия)

Программирование (Python), 9 класс
70
Сумма цифр числа (рекурсия)
def sumDigRec( N ):
if N == 0: return 0
else:
d = N % 10
sum = sumDigRec(N // 10)
return sum + d
? Зачем это?
? Где рекурсивный вызов?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

71. Задачи

Программирование (Python), 9 класс
71
Задачи
«A»: Напишите логическую функцию last01, которая
возвращает значение «истина», если десятичная
запись числа заканчивается на цифру 0 или 1.
Пример:
Введите число: 1230
Ответ: Да
«B»: Напишите логическую функцию inByte, которая
возвращает значение «истина», если переданное ей
число помещается в 8-битную ячейку памяти.
Пример:
Введите число: 751
Ответ: Нет
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

72. Задачи

Программирование (Python), 9 класс
72
Задачи
«C»: Напишите логическую функцию isPrime, которая
возвращает значение «истина», если переданное ей
число простое (делится только на само себя и на
единицу).
Пример:
Введите число: 17
Число простое!
Пример:
Введите число: 18
Число составное!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

73. Программирование (Python)

73
Программирование
(Python)
§ 20. Обработка массивов.
Поток данных
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

74. Обработка потока данных

Программирование (Python), 9 класс
74
Обработка потока данных
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Определить, сколько было введено
положительных чисел.
1) нужен счётчик
2) счётчик увеличивается еслиКогда
числоувеличивать
>0
счётчик?
3) нужен цикл
4) это цикл с условием (число шагов неизвестно)
Какой цикл?
?
?
счётчик = 0
пока не введён 0:
если введено число > 0 то
счётчик:= счётчик + 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

75. Обработка потока данных

Программирование (Python), 9 класс
75
Обработка потока данных
count = 0
x = int(input())
while x != 0:
if x > 0:
count += 1
x = int(input())
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
откуда взять x?
? Что плохо?
http://kpolyakov.spb.ru

76. Найди ошибку!

Программирование (Python), 9 класс
76
Найди ошибку!
count = 0
x = int(input())
while x != 0:
if x > 0:
count += 1
print(
count )
x = int(input())
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

77. Найди ошибку!

Программирование (Python), 9 класс
77
Найди ошибку!
xcount
= int(input())
count
== 00
while x == 0:
if x >!=
0:
count += 1
x = int(input())
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

78. Проблемы с отрицательными числами

Программирование (Python), 9 класс
78
Проблемы с отрицательными числами
Двузначные числа:
if 10 <= x and x <= 99: ...
? Что плохо?
abs – модуль числа
if 10 <= abs
abs(x) and abs
abs(x) <= 99: ...
Вычисление остатка:
if abs
x % 10 %
abs(x)
==10
3:==
...
3: ...
!
12 % 10 = 2
–12 % 10 = 8
–12 = (-2)*10 + 8
–12 % 10 = 8
-20
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
-12
-10
http://kpolyakov.spb.ru

79. Задачи

Программирование (Python), 9 класс
79
Задачи
«A»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сколько получено чисел, которые
делятся на 3.
«B»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сколько получено двузначных чисел,
которые заканчиваются на 3.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

80. Задачи

Программирование (Python), 9 класс
80
Задачи
«C»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти среднее арифметическое всех двузначных
чисел, которые делятся на 7.
«D»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти максимальное из введённых чётных чисел.
Если таких чисел нет, программа должна вывести
слово «нет».
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

81. Обработка потока данных: сумма

Программирование (Python), 9 класс
81
Обработка потока данных: сумма
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Найти сумму введённых чисел,
оканчивающихся на цифру "5".
1) нужна переменная для суммы
2) число добавляется к сумме, если оно
заканчивается на "5"
3) нужен цикл с условием
сумма = 0
? Как это записать?
пока не введён 0:
если число оканчивается на "5" то
сумма:= сумма + число
if x % 10 == 5:
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

82. Обработка потока данных: сумма

Программирование (Python), 9 класс
82
Обработка потока данных: сумма
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Найти сумму введённых чисел,
оканчивающихся на цифру "5".
Sum = 0
x = int(input())
while x != 0:
if x % 10 == 5:
Sum += x
x = int(input())
print( Sum )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Чего не хватает?
http://kpolyakov.spb.ru

83. Найди ошибку!

Программирование (Python), 9 класс
83
Найди ошибку!
Sum = 0
x
= int(input())
while
x != 0:
if x % 10 == 5:
Sum += x
x = int(input())
print( Sum )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

84. "Бесконечный" цикл

Программирование (Python), 9 класс
84
"Бесконечный" цикл
s=0
while True:
x = int(input())
if x == 0: break
break
if x % 10 == 5:
s += x
print( s )
выйти из
цикла
? Что плохо?
из цикла while True возможен только через
! Выход
оператор break!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

85. Условия отбора

Программирование (Python), 9 класс
85
Условия отбора
Положительные числа:
if x > 0: ...
Числа, делящиеся на 3:
if x % 3 == 0: ...
Числа, оканчивающиеся на 6:
if x % 10 == 6: ...
Числа, делящиеся на 3 и оканчивающиеся на 6:
if x % 3 == 0 and x % 10 == 6: ...
Как иначе?
?
if 10 <= x and x <= 99: ...
Двузначные числа:
if 9 < x and x < 100: ...
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

86. Если ни одного числа не нашли…

Программирование (Python), 9 класс
86
Если ни одного числа не нашли…
Задача: с клавиатуры вводятся числа, ввод
завершается числом 0. Найти сумму
введённых чисел, оканчивающихся на "5".
Вывести "нет", если таких чисел нет.
? Как определить, что таких чисел нет?
сумма = 0
Как вывести результат?
?
счётчик = 0
пока не введён 0:
если x оканчивается на "5":
сумма += x
счётчик += 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

87. Если ни одного числа не нашли…

Программирование (Python), 9 класс
87
Если ни одного числа не нашли…
сумма = 0
счётчик = 0
пока не введён 0:
если x оканчивается на "5":
сумма += x
счётчик += 1
if счётчик == 0:
print("Ответ: нет")
else:
print("Ответ:", s)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

88. Найди ошибку!

Программирование (Python), 9 класс
88
Найди ошибку!
k=0
s=0
x = int(input())
s += x
while x != 0:
if x % 10 == 5:
k += 1
x = int(input())
if k == 01:
print("Ответ: нет")
else:
print("Ответ:", sk)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

89. Задачи

Программирование (Python), 9 класс
89
Задачи
«A»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сумму чисел, которые делятся на 3.
Если таких чисел нет, программа должна вывести
слово «нет».
«B»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сумму двузначных чисел, которые
заканчиваются на 3. Если таких чисел нет,
программа должна вывести слово «нет».
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

90. Задачи

Программирование (Python), 9 класс
90
Задачи
«C»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти сумму цифр всех введённых чисел.
«D»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти число, у которого максимальная сумма цифр.
Если таких чисел несколько, нужно вывести
последнее их них.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

91. Поиск максимума (минимума)

Программирование (Python), 9 класс
91
Поиск максимума (минимума)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

92. Поиск максимума (минимума)

Программирование (Python), 9 класс
92
Поиск максимума (минимума)
1) нужна переменная для хранения максимума
2) как только прочитали первое число,
сохранили максимум («из одного»):
x = int(input())
M = x
3) читаем следующее значение:
x = int(input())
4) цикл: если новое число больше максимума,
заменяем M:
while x != 0:
if x > M: M = x
5) выводим результат M
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

93. Поиск максимума (минимума)

Программирование (Python), 9 класс
93
Поиск максимума (минимума)
x = int(input())
M = x
while x != 0:
if x > M: M = x
print(M)
x = int(input())
print(M)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что плохо?
http://kpolyakov.spb.ru

94. Поиск максимума (минимума) – II

Программирование (Python), 9 класс
94
Поиск максимума (минимума) – II
x = int(input())
M = x
while True:
x = int(input())
if x == 0: break
if x > M: M = x
print(M)
print(M)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что плохо?
http://kpolyakov.spb.ru

95. Максимум не из всех

Программирование (Python), 9 класс
95
Максимум не из всех
Задача: с клавиатуры вводятся числа в
диапазоне [-100;100], ввод завершается
числом 0. Найти наибольшее среди чётных
чисел. Вывести "нет", если таких чисел нет.
x = int(input())
Может быть, что
M = x
x нечётное!
while x != 0:
if x % 2 == ???
0 and x > M:
M = x
x = int(input())
Что плохо?
?
print(M)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

96. Минимум не из всех

Программирование (Python), 9 класс
96
Минимум не из всех
По условию: x [-100;100]
x = int(input())
Любое x больше
M = -1000
этого числа!
while x != 0:
if x % 2 == 0 and x > M:
M = x
Как определить, что
?
x = int(input())
ни одного числа не
if M == -1000:
нашли?
print("Нет таких чисел")
else:
print(M)
? Как искать минимум?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

97. Если диапазон неизвестен…

Программирование (Python), 9 класс
97
Если диапазон неизвестен…
x = int(input())
M = 1 # любое нечётное
while x != 0:
if x % 2 == 0:
if M % 2 == 1 or x > M:
M = x
новый
x = int(input()) максимум
if M == 1 :
print("Нет таких чисел")
else:
print(M)
? Когда не нашли?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

98. Задачи

Программирование (Python), 9 класс
98
Задачи
«A»: с клавиатуры вводятся числа, ввод завершается
числом 0. Определить минимальное и
максимальное из введённых чисел.
Пример:
5
13
34
15
0
Минимум: 5
Максимум: 34
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

99. Задачи

Программирование (Python), 9 класс
99
Задачи
«B»: с клавиатуры вводятся числа из отрезка [1;1000],
ввод завершается числом 0. Определить
минимальное и максимальное из тех введённых
чисел, которые делятся на 3. Вывести "нет", если
таких чисел нет.
Пример:
5
31
18
21
15
0
Минимум: 15
Максимум: 21
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
Пример:
5
34
17
41
11
0
Ответ: нет
http://kpolyakov.spb.ru

100. Задачи

Программирование (Python), 9 класс
100
Задачи
«C»: с клавиатуры вводятся натуральные числа, ввод
завершается числом 0. Определить минимальное и
максимальное из тех введённых двузначных
натуральных чисел, в записи которых есть цифра 6.
Вывести "нет", если таких чисел нет.
Пример:
Пример:
6
6
36
32
18
176
26
41
15
11
0
0
Минимум: 26
Ответ: нет
Максимум: 36
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

101. Задачи

Программирование (Python), 9 класс
101
Задачи
«D»: с клавиатуры вводятся числа, ввод завершается
числом 0. Определить минимальное из введённых
чисел Фибоначчи. Вывести "нет", если чисел
Фибоначчи в последовательности нет.
Числа Фибоначчи – это последовательность чисел, которая начинается
с двух единиц и каждое следующее число равно сумме двух
предыдущих: 1, 1, 2, 3, 5, 8, 13, …
Пример:
5
36
12
26
13
0
Ответ: 5
Пример:
6
32
176
41
11
0
Ответ: нет
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

102. Обработка потока данных (N чисел)

Программирование (Python), 9 класс
102
Обработка потока данных (N чисел)
Задача: с клавиатуры вводится число N, а
затем – N целых чисел. Определить, сколько
было введено положительных чисел.
? В чём отличие?
задано количество!
ввести N
в Python нет
такого!
счётчик = 0
сделай N раз:
Есть цикл for!
!
ввести число
если введено число > 0:
счётчик += 1
вывести счётчик
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

103. Обработка потока данных (N чисел)

Программирование (Python), 9 класс
103
Обработка потока данных (N чисел)
сделай N раз:
...
for i in range(N):
...
! range(N) = [0, 1, 2, …, N-2, N-1 ]
N раз
for i in range(4):
print(i)
0
1
2
3
? Что выведет?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
s = 0
for i in range(4):
s += i
print(s)
6
http://kpolyakov.spb.ru

104. Обработка потока данных (N чисел)

Программирование (Python), 9 класс
104
Обработка потока данных (N чисел)
N = int(input())
k = 0
for i in range(N):
x = int(input())
if x > 0: k += 1
print(k)
сделай N
раз!
Числа, делящиеся на 3:
if x % 3 == 0: k += 1
Числа, оканчивающиеся на 6:
if x % 10 == 6: k += 1
Числа, делящиеся на 3 и оканчивающиеся на 6:
if x % 3 == 0 and x % 10 == 6: k += 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

105. Задачи

Программирование (Python), 9 класс
105
Задачи
«A»: с клавиатуры вводится число N, а затем – N целых
чисел. Определить, сколько было введено
положительных и сколько отрицательных чисел
(нули не считать!).
Пример:
5
1
3
-34
15
0
Положительных: 3
Отрицательных: 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

106. Задачи

Программирование (Python), 9 класс
106
Задачи
«B»: с клавиатуры вводится число N, а затем – N целых
чисел. Определить сумму двузначных чисел (как
положительных, так и отрицательных). Если
двузначных чисел не было, вывести "нет".
Пример:
5
1
13
-34
5
31
Ответ: 10
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
Пример:
5
1
213
-134
5
3
Ответ: нет
http://kpolyakov.spb.ru

107. Задачи

Программирование (Python), 9 класс
107
Задачи
«C»: с клавиатуры вводится число N, а затем – N целых
чисел. Определить минимальное и максимальное
среди двузначных чисел, которые делятся на 3. Если
таких чисел не было, вывести "нет".
Пример:
Пример:
Пример:
5
5
5
18
1
1
33
-18
23
98
-6
132
513
-21
6
31
32
32
Минимум: 18
Минимум: -21
Ответ: нет
Максимум: 33
Максимум: -18
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

108. Задачи

Программирование (Python), 9 класс
108
Задачи
«D»: с клавиатуры вводится число N, а затем – N
натуральных чисел. Определить минимальное и
максимальное среди простых чисел (которые
делятся на сами не себя и на 1). Если таких чисел не
было, вывести "нет".
Пример:
Пример:
5
5
41
12
15
25
11
132
163
6
39
39
Минимум: 11
Ответ: нет
Максимум: 163
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

109. Программирование (Python)

109
Программирование
(Python)
Массивы (повторение)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

110. Обращение к элементу массива

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

111. Создание массива

Программирование (Python), 9 класс
111
Создание массива
11
22
35
41
53
A = [11, 22, 35, 41, 53]
A = [11, 22] + [35, 41] + [53]
A = [11]*5
A = [11] + [11] + [11] + [11] +[11]
11
11
11
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
11
11
http://kpolyakov.spb.ru

112. Обращение к элементу массива

Программирование (Python), 9 класс
112
Обращение к элементу массива
ИНДЕКС элемента массива: 2
A[2]
ЗНАЧЕНИЕ элемента массива
0
1
2
3
4
23
12
7
43
51
i = 1
A[2] = A[i] + 2*A[i-1] + A[2*i+1]
print( A[2]+A[4] )
? Что получится?
A[2] = A[1] + 2*A[0] + A[3]
print( A[2]+A[4] )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
101
152
http://kpolyakov.spb.ru

113. Что неверно?

Программирование (Python), 9 класс
113
Что неверно?
0
1
2
3
4
1
2
3
4
5
A = [1, 2, 3, 4, 5]
x = 1
? Что плохо?
print( A[x-8] )
A[x+4] = A[x-1] + A[2*x]
print( A[-7] )
A[5] = A[0] + A[2]
Выход за границы массива — это обращение к
элементу с индексом, который не существует в
массиве.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

114. Перебор элементов массива

Программирование (Python), 9 класс
114
Перебор элементов массива
Перебор элементов: просматриваем все элементы
массива и, если нужно, выполняем с каждым из них
некоторую операцию.
N = 10
A = [0]*N
# память уже выделена
0, 1, 2, 3, …, N-1
for i in range(N):
# здесь работаем с A[i]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

115. Заполнение массива

Программирование (Python), 9 класс
115
Заполнение массива
[0, 1, 2, 3, …, N-1]
for i in range(N):
A[i] = i
? Что произойдёт?
В развёрнутом виде
A[0] = 0
A[1] = 1
A[2] = 2
...
A[N-1] = N-1
0
1
2
...
N-1
В стиле Python:
A = [ i for i in range(N) ]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
116
Заполнение массива в обратном порядке
N
…
3
2
A[0] = N
A[1] = N-1
A[2] = N-2
...
A[N-1] = 1
1
X=N
for i in range(N):
A[i] = X
X=X-1
? Как меняется X?
X = N, N-1, …, 2, 1
начальное
значение
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
уменьшение
на 1
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
117
Заполнение массива в обратном порядке
N
…
3
2
A[i] = X
1
? Как связаны i и X?
+1
i
0
1
2
...
N-1
X
N
N-1
N-2
...
1
–1
for i in range(N):
A[i] = N – i
В стиле Python:
A = [ N-i
for i in range(N) ]
! Сумма i и X не меняется!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
i + X = N
X = N - i
http://kpolyakov.spb.ru

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

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

119. Вывод массива на экран (Python)

Программирование (Python), 9 класс
119
Вывод массива на экран (Python)
[1,2,3,4,5]
print ( *A )
print (1, 2, 3, 4, 5)
разбить список
на элементы
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
1 2 3 4 5
http://kpolyakov.spb.ru

120. Задачи

Программирование (Python), 9 класс
120
Задачи
«A»: 1) Заполните все элементы массива из 10
элементов значением X , введённым с клавиатуры.
2) Заполните массив из 10 элементов
последовательными натуральными числами,
начиная с X (значение X введите с клавиатуры).
«B»: 1) Заполните массив из 10 элементов натуральными
числами в порядке убывания. С клавиатуры
вводится значение X. Последний элемент должен
быть равен X, предпоследний равен X+1 и т.д.
2) Заполните массив из 10 элементов степенями числа
2 (от 21 до 2N), так чтобы первый элемент был равен
2, следующий – 4, следующий – 8 и т.д.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

121. Задачи

Программирование (Python), 9 класс
121
Задачи
«C»: а) Заполните массив из 10 элементов степенями
числа 2, начиная с конца, так чтобы последний
элемент массива был равен 1, а каждый
предыдущий был в 2 раза больше следующего.
б) С клавиатуры вводится целое число X. Заполните
массив из 11 элементов целыми числами, так чтобы
средний элемент массива был равен X, слева от
него элементы стояли по возрастанию, а справа – по
убыванию. Соседние элементы отличаются на
единицу. Например,
при X = 3 массив из 5 элементов заполняется так: 1
2 3 2 1.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
122
Заполнение случайными числами
из библиотеки
(модуля) random
взять функцию randint
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 i in range(N) ]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

123. Обработка элементов массива

Программирование (Python), 9 класс
123
Обработка элементов массива
N = 10
A = [0]*N
# память уже выделена
for i in range(N):
# здесь работаем с A[i]
Вывести на экран в столбик:
for i in range(N):
print( A[i] )
???
! Что вместо «???»?
Вывести на экран в строчку:
for i in range(N):
print( A[i], end = " " )
???
print( *A )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

124. Обработка элементов массива

Программирование (Python), 9 класс
124
Обработка элементов массива
Вывести числа, на 1 большие, чем A[i]:
for i in range(N):
print( A[i]+1 )
???
! Что вместо «???»?
Вывести последние цифры:
for i in range(N):
print( A[i]%10 )
???
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

125. Обработка элементов массива

Программирование (Python), 9 класс
125
Обработка элементов массива
Заполнить нулями:
for i in range(N):
A[i] = 0
???
! Что вместо «???»?
Увеличить на 1:
for i in range(N):
A[i] += 1
???
Умножить на 2:
for i in range(N):
A[i] *= 2
???
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

126. Задачи-2

Программирование (Python), 9 класс
126
Задачи-2
«A»: Напишите программу, которая заполняет массив из
10 элементов случайными числами в диапазоне
[0,10], выводит его на экран, а затем выводит на
экран квадраты всех элементов массива.
Пример:
Массив: 5 6 2 3 1 4 8 7
Квадраты: 25 36 4 9 1 16 64 49
«B»: Напишите программу, которая заполняет массив из
10 элементов случайными числами в диапазоне
[100,300] и выводит его на экран. После этого на экран
выводятся средние цифры (число десятков) всех
чисел, записанных в массив.
Пример:
Массив: 142 324 135 257 167 295 126 223 138 270
Число десятков: 4 2 3 5 6 9 2 2 3 7
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

127. Задачи-2

Программирование (Python), 9 класс
127
Задачи-2
«C»: Напишите программу, которая заполняет массив из
10 элементов случайными числами в диапазоне
[100,500] и выводит его на экран. После этого на экран
выводятся суммы цифр всех чисел, записанных в
массив.
Пример:
Массив: 162 425 340 128 278 195 326 414 312 177
Суммы цифр: 9 11 7 11 17 15 11 9 6 15
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
128
Сумма элементов массива
Задача. Найти сумму элементов массива из N
элементов.
? Какие переменные
нужны?
5
2
8
3
i
Sum = 0
for i in range(N):
Sum =
+ A[i]
+=Sum
A[i]
print( Sum )
Sum
0
0
1
2
5
7
15
В стиле Python:
3
4
18
19
1
print( sum(A) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

129. Сумма элементов массива (Python)

Программирование (Python), 9 класс
129
Сумма элементов массива (Python)
Задача. Найти сумму элементов массива A.
Sum = 0
for x in A:
Sum += x
print( Sum )
для всех
элементов из A
! Не нужно знать размер!
или так:
print( sum(A) )
встроенная
функция
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
130
Сумма не всех элементов массива
Задача. Найти сумму чётных элементов массива.
? Что делаем с нечётными?
Sum = 0
for i in range(N):
Sum
+= A[i]
if A[i]
% 2 == 0:
print(
)
SumSum
+= A[i]
print( Sum )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
131
Сумма не всех элементов массива
Задача. Найти сумму чётных элементов массива.
Sum = 0
for x in A:
if
% 2
Sumx+=
x == 0:
SumSum
+= x
print(
)
print( Sum )
A
4
x
1
8
6
3
4
Sum
18
10
4
0
3
6
8
отбираем
в новый
1
массив все нужные
значения
В стиле Python:
B = [x for x in A
if x % 2 == 0]
print ( sum(B) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

132. Задачи

Программирование (Python), 9 класс
132
Задачи
«A»: Напишите программу, которая заполняет массив из
10 элементов случайными числами на отрезке [–5; 5]
и находит сумму положительных элементов.
«B»: Напишите программу, которая заполняет массив из
10 элементов случайными числами на отрезке [–2; 2]
и находит произведение ненулевых элементов.
«C»: Напишите программу, которая заполняет массив из
10 элементов случайными числами на отрезке
[100; 1000] и находит отдельно сумму элементов в
первой и во второй половинах массива.
Решение должно работать при любом размере
массива, который хранится в переменной N.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

133. Подсчёт элементов по условию

Программирование (Python), 9 класс
133
Подсчёт элементов по условию
Задача. Найти количество чётных элементов массива.
? Какие переменные нужны?
count = 0
for i in range(N):
if A[i] % 2 == 0:
count += 1
print( count )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
переменнаясчётчик
? Что тут делаем?
http://kpolyakov.spb.ru

134. Подсчёт элементов по условию (Python)

Программирование (Python), 9 класс
134
Подсчёт элементов по условию (Python)
Задача. Найти количество чётных элементов массива.
count = 0
for x in A:
if x % 2 == 0:
count += 1
print( count )
В стиле Python:
B = [x for x in A
if x % 2 == 0]
print ( len(B) )
размер массива
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
135
Среднее арифметическое
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
Sum = 0
for x in A:
if x > 180:
Sum += x
print( Sum/N )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что плохо?
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
136
Среднее арифметическое
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
? Какие переменные нужны?
Sum = 0
count = 0
for x in A:
if x > 180:
count += 1
Что тут делаем?
?
Sum += x
print( Sum/count )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

137. Среднее арифметическое (Python)

Программирование (Python), 9 класс
137
Среднее арифметическое (Python)
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
B = [ x for x in A
if x > 180]
print ( sum(B)/len(B) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
отбираем нужные
http://kpolyakov.spb.ru

138. Задачи

Программирование (Python), 9 класс
138
Задачи
«A»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [0;
200] и считает число элементов, которые делятся на
10.
«B»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [0; 200]
и считает число двузначных чисел в массиве.
«C»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [10;
100] и считает число пар соседних элементов, сумма
которых делится на 3.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

139. Перестановка элементов массива

Программирование (Python), 9 класс
139
Перестановка элементов массива
? Как поменять местами значения двух
переменных a и b?
вспомогательная
переменная
элементы массива:
с = a
a = b
b = c
с = A[i]
A[i] = A[k]
A[k] = c
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

140. Перестановка пар соседних элементов

Программирование (Python), 9 класс
140
Перестановка пар соседних элементов
Задача. Массив A содержит чётное количество
элементов N. Нужно поменять местами пары соседних
элементов: 0-й с 1-м, 2-й — с 3-м и т. д.
0
1
2
3
7
12
38
5
0
1
2
3
12
7
5
38
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
…
…
N-2
N-1
40
23
N-2
N-1
23
40
http://kpolyakov.spb.ru

141. Перестановка пар соседних элементов

Программирование (Python), 9 класс
141
Перестановка пар соседних элементов
for i in range(N):
поменять местами A[i] и A[i+1]
0
1
2
3
Что плохо?
?
4
5
7
12
38
5
40
23
12
7
38
5
40
23
12
38
7
5
40
выход
23 за границы
массива
12
38
5
7
40
23
12
38
5
40
7
23
12
38
5
40
23
7
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
?
http://kpolyakov.spb.ru

142. Перестановка пар соседних элементов

Программирование (Python), 9 класс
142
Перестановка пар соседних элементов
for i in range(0,N-1,2):
# переставляем A[i] и A[i+1]
с = A[i]
A[i] = A[i+1]
A[i+1] = c
A[0] A[1]
A[2] A[3]
...
A[N-2] A[N-1]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
143
Реверс массива
Задача. Переставить элементы массива в обратном
порядке (выполнить реверс).
0
1
2
7
12
5
0
1
2
23
40
38
A[0] A[N-1]
A[1] A[N-2]
A[i] A[N-1-i]
A[N-1] A[0]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
…
…
N-3
N-2
N-1
38
40
23
N-3
N-2
N-1
5
12
7
0+N-1 = N-1
1+N-2 = N-1
i+??? = N-1
N-1+0 = N-1
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
144
Реверс массива
(N // 2):
for i in range(N):
поменять местами A[i] и A[N-1-i]
? Что плохо?
0
1
2
3
7
12
40
23
i=0
23
12
40
7
i=1
23
40
12
7
i=2
23
12
40
7
i=3
7
12
40
23
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Как исправить?
http://kpolyakov.spb.ru

145. Задачи

Программирование (Python), 9 класс
145
Задачи
«A»: Заполнить массив из 10 элементов случайными
числами в диапазоне [0; 100], поменять местами
пары соседних элементов, не трогая первый и
последний элементы.
Массив:
53 66 88 39 26 88 35 24 38 50
Результат: 53 88 66 26 39 35 88 38 24 50
«B»: Заполнить массив из 10 элементов случайными
числами в диапазоне [0; 100] и выполнить
циклический сдвиг влево: каждый элемент
перемещается на место предыдущего, а первый – на
место последнего.
Массив:
53 66 88 39 26 88 35 24 38 50
Результат: 66 88 39 26 88 35 24 38 50 53
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

146. Задачи

Программирование (Python), 9 класс
146
Задачи
«C»: Заполнить массив из 10 элементов случайными
числами в диапазоне [0; 100], сделать реверс
отдельно в первой и во второй половине массива.
Массив:
53 66 88 39 26 88 35 24 38 50
Результат: 26 39 88 66 53 50 38 24 35 88
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

147. Линейный поиск в массиве

Программирование (Python), 9 класс
147
Линейный поиск в массиве
Задача. Найти в массиве элемент, равный X, и его номер.
X=5
5
0
1
2
3
4
5
7
12
38
5
40
23
i = 0
while A[i]!=X:
i += 1
print( f"A[{i}]={X}" )
? Что плохо?
? Если искать 4?
! Нельзя выходить за границы массива!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

148. Линейный поиск в массиве

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

149. Досрочный выход из цикла

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

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

Программирование (Python), 9 класс
151
Задачи
«A»: Напишите программу, которая заполняет массив из
N = 10 элементов случайными числами в диапазоне
[0,20], выводит его на экран, а затем находит индекс
первого элемента, равного введённому числу X.
Программа должна вывести ответ «не найден», если
в массиве таких элементов нет.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Что ищем: 13
A[3] = 13
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

151. Задачи

Программирование (Python), 9 класс
152
Задачи
«B»: Напишите программу, которая заполняет массив из
N = 10 элементов случайными числами в диапазоне
[-5,5], выводит его на экран, а затем находит индекс
последнего элемента, равного введённому числу X.
Программа должна вывести ответ «не найден», если
в массиве таких элементов нет.
Пример:
Массив: -5 -6 2 3 -3 0 8 -3 0 9
Что ищем: 0
A[8] = 0
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

152. Задачи

Программирование (Python), 9 класс
153
Задачи
«C»: Напишите программу, которая заполняет массив из
N = 10 элементов случайными числами в диапазоне
[10,15], выводит его на экран, а затем находит
индексы всех элементов, равных введённому числу
X. Программа должна вывести ответ «не найден»,
если в массиве таких элементов нет.
Пример:
Массив: 12 15 10 13 13 15 10 14 12 13
Что ищем: 12
A[0] = 12
A[8] = 12
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

153. Задачи

Программирование (Python), 9 класс
154
Поиск максимального элемента
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

154. Поиск максимального элемента

Программирование (Python), 9 класс
155
Поиск максимального элемента
? Какие переменные нужны?
for i in range(N):
if A[i] > M:
M = A[i]
print( M )
? Чего не хватает?
начальное
? Какое
значение взять для M?
1) M – значение, которое заведомо меньше всех
элементов массива
или
2) M = A[0] (или любой другой элемент)
максимальный не меньше, чем A[0]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

155. Поиск максимального элемента

Программирование (Python), 9 класс
156
Поиск максимального элемента
начинаем с A[1], так как
A[0] мы уже посмотрели
M = A[0]
for i in range(1,N):
if A[i] > M:
M = A[i]
print( M )
? Как найти минимальный?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

156. Поиск максимального элемента

Программирование (Python), 9 класс
157
Поиск максимального элемента (Python)
M = A[0]
for x in A:
if x > M:
M = x
print( M )
перебрать все элементы
в массиве A
! Не нужно знать размер!
print( max(A) )
print( min(A) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

157. Поиск максимального элемента (Python)

Программирование (Python), 9 класс
158
Номер максимального элемента
Задача. Найти в массиве максимальный элемент и его
номер.
? Какие переменные нужны?
M = A[0]; nMax = 0
for i in range(1,N):
if A[i] > M:
ли убрать одну
? Можно
M = A[i]
переменную?
nMax = i
print( f"A[{nMax}]={M}" )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

158. Номер максимального элемента

Программирование (Python), 9 класс
159
Номер максимального элемента
! Если знаем nMax, то M=A[nMax]!
M = A[0]; nMax = 0
for i in range(1,N):
:
if A[i]> A[nMax]
M :
M = A[i]
nMax = i
print( f"A[{nMax}]={M}"
)
{A[nMax]}"
)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

159. Номер максимального элемента

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

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

Программирование (Python), 9 класс
161
Максимальный не из всех
Задача. Найти в массиве максимальный из
отрицательных элементов.
M = A[0]
for i in range(1,N):
if A[i]<0 and A[i]>M:
M = A[i]
print( M )
0
1
2
3
4
5
–2
8
3
–1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что плохо?
? Как исправить?
M = 5
http://kpolyakov.spb.ru

161. Максимальный не из всех

Программирование (Python), 9 класс
162
Максимальный не из всех
Задача. Найти в массиве максимальный из
отрицательных элементов.
M = A[0]
for i in range(1,N):
if A[i] < 0:
if M >= 0 or A[i]> M:
M = A[i]
сначала записали
неотрицательный!
print( M )
? Если нет отрицательных?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

162. Максимальный не из всех

Программирование (Python), 9 класс
163
Максимальный не из всех (Python)
Задача. Найти в массиве максимальный из
отрицательных элементов.
отбираем нужные
B = [ x for x in A
if x < 0]
? Если нет отрицательных?
print( max(B) )
if len(B):
if len(B)!= 0:
print( max(B) )
else:
print("Нет таких!")
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

163. Максимальный не из всех (Python)

Программирование (Python), 9 класс
164
Задачи (без min и max)
«A»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [50;
150] и находит в нём минимальный и максимальный
элементы и их номера.
«B»: Напишите программу, которая заполняет массив из
10 элементов в виде
A = [ 10, 2, 3, 4, 5, 10, 7, 8, 9, 10]
и выводит количество элементов, имеющих
максимальное значение.
«C»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [100;
200] и находит в нём пару соседних элементов,
сумма которых минимальна.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

164. Задачи (без min и max)

Программирование (Python), 9 класс
165
Задачи
«D»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [–100;
100] и находит в каждой половине массива пару
соседних элементов, сумма которых максимальна.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

165. Задачи

Программирование (Python), 9 класс
166
Задачи-2 (максимум в потоке)
«A»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Напишите программу, которая находит минимальное
и максимальное среди полученных чисел.
«B»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Напишите программу, которая находит минимальное
и максимально из тех чисел, которые делятся на 3.
«C»: На вход программы поступает неизвестное
количество чисел целых, ввод заканчивается нулём.
Напишите программу, которая находит
максимальное двузначное число, заканчивающееся
на 6, среди полученных чисел. Если такого числа
нет, нужно вывести слово «Нет».
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

166. Задачи-2 (максимум в потоке)

Программирование (Python), 9 класс
167
Задачи-2 (максимум в потоке)
«D»: На вход программы поступает неизвестное
количество целых чисел (не менее 2), ввод
заканчивается нулём. Напишите программу, которая
находит среди полученных чисел пару полученных
друг за другом чисел, сумма которых максимальна.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

167. Задачи-2 (максимум в потоке)

Программирование (Python), 9 класс
168
Сортировка
Сортировка — это расстановка элементов списка
(массива) в заданном порядке.
Задача. Отсортировать элементы в порядке
возрастания (неубывания – если есть одинаковые).
Алгоритмы сортировки:
• простые, но медленные (при больших N)
• быстрые, но сложные…
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

168. Сортировка

Программирование (Python), 9 класс
169
Сортировка выбором
? Где должен стоять минимальный элемент?
• нашли минимальный, поставили его на первое место
с = A[nMin]
A[nMin] = A[0]
A[0],A[nMin]
= A[nMin],A[0]
A[0] = c
? Как?
• из оставшихся нашли минимальный, поставили его на
второе место и т.д.
Что дальше?
5
–2
8
3
–1
–2
5
8
3
–1
–2
–1
8
3
5
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
?
http://kpolyakov.spb.ru

169. Сортировка выбором

Программирование (Python), 9 класс
170
Сортировка выбором
for i in range(N-1):
# ищем минимальный среди A[i]..A[N-1]
не трогаем те, которые
уже поставлены
nMin = i
for j in range(i+1,N):
if A[j] < A[nMin]:
nMin = j
# переставляем A[i] и A[nMin]
A[i],A[nMin] = A[nMin],A[i]
Решение в стиле Python:
A.sort()
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Почему цикл N-1 раз?
http://kpolyakov.spb.ru

170. Сортировка выбором

Программирование (Python), 9 класс
171
Задачи
«A»: Напишите программу, которая заполняет массив из N
= 10 элементов случайными числами в диапазоне
[0,20] и сортирует его в порядке убывания.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Сортировка: 18 16 16 14 13 13 9 5 3 2
«B»: Напишите программу, которая заполняет массив из N
= 10 элементов случайными числами в диапазоне
[10,100] и сортирует его по возрастанию последней
цифры числа (сначала идут все числа, которые
заканчиваются на 0, потом все, которые
заканчиваются на 1, и т.д.).
Пример:
Массив: 12 10 31 40 55 63 28 87 52 92
Сортировка: 10 40 31 12 52 92 63 55 87 28
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

171. Задачи

Программирование (Python), 9 класс
172
Задачи
«C»: Напишите программу, которая заполняет массив из N
= 10 элементов случайными числами в диапазоне
[0,20] и сортирует его в порядке возрастания. На
каждом шаге цикла выполняется поиск
максимального (а не минимального!) элемента.
Пример:
Массив: 5 16 2 13 3 14 18 13 16 9
Сортировка: 2 3 5 9 13 13 14 16 16 18
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

172. Задачи

173
Программирование
(Python)
§ 21. Матрицы (двумерные
массивы)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

173. Программирование (Python)

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

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

Программирование (Python), 9 класс
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
175
http://kpolyakov.spb.ru

175.

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

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

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

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

Программирование (Python), 9 класс
178
Вывод матриц
print ( A )
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
def printMatrix( A ):
for row in A:
for x in row:
print ( f"{x:4d}", end = "" )
print ()
1
4
7
2
5
8
3
6
9
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Зачем форматный вывод?
http://kpolyakov.spb.ru

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

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

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

Программирование (Python), 9 класс
180
Перебор элементов матрицы
Главная диагональ:
for i in range(N):
# работаем с A[i][i]
Побочная диагональ:
for i in range(N):
# работаем с A[i][N-1-i]
Главная диагональ и под ней:
for i in range(N):
for j in range( i+1 ):
# работаем с A[i][j]
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
181
Задачи
«A»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N случайными
числами в диапазоне [10; 100] и выводит её на экран.
Затем нужно обнулить все элементы на главной
диагонали и вывести полученную матрицу.
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
После обработки:
0 34 14 65
71 0 23 45
87 46 0 39
76 58 24 0
http://kpolyakov.spb.ru

181. Задачи

Программирование (Python), 9 класс
182
Задачи
«B»: Напишите программу, которая вводит размер
матрицы N (чётное число), заполняет матрицу N N
случайными числами в диапазоне [10; 100] и выводит
её на экран. Затем нужно обнулить все элементы
правой верхней четверти и вывести полученную
матрицу.
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
После обработки:
12 34 0 0
71 88 0 0
87 46 53 39
76 58 24 92
http://kpolyakov.spb.ru

182. Задачи

Программирование (Python), 9 класс
183
Задачи
«С»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N случайными
числами в диапазоне [10; 100] и выводит её на экран.
Затем нужно обнулить все элементы побочной
диагонали и все элементы под ней и вывести
полученную матрицу.
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
После обработки:
12 34 65 0
71 88 0 0
87 0 0 0
0 0 0 0
http://kpolyakov.spb.ru

183. Задачи

Программирование (Python), 9 класс
184
Суммирование элементов матрицы
Суммирование всех:
s=0
for i in range(N):
for j in range(M):
s += A[i][j]
print ( s )
s=0
for i in range(1,3):
for j in range(1,3):
s += A[i][j]
print ( s )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? Что суммируем?
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
http://kpolyakov.spb.ru

184. Суммирование элементов матрицы

Программирование (Python), 9 класс
185
Суммирование элементов матрицы
? Что суммируем?
s=0
for i in range(N):
s += A[2][i]
print ( s )
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
s=0
for i in range(N):
s += A[i][2]
print ( s )
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
s=0
for i in range(N):
s += A[i][i+2]
print ( s )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
! Index out
of range!
http://kpolyakov.spb.ru

185. Суммирование элементов матрицы

Программирование (Python), 9 класс
186
Задачи
«A»: Напишите программу, которая вводит размер
матрицы N (чётное число), заполняет матрицу N N
случайными числами в диапазоне [0; 15] и выводит на
экран саму матрицу и сумму её элементов в левой
верхней четверти.
Пример:
Введите N: 4
Матрица А:
1 3 4 6
1 8 3 5
7 6 3 9
6 8 4 2
Сумма: 13
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

186. Задачи

Программирование (Python), 9 класс
187
Задачи
«B»: Напишите программу, которая вводит размер
матрицы N (чётное число), заполняет матрицу N N
случайными числами в диапазоне [0; 15] и выводит на
экран саму матрицу и сумму её элементов на двух
диагоналях.
Пример:
Введите N: 4
Матрица А:
2 4 4 5
1 8 3 5
7 6 3 9
6 5 4 2
Сумма на двух диагоналях:
35
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

187. Задачи

Программирование (Python), 9 класс
188
Задачи
«С»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N случайными
числами в диапазоне [0; 15] и выводит на экран саму
матрицу и сумму её элементов под побочной
диагональю.
Пример:
Введите N: 4
Матрица А:
12 4 14 1
1 8 3 5
7 6 3 9
6 8 14 12
Сумма: 51
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

188. Задачи

Программирование (Python), 9 класс
189
Максимальный элемент
Максимум среди всех
Max = -10000
for i in range(N):
for j in range(M):
if A[i][j] > Max:
Max = A[i][j]
print ( Max )
? Как для части матрицы?
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
for i in range(1,3):
for j in range(1,3):
...
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
190
Максимальный элемент и его индексы
Максимум среди всех
Max = A[0][0]
iMax = jMax = 0
for i in range(N):
for j in range(M):
if A[i][j] > Max:
Max = A[i][j]
iMax = i iMax, jMax = i, j
jMax = j
print( f"A[{iMax}][{jMax}]={Max}" )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

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

Программирование (Python), 9 класс
191
Задачи
«A»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N матрицу
случайными числами в диапазоне [10; 100] и находит
максимальный элемент матрицы на главной
диагонали и его индексы (номера строки и столбца).
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 98
87 46 53 39
76 58 24 92
Максимум на главной диагонали:
A[1][1] = 88
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

191. Задачи

Программирование (Python), 9 класс
192
Задачи
«B»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N случайными
числами в диапазоне [10; 100] и находит
максимальный элемент в двух последних строках
матрицы и его индексы (номера строки и столбца).
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 98
87 46 53 39
76 58 24 92
Максимум в последних двух строках:
A[2][0] = 87
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

192. Задачи

Программирование (Python), 9 класс
193
Задачи
«C»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N случайными
числами в диапазоне [10; 100] и находит столбец,
сумма элементов которого максимальна. Нужно
вывести суммы для каждого столбца, индекс столбца
с максимумом и сумму его элементов.
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 98
87 46 53 39
76 58 24 92
Суммы столбцов: 246 226 114 294
Максимум: столбец 3 - 294
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

193. Задачи

Программирование (Python), 9 класс
194
Поиск заданного значения в матрице
X = int(input("Что ищем?"))
iX = jX = -1
for i in range(N):
for j in range(M):
if A[i][j] == X:
iX = i
iX, jX = i, j
jX = j
break
А из второго цикла?
if iX >= 0: break
?
if iX >= 0:
print( f"A[{iX}][{jX}]={X}" )
else:
print( "Нет таких" )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

194. Поиск заданного значения в матрице

Программирование (Python), 9 класс
195
Задачи
«A»: Напишите программу, которая вводит размер
матрицы N (чётное число), заполняет матрицу N N
матрицу случайными числами в диапазоне [10; 100] и
находит заданный элемент в нижней половине
матрицы или пишет, что его там нет.
Пример:
Введите N: 4
Матрица А:
12 34 14 65
71 88 23 98
87 46 53 39
76 58 24 92
Что ищем? 53
Что ищем? 51
A[2][2] = 53
Нет таких.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

195. Задачи

Программирование (Python), 9 класс
196
Задачи
«B»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N матрицу
случайными числами в диапазоне [10; 20] и находит
все элементы, равные заданному числу, выше главной
диагонали матрицы или пишет, что их там нет.
Пример:
Введите N: 4
Что ищем? 58
Матрица А:
A[0][2] = 58
12 34 58 65
A[1][3] = 58
71 88 23 58
58 46 53 39
Что ищем? 51
76 51 24 92
Нет таких.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

196. Задачи

Программирование (Python), 9 класс
197
Задачи
«С»: Напишите программу, которая вводит размер
матрицы N, заполняет матрицу N N матрицу
случайными числами в диапазоне [10; 20] и находит
все элементы, равные заданному числу, в полосе
шириной 3 с центром на побочной диагонали или
пишет, что их там нет.
Пример:
Что ищем? 58
Введите N: 4
A[1][3] = 58
Матрица А:
A[2][0] = 58
12 34 14 65
A[3][1] = 58
71 88 23 58
58 46 53 39
76 58 24 92
Что ищем? 51
Нет таких.
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

197. Задачи

198
Программирование
(Python)
§ 22. Сложность алгоритмов
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

198. Программирование (Python)

Программирование (Python), 9 класс
199
Как сравнивать алгоритмы?
• быстродействие (временна́я сложность)
• объём требуемой памяти (пространственная
сложность)
Обычно не бывает все хорошо!
• понятность
!
Время работы алгоритма – это количество
элементарных операций T, выполненных
исполнителем.
зависит от
количества данных
Функция T(N) называется
(размера массива N)
временно́й сложностью алгоритма
T(N) = 2N3
увеличится время работы
? Как
при увеличении N в 10 раз?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

199. Как сравнивать алгоритмы?

Программирование (Python), 9 класс
200
Примеры определения сложности
Задача 1. Вычислить сумму первых трёх элементов
массива (при N 3).
2 сложения
+ запись в
Sum = A[0] + A[1] + A[2] T(N) = 3
память
Задача 2. Вычислить сумму всех элементов массива.
T(N) = 2N + 1
Sum = 0
for i in range(N):
N сложений, N+1
Sum += A[i]
операций записи
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

200. Примеры определения сложности

Программирование (Python), 9 класс
201
Примеры определения сложности
Задача 3. Отсортировать все элементы массива по
возрастанию методом выбора.
for i in range(N-1):
nMin = i
for j in range(i+1,N):
if A[i] < A[nMin]:
nMin = j
A[i],A[nMin] = A[nMin],A[i]
Число сравнений:
N (N 1) 1 2 1
Tc (N ) (N 1) (N 2) ... 2 1
N N
2
2
2
Число перестановок: Tn(N) = N – 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

201. Примеры определения сложности

Программирование (Python), 9 класс
202
Примеры определения сложности
Задача 4. Найти сумму элементов квадратной матрицы
размером N N.
Sum = 0
for i in range(N):
for j in range(N):
Sum += A[i][j]
! Самостоятельно!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

202. Примеры определения сложности

Программирование (Python), 9 класс
203
Сравнение алгоритмов по сложности
T1(N ) 10000 N
T2 (N ) 100 N
2
T3 (N ) N 3
? Какой алгоритм выбрать?
при N < 100:
T3
T
T3 (N ) T2 (N ) T1(N )
T2
при N > 100:
T1
T3 (N ) T2 (N ) T1(N )
! Нужно знать размер
0
100
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
N
данных!
http://kpolyakov.spb.ru

203. Сравнение алгоритмов по сложности

Программирование (Python), 9 класс
204
Асимптотическая сложность
Асимптотическая сложность – это оценка скорости
роста количества операций при больших значениях N.
не зависит от N
сложность O(1)
постоянная
T(N) c для N N0
T(N) = 100 101 для всех N 1
O(1)
линейная
сложность O(N)
T(N) c N для N N0
сумма элементов массива:
T(N) = 2 N – 1 2 N для N 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
O(N)
http://kpolyakov.spb.ru

204. Асимптотическая сложность

Программирование (Python), 9 класс
205
Асимптотическая сложность
квадратичная
сложность O(N2)
T(N) c N2 для N N0
сортировка методом выбора:
1 2 1
1 2
Tc (N ) N N N для N 0
2
2
2
O(N2)
кубичная
сложность O(N3)
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
T(N) c N3 для N N0
http://kpolyakov.spb.ru

205. Асимптотическая сложность

Программирование (Python), 9 класс
206
Асимптотическая сложность
сложность O(2N)
сложность O(N!)
задачи оптимизации,
полный перебор вариантов
Факториал числа N: N ! = 1 2 3 … N
T(N)
N
N2
N3
2N
N!
время выполнения
100 нс
10 мс
0,001 с
1013 лет
10141 лет
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
N = 100,
1 млрд оп/с
http://kpolyakov.spb.ru

206. Асимптотическая сложность

Программирование (Python), 9 класс
207
Асимптотическая сложность
Алгоритм относится к классу
O( f(N) ), если найдется такая
постоянная c, что начиная с
некоторого N = N0 выполняется
условие
T(N) c f (N)
T
c f (N )
T (N )
0
N0
N
это верхняя
оценка!
O( N ) O( N2 ) O( N3 ) O( 2N )
«Алгоритм имеет сложность O(N2)».
обычно – наиболее точная
верхняя оценка!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

207. Асимптотическая сложность

208
Программирование
(Python)
§ 26. Динамическое
программирование
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

208. Программирование (Python)

Программирование (Python), 9 класс
209
Что такое динамическое программирование?
;
Числа Фибоначчи:
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)
повторное вычисление тех же значений
! Запоминать то, что вычислено!
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

209. Что такое динамическое программирование?

Программирование (Python), 9 класс
210
Когда это работает?
;
.
1) Решение задачи для числа
N можно выразить через
решения таких же (более простых) задач для меньших
чисел.
Fn = Fn-1 + Fn-2
2) При решении задачи для числа N решения задач для
меньших чисел нужны несколько раз.
F5
F3
F4
F3
F2
F2
F2
F1
F1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

210. Когда это работает?

Программирование (Python), 9 класс
211
Динамическое программирование
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Создание массива:
F = [0]*(N+1) # чтобы начать с 1
Заполнение массива:
F[1] = 1
F[2] = 1
for i in range(3,N+1):
F[i] = F[i-1] + F[i-2]
? Где ответ?
F35: рекурсия: 58 с
дин. программирование: < 0,001 с
? Можно ли обойтись без массива?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
F[N]
нужны только
два последних!
http://kpolyakov.spb.ru

211. Динамическое программирование

Программирование (Python), 9 класс
212
Динамическое программирование
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Создание массива:
F = [0]*(N+1) # чтобы начать с 1
Заполнение массива:
for i in range( 11 ,N+1):
if i <= 2:
F[i] = 1
else:
F[i] = F[i-1] + F[i-2]
print( F[N]
??? )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

212. Динамическое программирование

Программирование (Python), 9 класс
213
Задачи
«A»: Алгоритм вычисления значения функции F(n), где n
– натуральное число, задан следующими
соотношениями:
F(n) = n при n ≤ 3;
F(n) = 2 × F(n − 1) – F(n − 2) + 3, если n > 3
Напишите программу, которая вводит значение n и
вычисляет F(n).
Пример:
Введите число: 155
Ответ: 35039
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

213. Задачи

Программирование (Python), 9 класс
214
Задачи
«B»: Алгоритм вычисления значения функции F(n), где n
– натуральное число, задан следующими
соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и n – нечётно.
Напишите программу, которая вводит значение n и
вычисляет F(n).
Пример:
Введите число: 26
Ответ: 4122
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

214. Задачи

Программирование (Python), 9 класс
215
Задачи
«C»: Алгоритм вычисления значения функции F(n), где n
– целое неотрицательное число, задан следующими
соотношениями:
F(n) = 0 при n = 0
F(n) = F(n/2) – 2 при чётных n > 0
F(n) = 2 + F(n–1) при нечётных n > 0
Напишите программу, которая вводит значение K > 0
и определяет количество чисел n, меньших K, для
которых значение F(n) будет равно «–2».
Пример:
Введите число: 1000
Ответ: 111
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

215. Задачи

Программирование (Python), 9 класс
216
Подсчёт количества вариантов
;
Задача. Кузнечик прыгает по .столбикам, расположенным
на одной линии на равных расстояниях друг от друга.
Кузнечик сидит на столбике с номером 1. Он может
прыгать на следующий столбик, или сразу на второй
столбик, считая от текущего. Найти количество
способов, которыми Кузнечик может добраться до
столбика с номером N.
Как сюда попал?
?
Ki–2 Ki–1 Ki
1
2
3
Ki = Ki–1 + Ki–2
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
? На что похоже?
N
http://kpolyakov.spb.ru

216. Подсчёт количества вариантов

Программирование (Python), 9 класс
217
Числа Фибоначчи
F1
1
F2
1
F3
2
F4
3
F5
5
F1 = F2 = 1
Fn = Fn-1 + Fn-2, при n > 2
Создание массива:
F = [0]*(N+1) # чтобы начать с 1
Заполнение массива:
F[1] = 1
F[2] = 1
for i in range(3,N+1):
F[i] = F[i-1] + F[i-2]
? Как вывести ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
print( F[N] )
http://kpolyakov.spb.ru

217. Числа Фибоначчи

Программирование (Python), 9 класс
218
Задачи
«A»: Кузнечик прыгает по столбикам, расположенным на
одной линии на равных расстояниях друг от друга.
Кузнечик сидит на столбике с номером 1. Он может
прыгать на следующий столбик, сразу на второй
столбик, считая от текущего, или сразу на третий.
Напишите программу, которая вводит число N и
определяет количество способов, которыми
Кузнечик может добраться до столбика с номером N.
Пример:
Введите N: 30
Ответ: 29249425
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

218. Задачи

Программирование (Python), 9 класс
219
Задачи
«B»: Исполнитель Калькулятор изменяет число на
экране. У него есть две команды:
1. прибавь 1
2. умножь на 2
Программа для исполнителя – это
последовательность команд. Напишите программу,
которая вводит число N и определяет количество
программ, с помощью которых Калькулятор из числа
4 может получить число N.
Пример:
Введите N: 1
Ответ: 0
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
Пример:
Введите N: 100
Ответ: 1952
http://kpolyakov.spb.ru

219. Задачи

Программирование (Python), 9 класс
220
Задачи
«C»: Кузнечик прыгает по столбикам, расположенным на
одной линии на равных расстояниях друг от друга.
Кузнечик сидит на столбике с номером 1. Он может
прыгать вперёд на расстояние от 1 до K столбиков,
считая от текущего. Напишите программу, которая
вводит числа N и K, определяет количество
способов, которыми Кузнечик может добраться до
столбика с номером N.
Пример 1:
Введите N: 10
Введите K: 7
Ответ: 253
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
Пример 2:
Введите N: 30
Введите K: 5
Ответ: 175514464
http://kpolyakov.spb.ru

220. Задачи

Программирование (Python), 9 класс
221
Задачи
«D»: Кузнечик прыгает по столбикам, расположенным на
одной линии на равных расстояниях друг от друга.
Кузнечик сидит на столбике с номером 1. Он может
прыгать вперёд на расстояние от 1 до K столбиков,
считая от текущего. Напишите программу, которая
вводит числа N и K, определяет количество
способов, которыми Кузнечик может добраться до
столбика с номером N. Программа должна вывести
последние 6 цифр результата.
Пример 1:
Введите N: 30
Введите K: 5
Ответ: 514464
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
Пример 2:
Введите N: 2000000
Введите K: 1000000
Ответ: 777344
http://kpolyakov.spb.ru

221. Задачи

Программирование (Python), 9 класс
222
Оптимальные решения
;
Задача. В массиве А найти наибольшую
длину
.
непрерывной цепочки положительных чисел.
A
4 -1 6
8
0 -5 9
3
6 11
D
1
2
0
2
3
0
1
0
1
4
D[i] – наибольшая длина
цепочки, которая
заканчивается на A[i]
? Как вывести ответ?
print( max(D) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

222. Оптимальные решения

Программирование (Python), 9 класс
223
Оптимальные решения
;
Задача. В массиве А найти наибольшую
длину цепочки
.
положительных чисел.
A = [4,-1,6,8,0,-5,9,3,6,11]
N = len(A)
D = [0]*N
if A[0] > 0:
D[0] = 1
D[0] = 1 if A[0] > 0 else 0
else:
D[0] = 0
for i in range(1,N):
if A[i] > 0:
D[i] = D[i-1]
D[i]+ =1 D[i-1]+1 if A[i] > 0 \
else:
else 0
D[i] = 0
print( max(D) )
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

223. Оптимальные решения

Программирование (Python), 9 класс
224
Оптимальные решения
;
Задача. В массиве А найти наибольшую
сумму
.
непрерывной цепочки чисел.
? В такой цепочке могут быть отрицательные числа?
A
4 -1 3 -8 1 -5 2
3
1 -4
D
4
5
6
3
6 -2 1 -4 2
2
D[i] – наибольшая сумма
цепочки, которая
заканчивается на A[i]
? Как вывести ответ?
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
print( max(D) )
http://kpolyakov.spb.ru

224. Оптимальные решения

Программирование (Python), 9 класс
225
Оптимальные решения
;
Задача. В массиве А найти наибольшую
сумму
.
непрерывной цепочки чисел.
A = [4,-1,3,-8,1,-5,2,3,1,-4]
N = len(A)
D = [0]*N
D[0] = A[0]
for i in range(1,N):
D[i] = max( A[i], D[i-1]+A[i] )
print( max(D) )
если начинаем
новую цепочку
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
если продолжаем
старую цепочку
http://kpolyakov.spb.ru

225. Оптимальные решения

Программирование (Python), 9 класс
226
Задачи
«A»: В массиве А найти наибольшую длину цепочки
нулей.
Пример 1:
A = [1,0,0,3,0,4,0,0,0,0]
Ответ: 4
Пример 2:
A = [0,0,0,0,0,0,0,0,0,0]
Ответ: 10
Пример 3:
A = [1,2,3,4,5,6,7,8,9,1]
Ответ: 0
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

226. Задачи

Программирование (Python), 9 класс
227
Задачи
«B»: В массиве А найти наибольшую длину непрерывной
цепочки чисел, в которой каждое число отличается
от предыдущего не более, чем на 1.
Пример 1:
A = [1,9,1,2,3,2,0,1,1,10]
Ответ: 4
Пример 2:
A = [1,2,1,2,3,2,1,0,-1,0]
Ответ: 10
Пример 3:
A = [2,4,1,4,2,4,1,4,2,4]
Ответ: 1
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

227. Задачи

Программирование (Python), 9 класс
228
Задачи
«C»: Определить, сколько в массиве А непрерывных
цепочек чисел, в которых каждое число отличается
от предыдущего не более, чем на 1.
Пример 1:
A = [1,9,1,2,3,2,0,8,3,10]
Ответ: 7
Пример 2:
A = [1,2,1,2,3,2,1,0,-1,0]
Ответ: 1
Пример 3:
A = [2,4,1,4,2,4,1,4,2,4]
Ответ: 10
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

228. Задачи

Программирование (Python), 9 класс
229
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
eremin@pspu.ac.ru
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru

229. Конец фильма

Программирование (Python), 9 класс
230
Источники иллюстраций
1.
2.
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2021-2024
http://kpolyakov.spb.ru