Файл: Учебник по информатике. Программирование на Python. Основы 1 Программирование на Python. Основы.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 102
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Функция zip
Функция запаковки zip – возвращает итератор кортежей, где i-тый кортеж содержит i-е элементы всех переданных аргументов.
Говоря иначе, итератор кортежей возвращает кортежи вида (a
i
, b
i
, …, z
i
), где
a, b, …, z – итерируемые объекты, переданные в качестве аргументов функции
zip, i – допустимый для всех объектов индекс.
Кортежи возвращаются по возрастанию индекса i до тех пор, пока на возвращаемой позиции всех переданных последовательностей есть значение.
Рассмотрим пример с запаковкой трех последовательностей (см.рис.2). iter1 = [8, -3, 1, 0, 13, 7, 19] iter2 = [9, 5, 4, -6] iter3 = [3, 1, 5, 1, 71]
Тогда итератор z z = zip(iter1, iter2, iter3)
Будет последовательно возвращать кортежи (8, 9, 3), (-3, 5, 1), (1, 4, 5),
(0, -6, 1).
Рисунок 2. Пример запаковки
Открытый учебник по информатике. Программирование на Python. Основы
78
Циклы for и while. Простые алгоритмы
Цикл for
Конструкция for в языке python значительно отличается от подобной конструкции в других языках. В python данная конструкция служит только для перебора элементов итерируемого объекта.
Синтаксически конструкция выглядит так:
for переменные in итерируемый_объект: код_для_обработки
Говоря иначе, каждый элемент итерируемого объекта распаковывается в список переменных или сохраняется в одной переменной.
Одно выполнение списка команд, записанных внутри цикла, называется итерацией.
Важно понимать, что все операции, описанные внутри цикла, выполняются от первой строки до последней (кроме случаев, когда выполнение какой-либо команды приводит к ошибке или когда указаны специальные команды, которые управляют работой цикла).
Примеры.
>>>for x in [1, 3, 7, 13]:
>>> print(x)
1 3
7 13
>>>for i in range(2, 10, 2):
>>> print(i, end = ':')
2:4:6:8:
>>>from itertools import product
>>>l = []
>>>for a, b in product([2,4,6], [3,4,5]):
>>> if (a + b) % 2 == 0:
>>> l.append(a+b)
>>>l
[6, 8, 10]
Открытый учебник по информатике. Программирование на Python. Основы
79
Операторы continue и break
Оператор continue – переход на следующую итерацию цикла без выполнения кода текущей итерации до конца.
Оператор break – выход из цикла без завершения кода текущей итерации и выполнения последующих за строкой с break команд.
При этом итерация считается выполненной, то есть прерывание выполнения тела цикла именно завершает итерацию без выполнения последующих команд.
Примеры.
>>>for a in [1,3,5,7,9,11]:
>>> if a > 8:
>>> break
>>> print(a*2, end=' ')
2, 6, 10, 14
>>>for a in [1,3,5,7,9,11]:
>>> if 4 <= a < 8:
>>> continue
>>> print(a*2, end=' ')
2, 6, 18, 22
Конструкция for…else
Также конструкция for..in в python имеет возможность проверить, завершился ли цикл без выхода с помощью оператора break.
for переменные in итерируемый_объект: тело цикла
else: если цикл окончил работу без остановки с помощью break
Пример.
>>>for i in [2, 10, 20, 50, 4, 70]:
>>> if i <= 50:
>>> print('Не все числа больше, чем 50')
>>> break
>>>else:
>>> print('Все числа больше, чем 50')
Открытый учебник по информатике. Программирование на Python. Основы
80
Примеры использования
Перебрать все целочисленные концы диапазонов между целыми значениями a и b. from itertools import combinations a, b = map(int, input().split()) print(list(combinations(range(a, b+1), r=2)))
Пример вывода для a = 2 и b = 5.
[(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
Построить таблицу истинности для выражения ???? ∧ ???? → ¬???? from itertools import product for a, b, c in product([0, 1], repeat=3): print(a, b, c, (a and b) <= (not c))
Вывод
0 0 0 True
0 0 1 True
0 1 0 True
0 1 1 True
1 0 0 True
1 0 1 True
1 1 0 True
1 1 1 False
Сколько последовательностей длиной 5 можно составить путем перестановки букв слова ПРИМЕР? from itertools import permutations print(len(set(permutations('ПРИМЕР'))))
Сколько в списке смежных пар таких, что их сумма кратна 10? Смежной парой называется пара подряд идущих чисел. nums = [1, 5, 3, 7, 5, 6, 4 ,6, 6 ,2, 8] res = [] for a, b in zip(nums, nums[1: ]): if (a + b) % 10 == 0: res.append(a+b) print(len(res))
Открытый учебник по информатике. Программирование на Python. Основы
81
Цикл while
Также бывают случаи, когда итерации необходимо выполнять до тех пор, пока соблюдается какое-то условие. И именно для решения таких задач существует конструкция цикла while. while условие_продолжения:
# тело цикла
Тело цикла будет повторно выполняться до тех пор, пока истинно условие.
Сделаем трассировку простого алгоритма, использующего цикл while.
1. x = 5 2. while x < 30:
3. x += 7 4. print(x)
Номер строки Команда
х
x < 30
1 x = 5 5
2 while x < 30:
5 < 30 # True
3 x += 7 12 2 while x < 30:
12 < 30 # True
3 x += 7 19 2 while x < 30:
19 < 30 # True
3 x += 7 26 2 while x < 30:
26 < 30 # True
3 x += 7 33 2 while x < 30:
33 < 30 # False
4 print(x)
Как можно заметить, цикл выполнил 4 итерации и завершился, когда значение
x перестало соответствовать условию x < 30.
Пример.
С клавиатуры вводятся числа. Необходимо накопить сумму введенных чисел, большую, чем 100. Вывести на экран первую такую сумму. s = [] while sum(s) <= 100: x = int(input()) s.append(x) print('Sum = ', sum(s))
Открытый учебник по информатике. Программирование на Python. Основы
82
Операторы continue и break
Как и в случае с циклом for для цикла while существует пара операторов, которая позволяет управлять выполнением циклического алгоритма.
Оператор continue – пропускает весь код до конца тела цикла и переходит к следующей итерации.
Оператор break – прерывает выполнение цикла на строке, в которой вызван.
Конструкция while…else
Данная конструкция аналогична конструкции for…else, код, написанный в блоке else, выполняется только в том случае, если цикл был окончен без использования оператора break.
Простые алгоритмы
Рассмотрим реализацию простых алгоритмов, на основе которых в дальнейшем будем строить более сложные алгоритмы.
Реализация счетчика
Идея алгоритма очень простая – если при последовательном переборе вариантов встречаем удовлетворяющее условию значение, увеличиваем счетчик на 1. Перед началом перебора принимаем его значение за 0.
Псевдокод алгоритма: count = 0 цикл_для_перебора: if условие_отбора: count += 1
Пример.
Сколько чисел, входящих в диапазон [1000;5000], кратны 3 и не кратны 5? count = 0 for x in range(1000; 5001): if x % 3 == 0 and x % 5 != 0: count += 1 print(count)
Открытый учебник по информатике. Программирование на Python. Основы
83
Нахождение суммы/произведения
Идея алгоритма аналогична алгоритму для счётчика, за тем исключением, что мы добавляем не единицу, а найденное число. Для нахождения суммы изначально задаем значение 0 (0+х = х), для произведения – 1 (1⸱х = х).
Псевдокод алгоритма для нахождения суммы: s = 0 цикл_для_перебора: if условие_отбора: s += найденное_значение
Псевдокод алгоритма для нахождения произведения: p = 1 цикл_для_перебора: if условие_отбора: p *= найденное_значение
Пример.
В многострочном файле test.txt посчитайте суммарное количество букв А в строках, длина которых больше 100. f = open('test.txt') line = f.readline() s = 0 while line: if len(line) > 100: s += line.count('A') line = f.readline() print(s) f.close()
Открытый учебник по информатике. Программирование на Python. Основы
84
Нахождение минимума/максимума
Логика этого алгоритма строится на следующем рассуждении: если текущее подходящее значение меньше (для нахождения минимума) уже найденного значения минимума, тогда переопределяем данное значение.
Аналогичное рассуждение производится для максимума. В качестве начальных значений на языке Python удобно использовать специальные числовые объекты – значения бесконечностей – float('-inf') и float('inf').
Обобщенный алгоритм для минимума: m = float('inf') цикл_для_перебора: if условие_отбора and m > найденное_значение: m = найденное_значение
Для нахождения максимума достаточно изменить «плюс бесконечность» на
«минус бесконечность» и знак сравнения.
Однако, в отличии от предыдущих алгоритмов, у алгоритмов нахождения максимума и минимума может быть требование к нахождению первого или последнего совпадения.
Предложенный ранее обобщенный алгоритм находит первое минимальное значение, так как ищется значение строго меньшее. Если же нам необходимо найти последнее совпадение – нужно заменить строгий знак на нестрогий.
Обобщенный алгоритм для нахождения последнего минимального значения: m = float('inf') цикл_для_перебора: if условие_отбора and m >= найденное_значение: m = найденное_значение
Открытый учебник по информатике. Программирование на Python. Основы
85
Основная идея динамического программирования
Стоит отметить, что рассмотренные алгоритмы реализации счётчика, нахождения суммы/произведения/минимума/максимума являются самыми простыми примерами динамического программирования.
Идея динамического программирования следующая: нет необходимости сохранять весь обработанный массив данных, достаточно сохранить только те значения, которые будут полезны по отношению к решаемой задаче.
Например, мы ищем четный максимум и уже обработали N элементов.
Рисунок 1. Пример обрабатываемой последовательности
Что нам нужно знать об уже обработанных N элементах?
Во-первых, были ли вообще удовлетворяющие условию элементы. Для этого принято использовать «нейтральные» значения – такие значения, которые не удовлетворяют ограничениям задачи. Например, любое нечетное значение или значение для минус бесконечности (float('-inf')).
Определив такие значения, после выполнения алгоритма мы можем понять, нашли искомое значение или нет. Ведь в последовательности может и не быть элементов, удовлетворяющих условию поиска. Для рассматриваемой задачи – последовательность из нечетных элементов не содержит нужных значений.
Во-вторых, указать условие, которое определит найден ли подходящий элемент. В случае с четным максимумом это признак четности (x % 2 == 0).
В-третьих, указать условие для нахождения нового максимума.
Подытожим и перенесем наше рассуждение в псеводкод на Python.
Для начального нечетного
Для начального бесконечного mx = 3 цикл_для_перебора: x = вычисляем_значение if x%2==0 and (mx==3 or mx (mx==float('-inf') or mxПри работе данного алгоритма первое найденное чётное значение сохраняется, так как проходит проверка на нейтральное значение. После чего первое условие в скобке перестанет выполняться и алгоритм будет постепенно
Открытый учебник по информатике. Программирование на Python. Основы
86 находить максимальное чётное значение. Если после завершения алгоритма значение переменной mx останется начальным, значит в последовательности не было чётных чисел.
В чем же существенное отличие значений 3 и float('-inf')? Все дело в том, что значение float('-inf') меньше любого значения, которое может встретиться при переборе последовательности. Поэтому алгоритм можно преобразовать следующим образом.
Начальная версия
Оптимизированная версия mx = float('-inf') цикл_для_перебора: x = вычисляем_значение if x%2==0 and \
(mx==float('-inf') or mxТогда, если начальное значение переменной mx останется равным float('-inf'), значит в последовательности не было удовлетворяющих элементов.
Преимущество таких алгоритмов заключается в эффективном использовании памяти и скорости работы. Потому что нет необходимости запускать встроенные функции для всего обрабатываемого потока данных и формировать новые «тяжелые» структуры в памяти.
Пример реализации на встроенных функциях nums = map(int, open('file')) evens = filter(lambda x: x % 2 == 0, nums) print(max(evens))
Динамический пример mx = float('-inf') for x in map(int, open('file'): if x % 2 == 0 and mx < x: mx = x print(mx)
Открытый учебник по информатике. Программирование на Python. Основы
87
В некоторых случаях подобные алгоритмы позволяют преобразовать переборы с нелинейной сложностью (переборы пар, троек и т.п) в линейные.
Например, если необходимо найти количество пар чисел с четной суммой в списке целых чисел nums.
from random import randrange nums = [randrange(-
10000
,
10000
) for
_ in range
(
10000
)]
Переборный алгоритмы
from itertools import combinations count = 0 for t in combinations(nums, r=2): if sum(t) % 2 == 0: count += 1 print(count)
Однако мы можем подумать о динамическом программировании и понять, что четные суммы образуют пары чисел с одинаковой четностью. Поэтому достаточно посчитать количества четных и нечетных значений и по формуле сочетаний вычислить интересующее нас количество.
Статистический алгоритм
odd, even = 0, 0 for x in nums: if x % 2 == 0: even += 1 else: odd += 1 print((even*(even-1) + odd*(odd-1)) // 2)
Или можем считать количество четных сумм на каждой итерации, использовав подход динамического программирования.
Динамическое программирование
count, odd, even = 0, 0, 0 for x in nums: if x % 2 == 0: count += even even += 1 else: count += odd odd += 1 print(count)
Скорость работы переборного алгоритма можно наглядно сопоставить со скоростью работы последних двух алгоритмов на примере
Открытый учебник по информатике. Программирование на Python. Основы
88 последовательности из 10 тысяч чисел. Так переборный алгоритм будет считать порядка 10 секунд, в то время как другим алгоритмам для этого понадобятся доли секунды.
Реализации более сложных алгоритмов изучим в следующих главах.
Перебор цифр числа
Еще одним популярным алгоритмом обработки чисел является алгоритм перебора разрядов числа.
Ручной алгоритм перевода выглядит следующий образом.
Число делится на основание системы счисления – остаток от деления является младшим (правым) разрядом, полученный результат деления (целая часть) делится на основание системы счисления – остаток от деления второй справа разряд. Данные действия повторятся до тех пор, пока результат деления не станет равен нулю.
Рисунок 2. Пример перевода 143 10
в семеричную систему счисления
Таким образом мы можем заключить, что алгоритм последовательного деления до нуля позволяет перебрать все разряды числа в n-ричной системе счисления.
Как же будет выглядеть такой алгоритм на языке Python? x = int(input('Введите число в 10 сс:')) n = int(input('Введите основание конечной сс:'))
# пока не дошли до нуля while x > 0:
# определяем младший ненайденный разряд digit = x % n
# находим число для следующего шага x = x // n
Данный алгоритм можно расширять с помощью рассмотренных ранее базовых алгоритмов. Например, для подсчета количества разрядов с определенным значением или суммы всех разрядов.
Открытый учебник по информатике. Программирование на Python. Основы
89
Генераторы. Функции all и any
В данной главе мы рассмотрим как работают генераторы на самом общем уровне – узнаем, что это такое и какой принцип формирования значений используется при работе. Более глубокий анализ и продвинутые методы работы с генераторами в Python будут освещены в одной из следующих глав.
Генераторы
Генераторы, как можно понять из названия типа объектов, это объекты, которые генерируют значения. Говоря иначе при каждом новом запросе вычисляют новое значение по заданному алгоритму.
Генераторы ведут себя как итераторы, то есть вычисляют значения по мере обращения к ним. То есть при многократном вызове метода next(gen), где gen
– созданный генератор, мы последовательно получаем генерируемую последовательность.
Генератор не является последовательностью, то есть нельзя обратиться к возвращаемым элементам генератора по индексу.
Генераторы реализуют модель ленивых вычислений. Говоря иначе, следующее значение вычисляется только тогда, когда в программе указана команда возвращения этого значения. Например, при очередном вызове функции next.
Выражения-генераторы
Выражения-генераторы очень удобный инструмент для создания итераторов.
Синтаксически описание выражения-генератора выглядит так: выражение_генератора ::=
(выражение for набор_переменных1 in итер.об1 [if условие1]
[for набор_переменныхN in итер.обN [if условиеN]])
В итоге возвращается генератор который выдает значения выражения, которые генерируются в соответствии с порядком описанным в циклах for и соответствующие указанным условиям.
Стоит отметить, что переменные в таких генераторах определяются слева направо и условиеK может содержать любую из переменных, входящих в наборы 1..K.
Функция запаковки zip – возвращает итератор кортежей, где i-тый кортеж содержит i-е элементы всех переданных аргументов.
Говоря иначе, итератор кортежей возвращает кортежи вида (a
i
, b
i
, …, z
i
), где
a, b, …, z – итерируемые объекты, переданные в качестве аргументов функции
zip, i – допустимый для всех объектов индекс.
Кортежи возвращаются по возрастанию индекса i до тех пор, пока на возвращаемой позиции всех переданных последовательностей есть значение.
Рассмотрим пример с запаковкой трех последовательностей (см.рис.2). iter1 = [8, -3, 1, 0, 13, 7, 19] iter2 = [9, 5, 4, -6] iter3 = [3, 1, 5, 1, 71]
Тогда итератор z z = zip(iter1, iter2, iter3)
Будет последовательно возвращать кортежи (8, 9, 3), (-3, 5, 1), (1, 4, 5),
(0, -6, 1).
Рисунок 2. Пример запаковки
Открытый учебник по информатике. Программирование на Python. Основы
78
Циклы for и while. Простые алгоритмы
Цикл for
Конструкция for в языке python значительно отличается от подобной конструкции в других языках. В python данная конструкция служит только для перебора элементов итерируемого объекта.
Синтаксически конструкция выглядит так:
for переменные in итерируемый_объект: код_для_обработки
Говоря иначе, каждый элемент итерируемого объекта распаковывается в список переменных или сохраняется в одной переменной.
Одно выполнение списка команд, записанных внутри цикла, называется итерацией.
Важно понимать, что все операции, описанные внутри цикла, выполняются от первой строки до последней (кроме случаев, когда выполнение какой-либо команды приводит к ошибке или когда указаны специальные команды, которые управляют работой цикла).
Примеры.
>>>for x in [1, 3, 7, 13]:
>>> print(x)
1 3
7 13
>>>for i in range(2, 10, 2):
>>> print(i, end = ':')
2:4:6:8:
>>>from itertools import product
>>>l = []
>>>for a, b in product([2,4,6], [3,4,5]):
>>> if (a + b) % 2 == 0:
>>> l.append(a+b)
>>>l
[6, 8, 10]
Открытый учебник по информатике. Программирование на Python. Основы
79
Операторы continue и break
Оператор continue – переход на следующую итерацию цикла без выполнения кода текущей итерации до конца.
Оператор break – выход из цикла без завершения кода текущей итерации и выполнения последующих за строкой с break команд.
При этом итерация считается выполненной, то есть прерывание выполнения тела цикла именно завершает итерацию без выполнения последующих команд.
Примеры.
>>>for a in [1,3,5,7,9,11]:
>>> if a > 8:
>>> break
>>> print(a*2, end=' ')
2, 6, 10, 14
>>>for a in [1,3,5,7,9,11]:
>>> if 4 <= a < 8:
>>> continue
>>> print(a*2, end=' ')
2, 6, 18, 22
Конструкция for…else
Также конструкция for..in в python имеет возможность проверить, завершился ли цикл без выхода с помощью оператора break.
for переменные in итерируемый_объект: тело цикла
else: если цикл окончил работу без остановки с помощью break
Пример.
>>>for i in [2, 10, 20, 50, 4, 70]:
>>> if i <= 50:
>>> print('Не все числа больше, чем 50')
>>> break
>>>else:
>>> print('Все числа больше, чем 50')
Открытый учебник по информатике. Программирование на Python. Основы
80
Примеры использования
Перебрать все целочисленные концы диапазонов между целыми значениями a и b. from itertools import combinations a, b = map(int, input().split()) print(list(combinations(range(a, b+1), r=2)))
Пример вывода для a = 2 и b = 5.
[(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
Построить таблицу истинности для выражения ???? ∧ ???? → ¬???? from itertools import product for a, b, c in product([0, 1], repeat=3): print(a, b, c, (a and b) <= (not c))
Вывод
0 0 0 True
0 0 1 True
0 1 0 True
0 1 1 True
1 0 0 True
1 0 1 True
1 1 0 True
1 1 1 False
Сколько последовательностей длиной 5 можно составить путем перестановки букв слова ПРИМЕР? from itertools import permutations print(len(set(permutations('ПРИМЕР'))))
Сколько в списке смежных пар таких, что их сумма кратна 10? Смежной парой называется пара подряд идущих чисел. nums = [1, 5, 3, 7, 5, 6, 4 ,6, 6 ,2, 8] res = [] for a, b in zip(nums, nums[1: ]): if (a + b) % 10 == 0: res.append(a+b) print(len(res))
Открытый учебник по информатике. Программирование на Python. Основы
81
Цикл while
Также бывают случаи, когда итерации необходимо выполнять до тех пор, пока соблюдается какое-то условие. И именно для решения таких задач существует конструкция цикла while. while условие_продолжения:
# тело цикла
Тело цикла будет повторно выполняться до тех пор, пока истинно условие.
Сделаем трассировку простого алгоритма, использующего цикл while.
1. x = 5 2. while x < 30:
3. x += 7 4. print(x)
Номер строки Команда
х
x < 30
1 x = 5 5
2 while x < 30:
5 < 30 # True
3 x += 7 12 2 while x < 30:
12 < 30 # True
3 x += 7 19 2 while x < 30:
19 < 30 # True
3 x += 7 26 2 while x < 30:
26 < 30 # True
3 x += 7 33 2 while x < 30:
33 < 30 # False
4 print(x)
Как можно заметить, цикл выполнил 4 итерации и завершился, когда значение
x перестало соответствовать условию x < 30.
Пример.
С клавиатуры вводятся числа. Необходимо накопить сумму введенных чисел, большую, чем 100. Вывести на экран первую такую сумму. s = [] while sum(s) <= 100: x = int(input()) s.append(x) print('Sum = ', sum(s))
Открытый учебник по информатике. Программирование на Python. Основы
82
Операторы continue и break
Как и в случае с циклом for для цикла while существует пара операторов, которая позволяет управлять выполнением циклического алгоритма.
Оператор continue – пропускает весь код до конца тела цикла и переходит к следующей итерации.
Оператор break – прерывает выполнение цикла на строке, в которой вызван.
Конструкция while…else
Данная конструкция аналогична конструкции for…else, код, написанный в блоке else, выполняется только в том случае, если цикл был окончен без использования оператора break.
Простые алгоритмы
Рассмотрим реализацию простых алгоритмов, на основе которых в дальнейшем будем строить более сложные алгоритмы.
Реализация счетчика
Идея алгоритма очень простая – если при последовательном переборе вариантов встречаем удовлетворяющее условию значение, увеличиваем счетчик на 1. Перед началом перебора принимаем его значение за 0.
Псевдокод алгоритма: count = 0 цикл_для_перебора: if условие_отбора: count += 1
Пример.
Сколько чисел, входящих в диапазон [1000;5000], кратны 3 и не кратны 5? count = 0 for x in range(1000; 5001): if x % 3 == 0 and x % 5 != 0: count += 1 print(count)
Открытый учебник по информатике. Программирование на Python. Основы
83
Нахождение суммы/произведения
Идея алгоритма аналогична алгоритму для счётчика, за тем исключением, что мы добавляем не единицу, а найденное число. Для нахождения суммы изначально задаем значение 0 (0+х = х), для произведения – 1 (1⸱х = х).
Псевдокод алгоритма для нахождения суммы: s = 0 цикл_для_перебора: if условие_отбора: s += найденное_значение
Псевдокод алгоритма для нахождения произведения: p = 1 цикл_для_перебора: if условие_отбора: p *= найденное_значение
Пример.
В многострочном файле test.txt посчитайте суммарное количество букв А в строках, длина которых больше 100. f = open('test.txt') line = f.readline() s = 0 while line: if len(line) > 100: s += line.count('A') line = f.readline() print(s) f.close()
Открытый учебник по информатике. Программирование на Python. Основы
84
Нахождение минимума/максимума
Логика этого алгоритма строится на следующем рассуждении: если текущее подходящее значение меньше (для нахождения минимума) уже найденного значения минимума, тогда переопределяем данное значение.
Аналогичное рассуждение производится для максимума. В качестве начальных значений на языке Python удобно использовать специальные числовые объекты – значения бесконечностей – float('-inf') и float('inf').
Обобщенный алгоритм для минимума: m = float('inf') цикл_для_перебора: if условие_отбора and m > найденное_значение: m = найденное_значение
Для нахождения максимума достаточно изменить «плюс бесконечность» на
«минус бесконечность» и знак сравнения.
Однако, в отличии от предыдущих алгоритмов, у алгоритмов нахождения максимума и минимума может быть требование к нахождению первого или последнего совпадения.
Предложенный ранее обобщенный алгоритм находит первое минимальное значение, так как ищется значение строго меньшее. Если же нам необходимо найти последнее совпадение – нужно заменить строгий знак на нестрогий.
Обобщенный алгоритм для нахождения последнего минимального значения: m = float('inf') цикл_для_перебора: if условие_отбора and m >= найденное_значение: m = найденное_значение
Открытый учебник по информатике. Программирование на Python. Основы
85
Основная идея динамического программирования
Стоит отметить, что рассмотренные алгоритмы реализации счётчика, нахождения суммы/произведения/минимума/максимума являются самыми простыми примерами динамического программирования.
Идея динамического программирования следующая: нет необходимости сохранять весь обработанный массив данных, достаточно сохранить только те значения, которые будут полезны по отношению к решаемой задаче.
Например, мы ищем четный максимум и уже обработали N элементов.
Рисунок 1. Пример обрабатываемой последовательности
Что нам нужно знать об уже обработанных N элементах?
Во-первых, были ли вообще удовлетворяющие условию элементы. Для этого принято использовать «нейтральные» значения – такие значения, которые не удовлетворяют ограничениям задачи. Например, любое нечетное значение или значение для минус бесконечности (float('-inf')).
Определив такие значения, после выполнения алгоритма мы можем понять, нашли искомое значение или нет. Ведь в последовательности может и не быть элементов, удовлетворяющих условию поиска. Для рассматриваемой задачи – последовательность из нечетных элементов не содержит нужных значений.
Во-вторых, указать условие, которое определит найден ли подходящий элемент. В случае с четным максимумом это признак четности (x % 2 == 0).
В-третьих, указать условие для нахождения нового максимума.
Подытожим и перенесем наше рассуждение в псеводкод на Python.
Для начального нечетного
Для начального бесконечного mx = 3 цикл_для_перебора: x = вычисляем_значение if x%2==0 and (mx==3 or mx
Открытый учебник по информатике. Программирование на Python. Основы
86 находить максимальное чётное значение. Если после завершения алгоритма значение переменной mx останется начальным, значит в последовательности не было чётных чисел.
В чем же существенное отличие значений 3 и float('-inf')? Все дело в том, что значение float('-inf') меньше любого значения, которое может встретиться при переборе последовательности. Поэтому алгоритм можно преобразовать следующим образом.
Начальная версия
Оптимизированная версия mx = float('-inf') цикл_для_перебора: x = вычисляем_значение if x%2==0 and \
(mx==float('-inf') or mx
Преимущество таких алгоритмов заключается в эффективном использовании памяти и скорости работы. Потому что нет необходимости запускать встроенные функции для всего обрабатываемого потока данных и формировать новые «тяжелые» структуры в памяти.
Пример реализации на встроенных функциях nums = map(int, open('file')) evens = filter(lambda x: x % 2 == 0, nums) print(max(evens))
Динамический пример mx = float('-inf') for x in map(int, open('file'): if x % 2 == 0 and mx < x: mx = x print(mx)
Открытый учебник по информатике. Программирование на Python. Основы
87
В некоторых случаях подобные алгоритмы позволяют преобразовать переборы с нелинейной сложностью (переборы пар, троек и т.п) в линейные.
Например, если необходимо найти количество пар чисел с четной суммой в списке целых чисел nums.
from random import randrange nums = [randrange(-
10000
,
10000
) for
_ in range
(
10000
)]
Переборный алгоритмы
from itertools import combinations count = 0 for t in combinations(nums, r=2): if sum(t) % 2 == 0: count += 1 print(count)
Однако мы можем подумать о динамическом программировании и понять, что четные суммы образуют пары чисел с одинаковой четностью. Поэтому достаточно посчитать количества четных и нечетных значений и по формуле сочетаний вычислить интересующее нас количество.
Статистический алгоритм
odd, even = 0, 0 for x in nums: if x % 2 == 0: even += 1 else: odd += 1 print((even*(even-1) + odd*(odd-1)) // 2)
Или можем считать количество четных сумм на каждой итерации, использовав подход динамического программирования.
Динамическое программирование
count, odd, even = 0, 0, 0 for x in nums: if x % 2 == 0: count += even even += 1 else: count += odd odd += 1 print(count)
Скорость работы переборного алгоритма можно наглядно сопоставить со скоростью работы последних двух алгоритмов на примере
Открытый учебник по информатике. Программирование на Python. Основы
88 последовательности из 10 тысяч чисел. Так переборный алгоритм будет считать порядка 10 секунд, в то время как другим алгоритмам для этого понадобятся доли секунды.
Реализации более сложных алгоритмов изучим в следующих главах.
Перебор цифр числа
Еще одним популярным алгоритмом обработки чисел является алгоритм перебора разрядов числа.
Ручной алгоритм перевода выглядит следующий образом.
Число делится на основание системы счисления – остаток от деления является младшим (правым) разрядом, полученный результат деления (целая часть) делится на основание системы счисления – остаток от деления второй справа разряд. Данные действия повторятся до тех пор, пока результат деления не станет равен нулю.
Рисунок 2. Пример перевода 143 10
в семеричную систему счисления
Таким образом мы можем заключить, что алгоритм последовательного деления до нуля позволяет перебрать все разряды числа в n-ричной системе счисления.
Как же будет выглядеть такой алгоритм на языке Python? x = int(input('Введите число в 10 сс:')) n = int(input('Введите основание конечной сс:'))
# пока не дошли до нуля while x > 0:
# определяем младший ненайденный разряд digit = x % n
# находим число для следующего шага x = x // n
Данный алгоритм можно расширять с помощью рассмотренных ранее базовых алгоритмов. Например, для подсчета количества разрядов с определенным значением или суммы всех разрядов.
Открытый учебник по информатике. Программирование на Python. Основы
89
Генераторы. Функции all и any
В данной главе мы рассмотрим как работают генераторы на самом общем уровне – узнаем, что это такое и какой принцип формирования значений используется при работе. Более глубокий анализ и продвинутые методы работы с генераторами в Python будут освещены в одной из следующих глав.
Генераторы
Генераторы, как можно понять из названия типа объектов, это объекты, которые генерируют значения. Говоря иначе при каждом новом запросе вычисляют новое значение по заданному алгоритму.
Генераторы ведут себя как итераторы, то есть вычисляют значения по мере обращения к ним. То есть при многократном вызове метода next(gen), где gen
– созданный генератор, мы последовательно получаем генерируемую последовательность.
Генератор не является последовательностью, то есть нельзя обратиться к возвращаемым элементам генератора по индексу.
Генераторы реализуют модель ленивых вычислений. Говоря иначе, следующее значение вычисляется только тогда, когда в программе указана команда возвращения этого значения. Например, при очередном вызове функции next.
Выражения-генераторы
Выражения-генераторы очень удобный инструмент для создания итераторов.
Синтаксически описание выражения-генератора выглядит так: выражение_генератора ::=
(выражение for набор_переменных1 in итер.об1 [if условие1]
[for набор_переменныхN in итер.обN [if условиеN]])
В итоге возвращается генератор который выдает значения выражения, которые генерируются в соответствии с порядком описанным в циклах for и соответствующие указанным условиям.
Стоит отметить, что переменные в таких генераторах определяются слева направо и условиеK может содержать любую из переменных, входящих в наборы 1..K.