Язык Python в школьной информатике
Язык Python в школьной информатике Переменные. Ввод и вывод
Тип переменных – автовывод типов
Особенность переменных в Python
Множественное присваивание
Ввод с клавиатуры
Ввод нескольких значений
Что такое генератор?
Ввод нескольких значений
Ввод нескольких значений
Деление и остаток
Деление и остаток для вещественных чисел
Сокращённая запись операций
Вывод
Вывод: f-строки
Функции min и max
Язык Python в школьной информатике Операторы управления
Условный оператор
Тернарный оператор
Циклы с условием
Циклы с переменной
Циклы с переменной
Функции
ЕГЭ-2 (демо-2021)
Частичная таблица истинности
Через [0, 1]
ЕГЭ-2
ЕГЭ-25
Решение («пифагоровы тройки»)
Язык Python в школьной информатике Делимость
Делимость
Делимость: D, ND
ЕГЭ-15 (демо-2021)
Решение
Делимость: DivsAll, DivsAny
Делимость: DivsAll, DivsAny
Делимость: DivsAll, DivsAny
ЕГЭ-17
Решение
ЕГЭ-17
Решение
Язык Python в школьной информатике Длинная арифметика
Длинные числа
ЕГЭ-14
Решение
ЕГЭ-14
Решение
ЕГЭ-14
Решение
Язык Python в школьной информатике Функции
Определения функций
ЕГЭ-5
Решение
ЕГЭ-16
Решение
Решение
ЕГЭ-16
Решение
ЕГЭ-16
Решение
ЕГЭ-23 (демо-2021)
Решение
ЕГЭ-23
Решение
ЕГЭ-23
Решение
Простые числа
Как ускорить?
Простые числа
ЕГЭ-25
ЕГЭ-25
Решение
Решение
Язык Python в школьной информатике Массивы (списки)
Массивы (списки)
Массивы и списки
Создание массивов
Создание массивов
Ввод элементов массивов по одному
Ввод массивов из одной строки
Ввод массивов из одной строки
Заполнение случайными числами
Вывод массивов
Вывод массивов с номером
Срезы массивов
Удаление элементов списка
Массивы: функции
ЕГЭ-24
Решение
Все делители
Как ускорить?
Все делители
ЕГЭ-17
Решение
ЕГЭ-25
Решение
ЕГЭ-25
Решение
ЕГЭ-25
Решение
ЕГЭ-25
Решение
Только полные квадраты
Основная теорема арифметики
Чётвертые степени простых чисел
ЕГЭ-23
Решение
Язык Python в школьной информатике Операции с массивами
Фильтрация (отбор нужных)
Фильтрация (отбор нужных)
Преобразование
Преобразование
Преобразование к другому типу
Преобразование в кортеж
Преобразование в кортеж
Проверка условия для всех
Язык Python в школьной информатике Перебор
ЕГЭ-17
Решение (уже было)
Решение (новое)
ЕГЭ-17
Решение
ЕГЭ-17
Решение
ЕГЭ-15
ЕГЭ-15
ЕГЭ-15
ЕГЭ-15 (с функцией)
ЕГЭ-15
ЕГЭ-15 (демо-2021)
Решение
ЕГЭ-15
Решение
ЕГЭ-15
Решение
ЕГЭ-15 (поразрядное И)
Решение
Комбинаторика: декартово произведение
Комбинаторика: декартово произведение
ЕГЭ-15
ЕГЭ-15
ЕГЭ-15
Решение
Решение (до первого)
ЕГЭ-16
Решение
ЕГЭ-5
Решение
ЕГЭ-5
Решение
ЕГЭ-6 (демо-2021)
Решение
ЕГЭ-6
Решение
Язык Python в школьной информатике Символьные строки
Символьные строки
Срезы строк
Символьные строки
Методы обработки строк
Замена подстрок
Методы обработки строк
ЕГЭ-8
Решение («КАБИНЕТ»)
ЕГЭ-8
Решение («АССАСИН»)
Комбинаторика: декартово произведение
ЕГЭ-8
ЕГЭ-8
ЕГЭ-8
ЕГЭ-8
ЕГЭ-8
ЕГЭ-8
Решение («КРА»)
ЕГЭ-8
Решение («КРА-2»)
ЕГЭ-8
Решение («САЗАН»)
Решение («САЗАН-2»)
ЕГЭ-8
Решение («РАФТ»)
ЕГЭ-8
Решение («АЛГОРИТМ»)
ЕГЭ-8
Решение («РАЗМАХ»)
Пары соседних
Пары соседних c отбором
ЕГЭ-8
Решение
ЕГЭ-8
Решение («АРЕАЛ»)
ЕГЭ-8
Решение
Язык Python в школьной информатике Работа с файлами
Классика
Менеджер контекста
Чтение всех строк
Обработка строк
ЕГЭ-24
Решение
Решение
ЕГЭ-24
Решение
ЕГЭ-24
Решение
Решение
ЕГЭ-24
Решение
Решение
Решение
Решение
Решение
Язык Python в школьной информатике
Словари (ассоциативные массивы)
Словари: перебор
Частотный словарь
Частотный словарь (сортировка)
ЕГЭ – С4
Решение
ЕГЭ–16
Решение
Решение (мемоизация)
ЕГЭ–16
Решение (мемоизация)
ЕГЭ–1921 (демо-2021)
ЕГЭ-1921. Оценка позиции
ЕГЭ-1921. Оценка позиции
ЕГЭ-1921. Решение (плохое)
ЕГЭ-1921. Оценка позиции (+mem)
ЕГЭ-1921. Решение
ЕГЭ-1921. Полная автоматизация
ЕГЭ–1921
ЕГЭ-1921. Оценка позиции
ЕГЭ-1921. Основная программа
Язык Python в школьной информатике Обработка потока данных (ЕГЭ-27)
ЕГЭ-27
Решение (подготовка)
Решение (обработка)
ЕГЭ-27
Решение (подготовка)
Решение (обработка)
ЕГЭ-27 (демо-2021)
Решение (подготовка)
Решение (обработка)
Решение через reduce
Группировка
Группировка (x > 3)
Группировка (по остатку)
ЕГЭ – С4 (ещё раз)
Решение (через groupby)
ЕГЭ-27 (демо-2021) – ещё раз
Решение (подготовка – без сортировки)
Решение (обработка через groupby)
ЕГЭ-27
Решение (подготовка – без сортировки)
Решение (через groupby)
ЕГЭ-27
Решение (подготовка)
Идея решения
Решение (обработка через groupby)
ЕГЭ-27
Решение (подготовка)
Решение (обработка через groupby)
Конец фильма
3.18M
Категория: ПрограммированиеПрограммирование

Язык Python в школьной информатике

1. Язык Python в школьной информатике

К.Ю. Поляков
Язык Python в школьной
информатике
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

2. Язык Python в школьной информатике Переменные. Ввод и вывод

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

3. Тип переменных – автовывод типов

Язык Python в школьной информатике
3
Тип переменных – автовывод типов
count = 0
# int
x = 1.12345 # float
b = True # bool
s = "Маша ела кашу" # str
s2 = 'Меня зовут Вася' # str
A = [1, 2, 13, 45, 0, 14] # list
S = {1, 2, 8} # set
D = { 'A': 1, 'B': 15, 'C': 28 } # dict
!
Имена регистрозависимые (A ≠ a)!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

4. Особенность переменных в Python

Язык Python в школьной информатике
4
Особенность переменных в Python
Таблица имен
a = 5
b = 5
a
b
str
Ку!
a = "Ку!"
b = 1.23
К.Ю. Поляков, 2021
int
5
float
1.23
указатели:
id(a)
http://kpolyakov.spb.ru

5. Множественное присваивание

Язык Python в школьной информатике
5
Множественное присваивание
(x, y) = (4, 5)
(count, s, b) = (0, "Иванов", True)
распаковка кортежа
кортеж
x, y = 4, 5
count, s, b = 0, "Иванов", True
a, b = b, a
счётчик и
a, b = b, a+b
сумма
count, s = count+1, s+x
a = b = c = 0
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
6
Ввод с клавиатуры
s
n
x
L
=
=
=
=
#
b =
#
input()
# строка
int(input())
# целое
float(input()) # вещественное
list(input()) # по символам
ABCD ['A', 'B', 'C', 'D']
bool(input()) # не пустая строка?
"" False
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

7. Ввод нескольких значений

Язык Python в школьной информатике
7
Ввод нескольких значений
a, b, c
s = input()
w = s.split()
# a =
# b =
# c =
a, b,
# строка 10 21 32
# список строк
# w[0] w[1] w[2]
# ["10", "21", "32"]
int(w[0])
int(w[1])
int(w[2])
c = map( int, w
кортеж
генератор
применить функцию
int к каждому
элементу w
)
должно быть
ровно 3
элемента!
a, b, c = map( int, input().split() )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

8. Что такое генератор?

Язык Python в школьной информатике
8
Что такое генератор?
s = "10 21 32"
g = map( int, s.split() )
print( g )
<map object at 0x0132EBD0>
print( list(g) )
print( list(g) )
[10, 21, 32]
[]
Генератор уже «выбрал» все
данные!
!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

9. Ввод нескольких значений

Язык Python в школьной информатике
9
Ввод нескольких значений
генератор!
a, b, c
a, b, c = map( int, input().split() )
a, b, c = (int(x) for x in input().split())
генератор
<generator object <genexpr> at 0x0132BA80>
a, b, c = [int(x) for x in input().split()]
список
[10, 21, 32]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

10. Ввод нескольких значений

Язык Python в школьной информатике
10
Ввод нескольких значений
a, b и, возможно, ещё что-то
a, b, *c = map( int, input().split() )
всё остальное
10 21 32
10 21
a
10
10
b
21
21
с
[32]
[]
10 21 32 45 56
10
21
[32, 45, 56]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

11. Деление и остаток

Язык Python в школьной информатике
11
Деление и остаток
// – деление нацело (div)
% – остаток от деления (mod)
print( 13 // 10 )
print( 13 % 10 )
print( -13 // 10 )
print( -13 % 10 )
# 1
# 3
# -2
# 7
-1,3
-2
-20
К.Ю. Поляков, 2021
1,3
-1
-13
0
-10
0
1
2
13
10
20
http://kpolyakov.spb.ru

12. Деление и остаток для вещественных чисел

Язык Python в школьной информатике
12
Деление и остаток для вещественных чисел
// – деление нацело (div)
% – остаток от деления (mod)
print( 8 // 2.5 )
print( 8 % 2.5 )
8 = 3*2,5 + 0,5
# 3.0
# 0.5
print( -8 // 2.5 )
print( -8 % 2.5 )
# -4.0
# 2.0
-8 = (-4)*2,5 + 2,0
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

13. Сокращённая запись операций

Язык Python в школьной информатике
13
Сокращённая запись операций
a
x
a
a
a
x
a
= 3
= 3.62
+= 15
-= 7 + a // 3
*= round(x)
/= 2
//= 2
К.Ю. Поляков, 2021
#
#
#
#
#
a
a
a
x
a
=
=
=
=
=
a + 15
a – (7 + a // 3)
a*round(x)
x / 2
a // 2
http://kpolyakov.spb.ru

14. Вывод

Язык Python в школьной информатике
14
Вывод
Через пробел
print( x, '+', y )
# 12 + 34
Без пробелов
print( x, '+', y, sep="" )
# 12+34
Без перехода на новую строку
print( 1, end=" " )
print( 2, end=" " )
print( 3, end=" " )
print( 4, end=" " )
# 1 2 3 4
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

15. Вывод: f-строки

Язык Python в школьной информатике
15
Вывод: f-строки
x, y = 12, 31.523 вычисляется
print( f"{5*5}" ) # 25
print( f"{5*x}" ) # 60
print( f"x = {x}, z = {round(y)}" )
# x = 12, z = 32
print( f"{x if x > y else y}" ) # 31.523
Форматирование чисел
x = 1.234
print( f"{5*x:0.3f}")
всего
К.Ю. Поляков, 2021
// 6.170
в дробной
части
http://kpolyakov.spb.ru

16. Функции min и max

Язык Python в школьной информатике
16
Функции min и max
a, b = map( int, input().split() )
c, d = map( int, input().split() )
mi = min( a, b, c, d )
ma = max( a, b, c, d )
print( mi, ma )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

17. Язык Python в школьной информатике Операторы управления

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

18. Условный оператор

Язык Python в школьной информатике
18
Условный оператор
if условие :
c # что делать,
#
если да
else:
# что делать,
#
если нет
!
Отступы – часть синтаксиса!
Отношения: <
<=
>
>=
Логические операции: and
К.Ю. Поляков, 2021
==
or
!=
not
http://kpolyakov.spb.ru

19. Тернарный оператор

Язык Python в школьной информатике
19
Тернарный оператор
if a < b:
c = 0
else:
c = 1
условие
c = 0 if a < b else 1
значение
«нет»
значение
«да»
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

20. Циклы с условием

Язык Python в школьной информатике
20
Циклы с условием
while условие :
c # что-то делать
# ещё что-то делать
!
Отступы – часть синтаксиса!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

21. Циклы с переменной

Язык Python в школьной информатике
21
Циклы с переменной
for x in [10, 1, 2, 15]:
# что-то делать
for x in range(10):
# что-то делать
«сделай
10 раз»
[5,6,7,8,9] 10
for x in range(5,10):
# что-то делать
!
К.Ю. Поляков, 2021
range – это генератор!
http://kpolyakov.spb.ru

22. Циклы с переменной

Язык Python в школьной информатике
22
Циклы с переменной
[5,7,9] 11
for x in range(5,11,2):
# что-то делать шаг
[11,9,7] 5
for x in range(11,5,-2):
# что-то делать
уменьшение
переменной
data = # как-то получили массив данных
for x in data:
перебор
массива
# что-то делать c x
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

23. Функции

Язык Python в школьной информатике
23
Функции
def D( x, d ):
return x % d == 0
строится
объект-функция
в памяти
def ND( x, d ): return x % d != 0
def sumDigits( x ):
s = 0
while x:
s += x % 10
x //= 10
return s
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

24. ЕГЭ-2 (демо-2021)

Язык Python в школьной информатике
24
ЕГЭ-2 (демо-2021)
Логическая функция F задаётся выражением
(x y) ¬(y z) ¬w
На рисунке приведён частично заполненный фрагмент
таблицы истинности функции F, содержащий
неповторяющиеся строки. Определите, какому столбцу
таблицы истинности функции F соответствует каждая из
переменных x, y, z, w.
?
1
0
?
1
1
?
1
1
?
0
0
F
1
1
1
zyxw
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

25. Частичная таблица истинности

Язык Python в школьной информатике
25
Частичная таблица истинности
print( "x y z w" )
b = [False, True]
for x in b:
for y in b:
(x y) ¬(y z) ¬w
for z in b:
for w in b:
if (x or y) and (y != z) \
and not w:
print( int(x), int(y),
int(z), int(w) )
x
0
1
1
y
1
0
1
z
0
1
0
w
0
0
0
К.Ю. Поляков, 2021
z
1
0
0
y
0
1
1
x
1
0
1
w
0
0
0
F
1
1
1
http://kpolyakov.spb.ru

26. Через [0, 1]

Язык Python в школьной информатике
26
Через [0, 1]
print( "x y z w" )
b = [0, 1]
for x in b:
for y in b:
for z in b:
for w in b:
if (x or y) and (y != z) \
and not w:
print( x, y, z, w )
x
0
1
1
y
1
0
1
z
0
1
0
w
0
0
0
К.Ю. Поляков, 2021
z
1
0
0
y
0
1
1
x
1
0
1
w
0
0
0
F
1
1
1
http://kpolyakov.spb.ru

27. ЕГЭ-2

Язык Python в школьной информатике
27
ЕГЭ-2
Логическая функция F задаётся выражением
((x ¬y) (w z)) (z x)
На рисунке приведён частично заполненный фрагмент
таблицы истинности функции F, содержащий
неповторяющиеся строки. Определите, какому столбцу
таблицы истинности функции F соответствует каждая из
переменных x, y, z, w.
?
0
0
?
0
1
?
0
0
?
1
0
1
F
1
1
1
zywx
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

28. ЕГЭ-25

Язык Python в школьной информатике
28
ЕГЭ-25
(С. Неретин) Пифагоровой тройка назовём
тройку чисел (a, b, c), такую что a ≤ b ≤ с и
a2+b2=c2. Найдите все пифагоровы тройки, в
которых все числа находятся в диапазоне [1;
5000]. Запишите в ответе количество подходящих
троек, а затем – значение c для тройки, в которой
сумма a+b+c максимальна.
5681 4988
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

29. Решение («пифагоровы тройки»)

Язык Python в школьной информатике
29
Решение («пифагоровы тройки»)
count, maxSum = 0, 0
for a in range(1,5000+1):
for b in range(a,5000+1):
c = round((a*a + b*b)**0.5)
if c <= 5000 and c*c == a*a+b*b:
count += 1
if a+b+c > maxSum:
maxSum = a+b+c
triple = a, b, c
print( count, triple )
5681 (3440,3612,4988)
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

30. Язык Python в школьной информатике Делимость

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

31. Делимость

Язык Python в школьной информатике
31
Делимость
a = 25
if a % 5 == 0:
print(1)
if a % 7 != 0:
print(0)
...
делится на 5
не делится на 7
1 0
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

32. Делимость: D, ND

Язык Python в школьной информатике
32
Делимость: D, ND
def D( x, d ): return x % d == 0
def ND( x, d ): return x % d != 0
a = 25
if D(a,5):
print(1)
if ND(a,7):
print(0)
...
1 0
К.Ю. Поляков, 2021
делится на 5
не делится на 7
http://kpolyakov.spb.ru

33. ЕГЭ-15 (демо-2021)

Язык Python в школьной информатике
33
ЕГЭ-15 (демо-2021)
Для какого наибольшего натурального числа А
формула
¬ДЕЛ(x,А) (ДЕЛ(x,6) ¬ДЕЛ(x,9))
тождественно истинна (то есть принимает
значение 1 при любом натуральном значении
переменной х)?
18
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

34. Решение

Язык Python в школьной информатике
34
Решение
¬ДЕЛ(x,А) (ДЕЛ(x,6) ¬ДЕЛ(x,9))
def D( x, d ): return x % d == 0
def ND( x, d ): return x % d != 0
for A in range(1,1000):
не делится на 9
OK = True
for x in range(1,1000):
if not (ND(x,A) <= (D(x,6) <= ND(x,9))):
OK = False
1
break
2
делится
на
6
if OK:
3
print( A )
6
9
18
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

35. Делимость: DivsAll, DivsAny

Язык Python в школьной информатике
35
Делимость: DivsAll, DivsAny
делится на все
a = 25
if DivsAll(a, [5, 7, 11]):
print(1)
if DivsAny(a, [5, 7, 11, 13]):
print(2)
делится хотя бы
на одно из…
2
!
Но таких функций нет!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

36. Делимость: DivsAll, DivsAny

Язык Python в школьной информатике
36
Делимость: DivsAll, DivsAny
def DivsAll( x, divs ):
for d in divs:
if x % d != 0: return False
return True
def DivsAll( x, divs ): bool
return all( x % d == 0 for d in divs )
все
истинны
К.Ю. Поляков, 2021
массив
логических
значений
http://kpolyakov.spb.ru

37. Делимость: DivsAll, DivsAny

Язык Python в школьной информатике
37
Делимость: DivsAll, DivsAny
def DivsAny( x, divs ):
for d in divs:
if x % d == 0: return True
return False
def DivsAny( x, divs ):
return any( x % d == 0 for d in divs )
хотя бы один
– истина
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

38. ЕГЭ-17

Язык Python в школьной информатике
38
ЕГЭ-17
Рассматривается множество целых чисел,
принадлежащих числовому отрезку [1016; 7937],
которые делятся на 3, 4 и 5, и не делятся на 7,
17, 19, 27. Найдите количество таких чисел,
минимальное и максимальное из них.
77 1200 7920
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

39. Решение

Язык Python в школьной информатике
39
Решение
последний не
входит
count, mi, ma = 0, 0, 0
+1
for x in range(1016,7937+1):
if DivsAll(x, [3, 4, 5]) and \
not DivsAny(x, [7, 17, 19, 27]):
count += 1
if mi == 0: mi = x
ma = x
print( count, mi, ma
К.Ю. Поляков, 2021
)
http://kpolyakov.spb.ru

40. ЕГЭ-17

Язык Python в школьной информатике
40
ЕГЭ-17
(Е. Джобс) Рассматривается множество целых
чисел, принадлежащих числовому отрезку
[25552; 58885], которые имеют не менее 15
двузначных делителей. Найдите наименьшее и
наибольшее из таких чисел, а также их
количество.
25650 58800 420
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

41. Решение

Язык Python в школьной информатике
41
Решение
count, mi, ma = 0, 0, 0
for x in range(25552, 58885+1):
двузначные
dCount = 0
10,100
for d in range(10,100):
if x % d == 0: dCount += 1
if dCount >= 15:
count += 1
if mi == 0: mi = x
ma = x
print( mi, ma, count
К.Ю. Поляков, 2021
)
http://kpolyakov.spb.ru

42. Язык Python в школьной информатике Длинная арифметика

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

43. Длинные числа

Язык Python в школьной информатике
43
Длинные числа
Задача. Найти 100! = 1·2·3·…·99·100
p = 1
for i in range(2,100+1):
p *= i
print( "100!=", p )
100!=933262154439441526816992388562667004
90715968264381621468592963895217599993229
91560894146397615651828625369792082722375
8251185210916864000000000000000000000000
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

44. ЕГЭ-14

Язык Python в школьной информатике
44
ЕГЭ-14
Сколько значащих нулей в двоичной записи
числа
4512 + 8512 – 2128 – 250
519
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

45. Решение

Язык Python в школьной информатике
45
Решение
x = 4**512 + 8**512 - 2**128 - 250
print( bin(x)[2:].count('0') )
x = 19
bin(x) = '0b10011'
bin(x)[2:] = '10011'
bin(x)[2:].count('0') = 2
x = 4**512 + 8**512 - 2**128 - 250
print( f"{x:b}".count('0') )
519
К.Ю. Поляков, 2021
двоичная
запись
http://kpolyakov.spb.ru

46. ЕГЭ-14

Язык Python в школьной информатике
46
ЕГЭ-14
Значение арифметического выражения:
497 + 721 – 7
записали в системе счисления с основанием 7.
Сколько цифр 6 содержится в этой записи?
13
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

47. Решение

Язык Python в школьной информатике
47
Решение
x = 49**7 + 7**21 - 7
count = 0
while x > 0:
if x % 7 == 6: count += 1
# count += 1 if x % 7 == 6 else 0
# count += int(x % 7 == 6)
# count += (x % 7 == 6)
x //= 7
print( count )
13
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

48. ЕГЭ-14

Язык Python в школьной информатике
48
ЕГЭ-14
Значение выражения
52004 – 51016 – 25508 – 5400 + 25250 – 27
записали в пятеричной системе счисления.
Найдите сумму цифр в такой записи.
5948
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

49. Решение

Язык Python в школьной информатике
49
Решение
x = 5**2004 - 5**1016 \
- 25**508 - 5**400 + 25**250 - 27
s = 0
while x:
s += x % 5
x //= 5
print( s )
5948
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

50. Язык Python в школьной информатике Функции

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

51. Определения функций

Язык Python в школьной информатике
51
Определения функций
def D( x, d ):
return x % d == 0
def sign( x ):
if x < 0: return -1
elif x == 0: return 0
else: return 1
return -1 if x < 0 else \
0 if x == 0 else \
1
print( sign(-3), sign(0), sign(15) )
-1 0 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

52. ЕГЭ-5

Язык Python в школьной информатике
52
ЕГЭ-5
На вход алгоритма подаётся натуральное
число N. Алгоритм строит по нему число R:
1. Строится двоичная запись числа N.
2. Справа дописывается бит чётности.
3. Справа дописывается её один бит чётности.
Укажите такое наименьшее число N, для
которого результат работы данного
алгоритма больше числа 80.
21
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

53. Решение

Язык Python в школьной информатике
53
Решение
def alg( n ):
b = f"{n:b}"
b += '0' if b.count('1') % 2 == 0 else '1'
b += '0'
return int(b, 2)
b += str(b.count('1')%2)
n = 1
while alg(n) <= 80:
n += 1
print( n )
21
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

54. ЕГЭ-16

Язык Python в школьной информатике
54
ЕГЭ-16
Алгоритм вычисления функции F(n) задан
следующими соотношениями:
F(n) = 1 при n = 1
F(n) = n + F(n–1), если n чётно,
F(n) = 2· F(n–2), если n > 1 и n нечётно.
Чему равно значение функции F(26)?
4122
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

55. Решение

Язык Python в школьной информатике
55
Решение
def F( n ):
if n == 1: return 1
elif n % 2 == 0: return n + F(n-1)
else: return 2*F(n-2)
print( F(26) )
4122
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

56. Решение

Язык Python в школьной информатике
56
Решение
def F( n ):
return 1 if n == 1 else \
n + F(n-1) if n % 2 == 0 else \
2*F(n-2)
print( F(26) )
4122
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

57. ЕГЭ-16

Язык Python в школьной информатике
57
ЕГЭ-16
Алгоритм вычисления функции F(n), где n –
натуральное число, задан следующими
соотношениями:
F(1) = 1,
F(n) = F(n / 2) + 1, когда n 2 и чётное,
F(n) = F(n – 1) + n , когда n 2 и нечётное.
Назовите количество значений n на отрезке
[1;100000], для которых F(n) равно 16.
5
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

58. Решение

Язык Python в школьной информатике
58
Решение
def F( n ):
return 1 if n == 1 else \
F(n // 2) + 1 if n % 2 == 0 else \
F(n-1) + n
count = 0
for n in range(1,100000+1):
if F(n) == 16:
count += 1
print( count )
5
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

59. ЕГЭ-16

Язык Python в школьной информатике
59
ЕГЭ-16
Алгоритм вычисления функции F(n), где n –
натуральное число, задан следующим образом:
F(n) = n, при n 5,
F(n) = n + F(n / 5+1), когда n > 5 и делится на 5,
F(n) = n + F(n+6) , когда n > 5 и не делится на 5.
Найдите минимальное значение n, для которого
F(n) определено и больше 1000.
131
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

60. Решение

Язык Python в школьной информатике
60
Решение
def F( n, nest ):
return -10**10 if nest
nest > 100 else \
n if n <= 5 else \
n + F(n//5+1, nest+1
nest+1) \
if n % 5 == 0 else \
n + F(n + 6, nest+1 )
n = 6
while F(n, 0) <= 1000:
n += 1
print( n )
131
К.Ю. Поляков, 2021
!
nest – уровень
вложенности!
http://kpolyakov.spb.ru

61. ЕГЭ-23 (демо-2021)

Язык Python в школьной информатике
61
ЕГЭ-23 (демо-2021)
У исполнителя есть две команды:
1. Прибавить 1
2. Умножить на 2
Сколько существует программ, для которых при
исходном числе 1 результатом является число 20,
и при этом траектория вычислений содержит
число 10?
28
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

62. Решение

Язык Python в школьной информатике
62
Решение
def F( fromN, toN ):
return 0 if fromN > toN else \
1 if fromN == toN else \
F(fromN+1, toN) + F(fromN*2, toN)
print( F(1,10)*F(10,20) )
28
К.Ю. Поляков, 2021
команды
здесь!
http://kpolyakov.spb.ru

63. ЕГЭ-23

Язык Python в школьной информатике
63
ЕГЭ-23
У исполнителя есть две команды:
1. Прибавить 1
2. Умножить на 2
Сколько существует программ, для которых при
исходном числе 1 результатом является число 30,
и при этом траектория вычислений содержит
число 10 и не содержит числа 5.
42
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

64. Решение

Язык Python в школьной информатике
64
Решение
def F( fromN, toN ):
return 0 if fromN > toN else \
0 if fromN == 5 else \
1 if fromN == toN else \
F(fromN+1, toN) + F(fromN*2, toN)
print( F(1,10)*F(10,30) )
42
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

65. ЕГЭ-23

Язык Python в школьной информатике
65
ЕГЭ-23
У исполнителя Калькулятор есть три команды,
которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Сколько существует программ, которые
преобразуют исходное число 5 в число 26, и при
этом траектория вычислений содержит число 11 и
не содержит чисел 13 и 15?
1157
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

66. Решение

Язык Python в школьной информатике
66
Решение
def F( fromN, toN ):
return 0 if fromN > toN else \
0 if fromN in [13,15] else \
1 if fromN == toN else \
F(fromN+1, toN) + F(fromN+2, toN) \
+ F(fromN*3, toN)
print( F(5,11)*F(11,26) )
1157
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

67. Простые числа

Язык Python в школьной информатике
67
Простые числа
Составить функцию, которая для заданного
натурального числа возвращает True, если оно
простое, и False, если составное.
def isPrime( x ):
for d in range(2,x):
if x % d == 0:
return False
return True
!
Долго для 200000000!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

68. Как ускорить?

Язык Python в школьной информатике
68
Как ускорить?
a b x
a a x
a x
К.Ю. Поляков, 2021
a b
!
Перебирать до
x!
http://kpolyakov.spb.ru

69. Простые числа

Язык Python в школьной информатике
69
Простые числа
def isPrime( x ):
for d in range(2, round(x**0.5)+1 ):
if x % d == 0:
return False
return True
def isPrime( x ):
return all( x % d != 0
for d in range(2, round(x**0.5)+1) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

70. ЕГЭ-25

Язык Python в школьной информатике
70
ЕГЭ-25
(Д.Ф. Муфаззалов) Определите количество
простых чисел в диапазоне [2; 357700].
30580
count = 0
for x in range(2,357700+1):
if isPrime(x):
count += 1
print( count )
print( len([x for x in range(2,357701)
if isPrime(x)]) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

71. ЕГЭ-25

Язык Python в школьной информатике
71
ЕГЭ-25
(Б.С. Михлин) Напишите программу, которая
ищет среди целых чисел, принадлежащих
числовому отрезку [194441; 196500] простые
числа, оканчивающиеся на 93.
195193
195493
195593
195893
196193
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

72. Решение

Язык Python в школьной информатике
72
Решение
for x in range(194441,196500+1):
if x % 100 == 93 and isPrime(x):
print(x)
195193
195493
195593
195893
196193
К.Ю. Поляков, 2021
?
Как ускорить?
http://kpolyakov.spb.ru

73. Решение

Язык Python в школьной информатике
73
Решение
for x in range(194493,196500+1,100):
93
100
if isPrime(x):
print(x)
195193
195493
195593
195893
196193
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

74. Язык Python в школьной информатике Массивы (списки)

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

75. Массивы (списки)

Язык Python в школьной информатике
75
Массивы (списки)
• нумерация элементов с нуля
• можно определить длину
• легко передавать в подпрограмму
Списки в Python:
• могут содержать данные разных типов и
размеров
• можно добавлять и удалять элементы
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

76. Массивы и списки

Язык Python в школьной информатике
76
Массивы и списки
Массивы в Паскале, С++:
A[0]
!
A[1]
A[2]
A[3]
A[4]
A[5]
Доступ по индексу к ЗНАЧЕНИЮ!
Списки в Python:
A[0]
A[1]
A[2]
!
К.Ю. Поляков, 2021
A[3]
A[4]
A[5]
Доступ по индексу к ССЫЛКЕ!
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
77
Создание массивов
A = [1, 23, 4, 56, 8]
B = [0]*5 # [0, 0, 0, 0, 0]
for i in range(5):
генератор списка (list
B[i] = i + 8
comprehension)
# или так
B = [ i+8 for i in range(5) ]
выделить
память и
заполнить
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
78
Создание массивов
C = []
# пустой массив
for i in range(10):
C[i] = i*i
!
Не выделена память!
C = []
# пустой массив
for i in range(10):
C.append( i*i ) # C += [i*i]
добавить в
конец
массива
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

79. Ввод элементов массивов по одному

Язык Python в школьной информатике
79
Ввод элементов массивов по одному
Массив целых чисел
N = 5
A = []
for i in range(N):
x = int(input())
A.append( x )
A.append(int(input()))
N = 5
A = [ int(input())
for i in range(N) ]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

80. Ввод массивов из одной строки

Язык Python в школьной информатике
80
Ввод массивов из одной строки
Массив слов
s = input()
A = s.split()
A = input().split()
Массив целых чисел
s = input()
A = list( map(int, s.split()) )
<map object at 0x0132E5D0>
генератор
последовательности
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

81. Ввод массивов из одной строки

Язык Python в школьной информатике
81
Ввод массивов из одной строки
Массив целых чисел
генератор
списка
s = input()
A = [int(x) for x in s.split()]
Массив вещественных чисел
A = [float(x)
for x in input().split()]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
82
Заполнение случайными числами
Массив целых чисел
from random import randint
N = 5
A = []
for i in range(N):
A.append( randint(1,100) )
from random import randint
N = 5
A = [ randint(1,100)
for i in range(N) ]
К.Ю. Поляков, 2021
генератор
списка
http://kpolyakov.spb.ru

83. Вывод массивов

Язык Python в школьной информатике
83
Вывод массивов
A = [1, 23, 4, 56, 8]
print( A ) # [1, 23, 4, 56, 8]
print( *A ) # 1 23 4 56 8
for x in A:
print( x )
1
23
4
56
8
К.Ю. Поляков, 2021
for x in A:
print( x, end=" " )
print()
1 23 4 56 8
http://kpolyakov.spb.ru

84. Вывод массивов с номером

Язык Python в школьной информатике
84
Вывод массивов с номером
A = [1, 23, 4, 56, 8]
for i, x in enumerate(A):
print( i, "->", x )
0
1
2
3
4
->
->
->
->
->
1
23
4
56
8
К.Ю. Поляков, 2021
кортежи
(номер, значение)
(0,1) (1,23) (2,4) (3,56) (4,8)
i x
i x
i x
i x
i x
http://kpolyakov.spb.ru

85. Срезы массивов

Язык Python в школьной информатике
85
Срезы массивов
0
1
2
3
4
5
A = [ 2, 5, 3, 1, 8, 6 ]
последний не входит!
print(
print(
print(
print(
print(
print(
*A[1:3] )
*A[:3] )
*A[4:] )
*A[1::2] )
*A[::-1] )
*A[2:-2] )
#
#
#
#
#
#
5
2
8
5
6
3
3
5 3
6
1 6
8 1 3 5 2
1
2-й с конца
print( *A[-2:] )
#
8 6
последние 2
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

86. Удаление элементов списка

Язык Python в школьной информатике
86
Удаление элементов списка
A = [5, 75, 12, 27, 32, 40]
x = A.pop()
y = A.pop(1)
del A[1]
# 40 [5, 75, 12, 27, 32]
# 75 [5, 12, 27, 32]
# [5, 27, 32] удалить по индексу
A.remove(27) # [5, 32] удалить по значению
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

87. Массивы: функции

Язык Python в школьной информатике
87
Массивы: функции
0
1
2
3
4
5
A = [ 2, 5, 3, 1, 8, 6 ]
print(
print(
print(
print(
print(
print(
print(
print(
len(A) )
min(A) )
max(A) )
sum(A) )
A.index(
A.index(
A.index(
A.index(
К.Ю. Поляков, 2021
# 6
# 1
# 8
# 25
min(A) ) )
max(A) ) )
1 ) )
11 ) )
#
#
#
#
3
4
3
Value error
http://kpolyakov.spb.ru

88. ЕГЭ-24

Язык Python в школьной информатике
88
ЕГЭ-24
Файл input.txt содержит только заглавные
латинские буквы. Определите, какая буква
встречается в этом файле чаще всего и сколько
раз она встретилась. Если таких букв несколько
выведите первую по алфавиту.
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

89. Решение

Язык Python в школьной информатике
89
Решение
with open("24-s2.txt") as F:
s = F.readline()
counters = [0]*26
номер буквы
(0 – A, 1 – B, …)
for c in s:
counters[ord(c)-ord('A')] += 1
maxCnt = max(counters)
code = counters.index(maxCnt) + ord('A')
print( chr(code), maxCnt )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

90. Все делители

Язык Python в школьной информатике
90
Все делители
Составить функцию, которая возвращает все
делители заданного натурального числа.
def Divisors( x ):
divs = [ d for d in range(1,x+1)
if x % d == 0]
return divs
!
Долго для 200000000!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

91. Как ускорить?

Язык Python в школьной информатике
91
Как ускорить?
a b x
a a x
a x
a b
!
Перебирать до x
и добавлять сразу два
делителя
Особый случай: полный квадрат (a = b).
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

92. Все делители

Язык Python в школьной информатике
92
Все делители
def Divisors( x ):
divs = [1, x]
q = round(x**0.5)
if q*q == x:
divs.append(q)
for d in range(2,q):
if x % d == 0:
divs += [ d, x//d ]
return sorted(divs)
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

93. ЕГЭ-17

Язык Python в школьной информатике
93
ЕГЭ-17
(Е. Джобс) Рассматривается множество целых
чисел, принадлежащих числовому отрезку
[25552; 58885], которые имеют не менее 15
двузначных делителей. Найдите наименьшее и
наибольшее из таких чисел, а также их
количество.
25650 58800 420
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

94. Решение

Язык Python в школьной информатике
94
Решение
count, mi, ma = 0, 0, 0
for x in range(25552, 58885+1):
divs = [d for d in Divisors(x)
if 10 <= d < 100]
if len(divs) >= 15:
count += 1
if mi == 0: mi = x
ma = x
print( mi, ma, count )
25650 58800 420
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

95. ЕГЭ-25

Язык Python в школьной информатике
95
ЕГЭ-25
(Е. Джобс) Среди целых чисел, принадлежащих
числовому отрезку [135790; 163228], найдите
числа, для которых сумма нетривиальных
делителей (не включающих 1 и само число)
больше 460000. Для каждого найденного числа
запишите количество нетривиальных делителей и
их сумму.
142 473759
118 462767
126 464999
118 461969
118 477071
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

96. Решение

Язык Python в школьной информатике
96
Решение
for x in range(135790, 163228+1):
divs = Divisors(x)[1:-1]
убрать
1иx
if sum(divs) > 460000:
print( len(divs), sum(divs) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

97. ЕГЭ-25

Язык Python в школьной информатике
97
ЕГЭ-25
Среди целых чисел, принадлежащих отрезку
[174457; 174505], найдите числа, имеющие ровно
два различных натуральных делителя, не считая
единицы и самого числа. Для каждого найденного
числа запишите эти два делителя в порядке
возрастания.
3 58153
7 24923
59 2957
...
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

98. Решение

Язык Python в школьной информатике
98
Решение
for x in range(174457, 174505+1):
divs = Divisors(x)[1:-1]
if len(divs) == 2:
убрали первый и
print( *divs )
последний
3 58153
7 24923
59 2957
...
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

99. ЕГЭ-25

Язык Python в школьной информатике
99
ЕГЭ-25
Рассматриваются целые числа, принадлежащих
числовому отрезку [631632; 685934], которые
представляют собой произведение двух
различных простых делителей. Найдите такое
из этих чисел, у которого два простых делителя
больше всего отличаются друг от друга.
Запишите найденное число и разность его
простых делителей.
685898 342947
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

100. Решение

Язык Python в школьной информатике
100
Решение
maxDiff = 0
for x in range(631632,685934+1):
divs = Divisors(x)[1:-1]
if len(divs) == 2 and \
divs[1] - divs[0] > maxDiff:
maxDiff = divs[1] - divs[0]
divsMax = divs
print( divsMax[0]*divsMax[1],
divsMax[1]-divsMax[0] )
685898 342947
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

101. ЕГЭ-25

Язык Python в школьной информатике
101
ЕГЭ-25
Найдите все натуральные числа, принадлежащие
отрезку [289123456; 389123456] и имеющие
ровно три нетривиальных делителя. Для
каждого найденного числа запишите в ответе его
наибольший нетривиальный делитель.
2248091
2571353
2685619
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

102. Решение

Язык Python в школьной информатике
102
Решение
for x in range(289123456,389123456+1):
divs = Divisors(x)[1:-1]
очень большие
if len(divs) == 3:
числа!
print( divs[-1] )
?
Как уcкорить?
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

103. Только полные квадраты

Язык Python в школьной информатике
103
Только полные квадраты
Три (нечётное число) нетривиальных делителя –
полный квадрат!
from math import ceil
for x in range( int(289123456**0.5),
ceil(389123456**0.5)+1):
divs = Divisors(x*x)[1:-1]
x*x
if len(divs) == 3:
print( divs[-1] )
2248091
2571353
2685619
К.Ю. Поляков, 2021
?
Как ещё уcкорить?
http://kpolyakov.spb.ru

104. Основная теорема арифметики

Язык Python в школьной информатике
104
Основная теорема арифметики
Любое число единственным способом
представляется в виде произведения простых
чисел:
km
k1 k2
1
2
m
Число нетривиальных делителей:
n p p
(k1 1)(k2 1)
Если = 3:
p
(km 1) 2
(k1 1)(k2 1) (km 1) 5
k1 4, k2 k3 km 0
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

105. Чётвертые степени простых чисел

Язык Python в школьной информатике
105
Чётвертые степени простых чисел
from math import ceil
for x in range( int(289123456**0.25),
ceil(389123456**0.25)+1):
if isPrime(x) :
print( x*x*x )
2248091
2571353
2685619
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

106. ЕГЭ-23

Язык Python в школьной информатике
106
ЕГЭ-23
У исполнителя есть две команды:
1. Прибавь 1
2. Умножь на 2 и прибавь 1
Сколько различных результатов можно получить из
исходного числа 3 после выполнения программы,
содержащей ровно 11 команд?
820
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

107. Решение

Язык Python в школьной информатике
107
Решение
def F( fromN, steps ):
все
возможные
if steps == 0:
результаты
return [fromN]
else:
return F( fromN+1, steps-1 ) + \
F( fromN*2+1, steps-1 )
print( len(set(F(3,11))) )
820
К.Ю. Поляков, 2021
убираем
одинаковые
http://kpolyakov.spb.ru

108. Язык Python в школьной информатике Операции с массивами

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

109. Фильтрация (отбор нужных)

Язык Python в школьной информатике
109
Фильтрация (отбор нужных)
A = [ 1, 2, 3, 4, 5, 6 ]
B = [x for x in A
if x > 3 ]
print( *B )
# 4 5 6
print( len(B) )
# 3
Делятся на 3:
A = [ 11, 21, 32, 43, 54, 61 ]
B = [x for x in A
if x % 3 == 0 ]
print( *B )
# 21 54
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

110. Фильтрация (отбор нужных)

Язык Python в школьной информатике
110
Фильтрация (отбор нужных)
Оканчиваются на 1:
A = [ 11, 21, 32,
B = [x for x in A
print( *B )
#
print( sum(B) ) #
43, 54, 61 ]
if x % 10 == 1 ]
11 21 61
93
A = [ 11, 21, 32, 43, 54, 61 ]
print( sum(x for x in A if x % 10 == 1) )
# 93
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

111. Преобразование

Язык Python в школьной информатике
111
Преобразование
Возведение в квадрат:
A = [ 1, 2, 3, 4, 5, 6 ]
B = [ x*x for x in A ]
print( *B )
# 1 4 9 ... 36
Последняя цифра:
A = [ 11, 21, 32, 43, 54, 61 ]
B = [ x % 10 for x in A ]
print( *B )
# 1 1 2 …
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

112. Преобразование

Язык Python в школьной информатике
112
Преобразование
Различные последние цифры:
A = [ 11, 21, 32, 43, 54, 61 ]
B = set( x % 10 for x in A )
print( *B ) # 1 2 3 4
set() – множество, одинаковые элементы
не допускаются
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

113. Преобразование к другому типу

Язык Python в школьной информатике
113
Преобразование к другому типу
В символы:
A = [ 0, 1, 2, 3, 4, 5 ]
B = [ chr(x+65) for x in A ]
print( *B )
# A B C D E F
Из символов в целые:
A = [ 'a', 'b', 'c', 'd', 'e', 'f' ]
B = [ ord(x) for x in A ]
print( *B ) # 97 98 99 100 101 102
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

114. Преобразование в кортеж

Язык Python в школьной информатике
114
Преобразование в кортеж
Кортеж – «неизменяемая запись»:
A = [ 'a', 'b', 'c', 'd', 'e', 'f' ]
B = [ (x,
(x, ord(x))
ord(x)) for x in A ]
print( *B )
# (a,97) (b,98) (c,99) ... (f,102)
(x,ord(x))
кортеж
К.Ю. Поляков, 2021
1) сохранить
исходные данные
2) добавить что-то к
каждому
http://kpolyakov.spb.ru

115. Преобразование в кортеж

Язык Python в школьной информатике
115
Преобразование в кортеж
В кортеж (число, список делителей):
A = range(15,21)
B = [ (x, Divisors(x)) for x in A ]
print( *B )
(15,[1,3,5,15]) (16,[1,2,4,8,16])
(17,[1,17]) (18,[1,2,3,6,9,18])
(19,[1,19]) (20,[1,2,4,5,10,20])
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

116. Проверка условия для всех

Язык Python в школьной информатике
116
Проверка условия для всех
все
список
A = [ 11, 21, 32, 43, 54, 61 ]
print( all([x > 20 for x in A]) ) # False
print( any( x > 20 for x in A ) ) # True
хотя бы
один
К.Ю. Поляков, 2021
генератор
http://kpolyakov.spb.ru

117. Язык Python в школьной информатике Перебор

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

118. ЕГЭ-17

Язык Python в школьной информатике
118
ЕГЭ-17
Рассматривается множество целых чисел,
принадлежащих числовому отрезку [1016; 7937],
которые делятся на 3, 4 и 5, и не делятся на 7,
17, 19, 27. Найдите количество таких чисел,
минимальное и максимальное из них.
77 1200 7920
def DivsAll( x, divs ):
return all( x % d == 0 for d in divs )
def DivsAny( x, divs ):
return any( x % d == 0 for d in divs )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

119. Решение (уже было)

Язык Python в школьной информатике
119
Решение (уже было)
count, mi, ma = 0, 0, 0
for x in range(1016, 7937+1):
if DivsAll(x, [3,4,5]) and \
not DivsAny(x, [7,17,19,27]):
count += 1
if not mi: mi = x
ma = x
print( count, mi, ma )
77 1200 7920
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

120. Решение (новое)

Язык Python в школьной информатике
120
Решение (новое)
Q = [ x for x in range(1016, 7937+1)
if DivsAll(x, [3,4,5]) and \
not DivsAny(x, [7,17,19,27]) ]
print( len(Q), min(Q), max(Q) )
77 1200 7920
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

121. ЕГЭ-17

Язык Python в школьной информатике
121
ЕГЭ-17
(П. Волгин) Рассматривается множество целых
чисел, принадлежащих числовому отрезку [697;
3458], которые удовлетворяют следующим
условиям:
а) Число в шестнадцатеричной записи
оканчивается цифрой «E»;
б) Число в семеричной записи и в восьмеричной
записи оканчивается на одну цифру.
Найдите сумму таких чисел и их количество.
51950 25
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

122. Решение

Язык Python в школьной информатике
122
Решение
Q = [ x for x in range(697,3458+1)
if x % 16 == 14 and \
x % 7 == x % 8 ]
print( sum(Q), len(Q) )
51950 25
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

123. ЕГЭ-17

Язык Python в школьной информатике
123
ЕГЭ-17
(А.Н. Носкин) Рассматривается множество целых
чисел, принадлежащих числовому отрезку [9999;
15346], которые кратны сумме своих цифр.
Найдите количество таких чисел и такое из них,
сумма цифр которого максимальна.
876 13888
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

124. Решение

Язык Python в школьной информатике
124
Решение
count, maxSd, ma = 0, 0, 0
for x in range(9999, 15346+1):
sd = sum( map(int, str(x)) )
if x % sd == 0:
Сумма цифр:
count += 1
x = 123
if sd > maxSd:
str(x): "123"
map(int, str(x)):
maxSd = sd
(1, 2, 3)
ma = x
sum(...): 6
print( count, ma )
876 13888
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

125. ЕГЭ-15

Язык Python в школьной информатике
125
ЕГЭ-15
Для какого наибольшего натурального числа А
формула
ДЕЛ(x,10) ДЕЛ(x,A)
тождественно истинна?
10
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

126. ЕГЭ-15

Язык Python в школьной информатике
126
ЕГЭ-15
ДЕЛ(x,10) ДЕЛ(x,A)
def D(x, d): return x % d == 0
AA = range(1, 1000+1)
XX = range(1, 1000+1)
for A in AA:
allOK = True
for x in XX:
allOK = allOK and D(x,10)
D(x,10) <=
<= D(x,A)
D(x,A)
if allOK:
print( A )
10
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

127. ЕГЭ-15

Язык Python в школьной информатике
127
ЕГЭ-15
ДЕЛ(x,10) ДЕЛ(x,A)
def D(x, d): return x % d == 0
AA = range(1, 1000+1)
XX = range(1, 1000+1)
for A in AA:
if all(
all( D(x,10)
D(x,10) <=
<= D(x,A)
D(x,A)
if
x in
forfor
x in
XX XX
): ):
print( A )
10
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

128. ЕГЭ-15 (с функцией)

Язык Python в школьной информатике
128
ЕГЭ-15 (с функцией)
ДЕЛ(x,10) ДЕЛ(x,A)
def D(x, d): return x % d == 0
def valid( A ):
return all( D(x,10) <= D(x,A)
for x in XX )
AA = range(1, 1000+1)
XX = range(1, 1000+1)
for A in AA:
if valid( A ): print( A )
10
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

129. ЕГЭ-15

Язык Python в школьной информатике
129
ЕГЭ-15
ДЕЛ(x,10) ДЕЛ(x,A)
def D(x, d): return x % d == 0
def valid( A ):
return all( D(x,10) <= D(x,A)
for x in XX )
Все подходящие
AA = range(1, 1000+1)
A записать в R
XX = range(1, 1000+1)
R = [ A for A in AA if valid(A) ]
print( max(R) )
10
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

130. ЕГЭ-15 (демо-2021)

Язык Python в школьной информатике
130
ЕГЭ-15 (демо-2021)
Для какого наибольшего натурального числа А
формула
¬ДЕЛ(x,А) (ДЕЛ(x,6) ¬ДЕЛ(x,9))
тождественно истинна при всех натуральных x?
18
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

131. Решение

Язык Python в школьной информатике
131
Решение
¬ДЕЛ(x,А) (ДЕЛ(x,6) ¬ДЕЛ(x,9))
def D(x, d): return x % d == 0
def ND(x, d): return x % d != 0
def valid( A ):
return all(
ND(x,A) <= (D(x,6) <= ND(x,9))
for x in XX )
AA = XX = range(1, 1000+1)
R = [ A for A in AA if valid(A) ]
print( max(R) )
18
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

132. ЕГЭ-15

Язык Python в школьной информатике
132
ЕГЭ-15
Для какого наименьшего натурального числа A
формула
ДЕЛ(A,3)
(ДЕЛ(220,x) → (¬ДЕЛ(A,x) → ¬ДЕЛ(550,x)))
тождественно истинна при всех натуральных x?
330
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

133. Решение

Язык Python в школьной информатике
133
Решение
ДЕЛ(A,3)
(ДЕЛ(220,x) → (¬ДЕЛ(A,x) → ¬ДЕЛ(550,x)))
def D(x, d): return x % d == 0
def ND(x, d): return x % d != 0
def valid( A ):
return all( D(A,3) and
(D(220,x) <= (ND(A,x) <= ND(550,x)))
for x in XX )
AA = XX = range(1, 1000+1)
R = [ A for A in AA if valid(A) ]
print( min(R) )
К.Ю. Поляков, 2021
330
http://kpolyakov.spb.ru

134. ЕГЭ-15

Язык Python в школьной информатике
134
ЕГЭ-15
(В. Шубинкин) Для какого наименьшего
натурального числа A формула
((ДЕЛ(x, A) ДЕЛ(x, 45)) ДЕЛ(x, 162)) ( A > 200)
тождественно истинна (то есть принимает
значение 1 при любом натуральном значении
переменной х)?
324
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

135. Решение

Язык Python в школьной информатике
135
Решение
((ДЕЛ(x, A) ДЕЛ(x, 45)) ДЕЛ(x, 162)) (A > 200)
def D(x, d): return x % d == 0
def valid( A ):
return all(
(D(x,A) and D(x,45)) <= D(x,162)
for x in XX )
AA = range(201, 1000+1)
XX = range(1, 20000 + 1)
R = [ A for A in AA if valid(A) ]
print( min(R) )
324
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

136. ЕГЭ-15 (поразрядное И)

Язык Python в школьной информатике
136
ЕГЭ-15 (поразрядное И)
Для какого наименьшего натурального числа A
формула
(X & 107 = 0) ((X & 55 0) (X & A 0))
тождественно истинна?
20
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

137. Решение

Язык Python в школьной информатике
137
Решение
(X & 107 = 0) ((X & 55 0) (X & A 0))
def valid( A ):
return all(
(x & 107
((x & 55
for x
==
!=
in
0)
0)
XX
<=
<= (x & A != 0))
)
AA = XX = range(1, 1000+1)
R = [ A for A in AA if valid(A) ]
print( min(R) )
20
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

138. Комбинаторика: декартово произведение

Язык Python в школьной информатике
138
Комбинаторика: декартово произведение
R = [1, 2, 3]
каждый с
каждым!
for x in R:
for y in R:
print( (x, y), end=" " )
(1, 1) (1, 2) (1, 3) (2, 1) (2, 2)
(2, 3) (3, 1) (3, 2) (3, 3)
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

139. Комбинаторика: декартово произведение

Язык Python в школьной информатике
139
Комбинаторика: декартово произведение
from itertools import product
prod = product( [1,2,3], repeat=2 )
print( prod )
каждый с каждым!
<itertools.product object at 0x0133A8F0>
for p in prod:
print( p, end=" " )
(1, 1) (1, 2) (1, 3) (2, 1) (2, 2)
(2, 3) (3, 1) (3, 2) (3, 3)
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

140. ЕГЭ-15

Язык Python в школьной информатике
140
ЕГЭ-15
Укажите наибольшее целое значение А, при
котором выражение
(y + 5x 80) ∨ (3x > A) ∨ (y > A)
истинно для любых целых положительных x и y.
29
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

141. ЕГЭ-15

Язык Python в школьной информатике
141
ЕГЭ-15
(y + 5x 80) ∨ (3x > A) ∨ (y > A)
from itertools import product
def valid( A ):
return all(
(y+5*x != 80) or (3*x > A) or (y > A)
for x, y in product(XY, repeat=2) )
AA = range(1, 200+1)
XY = range(1, 500+1)
R = [ A for A in AA if valid(A) ]
print( max(R) )
29
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

142. ЕГЭ-15

Язык Python в школьной информатике
142
ЕГЭ-15
Укажите наименьшее целое значение А, при
котором выражение
(2y + 4x < A) ∨ (x + 2y > 80)
истинно для любых неотрицательных x и y.
321
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

143. Решение

Язык Python в школьной информатике
143
Решение
from itertools import product
def valid( A ):
return all(
(2*y + 4*x < A) or (x + 2*y > 80)
for x, y in product(XY, repeat=2)
AA = range(1, 500+1)
XY = range(0, 200+1)
R = [ A for A in AA if valid(A) ]
print( min(R) )
321
К.Ю. Поляков, 2021
Перебираем дальше,
когда уже нашли
минимальное!
?
)
Что плохо?
http://kpolyakov.spb.ru

144. Решение (до первого)

Язык Python в школьной информатике
144
Решение (до первого)
from itertools import product
def valid( A ):
return all(
(2*y + 4*x < A) or (x + 2*y > 80)
for x, y in product(XY, repeat=2)
AA = range(1, 500+1)
XY = range(0, 200+1)
for A in AA:
if valid(A):
print( A )
НЕ перебираем
дальше, когда уже
break
)
нашли минимальное!
321
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

145. ЕГЭ-16

Язык Python в школьной информатике
145
ЕГЭ-16
Алгоритм вычисления функции F(n), где n –
натуральное число, задан следующими
соотношениями:
F(1) = 1,
F(n) = F(n / 2) + 1, когда n 2 и чётное,
F(n) = F(n – 1) + n , когда n 2 и нечётное.
Назовите количество значений n на отрезке
[1;100000], для которых F(n) равно 16.
5
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

146. Решение

Язык Python в школьной информатике
146
Решение
def F( n ):
return 1 if n == 1 else \
F(n//2) + 1 if n % 2 == 0 else \
F(n-1) + n
A = [ n for n in range(1,100000+1)
if F(n) == 16 ]
print( len(A) )
5
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

147. ЕГЭ-5

Язык Python в школьной информатике
147
ЕГЭ-5
На вход алгоритма подаётся натуральное
число N. Алгоритм строит по нему число R:
1. Строится двоичная запись числа N.
2. Запись разворачивается «задом наперёд».
3. Если в полученной записи чётное число
единиц, справа дописывается 0, иначе справа
дописывается 1.
5Укажите наименьшее число R > 45, которое
может быть получено в результате работы
данного алгоритма.
46
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

148. Решение

Язык Python в школьной информатике
148
Решение
def alg( n ):
b = bin(n)[2:]
b = f"{n:b}"
b = b[::-1]
b += str( b.count('1') % 2 )
return int(b, 2)
R = [ alg(n) for n in range(1,1000)
if alg(n) > 45 ]
print( min(R) )
Немонотонность alg(n)!
46
К.Ю. Поляков, 2021
?
Почему не до первого?
http://kpolyakov.spb.ru

149. ЕГЭ-5

Язык Python в школьной информатике
149
ЕГЭ-5
(С. Скопинцева) Алгоритм преобразует натуральное
число N в новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дважды справа дописывается один
разряд по следующему правилу: если количество единиц
в двоичной записи числа больше количества нулей, то
справа дописывается единица, иначе дописывается 0.
Полученная таким образом запись (в ней на два разряда
больше, чем в записи исходного числа N) является
двоичной записью искомого числа R. Укажите
наибольшее число R, меньшее 57, которое может быть
получено в результате работы данного алгоритма.
55
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

150. Решение

Язык Python в школьной информатике
150
Решение
def alg( n ):
b = f"{n:b}"
b += '1' if b.count('1') > b.count('0') \
else '0'
b += '1' if b.count('1') > b.count('0') \
else '0'
return int(b, 2)
R = [ alg(n) for n in range(1,1000)
if alg(n) < 57 ]
print( max(R) )
55
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

151. ЕГЭ-6 (демо-2021)

Язык Python в школьной информатике
151
ЕГЭ-6 (демо-2021)
Определите, при каком наименьшем введённом значении
переменной s программа выведет число 64.
s = int(input())
n = 1
while s < 51:
s = s + 5
n = n * 2
print( n )
21
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

152. Решение

Язык Python в школьной информатике
152
Решение
def F( s ):
n = 1
while s < 51:
s = s + 5
n = n * 2
return n
R = [ s for s in range(1,1000)
if F(s) == 64 ]
print( min(R) )
21
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

153. ЕГЭ-6

Язык Python в школьной информатике
153
ЕГЭ-6
(Е. Джобс) Сколько существует значений s, подаваемых
на вход программе, при которых в результате работы
программы на экран будет выведено значение 125?
s = int(input())
n = 1
while s > n:
s = s – 15
n = n * 5
print( n )
115
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

154. Решение

Язык Python в школьной информатике
154
Решение
def F( s ):
n = 1
while s > n:
s = s - 15
n = n * 5
return n
R = [ s for s in range(1,1000)
if F(s) == 125 ]
print( len(R) )
115
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

155. Язык Python в школьной информатике Символьные строки

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
156
Символьные строки
s
s
s
s
= '123456'
+= "789"
= 'a'*10
= 5*"xyz"
# повтор 10 раз
# повтор 5 раз
s1 = '123456'
s2 = "ABCD"
s = s1 + s2 # "123456ABCD”
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
157
Срезы строк
0 1 2 3 4 5 67
s = "ABCDEFGH"
print(
print(
print(
print(
print(
print(
последний не входит!
s[2:3] ) # B
s[:3] ) # AB
s[4:] ) # DEFGH
s[1::2] ) # ACEG
s[::-1] ) # HGFEDCBA
s[2:-2] ) # BCDEF
2-й с конца
print( s[-2:] ) #
GH
последние 2
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
158
Символьные строки
s = str( 12345 ) # число –> строка
i = int( "6789" ) # строка –> число
s = "abcdefg"
print( s[-5:].upper() ) # CDEFG
5 последних
символов
в верхний
регистр
s = "QWERTY"
print( s[:3].lower() )
первые 3
символа
К.Ю. Поляков, 2021
# qwe
в нижний
регистр
http://kpolyakov.spb.ru

159. Методы обработки строк

Язык Python в школьной информатике
159
Методы обработки строк
s = input( "Введите строку > " )
print( "-".join( reversed(s.split()) ) )
Введите строку > мама мыла раму
s.split()
[мама, мыла, раму]
reversed(s.split())
[раму, мыла, мама]
"-".join( ... )
раму-мыла-мама
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
160
Замена подстрок
s = "a и b и c"
print( s.replace("и", "and") )
'a and b and c'
s = "a и b и c"
print( s.replace("и", "and", 1 ) )
'a and b и c'
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

161. Методы обработки строк

Язык Python в школьной информатике
161
Методы обработки строк
s = "123"
print( s.isdigit(), s.isalpha() )
# True False
s = "AbcЭюя"
print( s.isdigit(), s.isalpha() )
# False True
s = "
123
"
print( s.lstrip(), s.rstrip(), s.strip() )
"123
"
"
123"
"123"
https://www.w3schools.com/python/python_ref_string.asp
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

162. ЕГЭ-8

Язык Python в школьной информатике
162
ЕГЭ-8
Вася составляет 7-буквенные коды из букв
К, А, Б, И, Н, Е, Т. Каждую букву нужно
использовать ровно 1 раз, при этом код не может
заканчиваться на букву Б и не может
содержать сочетаний ЕА и ЕИ. Сколько
различных кодов может составить Вася?
3120
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

163. Решение («КАБИНЕТ»)

Язык Python в школьной информатике
163
Решение («КАБИНЕТ»)
from itertools import permutations
words = [ "".join(p)
for p in permutations("КАБИНЕТ") ]
words = [ w for w in words
if w[-1] != 'Б'
and "ЕА" not in w
and "ЕИ" not in w ]
print( len(words) )
3120
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

164. ЕГЭ-8

Язык Python в школьной информатике
164
ЕГЭ-8
(А.Н. Носкин) Петя составляет семибуквенные
слова перестановкой букв слова АССАСИН.
Сколько всего различных слов может составить
Петя?
420
! Есть одинаковые буквы!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

165. Решение («АССАСИН»)

Язык Python в школьной информатике
Решение («АССАСИН»)
!
165
Не работает!
from itertools import permutations
words = [ p for p in
permutations("АССАСИН") ]
print( len(words) )
print( len(words)//2//6 ) # 2! ?3! Что плохо?
from itertools import permutations
words = set( p for p in
permutations("АССАСИН") )]
print( len(words) )
420
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

166. Комбинаторика: декартово произведение

Язык Python в школьной информатике
166
Комбинаторика: декартово произведение
from itertools import product
for p in product( "ABC", repeat=2 ):
print( p, end=" " )
('A', 'A') ('A', 'B') ('A', 'C') ('B', 'A')
('B', 'B') ('B', 'C') ('C', 'A') ('C', 'B')
('C', 'C')
s = "ABC"
for x in s:
for y in s:
print( (x, y), end=" " )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

167. ЕГЭ-8

Язык Python в школьной информатике
167
ЕГЭ-8
Вася составляет 4-буквенные слова, в которых
есть только буквы Б, А, Л, К, О, Н. Сколько слов
может написать Вася?
from itertools import product
words = [ p for p in
product( "БАЛКОН", repeat=4 ) ]
print( len(words) )
1296
words = list( product( "БАЛКОН", repeat=4 ) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

168. ЕГЭ-8

Язык Python в школьной информатике
168
ЕГЭ-8
Вася составляет 4-буквенные слова, в которых
есть только буквы Б, А, Л, К, О, Н. Сколько слов,
которые начинаются с «А», может написать
Вася?
from itertools import product
words = [ p for p in
product( "БАЛКОН", repeat=4 )
if p[0] == 'А' ]
print( len(words) )
216
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

169. ЕГЭ-8

Язык Python в школьной информатике
169
ЕГЭ-8
Вася составляет 4-буквенные слова, в которых
есть только буквы Б, А, Л, К, О, Н. Сколько слов,
которые начинаются с гласной, может написать
Вася?
from itertools import product
words = [ p for p in
product( "БАЛКОН", repeat=4 )
if p[0] in 'АО' ]
print( len(words) )
432
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

170. ЕГЭ-8

Язык Python в школьной информатике
170
ЕГЭ-8
Вася составляет 4-буквенные слова, в которых
есть только буквы Б, А, Л, К, О, Н, причём в
каждом слове буква Б используется хотя бы 1
раз. Сколько слов может написать Вася?
from itertools import product
words = [ p for p in
product( "БАЛКОН", repeat=4 )
if 'Б' in p]
print( len(words) )
671
if p.count('Б') > 0
if p.count('Б')
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

171. ЕГЭ-8

Язык Python в школьной информатике
171
ЕГЭ-8
Вася составляет 4-буквенные слова, в которых
есть только буквы Б, А, Л, К, О, Н, причём в
каждом слове есть сочетание ЛК. Сколько слов
может написать Вася?
from itertools import product
words = [ ''.join(p)
for p in product( "БАЛКОН", repeat=4 )]
words = [ w for w in words
if "ЛК" in w ]
print( len(words) )
107
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

172. ЕГЭ-8

Язык Python в школьной информатике
172
ЕГЭ-8
Петя составляет список из 5-буквенных слов, в
состав которых входят только буквы К, Р, А. Петя
расположил слова в алфавитном порядке. Вот
начало списка:
1. ААААА
2. ААААК
3. ААААР
4. АААКА
……
Запишите слово, которое стоит в этом списке под
номером 100.
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

173. Решение («КРА»)

Язык Python в школьной информатике
173
Решение («КРА»)
from itertools import product
words = [''.join(p) for p in
sorted("КРА")
"КРА", repeat=5 ) ]
product(product(
sorted("КРА"),
print( words[100-1] )
КАРАА
К.Ю. Поляков, 2021
?
Что плохо?
http://kpolyakov.spb.ru

174. ЕГЭ-8

Язык Python в школьной информатике
174
ЕГЭ-8
Петя составляет список из 5-буквенных слов, в
состав которых входят только буквы К, Р, А. Петя
расположил слова в обратном алфавитном
порядке. Вот начало списка:
1. PPPPP
2. PPPPК
3. PPPPA
4. PPPКP
……
Под каким номером в этом списке стоит слово
КРААР?
106
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

175. Решение («КРА-2»)

Язык Python в школьной информатике
175
Решение («КРА-2»)
from itertools import product
words = [''.join(p) for p in
product( sorted("КРА"), repeat=5 ) ]
print( words [::-1] .index("КРААР")+1 )
106
К.Ю. Поляков, 2021
в обратном
порядке
http://kpolyakov.spb.ru

176. ЕГЭ-8

Язык Python в школьной информатике
176
ЕГЭ-8
Все 5-буквенные слова, составленные из букв А,
З, Н, С, записаны в алфавитном порядке и
пронумерованы. Вот начало списка:
1. ААААА
2. ААААЗ
3. ААААН
4. ААААС
5. АААЗА

Какое количество слов находятся между словами
САЗАН и ЗАНАС (включая эти слова)?
496
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

177. Решение («САЗАН»)

Язык Python в школьной информатике
177
Решение («САЗАН»)
from itertools import product
words = [ ''.join(p) for p in
product( "АЗНС", repeat=5 ) ]
print( words.index("САЗАН") words.index("ЗАНАС") + 1 )
496
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

178. Решение («САЗАН-2»)

Язык Python в школьной информатике
178
Решение («САЗАН-2»)
0 1 2 3
'САЗАН'
[А,З,Н,С]
print( int("30102", 4)
- int("10203", 4) + 1 )
'ЗАНАС'
496
К.Ю. Поляков, 2021
система
счисления
http://kpolyakov.spb.ru

179. ЕГЭ-8

Язык Python в школьной информатике
179
ЕГЭ-8
Все 5-буквенные слова, составленные из букв Р,
А, Ф, Т записаны в алфавитном порядке. Вот
начало списка:
1. ААААА
2. ААААР
3. ААААТ
4. ААААФ
5. АААРА
……
Найдите номер первого слова, которое
начинается на букву Т.
513
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

180. Решение («РАФТ»)

Язык Python в школьной информатике
180
Решение («РАФТ»)
from itertools import product
words = [ ''.join(p) for p in
product( sorted("РАФТ"), repeat=5 ) ]
print( words.index("ТАААА") + 1 )
513
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

181. ЕГЭ-8

Язык Python в школьной информатике
181
ЕГЭ-8
Все четырёхбуквенные слова, составленные из
букв А, Л, Г, О, Р, И, Т, М записаны в алфавитном
порядке и пронумерованы, начиная с 1. Начало
списка выглядит так:
1. АААА
2. АААГ
3. АААИ
4. АААЛ

Под каким номером в списке идёт последнее
слово, которое заканчивается на АЛ?
4036
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

182. Решение («АЛГОРИТМ»)

Язык Python в школьной информатике
182
Решение («АЛГОРИТМ»)
from itertools import product
words = [ ''.join(p) for p in
product( sorted("АЛГОРИТМ"),
repeat=4 ) ]
print( words.index("ТТАЛ") + 1 )
4036
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

183. ЕГЭ-8

Язык Python в школьной информатике
183
ЕГЭ-8
Из букв слова Р А З М А Х составляются 6буквенные последовательности. Сколько можно
составить различных последовательностей, в
которых содержится не менее 3 согласных?
15360
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

184. Решение («РАЗМАХ»)

Язык Python в школьной информатике
184
Решение («РАЗМАХ»)
from itertools import product
words = set( ''.join(p) for p in
product( "РАЗМАХ", repeat=6 ) )
words = [ w for w in words
if w.count('Р')+w.count('З') +
w.count('М')+w.count('Х') >= 3 ]
print( len(words) )
15360
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

185. Пары соседних

Язык Python в школьной информатике
185
Пары соседних
S = "АБВГ"
print( list( zip(S,S[1:]) ) )
# [(А,Б), (Б,В), (В,Г)]
A = [1, 2, 3, 4]
print( [p for p in zip(A,A[1:])]
# [(1, 2), (2, 3), (3, 4)]
S S[1:] zip()
A Б
(А,Б)
(Б,В)
Б В
В Г
(В,Г)
Г
К.Ю. Поляков, 2021
)
можно
добавить
условие!
http://kpolyakov.spb.ru

186. Пары соседних c отбором

Язык Python в школьной информатике
186
Пары соседних c отбором
A = [1, 2, 3, 4]
pairs = [p for p in zip(A,A[1:])
if p[0]+p[1] == 5 ]
print( *pairs )
# (2, 3)
раскрыли
кортеж!
pairs = [(a,b) for a, b in zip(A,A[1:])
if a+b == 5 ]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

187. ЕГЭ-8

Язык Python в школьной информатике
187
ЕГЭ-8
Сколько существует чисел, восьмеричная запись
которых содержит 5 цифр, причём все цифры
различны и никакие две чётные и две нечётные
цифры не стоят рядом.
504
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

188. Решение

Язык Python в школьной информатике
Решение
188
все цифры
разные!
def valid( x ):
return len(set(x)) == len(x) and \
all(
(int(p[0])+int(p[1])) % 2
for p in zip(x,x[1:])
)
пары соседних
цифр
0o12345 12345
num8 = [ oct(x)[2:]
for x in range(8**4,8**5) ]
num8 = [ x for x in num8 if valid(x) ]
print( len(num8) )
504
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

189. ЕГЭ-8

Язык Python в школьной информатике
189
ЕГЭ-8
Артур составляет 5-буквенные коды
перестановкой букв слова АРЕАЛ. При этом
нельзя ставить рядом две гласные. Сколько
различных кодов может составить Артур?
6
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

190. Решение («АРЕАЛ»)

Язык Python в школьной информатике
190
Решение («АРЕАЛ»)
from itertools import permutations
def valid ( w ):
return all( a+b not in "ААЕЕА"
for a, b in zip(w,w[1:]) )
words = set( ''.join(p) for p in
permutations( "АРЕАЛ" ) )
words = [ w for w in words
if valid(w) ]
print( len(words) )
6
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

191. ЕГЭ-8

Язык Python в школьной информатике
191
ЕГЭ-8
Сколько шестнадцатеричных кодов чисел длиной
12 можно составить, если известно, что цифры
идут в порядке убывания, при этом четные и
нечетные цифры чередуются?
104
в порядке возрастания
(в том числе с 0)
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

192. Решение

Язык Python в школьной информатике
192
Решение
from itertools import combinations
def valid( s ):
return all(
(ord(a)+ord(b)) % 2 == 1
for a, b in zip(s,s[1:]) )
cmb = combinations(
BCDEFG ), 12 )
reversed("0123456789BCDEFG"
cmb = [c for c in cmb
Код B
if valid(c)]
чётный!
print( len(cmb) )
104
К.Ю. Поляков, 2021
Автор идеи: А. Богданов
http://kpolyakov.spb.ru

193. Язык Python в школьной информатике Работа с файлами

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

194. Классика

Язык Python в школьной информатике
194
Классика
F = open("input.txt")
while True:
s = F.readline() .rstrip()
if not s: break
убрать символ
print( s )
F.close()
1
2
3
перевода
строки в конце!
1
2
3
4
5
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

195. Менеджер контекста

Язык Python в школьной информатике
195
Менеджер контекста
with open("input.txt") as F:
while True:
s = F.readline().rstrip()
if not s: break
print( s )
!
Не нужно закрывать файл!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

196. Чтение всех строк

Язык Python в школьной информатике
196
Чтение всех строк
for s in open("input.txt"):
print( s.rstrip() )
по одной строке!
!
Не нужно закрывать файл!
with open("input.txt") as F:
arS = F.readlines()
for s in arS:
print( s.rstrip() )
К.Ю. Поляков, 2021
сразу все!
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
197
Обработка строк
Вывести инициалы и фамилии всех, кто получил
"5" на экзамене. Данные в файле:
w[0]
w[1]
w[2]
w[3] w[4]
Иванов Семён Семёнович 1998 5
отметка
Семёнов Пётр Петрович 1997 4
...
for s in open("exam.txt"):
w = s.split()
if int(w[4]) == 5: # или w[4] == '5'
print( w[1][0]+'.'+w[2][0]+'. '+w[0])
С.С. Иванов
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

198. ЕГЭ-24

Язык Python в школьной информатике
198
ЕГЭ-24
Текстовый файл 24.txt состоит не более чем из
106 символов X, Y и Z. Определите максимальное
количество идущих подряд символов, среди
которых каждые два соседних различны.
35
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

199. Решение

Язык Python в школьной информатике
199
Решение
with open("24.txt") as F:
s = F.readline()
print( s[:10] )
для проверки
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

200. Решение

Язык Python в школьной информатике
200
Решение
with open("24.txt") as F:
s = F.readline()
prev, curLen, maxLen = '*', 0, 0
for c in s:
curLen = curLen+1 if c != prev else 1
maxLen = max(maxLen, curLen)
prev = c
if c != prev:
print( maxLen )
curLen = curLen+1
35
else:
curLen = 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

201. ЕГЭ-24

Язык Python в школьной информатике
201
ЕГЭ-24
(А.М. Кабанов) В текстовом файле 24-1.txt
находится цепочка из символов латинского
алфавита. Найдите длину самой длинной
подцепочки, состоящей из символов A, B или C (в
произвольном порядке).
12
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

202. Решение

Язык Python в школьной информатике
202
Решение
with open("24.txt") as F:
s = F.readline()
curLen, maxLen = 0, 0
for c in s:
curLen = curLen+1 if c in "ABC" else 0
maxLen = max(maxLen, curLen)
print( maxLen )
12
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

203. ЕГЭ-24

Язык Python в школьной информатике
203
ЕГЭ-24
Текстовый файл 24-2.txt состоит не более чем из
106 заглавных латинских букв (A..Z). Текст разбит
на строки различной длины. Определите
количество строк, в которых встречается
комбинация FO.
780
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

204. Решение

Язык Python в школьной информатике
204
Решение
with open("24-2.txt") as F:
arS = F.readlines()
count = 0
for s in arS:
if "FO" in s: count += 1
print( count )
780
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

205. Решение

Язык Python в школьной информатике
205
Решение
with open("24-2.txt") as F:
arS = F.readlines()
R = [ s for s in arS
if 'FO' in s ]
print(
len(R) )
780
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

206. ЕГЭ-24

Язык Python в школьной информатике
206
ЕГЭ-24
Текстовый файл 24-2.txt состоит не более чем из
106 заглавных латинских букв (A..Z). Текст разбит
на строки различной длины. Определите
количество строк, в которых встречается
комбинация F*O, где звёздочка обозначает
любой символ.
1434
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

207. Решение

Язык Python в школьной информатике
207
Решение
with open("24-2.txt") as F:
arS = F.readlines()
count = 0
for s in arS:
for c in range(ord('A'), ord('Z')+1):
if 'F'+chr(c)+'O' in s:
count += 1
break
print( count )
757
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

208. Решение

Язык Python в школьной информатике
208
Решение
with open("24-2.txt") as F:
arS = F.readlines()
import string
count = 0
for s in arS:
for c in string.ascii_uppercase :
if 'F'+c+'O' in s:
count += 1
break
print( count )
757
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

209. Решение

Язык Python в школьной информатике
209
Решение
with open("24-2.txt") as F:
arS = F.readlines()
count = 0
for s in arS:
for i in range(len(s)-2):
if s[i] == 'F' and s[i+2] == 'O':
count += 1
break
print( count )
757
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

210. Решение

Язык Python в школьной информатике
210
Решение
with open("24-2.txt") as F:
arS = F.readlines()
регулярное
import re
выражение
count = 0
for s in arS:
if re.search( "F.O", s ) :
count += 1
print( count )
один любой
символ
757
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

211. Решение

Язык Python в школьной информатике
211
Решение
with open("24-2.txt") as F:
arS = F.readlines()
import re
R = [ s for s in arS
if re.search("F.O", s) ]
print( len(R) )
757
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

212. Язык Python в школьной информатике

Словари
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

213. Словари (ассоциативные массивы)

Язык Python в школьной информатике
213
Словари (ассоциативные массивы)
• пары «ключ => значение»
• основной метод – поиск по ключу (не по индексу!)
Задача. Построить русско-английский словарь.
ключ
значение
D = {}
D["кошка"] = "cat"
D["собака"] = "dog"
...
word = input("Введите слово:")
if word in D:
print( "Перевод: " + D[word] )
else:
print( "Не знаю!" )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

214. Словари: перебор

Язык Python в школьной информатике
214
Словари: перебор
список кортежей
(ключ, значение)
for key, value in D.items():
print( key, value )
кошка cat
собака dog
for pair in D.items():
print( pair[0], pair[1] )
for pair in sorted(D.items()):
print( pair[0], pair[1] )
К.Ю. Поляков, 2021
сортировка
по key
http://kpolyakov.spb.ru

215. Частотный словарь

Язык Python в школьной информатике
215
Частотный словарь
D = {} # пустой словарь
for s in open("test.txt"):
words = s.lower().split()
нет ключа 0
for w in words:
D[w] = D.get( w, 0 ) + 1
for word, count in D.items():
print( word, count )
даша 1
брюкву 1
Маша ела кашу
и 1
брюкву и кашу
кашу 2
ела Даша
ела 2
маша 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

216. Частотный словарь (сортировка)

Язык Python в школьной информатике
216
Частотный словарь (сортировка)
D = {}
for s in open("test.txt"):
words = s.lower().split()
for w in words:
D[w] = D.get(w,0) + 1
for word, count in sorted( D.items(),
key = lambda p: -p[1] ):
print( word, count )
Маша ела кашу
брюкву и кашу ела
Даша
К.Ю. Поляков, 2021
ела 2
кашу 2
даша 1
и 1
...
сортировать
по значению
http://kpolyakov.spb.ru

217. ЕГЭ – С4

Язык Python в школьной информатике
217
ЕГЭ – С4
Задача. В первой строчке поступает количество
пришедших sms-сообщений N. В каждой из
последующих N строк записано название фильма:
6
Белое солнце пустыни
Бриллиантовая рука
Белое солнце пустыни
Белое солнце пустыни
Гараж
Бриллиантовая рука
Нужно вывести список фильмов в порядке убывания
количества отданных за них голосов:
Белое солнце пустыни 3
Бриллиантовая рука 2
Гараж 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

218. Решение

Язык Python в школьной информатике
218
Решение
with open('films.txt') as F:
N = int(F.readline())
фильм число голосов
data = {}
for i in range(N):
увеличить
film = F.readline().strip()
счётчик
data[film] = data.get(film,0) + 1
data = sorted( data.items(),
key = lambda x: -x[1] )
for film, count in data:
сортировать
print( film, count )
по убыванию
значений
Белое солнце пустыни 3
Бриллиантовая рука 2
Гараж 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

219. ЕГЭ–16

Язык Python в школьной информатике
219
ЕГЭ–16
Алгоритм вычисления значения функции F(n), где n – целое
неотрицательное число, задан следующими
соотношениями:
F(0) = 1, F(1) = 3,
F(n) = F(n–1) – F(n–2) + 3n при n>1
Чему равно значение функции F(140)?
422
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

220. Решение

Язык Python в школьной информатике
220
Решение
def f( n ):
if n == 0: return 1
elif n == 1: return 3
else:
return f(n-1) - f(n-2) + 3*n
print( f(140) )
!
Не дождаться!
К.Ю. Поляков, 2021
1) массив
2) словарь
http://kpolyakov.spb.ru

221. Решение (мемоизация)

Язык Python в школьной информатике
221
Решение (мемоизация)
mem = {}
def f( n ):
if n in mem: return mem[n]
if n == 0: res = 1
elif n == 1: res = 3
else: res = f(n-1) - f(n-2) + 3*n
mem[n] = res
return res
print( f(140) )
422
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

222. ЕГЭ–16

Язык Python в школьной информатике
222
ЕГЭ–16
(Е. Джобс) Алгоритм вычисления значения функции F(n),
где n – целое неотрицательное число, задан следующими
соотношениями:
F(0) = 1, F(1) = 3
F(n) = F(n–1) – F(n–2) + 3n, при чётном n>1
F(n) = F(n–2) – F(n–3) + 2n, при нечётном n>1
Чему равно значение функции F(140)?
284
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

223. Решение (мемоизация)

Язык Python в школьной информатике
223
Решение (мемоизация)
mem = {}
def f( n ):
if n in mem: return mem[n]
if n == 0: res = 1
elif n == 1: res = 3
elif n % 2 == 0:
res = f(n-1) - f(n-2) + 3*n
else:
res = f(n-2) - f(n-3) + 2*n
mem[n] = res
return res
print( f(140) )
К.Ю. Поляков, 2021
284
http://kpolyakov.spb.ru

224. ЕГЭ–1921 (демо-2021)

Язык Python в школьной информатике
224
ЕГЭ–1921 (демо-2021)
За один ход игрок может добавить в одну из куч (по
своему выбору) один камень или увеличить
количество камней в куче в два раза. Игра завершается
в тот момент, когда суммарное количество камней в кучах
становится не менее 77. В начальный момент в первой
куче было семь камней, во второй куче – S камней;
1 ≤ S ≤ 69. Найдите:
20) значения S, при которых у Пети есть выигрышная
стратегия за 2 хода, но не за 1 ход
21) значения S, при которых у Вани есть выигрышная
стратегия за 2 хода, но не за 1 ход
20) 31, 34
21) 30, 33
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

225. ЕГЭ-1921. Оценка позиции

Язык Python в школьной информатике
225
ЕГЭ-1921. Оценка позиции
0 – игра окончена
проигрыш
1 – есть ход в 0
выигрыш за 1 ход
-1 – все ходы в 1
проигрыш за 1 ход
2 – есть ход в -1
выигрыш за 2 хода
-2 – все ходы в 1 и 2 проигрыш за 2 хода

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

226. ЕГЭ-1921. Оценка позиции

Язык Python в школьной информатике
226
ЕГЭ-1921. Оценка позиции
def gameResult( x, y ):
возможные
if x+y >= 77: return 0
ходы
nextMove = [ gameResult(x+1,y),
gameResult(x,y+1),
gameResult(2*x,y),
gameResult(x,2*y) ]
negative = [m for m in nextMove
if m <= 0]
if negative:
скорее
res = - max(negative) + 1
выиграть
else:
дольше
res = - max(nextMove)
продержаться
return res
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

227. ЕГЭ-1921. Решение (плохое)

Язык Python в школьной информатике
227
ЕГЭ-1921. Решение (плохое)
for s in range(69, 0, -1):
print( s, gameResult(7,s) )
69 1
68 1
...
45 1
!
!
К.Ю. Поляков, 2021
Не дождаться!
Запоминать результаты в словаре
(или массиве)!
http://kpolyakov.spb.ru

228. ЕГЭ-1921. Оценка позиции (+mem)

Язык Python в школьной информатике
228
ЕГЭ-1921. Оценка позиции (+mem)
mem = {}
def gameResult( x, y ):
ключ словаря кортеж
if (x, y) in mem:
return mem[(x,y)]
... # всё, что было раньше
mem[(x,y)] = res
return res
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

229. ЕГЭ-1921. Решение

Язык Python в школьной информатике
229
ЕГЭ-1921. Решение
for s in range(69, 0, -1):
print( s, gameResult(7,s) )
...
36 1
35 1
34 2
33 -2
32 3
31 2
30 -2
29 3
28 4
...
К.Ю. Поляков, 2021
20
выигрыш Пети
на 2-м ходу
21
выигрыш Вани
на 2-м ходу
http://kpolyakov.spb.ru

230. ЕГЭ-1921. Полная автоматизация

Язык Python в школьной информатике
230
ЕГЭ-1921. Полная автоматизация
res20, res21 = [], []
for s in range(69, 0, -1):
r = gameResult(7,s)
if r == 2: res20.append(s)
if r == -2: res21.append(s)
print( sorted(res20),
sorted(res21), sep="\n" )
[31,34]
[30,33]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

231. ЕГЭ–1921

Язык Python в школьной информатике
231
ЕГЭ–1921
(А. Кабанов) Перед игроками лежит куча камней. Игроки
ходят по очереди, первый ход делает Петя. За один ход
игрок может добавить в кучу два камня или увеличить
количество камней в куче в два раза. Игра завершается в
тот момент, когда количество камней в куче становится не
менее 25. В начальный момент в куче было S камней,
1 ≤ S ≤ 24. Найдите:
20) значения S, при которых у Пети есть выигрышная
стратегия за 2 хода, но не за 1 ход
21) значения S, при которых у Вани есть выигрышная
стратегия за 2 хода, но не за 1 ход
20) 6, 9, 10
21) 7, 8
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

232. ЕГЭ-1921. Оценка позиции

Язык Python в школьной информатике
232
ЕГЭ-1921. Оценка позиции
mem = {}
def gameResult( x ):
if x in mem: return mem[x]
if x >= 25: return 0
nextMove = [ gameResult(x+2),
gameResult(x*2) ]
negative = [m for m in nextMove
if m <= 0]
if negative:
res = - max(negative) + 1
else:
res = - max(nextMove)
mem[x] = res
return res
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

233. ЕГЭ-1921. Основная программа

Язык Python в школьной информатике
233
ЕГЭ-1921. Основная программа
res20, res21 = [], []
for s in range(24, 0, -1):
r = gameResult(s)
if r == 2: res20.append(s)
if r == -2: res21.append(s)
print( sorted(res20),
sorted(res21), sep="\n" )
[6,9,10]
[7,8]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

234. Язык Python в школьной информатике Обработка потока данных (ЕГЭ-27)

К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

235. ЕГЭ-27

Язык Python в школьной информатике
235
ЕГЭ-27
(Д.В. Богданов) В текстовом файле 27-0.txt
записаны N положительных целых чисел.
Необходимо определить количество пар
элементов (ai, aj) этого набора, в которых
1 i < j N и сумма элементов кратна 12. В
первой строке файла записано значение N,
каждая из следующих N строк содержит одно
натуральное число.
A: 17
B: 150016535
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

236. Решение (подготовка)

Язык Python в школьной информатике
236
Решение (подготовка)
with open("27-0.txt") as F:
N = int( F.readline() )
data = []
for i in range(N):
data.append( int(F.readline()) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

237. Решение (обработка)

Язык Python в школьной информатике
237
Решение (обработка)
...
счётчик
пар
D = 12
счётчики предыдущих
чисел с разными
count = 0
остатками
remCount = [0]*D
+ r = D или 0
for x in data:
r = x % D
count += remCount[(D - r) % D]
remCount[r] += 1
сколько
print( count )
К.Ю. Поляков, 2021
пар для
числа x
http://kpolyakov.spb.ru

238. ЕГЭ-27

Язык Python в школьной информатике
238
ЕГЭ-27
(А. Жуков) В текстовом файле 27-1.txt записаны
N положительных чисел. Необходимо определить
максимальное произведение подпоследовательности, состоящей из одного или более
идущих подряд элементов. В первой строке
файла записано значение N, каждая из
следующих N строк содержит одно натуральное
число.
A: 663497670
К.Ю. Поляков, 2021
B: 999806976
http://kpolyakov.spb.ru

239. Решение (подготовка)

Язык Python в школьной информатике
239
Решение (подготовка)
with open("27-1.txt") as F:
N = int( F.readline() )
data = []
for i in range(N):
data.append( int(F.readline()) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

240. Решение (обработка)

Язык Python в школьной информатике
240
Решение (обработка)
...
minProd, maxProd, maxTotal = 1, 1, 1
for x in data:
minProd, maxProd = (
min( x, minProd*x, maxProd*x ),
max( x, minProd*x, maxProd*x ) )
maxTotal = max(maxTotal, maxProd)
print( maxTotal )
A: 663497670
К.Ю. Поляков, 2021
B: 999806976
http://kpolyakov.spb.ru

241. ЕГЭ-27 (демо-2021)

Язык Python в школьной информатике
241
ЕГЭ-27 (демо-2021)
В текстовом файле 27-2.txt записано значение N
(в первой строке), а затем – N пар целых
положительных чисел, каждая пара в отдельной
строке. Необходимо выбрать из каждой пары
ровно одно число так, чтобы сумма всех
выбранных чисел не делилась на 3 и при этом
была максимально возможной.
A: 127127
К.Ю. Поляков, 2021
B: 399762080
http://kpolyakov.spb.ru

242. Решение (подготовка)

Язык Python в школьной информатике
242
Решение (подготовка)
with open("27-2.txt") as F:
N = int( F.readline() )
data = []
пара в
строке
for i in range(N):
p = map( int, F.readline().split() )
data.append( sorted(p) )
# [1,3] [5,12] [6,9] [4,5] ...
p[1]≥p[0]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

243. Решение (обработка)

Язык Python в школьной информатике
243
Решение (обработка)
...
maxSum, diff = 0, 10**10
for pair in data:
p[1]≥p[0]
maxSum += pair[1]
if (pair[1]-pair[0]) % 3 != 0:
diff = min( diff, pair[1]-pair[0] )
print( maxSum if maxSum % 3 != 0
else maxSum-diff )
A: 127127
К.Ю. Поляков, 2021
B: 399762080
коррекция
http://kpolyakov.spb.ru

244. Решение через reduce

Язык Python в школьной информатике
244
Решение через reduce
from functools import reduce
res = reduce( lambda a,p:
(a[0]+p[1], sum
diff
min(a[1], p[1]-p[0])
if (p[1]-p[0]) % 3 != 0
else a[1]),
(sum,diff)
data, (0, 10**10) )
print( res[0] if res[0] % 3 != 0
else res[0]-res[1] ))
A: 127127
К.Ю. Поляков, 2021
B: 399762080
коррекция
http://kpolyakov.spb.ru

245. Группировка

Язык Python в школьной информатике
245
Группировка
from itertools import groupby
A = [ 1, 2, 3, 1, 2, 1 ]
A.sort()
for key, group in groupby( A ):
print( key, list(group) )
генератор
кортежей
# 1 [1,1,1]
(key,генератор)
# 2 [2,2]
# 3 [3]
!
Предварительно отсортировать
по нужному признаку!
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

246. Группировка (x > 3)

Язык Python в школьной информатике
246
Группировка (x > 3)
from itertools import groupby
A = [ 1, 2, 3, 4, 5, 6 ]
A.sort( key = lambda x: x > 3 )
for k, g in groupby( A,
key = lambda x: x > 3 ):
print( list(g) )
# [1,2,3] [4,5,6]
False
True
x > 3
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

247. Группировка (по остатку)

Язык Python в школьной информатике
247
Группировка (по остатку)
from itertools import groupby
A = [ 1, 2, 3, 4, 5, 6 ]
func = lambda x: x % 3
A.sort( key = func )
for k, g in groupby( A, key = func ):
print( list(g) )
# [3,6] [1,4] [2,5]
0
К.Ю. Поляков, 2021
1
x % 3
2
http://kpolyakov.spb.ru

248. ЕГЭ – С4 (ещё раз)

Язык Python в школьной информатике
248
ЕГЭ – С4 (ещё раз)
Задача. В первой строчке поступает количество
пришедших sms-сообщений N. В каждой из
последующих N строк записано название фильма:
6
Белое солнце пустыни
Бриллиантовая рука
Белое солнце пустыни
Белое солнце пустыни
Гараж
Бриллиантовая рука
Нужно вывести список фильмов в порядке убывания
количества отданных за них голосов:
Белое солнце пустыни 3
Бриллиантовая рука 2
Гараж 1
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

249. Решение (через groupby)

Язык Python в школьной информатике
249
Решение (через groupby)
with open("films.txt") as F:
N = int(F.readline())
data = []
for i in range(N):
data.append( F.readline().rstrip() )
data.sort()
по названию
фильма
from itertools import groupby
(фильм, счётчик)
res = [ (k, len(list(g)))
for k, g in groupby(data) ]
for film, count in \
sorted( res, key = lambda x: -x[1] ):
print( film, count )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

250. ЕГЭ-27 (демо-2021) – ещё раз

Язык Python в школьной информатике
250
ЕГЭ-27 (демо-2021) – ещё раз
В текстовом файле 27-2.txt записано значение N
(в первой строке), а затем – N пар целых
положительных чисел, каждая пара в отдельной
строке. Необходимо выбрать из каждой пары
ровно одно число так, чтобы сумма всех
выбранных чисел не делилась на 3 и при этом
была максимально возможной.
A: 127127
К.Ю. Поляков, 2021
B: 399762080
http://kpolyakov.spb.ru

251. Решение (подготовка – без сортировки)

Язык Python в школьной информатике
251
Решение (подготовка – без сортировки)
with open("27-2.txt") as F:
N = int( F.readline() )
data = []
for i in range(N):
a, b = map(int, F.readline().split())
data.append( (a, b) )
массив пар
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

252. Решение (обработка через groupby)

Язык Python в школьной информатике
252
Решение (обработка через groupby)
from itertools import product, groupby
maxMod = [0]
max суммы с
разными остатками
func = lambda x: x % 3
for pair in data:
allSums = [a+b
for a, b in product( maxMod, pair )]
allSums.sort( key = func ) max в каждой
группе
maxMod = [max(g)
for k,g in groupby(allSums, key = func)]
print( max( m for m in maxMod
if m % 3 != 0 ) )
A: 127127
К.Ю. Поляков, 2021
группы по
остаткам
B: 399762080
http://kpolyakov.spb.ru

253. ЕГЭ-27

Язык Python в школьной информатике
253
ЕГЭ-27
В текстовом файле 27-3.txt записано значение N
(в первой строке), а затем – N пар целых
положительных чисел, каждая пара в отдельной
строке. Необходимо выбрать из каждой пары
ровно одно число так, чтобы сумма всех
выбранных чисел делилась на 5 и при этом
была минимально возможной.
A: 75960
К.Ю. Поляков, 2021
B: 203343860
http://kpolyakov.spb.ru

254. Решение (подготовка – без сортировки)

Язык Python в школьной информатике
254
Решение (подготовка – без сортировки)
with open("27-3.txt") as F:
N = int( F.readline() )
data = []
for i in range(N):
a, b = map( int, F.readline().split())
data.append( (a, b) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

255. Решение (через groupby)

Язык Python в школьной информатике
255
Решение (через groupby)
from itertools import product, groupby
maxMod = [0]
func = lambda x: x % 5
for pair in data:
allSums = [a+b
for a, b in product( maxMod, pair )]
allSums.sort( key = func )
maxMod = [min(g)
for k,g in groupby(allSums, key = func)]
print( maxMod[0] )
A: 127127
К.Ю. Поляков, 2021
B: 399762080
http://kpolyakov.spb.ru

256. ЕГЭ-27

Язык Python в школьной информатике
256
ЕГЭ-27
В файле 27-4.txt записана последовательность,
которая состоит из троек натуральных чисел.
Необходимо распределить все числа на три
группы, при этом в каждую группу должно
попасть ровно одно число из каждой исходной
тройки. Сумма всех чисел в первой группе
должна быть нечётной, во второй – чётной.
Определите максимально возможную сумму всех
чисел в третьей группе.
A: 621
B: 103914584
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

257. Решение (подготовка)

Язык Python в школьной информатике
257
Решение (подготовка)
with open("27-4.txt") as F:
N = int( F.readline() )
data = []
тройки
totalSum = 0
чисел в
строке
for i in range(N):
a, b, c =
map( int, F.readline().split() )
totalSum
totalSum +=
+= aa ++ bb ++ cc
сумма
data.append( (a, b, c) )
всех
массив
троек
К.Ю. Поляков, 2021
чисел
http://kpolyakov.spb.ru

258. Идея решения

Язык Python в школьной информатике
258
Идея решения
# (1,2,3) (5,9,12) (6,11,9) (4,7,5) ...
1
9
9
4
...
2
12
6
7
...
сумма
чётная
сумма
нечётная
сумма
нечётная
К.Ю. Поляков, 2021
3
5
11
5
...
!
сумма
max
Выбрать по одному
числу из группы так,
чтобы оставшаяся
сумма была нечётной!
http://kpolyakov.spb.ru

259. Решение (обработка через groupby)

Язык Python в школьной информатике
259
Решение (обработка через groupby)
...
from itertools import product, groupby
maxMod = [0]
max
чётной и
func = lambda x: x % 2
нечётной
for d3 in data:
allSums = [a+b for a, b in
product( maxMod, d3 )]
allSums.sort( key = func )
maxMod = [max(g) for k,g in
groupby(allSums, key = func)]
print( maxMod[0] if (totalSum-maxMod[0]) % 2 != 0
else maxMod[1] )
оставшаяся
сумма
A: 621
B: 103914584
нечётная
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

260. ЕГЭ-27

Язык Python в школьной информатике
260
ЕГЭ-27
(А. Куканова) В файле 27-5.txt записана
последовательность, которая состоит из пар
натуральных чисел. Необходимо выбрать из
каждой пары ровно одно число так, чтобы сумма
всех выбранных чисел имела такой же остаток от
деления на 7, как наименьшая возможная, и при
этом была максимальной возможной.
Гарантируется, что искомую сумму получить
можно.
A: 115110
К.Ю. Поляков, 2021
B: 410884352
http://kpolyakov.spb.ru

261. Решение (подготовка)

Язык Python в школьной информатике
261
Решение (подготовка)
with open("27-5.txt") as F:
N = int( F.readline() )
data = []
пары
чисел в
minSum = 0
строке
for i in range(N):
a, b = map(int, F.readline().split())
minSum += min(a, b)
минимальная
сумма
data.append( (a, b) )
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru

262. Решение (обработка через groupby)

Язык Python в школьной информатике
262
Решение (обработка через groupby)
from itertools import product, groupby
maxMod = [0]
max суммы по
func = lambda x: x % 7
остаткам
for pair in data:
allSums = [a+b for a, b in
product( maxMod, pair )]
allSums.sort( key = func )
maxMod = [max(g) for k,g in
groupby(allSums, key = func)]
res = [ s for s in maxMod
if s % 7 == minSum % 7 ]
print( res[0] )
A: 115110
К.Ю. Поляков, 2021
условие
равенства
остатков
B: 410884352
http://kpolyakov.spb.ru

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

Язык Python в школьной информатике
263
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru
English     Русский Правила