Учебник по информатике. Программирование на Python. Основы 1 Программирование на Python. Основы

• Название: Учебник по информатике. Программирование на Python. Основы 1 Программирование на Python. Основы
• Дата: 03.10.2022
• Размер: 1.27 Mb.
• Имя файла: py.pdf
• Тип: Учебник; #711558
• страница: 6 из 8

KEGEGKGEKEGEHKEGKEGEKKKKEGE, например, мы можем взять подстроки
EGKKEGEGKGEKEGEHKEG
или
EGEGKGEKEGEHKEGKEGEKKKKEG
. Или другими словами три подстроки, разделенные подстроками KEGE и ограниченные символами EGE и KEG, если они находятся в середине строки.
Поэтому разобьем строку по разделителю KEGE и узнаем длины всех таких подстрок. lens = list(map(len, s.split('KEGE')))
Для примера выше получим: [3, 4, 4, 3, 0]
Теперь нам нужно найти максимальную сумму трех подряд идущих слов и прибавить к ней 8 (2 строки KEGE) и 6 (EGE в начале и KEG в конце).
Так как у первого слова слева и у последнего слова справа нет комбинаций KEGE уменьшим их длину на 3, чтобы наше рассуждение работало для всех последовательных троек. lens[0] -= 3 lens[-1] -= 3
# lens = [0, 4, 4, 3, -3]
# [8 (0, 4, 4), 11 (4, 4, 3), 4 (4, 3, -3)] для примера print(max(map(lambda a,b,c: sum(a,b,c), lens, lens[1:], lens[2:])) + 14)
Передача функции в качестве аргумента
Ранее в качестве аргумента при вызове, например функции map мы передавали известные нам функции (len, max, sum) или лямбда-выражения. На самом деле в качестве такого аргумента мы можем передавать и имена функций, которые написали сами.
Например, нам надо посчитать сколько налогов нужно будет платить с заработанной суммы в мифической стране Х.
Мы знаем, что если человек заработал меньше 20000, то налог с него не удерживается, до 50000 – 4%, до 100000 – 6%, больше 100000 – 13%.

Открытый учебник по информатике. Программирование на Python. Основы
66
Да, мы можем написать лямбда выражение с вложенными тернарными операциями, но тогда код будет громоздким. Поэтому вынесем определение налога в отдельную функцию ploti_nologi(). def ploti_nologi(money): if money < 20000: return 0 elif money <= 50000: return money*0.04 elif money < 100000: return money*0.06 else: return money*0.13
Теперь, имея список с заработками граждан страны Х, мы можем посчитать сумму налогов которые они заплатят. profits = [15000, 54000, 22000, 143000, 20000] print(sum(map(ploti_nologi, profits)))
Рекурсивная функция
Отдельная разновидность функций – рекурсивные функции. Рекурсивной функцией называется такая функция, которая в ходе своего исполнения вызывает сама себя, возможно, через другую функцию. Чтобы рекурсивная функция не вызывала сама себя бесконечно, определяют либо условие выхода из рекурсии, либо условие продолжения рекурсии.
Традиционный пример – вычисление факториала N!
Через условие продолжения рекурсии. def factorial(n): if n > 0: return n*factorial(n-1) return 1
Через условие выхода из рекурсии. def factorial(n): if n == 0: return 1 return n*factorial(n-1)
Рекурсивные функции иногда весьма изящно описывают применяемый алгоритм, однако нужно проявлять некоторую аккуратность в их использовании.
Определено это тем, что рекурсия работает вглубь и углубляется до тех пор, пока либо выполняется условие продолжения рекурсии, либо не будет соблюдаться условие выхода из рекурсии.

Открытый учебник по информатике. Программирование на Python. Основы
67
Рассмотрим эту особенность на еще одном традиционном примере – вычисление чисел Фибоначчи. Напомню, что числа Фибоначчи – это ряд чисел, начинающийся с двух единим и продолжающийся суммой предыдущих двух чисел – 1, 1, 2 (1+1), 3 (1+2), 5 (2+3), 8 (3+5), 13 (5+8), …
Рекурсивно N-число последовательности можно получить с помощью следующей функции на Python. def fibonacci(N): if N < 3: return 1 return fibonacci(N-1) + fibonacci(N-2)
Разберемся, как работает эта функция на примере вызова fibonacci(5). fibonacci(5): if 5 < 3: # не выполняется return 1 return fibonacci(4): if 4 < 3: # не выполняется return 1 return fibonacci(3): if 3 < 3: return 1 return fibonacci(2): if 2 < 3: return 1
+ fibonacci(1): if 1 < 3: return 1
+ fibonacci(2): if 2 < 3: return 1
+ fibonacci(3): if 3 < 3: return 1 return fibonacci(2): if 2 < 3: return 1
+ fibonacci(1): if 1 < 3: return 1 1
1 2
1 3
1 1
2 5

Открытый учебник по информатике. Программирование на Python. Основы
68
Оставим только последовательность вызовов функции: fib
(5) →
(fib
(4) →
(fib
(3) →
(fib
(2) → fib(1))
) → fib(2)
) →
(fib
(3) →
(fib
(2) → fib(1))
)
Из последовательности можно сделать важные наблюдения.
Во-первых, каждое значение всегда считается заново. Во-вторых, любой вызов функции сначала доходит до точки выхода и только затем отдает управление обратно.
Второе наблюдение – вызов рекурсивной функции порождает цепочку вызовов этой же функции – стек вызовов. Это важно понимать, потому что глубина рекурсии в Python ограничена настройками среды. По умолчанию нельзя накапливать стек длиной больше 1000. Это можно избежать, если изменить системную переменную, ограничивающую глубину рекурсии.
Делается это с помощью функции setrecursionlimit из библиотеки sys. import sys sys.setrecursionlimit(10000)
Однако, стоит помнить, что стоит избегать применения рекурсивных функций там, где их можно заменить более простым алгоритмом, например, циклическим. Или, как минимум, постараться реализовать рекурсивный алгоритм таким образом, чтобы для одних и тех же значений функция не вычисляла результат несколько раз.
Например, можно использовать следующую рекурсивную функцию, которая запоминает все вычисленные значения. def fibonacci(N, fib_numbers=[1, 1]): if N <= len(fib_numbers): return fib_numbers[N-1] fib_numbers.append(fibonacci(N-1) + fibonacci(N-2)) return fib_numbers[-1]
Данная функция имеет список вычисленных значений, к которому мы можем обратиться по имени параметра. Так как данный список инициализируется один раз при объявлении функции, изменяя его, мы можем расширять набор вычисленных значений. Также за счет природы выполнения рекурсивных

Открытый учебник по информатике. Программирование на Python. Основы
69 алгоритмов строка с добавлением нового элемента всегда будет добавлять первое невычисленное значение, перед тем, как добавить следующее.
Посмотрим, как изменится порядок вычисления. В скобках указан порядок возвращения значений рекурсивной функцией. fib
(5) → # выход из рекурсии для 5 (5)
(fib
(4) → # выход из рекурсии для 4 (3)
(fib
(3) → # выход из рекурсии для 3 (1)
(fib
(2) → fib(1)) # уже посчитано (0)
) → fib(2)# уже посчитано (2)
) →
(fib(3) # это уже посчитано (4)
Можно придумать и другие способы хранения результатов работы рекурсивной функции. Однако в языке Python уже есть замечательный декоратор
1
@lru_cache() из библиотеки functools, который может сделать это за нас.
Теперь, если мы перепишем нашу первую реализацию рекурсивной функции в такую, которая не вычисляет значения для одного и того же числа N несколько раз, то получим следующий код. from functools import lru_cache
@lru_cache() def fibonacci(N): if N < 3: return 1 return fibonacci(N-1) + fibonacci(N-2)
Код стал компактным, остался понятным и мы потратили на его оптимизацию крайне мало времени и сил.
При работе с декоратором lru_cache надо помнить, что все значения параметров должны быть строго неизменяемого типа. При попытке вызова функции с, например, списковым значением аргумента, lru_cache вернет ошибку «TypeError: unhashable type: 'list'» или «Ошибка типа: нехешируемый тип 'список'».
Также сохранение полученных результатов – ручное или с помощью
lru_cache – не обходит проблему переполнения стека вызовов. Так как у нас каждому вызову функции fibonacci() будет предшествовать вызов функции
lru_cache(), количество допустимых рекурсивных вызовов fibonacci() будет
1
Декоратор – это функция, являющаяся своего рода «обёрткой» для другой функции. То есть такая функция, которая управляет запуском другой функции. Например, декоратор @lru_cache() перед запуском функции
fibonacci() проверит, был ли уже запуск с таким же параметром и, если значение для такого параметра уже было найдено, сразу вернет результат без повторного запуска функции fibonacci().
Подробнее работу с декораторами рассмотрим в будущих главах.

Открытый учебник по информатике. Программирование на Python. Основы
70 ограничено 500 (при каждом вызове в стек будет попадать сразу два вызова – для lru_cache() и для fibonacci()).
Однако, мы можем найти обходной путь – последовательно вычислить все значения до необходимого нам. from functools import lru_cache
@lru_cache() def fibonacci(N): if N < 3: return 1 return fibonacci(N-1) + fibonacci(N-2) list(map(fibonacci, range(1000))) print(fibonacci(1000))
При таком подходе последовательный вызов функции fibonacci() позволит декоратору lru_cache() запомнить результаты для предыдущих значений (по умолчанию для последних 128) и наш алгоритм не будет совершать более двух рекурсивных вызовов для вычисления любого значения от 1 до 1000!

Открытый учебник по информатике. Программирование на Python. Основы
71
Модуль itertools
Полезные типы данных
Перед тем, как переходить к «ручному» написанию обработки последовательностей добавим в нашу копилку пару полезных типов данных.
Диапазон
Диапазон – генератор целых чисел в заданном диапазоне с указанным шагом.
Синтаксис объявления диапазона: range(start, stop, step)
Генерирует последовательность от start до stop (не включая) с шагом step. В целом работает аналогично нахождению среза (генерирует такие же значения, как значения индексов в срезе).
Тип данных «диапазон» относится к последовательностям. Поэтому к переменным такого типа применимы все операции, допустимые для последовательностей, в том числе срезы и обращение по индексу.
>>> range(1, 100, 2)[10]
21
Однако, две операции над последовательностями – конкатенация (сложение) и повторение (дублирование) – диапазонами не поддерживаются.
Интересный факт.
Срез для диапазона возвращает диапазон, в котором начало, конец и шаг изменены в соответствии с указанными в срезе параметрами.
>>> range(10,100, 4)[10:5:-2] range(50, 30, -8)
В данном примере первичный диапазон вернет числа 10, 14, 18, …, 90, 92, 96.
Срез, соответственно, вернет числа 50, 46, 42, 38, 34 с шагом 2 или ряд
50, 42, 34. Как видим, шаг стал -8, начальное значение 50, первое не перечисляемое значение – 30 (из первичного среза без изменения шага).

Открытый учебник по информатике. Программирование на Python. Основы
72
Множество
Множеством называет набор уникальных значений. Множество является коллекцией, отличается коллекция от последовательности тем, что в ней нет строгого порядка следования элементов, поэтому нельзя обращаться к элементам множества по индексу.
Пустое множество объявляется так: set_a = set()
Если необходимо заполнить множество уже известными значениями set_a = {1, 2, 3, 'value'}
Также в множество можно добавить все уникальные значения итерируемого объекта, например, уникальные символы в строке или неповторяющиеся элементы списка. uniq_str = set('Hello world!') # {'H','e','l','o','w','r','d'} uniq_list = set([1,2,3,2,3,4,1,5,2]) # [1, 2, 3, 4, 5]
Операции над множествами
Операция
Обозначение Пример
Добавить элемент s.add(value) s = set() s.add(5) # {5}
Объединение
(все элементы множеств)
A | B
>>>{1,2,3} | {2,3,4}
{1,2,3,4}
Пересечение
(общие элементы множеств)
A & B
>>>{1,2,3} & {2,3,4}
{2,3}
Вычитание
(элементы А, которых нет в В)
A - B
>>> {1,2,3} - {2,3,4}
{1}
Тождественность
(множества А и В содержат одни и те же элементы)
A == B
>>> {1,2} == {2, 1}
True
>>> {2,3,4} == {2,3}
False
Подмножество
(множество А входит в В)
A <= B
A < B
>>> {1,2,3}<={2,1,3,4}
True
>>> {1,2,3} < {3,1,2}
False
Супермножество
(множество А включает В)
A >= B
A > B
>>> {1,2,3} >= {2,1,3}
True
>>> {1,2,3} > {3,1,2}
False
Количество элементов len(s)
>>> len({1,3,5,1,7})
4
Также множества поддерживают операторы изменения объекта:|=, &=, -=.

Открытый учебник по информатике. Программирование на Python. Основы
73
Модуль itertools
На данный момент мы научились перебирать параллельные элементы в нескольких последовательностях с помощью map. Но что делать, если необходимо перебрать все возможные комбинации элементов последовательности?
На помощь приходит модуль itertools, который в числе прочего содержит функции, которые помогут последовательно перебрать такие комбинации.
Перед изучением следующих функций приведем общие свойства.
1) Итерируемые объекты полностью распаковываются перед обработкой.
То есть, если в качестве параметра передать итератор, сначала он будет распакован в последовательность и только затем обработан. Данное замечание очень важно, потому что результат бесконечных генераторов не может быть обработан таким образом. Также важный нюанс, что результат работы конечных итераторов может быть очень велик, что может вызвать проблемы, связанные с выделением памяти под объект-последовательность.
Например, при передаче файлового объекта в качестве параметра, то сначала весь файл будет прочитан и только потом обработана полученная последовательность.
2) Результаты возвращаются в возрастающем порядке. Порядок возрастания определяется исходя из обрабатываемой последовательности – меньше индекс элемента, меньше значение.
Например, если передать последовательность [3, 1, 11, 10], то возвращаемые комбинации будут получаться по правилу 3 1
<1 2
< 11 3
< 10 4
. Нижние индексы отображают номер элемента в переданной последовательности.
Можно провести аналогию с цифрами в системах счисления – комбинация
1В54 будет точно идти после комбинации 01А2. Для примера из последовательности цепочка 11 3
1 2
11 3 будет больше 3 1
1 2
11 3.
3) Функции не проверяют элементы последовательность на одинаковость.
Если при распаковке итерируемого объекта будут получены одинаковые элементы, то стоящий правее будет бóльшим.
Например, если передать последовательность [3, 3, 3, 3] с соответствующим порядком 3 1
< 3 2
< 3 3
< 3 3
. Функции будут воспринимать последовательности
3 1
3 1
3 2
3 3
и 3 2
3 1
3 2
3 3
как разны. Хотя с точки зрения значений элементов

Открытый учебник по информатике. Программирование на Python. Основы
74 последовательностей разницы нет (так как индекс не возвращается в сгенерированной последовательности).
4) Результат вызова любой рассматриваемой функции – итератор.
Генерируемая последовательность не возвращается сразу вся и, соответственно, не хранится вся в памяти. Поэтому, если необходимо получить последовательность сгенерированных последовательностей, нужно привести итератор к списку или кортежу.
Размещения без повторений
Функция, возвращающая все размещения длиной r элементов последовательности – itertools.permutations. itertools.permutations
(итерируемый_объект, r=длина_размещения)
Предположим, что у нас имеет последовательность s из 3 элементов –
[s1, s2, s3]. Результатом работы функции permutations(s, r=3) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s2,s3),(s1,s3,s2),(s2,s1,s3),(s2,s3,s1),(s3,s1,s2),(s3,s2,s1)
Примеры.
>>> from itertools import permutations
>>> list(permutations('abc', r=3))
[('a',
'b',
'c'),
('a',
'c',
'b'),
('b',
'a',
'c'),
('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a') ]
>>> list(permutations('
сссс', r=2))
[('
с','с'),('с','с'),('с','с'),('с','с'),('с','с'),('с','с'),
('
с','с'),('с','с'),('с','с'),('с','с'),('с','с'),('с','с')]
Что? Почему 12 одинаковых перестановок? Дело в том, что permutations отличает все символы c (в такой постановке у нас 4 разных символа с) и выдает нам перестановки каждого символа с со всеми остальными (4⸱3 штук).

Открытый учебник по информатике. Программирование на Python. Основы
75
Размещения с повторениями
Для работы с размещениями с повторениями есть функция product.
Функция product возвращает размещениями с повторениями для элементов передаваемых итерируемых объектов длиной, указанной в параметре repeat.
Если значение repeat не задано, то для нескольких итерируемых объектов комбинации, где на первом месте будут расположены элементы первого итерируемого объекта, на втором – второго и т.д.. Если же в качестве аргументов был подан только один итерируемый объект, то в качестве результата последовательно вернуться кортежи из одного элемента.
Для последовательности s из 3 элементов – [s1, s2, s3]. Результатом работы функции product(s, repeat=2) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s1),(s1,s2),(s1,s3),(s2,s1),(s2,s2),(s2,s3),(s3,s1),(s3,s2),
(s3,s3)
Примеры.
>>> from itertools import product
>>> list(product('123'))
[('1',), ('2',), ('3',)]
>>> list(product('12', repeat=2))
[('1','1'), ('1','2'), ('2','1'), ('2','2')]
>>> list(product('abc', 'xy'))
[('a','x'), ('a','y'), ('b','x'), ('b','y'), ('c','x'), ('c','y')]
>>> list(product('bb', 'yyz'))
[('b','y'), ('b','y'), ('b','z'), ('b','y'), ('b','y'), ('b','z')]
>>> list(product('01', 'xy', repeat=2))
[('0', 'x', '0', 'x'), ('0', 'x', '0', 'y'), ('0', 'x', '1', 'x'),
('0', 'x', '1', 'y'), ('0', 'y', '0', 'x'), ('0', 'y', '0', 'y'),
('0', 'y', '1', 'x'), ('0', 'y', '1', 'y'), ('1', 'x', '0', 'x'),
('1', 'x', '0', 'y'), ('1', 'x', '1', 'x'), ('1', 'x', '1', 'y'),
('1', 'y', '0', 'x'), ('1', 'y', '0', 'y'), ('1', 'y', '1', 'x'),
('1', 'y', '1', 'y')]

Открытый учебник по информатике. Программирование на Python. Основы
76
Работу последнего примера можно проиллюстрировать с помощью следующего кода
>>> list(product(product('01', 'xy'), repeat=2))
[(('0', 'x'), ('0', 'x')), (('0', 'x'), ('0', 'y')), (('0', 'x'),
('1', 'x')), (('0', 'x'), ('1', 'y')), (('0', 'y'), ('0', 'x')),
(('0', 'y'), ('0', 'y')), (('0', 'y'), ('1', 'x')), (('0', 'y'),
('1', 'y')), (('1', 'x'), ('0', 'x')), (('1', 'x'), ('0', 'y')),
(('1', 'x'), ('1', 'x')), (('1', 'x'), ('1', 'y')), (('1', 'y'),
('0', 'x')), (('1', 'y'), ('0', 'y')), (('1', 'y'), ('1', 'x')),
(('1', 'y'), ('1', 'y'))]
Заметим, что в таком случае имеем дело с парами кортежей из seq. В предыдущем примере этап формирования кортежей пропущен, поэтому имеем дело с четверками, порядок следования элементов в которых соответствует порядку следования в парах кортежей.
Например, вместо
(('0', 'x'), ('1', 'y')) имеем
('0', 'x', '1', 'y')
).
Сочетания
Функция для получения сочетаний без повторений – itertools.combinations.
Количество элементов в сочетании устанавливается через параметр r, который является обязательным параметром.
Для последовательности s из 3 элементов – [s1, s2, s3]. Результатом работы функции combinations(s, r=2) будет итератор, который вернет следующие кортежи всегда в таком порядке, независимо от того, есть ли в последовательности повторяющиеся элементы:
(s1,s2), (s1,s3), (s2,s3)
Примеры.
>>> from itertools import combinations
>>> list(combinations('bbb', r=2))
[('b', 'b'), ('b', 'b'), ('b', 'b')]
>>> from itertools import combinations
>>> list(combinations('abc', r=2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]

Открытый учебник по информатике. Программирование на Python. Основы
77
Про уникальные комбинации
Если же мы хотим обработать только уникальные комбинации или не обрабатывать одинаковые, можно преобразовать возвращаемый итератор в множество и обработать только уникальные значения.
>>>from itertools import combinations
>>>set(combinations('bbc', r=2))
{('b', 'b'), ('b', 'c')}