![Через [0, 1]](https://cf3.ppt-online.org/files3/slide/y/yvwfi41S0Kk6lF8qnrRJBC5bXouphD7t3zeN9a/slide-25.jpg "Через [0, 1]")
ПрограммированиеПохожие презентации:
Язык Python в школьной информатике
1. Язык Python в школьной информатике
К.Ю. ПоляковЯзык Python в школьной
информатике
К.Ю. Поляков, 2021
http://kpolyakov.spb.ru
2. Язык Python в школьной информатике Переменные. Ввод и вывод
К.Ю. Поляков, 2021http://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 в школьной информатике Операторы управления
К.Ю. Поляков, 2021http://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 в школьной информатике Делимость
К.Ю. Поляков, 2021http://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 в школьной информатике Длинная арифметика
К.Ю. Поляков, 2021http://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 в школьной информатике Функции
К.Ю. Поляков, 2021http://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 в школьной информатике Массивы (списки)
К.Ю. Поляков, 2021http://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 в школьной информатике Операции с массивами
К.Ю. Поляков, 2021http://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 в школьной информатике Перебор
К.Ю. Поляков, 2021http://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 в школьной информатике Символьные строки
К.Ю. Поляков, 2021http://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 в школьной информатике Работа с файлами
К.Ю. Поляков, 2021http://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)
К.Ю. Поляков, 2021http://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