Подготовка к ЕГЭ. Программирование на Python. Основы. Учебник по информатике. Программирование на Python. Основы 1 Программирование на Python. Основы
 Скачать 1.49 Mb.
|
|
Функция 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 Открытый учебник по информатике. Программирование на 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. Открытый учебник по информатике. Программирование на Python. Основы 90 Пример 1. Генератор квадратов чисел из списка. a = [5, 2, 10, 9] gen = (x*x for x in a) print(list(gen)) # [25, 4, 100, 81] Данный алгоритм выводит на экран значения, аналогичные следующему алгоритму. gen_list = [] for x in a: gen_list.append(x*x) print(gen_list) Пример 2. Генератор целых значений по модулю, считанных из многострочного файла test.txt. gen = (int(s) if s[0]!='-' else -int(s) for s in open('test.txt')) print(list(gen)) Пояснение: из файла последовательно считываются строки. Если строка не начинается на '-', то возвращаем преобразованную в число строку, в противном случае, возвращаем число, переведенное из строки, с обратным знаком. Или для каждого значения s вычисляется выражение, записанное с помощью тернарного оператора, int(s) if s[0]!='-' else -int(s). Алгоритм с аналогичным результатом: gen_list = [] for s in open('test.txt'): if s[0] != '-': gen_list.append(int(s)) else: gen_list.append(-int(s)) print(gen_list) Открытый учебник по информатике. Программирование на Python. Основы 91 Пример 3. Генератор сумм пар чисел в диапазоне 0..5, в которых хотя бы один элемент кратен 3. gen = (a + b for a in range(5) for b in range(5) if a % 3 == 0 or b % 3 == 0) print(list(gen)) # (0, 1, 2, 3, 4, 1, 4, 2, 5, 3, 4, 5, 6, 7, 4, 7) Алгоритм с аналогичным результатом: gen_list = [] for a in range(5): for b in range(5): if a % 3 == 0 or b % 3 == 0: gen_list.append(a + b) print(gen_list) Генератор для пар чисел, где оба числа должны быть кратны трем: gen = (a + b for a in range(5) if a % 3 == 0 for b in range(5) if b % 3 == 0) print(list(gen)) Алгоритм с аналогичным результатом: gen_list = [] for a in range(5): if a % 3 == 0: for b in range(5): if b % 3 == 0: gen_list.append(a + b) print(gen_list) В данном примере важно заметить одну деталь. Дело в том, что при предварительной проверке на кратность трем значения переменной a алгоритм не будет перебирать значения b, если условие будет ложным. Такой подход позволяет перебирать значения быстрее, не инициализируя вложенный цикл без необходимости. Открытый учебник по информатике. Программирование на Python. Основы 92 Пример 4. Генератор для проверки соответствия наборов значений переменных условию ( 𝑎 ∧ ¬𝑏 ∨ 𝑐). from itertools import product gen = (a and not(b) or c for a, b, c in product([0, 1], repeat=3)) print(list(gen)) # (0, 1, 0, 1, True, True, 0, 1) Но почему получились разные результаты? Все дело в порядке вычисления. Дело в том, что в случаях, когда имеем случай a ≠ 1 или b ≠ 0, результат выражения зависит от значения с. Поэтому возвращается значения c. Если же a = 1 и b = 0, то значение a and not (b) равно True, так как является результатом выполнения логической операции and. Алгоритм с аналогичным результатом: from itertools import product gen_list = [] for a, b, c in product([0, 1], repeat=3): gen_list.append(a and not(b) or c) print(gen_list) Открытый учебник по информатике. Программирование на Python. Основы 93 List comprehension и set comprehension Как можно заметить, генераторы синтаксически объявляются в круглых скобках. При этом такая запись не формирует кортеж, а именно объект генератора-выражения. В python существует две формы записи для быстрого преобразования возвращаемых генератором значений в список и множество. При применении вместо круглых скобок квадратных последовательность будет сразу распакована в список (list comprehension, также списковое включение). Такой же приём можно применить и для преобразования в множество (set comprehension). [выражение_генератора] # список значений {выражение_генератора} # множество значений List comprehension и set comprehension помимо удобства использования помогают использовать вычислительные ресурсы эффективнее, чем привычное преобразование через приведение к типу через list(gen) и set(gen). К сожалению, подобного механизма для кортежей нет, в качестве альтернативы tuple(gen) можно использовать запись через распаковку с помощью операторов астерикса и запятой (без запятой запись не работает). *(выражение_генератор), Такая запись соответствует singleton tuple нотации и запаковывает две последовательности (результат работы gen и пустое значение) в кортеж. Стоит отметить, что такая запись не имеет преимуществ перед приведением через функцию tuple(gen) в плане потребления вычислительных ресурсов. Подобный принцип также можно использовать и при присвоении значений работы генератора в переменную в виде списка. *переменная_списка, = (выражение_генератор) Однако, предпочтительным вариантом сохранения списка, являющимся результатом работы выражения-генератора, является list comprehension. Открытый учебник по информатике. Программирование на Python. Основы 94 Функции-генераторы Функции-генераторы – особая разновидность функций, которые ведут себя как итераторы. То есть, при объявлении такой функции создается объект генератор, к которому можно обратиться с помощью функции next. Осуществляется это с помощью ключевого слова yield. Пример для иллюстрации. Создадим функцию-генератор test_gen, которая будет возвращать 3 значения по порядку, например, 5, 2 и 7. >>>def test_gen(): print('Generate first value') yield 5 print('Generate second value') yield 2 print('Generate third value') yield 7 Для обращения к генератору-функции нужно создать объект генератора функции (такая тавтология). >>>gen_obj = test_gen() Что из себя представляет объект и как работает такая функция? При вызове функции возвращается объект «генератор-функция». Выполнение такой функции «заморожено» в самом начале. Условно можно изобразить такой объект следующим образом, где вертикальная красная черта (далее курсор) определяет место текущего выполнения функции. gen_obj = |