Сборник. Сборник упражнений
 Скачать 1.68 Mb.
|
|
Глава 5 Списки До сих пор все переменные, которые мы создавали, хранили единственное значение. При этом само значение могло быть абсолютно любого типа – целочисленного, строкового, булевого и т. д. И хотя для более или менее простых задач это приемлемо, когда речь заходит о больших наборах данных, такого подхода становится недостаточно. И тогда на арену вы- ходят списки (list), позволяющие хранить в одной переменной множество значений. Переменная списка создается так же, как и все остальные, – при помощи оператора присваивания. Единственное отличие в случае со списком со- стоит в том, что его значения справа от знака равенства должны быть за- ключены в квадратные скобки и разделены запятыми. Например, в следу- ющем выражении создается список с именем data, состоящий из четырех чисел с плавающей запятой. В следующей строке осуществляется вывод списка на экран при помощи функции print. При этом будут отображены все четыре числа, поскольку они хранятся в одной переменной data. data = [2.71, 3.14, 1.41, 1.62] print(data) Список может содержать ноль или больше элементов. Пустой список, не содержащий значений, обозначается как [] (закрывающая квадратная скобка следует непосредственно за открывающей). Как целочисленные переменные могут быть инициализированы нулевым значением, которое впоследствии может измениться, так и списки могут изначально созда- ваться пустыми, а позже – по ходу выполнения программы – пополняться элементами. 5.1. д оступ к элементам списка Каждое значение в списке именуется элементом. Элементы списка прону- мерованы последовательными целыми числами, начиная с нуля. Каждое число идентифицирует конкретный элемент списка и называется индек- 90 Упражнения сом этого элемента. В предыдущем фрагменте кода число 2,71 соответ- ствует индексу 0, а 1,62 – индексу 3. Обратиться к конкретному элементу списка можно при помощи име- ни переменной, хранящей список, с последующим индексом, заключен- ным в квадратные скобки. Например, показанная ниже запись выведет на экран число 3,14. Обратите внимание, что индекс 1 соответствует не первому, а второму в списке элементу. data = [2.71, 3.14, 1.41, 1.62] print(data[1]) Изменить значение конкретного элемента списка можно при помо- щи обычного оператора присваивания. При этом слева от него должно стоять имя переменной, в которой хранится список, с индексом нужного элемента в квадратных скобках, а справа – новое значение. В результате выполнения этой операции значение будет присвоено соответствующему элементу с удалением предыдущего содержимого. Остальные элементы списка затронуты не будут. Посмотрите на следующий фрагмент кода. Здесь мы создали список из четырех элементов, после чего изменили значение элемента с индексом 2 на 2,30. В результате выполнения функции print будет выведено актуаль- ное содержимое списка со следующими значениями: 2,71, 3,14, 2,30 и 1,62. data = [2.71, 3.14, 1.41, 1.62] data[2] = 2.30 print(data) 5.2. ц иклы и списки Инструкция for позволяет проходить по элементам любой коллекции. При этом коллекцией может являться как диапазон целых чисел, созданный при помощи функции range, так и список. В следующем фрагменте кода цикл for используется для суммирования элементов из списка data. # Инициализируем переменные data и total data = [2.71, 3.14, 1.41, 1.62] total = 0 # Суммируем значения в списке for value in data: total = total + value # Выводим сумму print("Сумма значений элементов списка:", total) Списки 91 Данная программа начинается с инициализации переменных data и to- tal . Затем наступает черед цикла for. На первой итерации цикла перемен- ной value присваивается значение первого элемента списка data, пос ле чего выполняется тело цикла, в котором текущая сумма значений элемен- тов списка увеличивается на value. После выполнения тела цикла начинается следующая итерация, в про- цессе которой переменной value присваивается значение очередного элемента списка data, и тело цикла выполняется вновь. Цикл будет вы- полняться до тех пор, пока не будут пройдены все элементы списка. В ре- зультате будет рассчитана сумма значений всех элементов списка. После этого сумма будет выведена на экран, и на этом выполнение программы прекратится. Иногда необходимо пройти в цикле непосредственно по индексам спис ка, а не по значениям элементов. Для этого нужно сначала вычис- лить общее количество элементов, находящихся в списке. Сделать это можно при помощи функции len. Данная функция принимает на вход единственный аргумент в виде списка и возвращает текущее количество элементов в нем. Если в списке нет ни одного элемента, функция len ожи- даемо вернет ноль. Функцию len бывает удобно использовать вместе с функцией range для создания коллекции целых чисел, являющихся допустимыми индексами списка. Это можно сделать, передав в качестве единственного аргумента в функцию range длину списка. Поднабор индексов можно собрать, если передать функции range второй параметр. В следующем фрагменте кода демонстрируется использование цикла for для прохода по всем индексам списка data, за исключением первого, для определения позиции элемента с наибольшим значением в коллекции. # Инициализируем переменные data и largest_pos data = [1.62, 1.41, 3.14, 2.71] largest_pos = 0 # Находим позицию элемента с наибольшим значением for i in range(1, len(data)): if data[i] > data[largest_pos]: largest_pos = i # Отображаем результат print("Наибольшее значение", data[largest_pos], \ "находится в элементе с индексом", largest_pos) Программа начинается с инициализации переменных data и largest_ pos . После этого с использованием функции range создается коллекция, по которой будет проходить цикл for. При этом первым аргументом пере- дается единица, а вторым – длина списка, равная четырем. В результате 92 Упражнения в коллекции оказываются последовательные целые числа от единицы до трех, которые адресуют все элементы списка data, кроме первого, что нам и нужно. На первой итерации цикла for внутренней переменной цикла i при- сваивается значение 1, после чего в первый раз выполняется тело цикла. Внутри него выполняется сравнение элементов списка data с индексом i и largest_pos. Поскольку первых из них меньше, булево выражение воз- вращает значение False, и тело блока if пропускается. Далее управление передается в начало цикла for, и на этот раз пере- менной i присваивается значение 2. Тело цикла выполняется во второй раз. В этом случае значение элемента с индексом i оказывается больше по сравнению с largest_pos, в результате чего переменной largest_pos при- сваивается значение i, то есть 2. На третьей итерации переменная i получает значение 3. Проверка при- водит к пропуску тела блока if, и программа завершает свое выполнение, выводя на экран значение 3,14, расположенное в списке data на индексной позиции 2. Циклы while также можно использовать со списками. Например, в сле- дующем фрагменте кода цикл while используется для определения ин- декса первого элемента списка с положительным значением. В цикле ис- пользуется внешняя переменная i, содержащая индекс текущего элемента в списке, начиная с нуля. Значение переменной i увеличивается по ходу выполнения программы, пока не будет достигнут конец списка или най- ден элемент с положительным значением. # Инициализируем переменные data = [0, –1, 4, 1, 0] # Цикл, пока i является допустимым индексом списка и значение по этому индексу # не положительное i = 0 while i < len(data) and data[i] <= 0: i = i + 1 # Если i меньше длины списка, значит, положительное значение было найдено # В противном случае i будет равна длине списка, а это означает, что # положительных чисел в списке нет if i < len(data): print("Первое положительное число в списке располагается по индексу", i) else: print("Список не содержит положительных чисел") Данная программа также начинается с инициализации переменных data и i. После этого сразу запускается цикл while. Переменная i, равная нулю, меньше длины списка, и значение элемента, располагающееся по Списки 93 этому индексу, меньше или равно нулю, в результате чего в первый раз выполняется тело цикла, в котором i увеличивается на единицу. Управление возвращается к началу цикла while, и условие проверяется снова. Результатом по-прежнему будет True, и тело цикла выполнится вновь, а переменная i сменит значение с единицы на двойку. На третьем проходе по циклу условное выражение вернет False, по- скольку значение в третьей позиции больше нуля. Тело цикла пропуска- ется, и выполнение программы продолжается с условной инструкции if, следующей за ним. Поскольку текущее значение i меньше, чем длина списка, на экран будет выведена информация о найденном положитель- ном элементе с его индексом. 5.3. д ополнительные операции со списками Списки могут расширяться и сокращаться в процессе выполнения про- граммы. При этом новый элемент может быть вставлен в любое место списка, и также любой элемент из списка может быть удален по значению или по индексу. Кроме того, в Python представлены удобные механизмы для определения того, находится ли элемент в списке, поиска индекса первого вхождения элемента в список, перестановки членов списка и дру- гих важных задач. Добавление и удаление элементов из списка выполняется путем вызова соответствующих методов у объекта, представляющего список. Подобно функциям, методы ассоциируются с блоками кода, которые могут быть вызваны применительно к конкретному объекту. При этом синтаксис вы- зова метода несколько отличается от функций. Метод списка может быть вызван по имени, которое должно следовать за именем списка и точкой. Он также может быть вызван применительно к безымянному списку элементов, заключенных в квадратные скобки, но такой подход применяется довольно редко. Как и функция, метод со- провождается круглыми скобками после имени, в которых указываются передаваемые аргументы через запятую. Некоторые методы возвращают результат, который может быть присвоен переменной, передан в качестве аргумента в другую функцию или метод либо использоваться как часть вычисления – подобно результату, возвращаемому функцией. 5.3.1. Добавление элементов в список Элементы могут добавляться в конец списка при помощи метода append. Метод принимает один аргумент, являющийся элементом, который будет добавлен в список. Рассмотрим следующий фрагмент кода. 94 Упражнения data = [2.71, 3.14, 1.41, 1.62] data.append(2.30) print(data) В первой строке кода создается список с именем data, состоящий из четырех элементов. Далее следует вызов метода append применительно к списку data, в результате чего к концу списка добавляется элемент со значением 2,30, тем самым расширяя длину списка с четырех до пяти. На- конец, в последней строке осуществляется вывод на экран обновленного списка, состоящего из элементов 2,71, 3,14, 1,41, 1,62 и 2,30. Если необходимо вставить новый элемент в произвольное место в спис- ке, можно воспользоваться методом insert. Данный метод требует пере- дачи двух параметров, представляющих индекс, по которому необходимо вставить значение, и сам вставляемый элемент. После вставки элемента в список все его члены, расположенные справа от добавленного значения, обретут новый индекс, на единицу больший предыдущего. Например, в следующем фрагменте кода происходит вставка элемента 2,30 в середи- ну списка data, а не в конец. После выполнения этого кода на экран будет выведено новое содержимое списка в виде: [2.71, 3.14, 2.30, 1.41, 1.62]. data = [2.71, 3.14, 1.41, 1.62] data.insert(2, 2.30) print(data) 5.3.2. Удаление элементов из списка Метод pop может быть использован для удаления из списка элемента, на- ходящегося в определенной позиции. Индекс удаляемого элемента пере- дается в метод в качестве необязательного параметра. Если этот параметр пропустить, будет удален последний элемент из списка. Метод pop возвра- щает элемент, который был извлечен из списка. Если его значение может понадобиться для проведения последующих расчетов, можно сохранить его в переменную, поставив метод pop справа от знака присваивания. Вызов метода pop применительно к пустому списку вернет ошибку по причине попытки извлечь из списка элемент с индексом, находящимся за его пределами. Удалить элемент из списка можно также при помощи вызова метода re- move. Единственным параметром этого метода является значение удаля- емого элемента (в отличие от метода pop, который оперирует индексами). При запуске метод remove удаляет из списка первое вхождение элемента с указанным значением. Если элемент с таким значением в списке найден не будет, метод вернет ошибку. Рассмотрим еще один пример. В нем мы создадим список из четырех элементов, после чего удалим два из них. Первый вызов функции print Списки 95 выведет на экран список из оставшихся двух элементов 2,71 и 3,14, по- скольку элементы 1,62 и 1,41 были удалены из списка. Далее на экран будет выведено значение 1,41, соответствующее элементу, извлеченному из списка посредством вызова метода pop. data = [2.71, 3.14, 1.41, 1.62] data.remove(1.62) # Удаляем значение 1.62 из списка last = data.pop() # Извлекаем последний элемент из списка print(data) print(last) 5.3.3. Изменение порядка следования элементов в списке Бывает, что в списке содержатся нужные элементы, но расположены они не так, как требуется для решения той или иной задачи. Два элемента в списке можно поменять местами при помощи временной переменной и нескольких инструкций, как показано на примере ниже. # Создаем список data = [2.71, 3.14, 1.41, 1.62] # Меняем местами элементы в списке с индексами 1 и 3 temp = data[1] data[1] = data[3] data[3] = temp # Отображаем модифицированный список print(data) Изначально переменная списка data инициализируется значениями [2.71, 3.14, 1.41, 1.62]. После этого элемент списка с индексом 1, пред- ставляющий значение 3,14, присваивается временной переменной temp. Затем значение элемента с индексом 3 отправляется на место элемента с индексом 1, после чего операцию завершает присваивание значения из временной переменной элементу с индексом 3. На выходе мы получаем список с теми же элементами, но в измененном порядке: [2.71, 1.62, 1.41, 3.14]. Есть еще два способа изменить порядок следования элементов в списке, а именно воспользоваться специальными методами reverse и sort. Пер- вый из них, как ясно из названия, меняет на противоположный порядок, в котором расположены элементы в списке, а второй сортирует элемен- ты в порядке возрастания. Оба упомянутых метода могут быть вызваны 96 Упражнения применительно к спискам вовсе без аргументов. Вообще, список может быть отсортирован только в том случае, если его элементы могут сравни- ваться при помощи оператора <. Этот оператор в Python реализован для сравнения элементов самых разных типов, включая целые числа, числа с плавающей запятой, строки, списки и многие другие. В следующем примере мы попросим пользователя ввести перечень зна- чений и сохраним их в список. После этого отсортируем список и выведем его на экран. # Создаем пустой список values = [] # Запрашиваем числа у пользователя и собираем список, пока он не оставит строку пустой line = input("Введите число (Enter для завершения): ") while line != "": num = float(line) values.append(num) line = input("Введите число (Enter для завершения: ") # Сортируем список по возрастанию values.sort() # Отображаем значения for v in values: print(v) 5.3.4. Поиск в списке Иногда бывает необходимо выяснить, содержится ли тот или иной эле- мент в заданном списке. В других ситуациях нам требуется получить ин- декс конкретного элемента в списке, который точно в нем присутствует. Оператор in и функция index в Python помогут нам справиться с этими задачами. Оператор in используется для определения факта вхождения элемента в список. Искомое значение при этом помещается слева от оператора, а список, в котором будет осуществляться поиск, – справа. Такое буле- во выражение возвращает True, если элемент входит в заданный список, и False в обратном случае. Метод index применяется для идентификации позиции искомого эле- мента в списке, значение которого передается в метод в качестве един- ственного аргумента. На выходе будет получен индекс первого вхождения элемента в список. Если искомого значения в списке не окажется, метод вернет ошибку. Так что программисты зачастую сначала определяют при помощи оператора in, есть ли элемент в списке, а уже затем прибегают к помощи метода index для поиска индекса интересующего элемента. Списки 97 В следующем фрагменте кода мы продемонстрируем сразу несколько методов и операторов, о которых говорили в этой главе. Начинается про- грамма с запроса у пользователя целых чисел и добавления их в список. После этого пользователь должен ввести дополнительное целое число. Если в сформированном списке присутствует этот элемент, на экран будет выведен индекс его первого появления. В противном случае должно по- явиться сообщение о неудачном поиске. # Запрашиваем целые числа и собираем их в список, пока не будет введена пустая строка data = [] line = input("Введите целое число (Enter для окончания): ") while line != "": n = int(line) data.append(n) line = input("Введите целое число (Enter для окончания): ") # Запрашиваем у пользователя дополнительное число x = int(input("Введите дополнительное целое число: ")) # Отображаем индекс первого вхождения этого элемента в список (если он там есть) if x in data: print("Первое вхождение", x, "в списке – по индексу:", data.index(x)) else: print(x, "не находится в списке") 5.4. с писки как возвращаемые значения и аргументы Функции могут возвращать списки. Как и значения других типов, спис- ки из функций возвращаются при помощи ключевого слова return. По- сле этого выполнение функции завершается, а управление передает- ся следующей после вызова функции инструкции. Полученный таким образом список может быть сохранен в переменную или использован в расчетах. Списки также могут быть переданы в функции в качестве аргументов. Здесь тоже нет никаких отличий от значений других типов – имя списка передается в функцию в круглых скобках, как любой другой аргумент. Внутри списка переданный аргумент также сохраняется в переменной соответствующего параметра. Переменные параметров, представляющие собой списки, могут быть использованы в теле функции так же точно, как переменные любых дру- гих типов. Однако, в отличие от целых чисел, чисел с плавающей запятой, булевых выражений и строк, изменения, произведенные над элементами в списке внутри функции, могут повлиять на содержимое списка в вы- 98 Упражнения зывающем коде. В частности, изменения, сделанные в переданном спис- ке посредством методов вроде append, pop или sort, окажут влияние на содержимое переданного в функцию аргумента и полученного на входе параметра. То же самое можно сказать и об изменении отдельных элементов спис ка путем присвоения им новых значений с указанием в квадратных скобках конкретных индексов. При этом присвоение нового значения всему списку в целом, когда слева от знака равенства находится только имя списка, влияет лишь на переменную параметра внутри функции, тогда как переменная, представляющая входной аргумент, остается не- изменной. Различия в поведении списков в сравнении с переменными других типов применительно к их передаче функциям не случайны. Они обу- словлены серьезными техническими доводами, выходящими за рамки данной книги. 5.5. у пражнения Все упражнения из данной главы должны быть решены при помощи спис- ков. В программах, которые вы напишете, будут создаваться списки, мо- дифицироваться, а также по ним будет выполняться поиск. Будут и за- дания, в которых переменные, хранящие списки, должны передаваться в функции в качестве аргументов или возвращаться из них. Упражнение 110. Порядок сортировки (Решено. 22 строки) Напишите программу, которая будет запрашивать у пользователя цело- численные значения и сохранять их в виде списка. Индикатором оконча- ния ввода значений должен служить ноль. Затем программа должна вы- вести на экран все введенные пользователем числа (кроме нуля) в порядке возрастания – по одному значению в строке. Используйте для сортировки либо метод sort, либо функцию sorted. Упражнение 111. Обратный порядок (20 строк) Напишите программу, которая, как и в предыдущем случае, будет за- прашивать у пользователя целые числа и сохранять их в виде списка. Индикатором окончания ввода значений также должен служить ноль. На этот раз необходимо вывести на экран введенные значения в порядке убывания. Списки 99 Упражнение 112. Удаляем выбросы (Решено. 44 строки) При анализе собранных по результатам научных экспериментов данных зачастую возникает необходимость избавиться от экстремальных зна- чений, прежде чем продолжать двигаться дальше. Напишите функцию, создающую копию списка с исключенными из него n наибольшими и наи- меньшими значениями и возвращающую ее в качестве результата. Поря- док следования элементов в измененном списке не обязательно должен в точности совпадать с источником. В основной программе должна быть продемонстрирована работа вашей функции. Для начала попросите пользователя ввести целые числа, затем соберите их в список и вызовите написанную вами ранее функцию. Вы- ведите на экран измененную версию списка вместе с оригинальной. Если пользователь введет менее четырех чисел, должно быть отображено соот- ветствующее сообщение об ошибке. Упражнение 113. Избавляемся от дубликатов (Решено. 21 строка) В данном упражнении вам предстоит разработать программу, в которой у пользователя будет запрошен список слов, пока он не оставит строку ввода пустой. После этого на экране должны быть показаны слова, введен- ные пользователем, но без повторов, – каждое по одному разу. При этом слова должны быть отображены в том же порядке, в каком их вводили с клавиатуры. Например, если пользователь на запрос программы введет следующий список слов: first second first third second программа должна вывести: first second third Упражнение 114. Отрицательные, положительные и нули (Решено. 36 строк) Напишите программу, запрашивающую у пользователя целые числа, пока он не оставит строку ввода пустой. После окончания ввода на экран долж- ны быть выведены сначала все отрицательные числа, которые были вве- 100 Упражнения дены, затем нулевые и только после этого положительные. Внутри каждой группы числа должны отображаться в той последовательности, в которой были введены пользователем. Например, если он ввел следующие числа: 3, -4, 1, 0, -1, 0 и -2, вывод должен оказаться таким: -4, -1, -2, 0, 0, 3 и 1. Каждое значение должно отображаться на новой строке. Упражнение 115. Список собственных делителей (36 строк) Собственным делителем числа называется всякий его делитель, отличный от самого числа. Напишите функцию, которая будет возвращать список всех собственных делителей заданного числа. Само это число должно передаваться в функцию в виде единственного аргумента. Результатом функции будет перечень собственных делителей числа, собранных в спи- сок. Основная программа должна демонстрировать работу функции, за- прашивая у пользователя число и выводя на экран список его собственных делителей. Программа должна запускаться только в том случае, если она не импортирована в виде модуля в другой файл. Упражнение 116. Совершенные числа (Решено. 35 строк) Целое число n называется совершенным, если сумма всех его собственных делителей равна самому числу n. Например, 28 – это совершенное число, поскольку его собственными делителями являются 1, 2, 4, 7 и 14, а 1 + 2 + 4 + 7 + 14 = 28. Напишите функцию для определения того, является ли заданное число совершенным. Функция будет принимать на вход единственный пара- метр и возвращать True, если он представляет собой совершенное число, и False – если нет. Разработайте небольшую программу, которая будет использовать функцию для идентификации и вывода на экран всех со- вершенных чисел в диапазоне от 1 до 10 000. При решении этой задачи импортируйте функцию, написанную в упражнении 115. Упражнение 117. Только слова (38 строк) В данном упражнении вы напишете программу, которая будет выделять слова из строки, введенной пользователем. Начните с создания функции, принимающей на вход единственный строковый параметр. В качестве результата она должна возвращать список слов из строки с удаленны- ми знаками препинания, в число которых должны входить точки, за- пятые, восклицательный и вопросительный знаки, дефисы, апострофы, двоеточия и точки с запятыми. При этом не нужно избавляться от знаков Списки 101 препинания, стоящих внутри слова, таких как апостроф, служащий в анг- лийском языке для обозначения сокращений. Например, если на вход функции дать строку "Contractions include: don’t, isn’t, and wouldn’t.", функция должна вернуть следующий список: ["Contractions", "include", "don’t", "isn’t", "and", "wouldn’t"] В основной программе, как обычно, должна происходить демонстрация вашей функции. Запросите у пользователя строку и выведите на экран все составляющие ее слова с удаленными знаками препинания. Вам по- надобятся написанные при решении заданий 118 и 167 функции, так что убедитесь, что основная программа выполняется только в случае, если файл не импортирован в качестве модуля. Упражнение 118. Словесные палиндромы (34 строки) В упражнениях 75 и 76 мы уже имели дело со словами, являющимися па- линдромами. Тогда мы анализировали буквы в слове с начала и конца, иг- норируя пробелы и знаки препинания, чтобы понять, совпадает ли его написание в прямом и обратном направлениях. И хотя палиндромами обычно называют слова, это понятие вполне можно расширить. Например, английская фраза «Is it crazy how saying sentences backwards creates back- wards sentences saying how crazy it is?» является словесным палиндромом, поскольку если читать ее по словам, игнорируя при этом знаки препинания и заглавные буквы, в обоих направлениях она будет звучать одинаково. Еще примеры английских словесных палиндромов: «Herb the sage eats sage, the herb» и «Information school graduate seeks graduate school information». Напишите программу, которая будет запрашивать строку у пользова- теля и оповещать его о том, является ли она словесным палиндромом. Не забывайте игнорировать знаки препинания при выявлении результата. Упражнение 119. Ниже и выше среднего (44 строки) Напишите программу, которая будет запрашивать у пользователя чис- ла, пока он не пропустит ввод. Сначала на экран должно быть выведено среднее значение введенного ряда чисел, после этого друг за другом не- обходимо вывести список чисел ниже среднего, равных ему (если такие найдутся) и выше среднего. Каждый список должен предваряться соот- ветствующим заголовком. Упражнение 120. Форматирование списка (Решено. 41 строка) Обычно при написании перечислений и списков мы разделяем их эле- менты запятыми, а перед последним ставим союз «и», как показано ниже: 102 Упражнения яблоки яблоки и апельсины яблоки, апельсины и бананы яблоки, апельсины, бананы и лимоны Напишите функцию, которая будет принимать на вход список из строк и возвращать собранную строку из его элементов в описанной выше ма- нере. Хотя в представленном примере количество элементов списка огра- ничивается четырьмя, ваша функция должна уметь обрабатывать списки любой длины. В основной программе запросите у пользователя несколько элементов списка, отформатируйте их должным образом при помощи функции и выведите на экран. Упражнение 121. Случайные лотерейные номера (Решено. 28 строк) Для выигрыша главного приза необходимо, чтобы шесть номеров на ло- терейном билете совпали с шестью числами, выпавшими случайным об- разом в диапазоне от 1 до 49 во время очередного тиража. Напишите про- грамму, которая будет случайным образом подбирать шесть номеров для вашего билета. Убедитесь в том, что среди этих чисел не будет дубликатов. Выведите номера билетов на экран по возрастанию. Упражнение 122. «Поросячья латынь» (32 строки) «Поросячьей латынью» называют молодежный жаргонный язык, произ- водный от английского. И хотя корни этого новообразованного языка неизвестны, упоминание о нем есть как минимум в двух документах, датированных XIX веком, а это значит, что ему уже больше сотни лет. Для перевода слова с английского на «поросячью латынь» нужно сделать следующее: если слово начинается с согласной буквы (включая y), то все буквы с начала слова и до первой гласной (за исключением y) переносятся в конец слова и дополняются сочетанием букв ay. Например, слово computer будет преобразовано в omputercay, а слово think – в inkthay; если слово начинается с гласной буквы (не включая y), к концу сло- ва просто добавляется way. К примеру, слово algorithm превратится в algorithmway, а office – в officeway. Напишите программу, которая будет запрашивать у пользователя стро- ку. После этого она должна переводить введенный текст на «поросячью латынь» и выводить его на экран. Вы можете сделать допуск о том, что все слова пользователь будет вводить в нижнем регистре и разделять их пробелами. Списки 103 Упражнение 123. «Поросячья латынь» (продолжение) (51 строка) Расширьте свое решение упражнения 122, чтобы ваш анализатор коррект- но обрабатывал символы в верхнем регистре и знаки препинания, такие как запятая, точка, а также восклицательный и вопросительный знаки. Если в оригинале слово начинается с заглавной буквы, то в переводе на «поросячью латынь» оно также должно начинаться с заглавной буквы, тогда как буквы, перенесенные в конец слов, должны стать строчными. Например, слово Computer должно быть преобразовано в Omputercay. Если в конце слова стоит знак препинания, он там же и должен остаться после выполнения перевода. То есть слово в конце предложения Science! необ- ходимо трансформировать в Iencescay!. Упражнение 124. Линия наилучшего соответствия (41 строка) Линией наилучшего соответствия называется прямая, проходящая на наименьшем удалении от набора из n точек. В данном упражнении мы предположим, что каждая точка в коллекции обладает координатами x и y. Символы и мы будем использовать для подсчета средних зна- чений по осям x и y соответственно. Линия наилучшего соответствия представлена формулой y = mx + b, где m и b вычисляются по следующим формулам: Напишите программу, которая будет запрашивать у пользователя ко- ординаты коллекции точек. При этом пользователь должен вводить сна- чала координату x, а затем y. Ввод координат может продолжаться до тех пор, пока пользователь не оставит пустым ввод координаты x. Отобра- зите формулу, характеризующую линию наилучшего соответствия, вида y = mx + b путем замены переменных m и b на значения, вычисленные по предыдущим формулам. Например, если пользователь введет три точки (1, 1), (2, 2.1) и (3, 2.9), итоговая формула должна приобрести вид y = 0,95x + 0,1. 104 Упражнения Упражнение 125. Тасуем колоду карт (Решено. 49 строк) Стандартная игральная колода состоит из 52 карт. Каждая карта соответ- ствует одной из четырех мастей (пики, червы, бубны и трефы) и одному из 13 номиналов (от 2 до 10, валет (J), дама (Q), король (K) и туз (A)). Таким образом, каждая игральная карта может быть представлена при помощи двух символов. Первый из них указывает на номинал карты (от 2 до 9, T (десятка), J, Q, K или A), а второй – на масть (s = пики (spades), h = червы (hearts), d = бубны (diamonds) и c = трефы (clubs)). В табл. 5.1 представлены некоторые из возможных обозначений игральных карт. Таблица 5.1. Игральные карты Карта Обозначение Валет пик Js Двойка треф 2c Десятка бубен Td Туз червей Ah Девятка пик 9s Начните с написания функции createDeck. В ней должны использоваться циклы для создания полной колоды карт путем сохранения в список двух- символьных аббревиатур всех 52 карт. Именно этот список и будет воз- вращаемым из данной функции значением. На вход функция createDeck принимать параметры не будет. Напишите вторую функцию с именем shuffle, которая будет случай- ным образом перетасовывать карты в списке. Одна из техник тасования колоды заключается в проходе по элементам и перестановке их с любым другим случайным элементом в этом списке. Вы должны создать свой собственный цикл для тасования карт в колоде, а не пользоваться стан- дартной функцией shuffle языка Python. Используйте обе созданные функции в основной программе, в которой должна отображаться колода карт до и после тасования. Убедитесь, что основная программа выполняется только в случае, если файл не импор- тирован в качестве модуля. Примечание. Хороший алгоритм тасования игральной колоды должен быть беспри- страстным, что означает равную вероятность расположения каждой из карт в колоде после тасования. Однако алгоритм, предложенный в этом упражнении и предполага- ющий обмен позициями между каждой из карт в колоде с любой другой случайной Списки 105 картой, не является таковым. В частности, карты, которые появляются позже в исход- ном списке, с большой вероятностью окажутся ближе к концу и в перетасованном списке. Как это ни странно, беспристрастной будет версия алгоритма, в которой при последовательном проходе по элементам каждый из них будет меняться позициями не со случайным элементом из всего списка, а со случайным элементом в диапазоне от позиции текущей карты и до конца колоды. Упражнение 126. Раздача карманных карт (44 строки) Во многих карточных играх после процедуры тасования колоды каждый игрок получает на руки определенное количество карт. Напишите функ- цию deal, принимающую на вход три параметра: количество игроков, количество раздаваемых каждому из них карт и саму колоду. Функция должна возвращать список рук, которые были розданы игрокам. При этом каждая рука, в свою очередь, тоже является списком из входящих в нее карт. Во время раздачи карт игрокам функция параллельно должна удалять розданные карты из переданной ей третьим параметром колоды. Также принято раздавать карты каждому игроку по одной строго по очереди. Придерживайтесь этих принципов и при написании своей функции. Воспользуйтесь своими наработками из упражнения 125 при построе- нии структуры основной программы. Вам необходимо создать колоду карт, перетасовать ее и раздать четырем игрокам по пять карт. Выведите на экран карманные карты всех игроков, находящихся в раздаче, а также оставшиеся в колоде карты. Упражнение 127. Список уже отсортирован? (41 строка) Напишите функцию, показывающую, отсортирован ли переданный ей в качестве параметра список (по возрастанию или убыванию). Функция должна возвращать True, если список отсортирован, и False в противном случае. В основной программе запросите у пользователя последователь- ность чисел для списка, после чего выведите сообщение о том, является ли этот список отсортированным изначально. Примечание. Убедитесь в том, что вы правильно обрабатываете пустые списки, а так- же списки, состоящие из единственного элемента. 106 Упражнения Упражнение 128. Подсчитать элементы в списке (Решено. 48 строк) В стандартной библиотеке языка Python присутствует функция count, по- зволяющая подсчитать, сколько раз определенное значение встречается в списке. В данном упражнении вы создадите новую функцию countRange, которая будет подсчитывать количество элементов в списке, значения которых больше или равны заданному минимальному порогу и мень- ше максимального. Функция должна принимать три параметра: список, минимальную границу и максимальную границу. Возвращать она будет целочисленное значение, большее или равное нулю. В основной програм- ме реализуйте демонстрацию вашей функции для нескольких списков с разными минимальными и максимальными границами. Удостоверьтесь, что программа будет корректно работать со списками, содержащими как целочисленные значения, так и числа с плавающей запятой. Упражнение 129. Разбиение строки на лексемы (Решено. 47 строк) Разбиение строки на лексемы (Tokenizing) представляет собой процесс пре- образования исходной строки в список из подстрок, называемых лексе- мами (token). Зачастую со списком лексем работать бывает проще, чем со всей исходной строкой, поскольку в ней могут присутствовать неравно- мерные разрывы. Кроме того, иногда бывает непросто на лету определить, где заканчивается одна лексема и начинается другая. В математических выражениях лексемами являются, например, опера- торы, числа и скобки. Здесь и далее мы будем причислять к списку опе- раторов следующие: *, /, ˆ, - и +. Операторы и скобки легко идентифици- ровать, поскольку эти лексемы всегда состоят ровно из одного символа и никогда не являются составной частью других лексем. Числа выделить бывает сложнее, поскольку эти лексемы могут состоять из нескольких символов. Любая непрерывная последовательность цифр должна воспри- ниматься как одна числовая лексема. Напишите функцию, принимающую в качестве единственного вход- ного параметра строку, содержащую математическое выражение, и пре- образующую ее в список лексем. Каждая лексема должна быть либо опе- ратором, либо числом, либо скобкой. Для простоты реализации в данном упражнении мы будем оперировать только целочисленными значениями. Функция должна возвращать созданный список лексем. При решении поставленной задачи вы можете принять допущение о том, что входная строка всегда будет содержать математическое выраже- ние, состоящее из скобок, чисел и операторов. При этом в вашей функции должно быть предусмотрено, что лексемы могут отделяться друг от друга разным количеством пробелов, а могут и не отделяться вовсе. В основной Списки 107 программе продемонстрируйте работу функции, запросив у пользователя исходную строку и выведя на экран список составляющих ее лексем. Убе- дитесь, что основная программа выполняется только в случае, если файл не импортирован в качестве модуля. Упражнение 130. Унарные и бинарные операторы (Решено. 45 строк) Математические операторы бывают унарными (unary) и бинарными (bina- ry). Унарные операторы взаимодействуют с одним значением, тогда как бинарные – с двумя. Например, в выражении 2 * –3 оператор * является бинарным, поскольку взаимодействует с двумя числами: 2 и -3. При этом сам оператор – здесь унарный, ведь он применяется только к одному чис- лу 3. Одного лишь символа оператора недостаточно, чтобы определить, является ли он унарным или бинарным. Например, хотя в предыдущем случае оператор – был унарным, в выражении 2 – 3 он приобретет роль бинарного. Подобная неоднозначность, также характерная для оператора сложения, должна быть устранена до применения других операций к эле- ментам списка лексем математического выражения. Напишите функцию для поиска унарных операторов + и – в списке лек- сем и их замены на сочетание символов u+ и u– соответственно. Функция должна принимать в качестве единственного параметра список лексем математического выражения и возвращать его копию с произведенной заменой унарных операторов. Оператор + или – можно идентифицировать как унарный в одном из двух случаев: если он идет первым в списке или если ему предшествует другой оператор либо открывающая скобка. Во всех остальных случаях оператор может считаться бинарным. В основной программе продемонстрируйте работу функции. Запросите у пользователя строку с математическим выражением, разбейте ее на лексемы, выделите в отдельный список унарные операторы и выведите их на экран. Упражнение 131. Инфиксная запись – в постфиксную (63 строки) Математические выражения часто записываются в инфиксной форме (infix form), когда оператор ставится между операндами, с которыми взаимо- действует. И хотя такая форма записи наиболее распространена, сущест- вует и другая, именуемая постфиксной (postfix form), в которой оператор ставится после операндов. Например, инфиксной форме записи выра- жения 3 + 4 будет соответствовать постфиксный вариант 3 4 +. Чтобы преобразовать инфиксную форму записи в постфиксную, необходимо вы- полнить следующий алгоритм действий. 108 Упражнения Создаем новый пустой список operators Создаем новый пустой список postfix Для каждой лексемы в инфиксном выражении Если лексема представляет собой целое число, то Добавляем лексему к списку postfix Если лексема представляет собой оператор, то Пока список operators не пустой и последний элемент в operators не открывающая скобка и precedence(лексема) < precedence(последний элемент в operators), делаем Удаляем последний элемент из списка operators и добавляем его к postfix Добавляем лексему к списку operators Если лексема представляет собой открывающую скобку, то Добавляем лексему к списку operators Если лексема представляет собой закрывающую скобку, то Пока последний элемент в operators не является открывающей скобкой, делаем Удаляем последний элемент из списка operators и добавляем его к postfix Удаляем открывающую скобку из operators Пока список operators не пустой, делаем Удаляем последний элемент из списка operators и добавляем его к postfix Возвращаем postfix в качестве результата алгоритма Используйте свои наработки из упражнений 129 и 130 для разделения математических выражений на лексемы и поиска в них унарных опера- торов. После этого используйте алгоритм, приведенный выше, для преоб- разования выражения из инфиксной формы в постфиксную. Код, реали- зующий этот алгоритм, должен быть заключен в функцию, принимающую на вход список лексем инфиксного выражения (с помеченными унарными операторами). Возвращать функция будет список лексем в постфиксном выражении. В основной программе продемонстрируйте работу функции по преобразованию инфиксной формы записи математического выра- жения в постфиксную. Запросите у пользователя выражение инфиксного типа и выведите на экран его постфиксный аналог. Цель перевода математического выражения из одного вида в другой будет понятна вам, когда вы прочитаете текст упражнения 132. Кроме того, вам могут понадобиться наработки из заданий 96 и 97 при решении этого упражнения. И если первое решение вы можете использовать как есть, то решение задания 97 необходимо будет немного расширить, чтобы возвращался правильный приоритет для унарных операторов. Унарные операторы должны обладать более высоким приоритетом по сравнению с операциями умножения и деления, но более низким, если сравнивать с операцией возведения в степень. Списки 109 Упражнение 132. Выполнение постфиксных выражений (63 строки) Математические выражения, записанные в постфиксной форме, выпол- нять легче, чем те же выражения в инфиксной, поскольку в них нет скобок и не нужно учитывать старшинство операторов. Выражения в постфикс- ной форме могут быть выполнены при помощи реализации следующего алгоритма. Создаем новый пустой список values Для каждой лексемы в постфиксном выражении Если лексема представляет собой целое число, то Преобразуем лексему в целочисленный тип и добавляем к списку values Если лексема представляет собой унарный оператор –, то Удаляем последний элемент из списка values Применяем операцию логического НЕ к элементу и добавляем результат к списку values Если лексема представляет собой бинарный оператор, то Удаляем последний элемент из списка values и называем его right Удаляем последний элемент из списка values и называем его left Вычисляем результат применения оператора к операндам left и right Добавляем результат к списку values Возвращаем первый элемент списка values в качестве значения выражения Напишите программу, запрашивающую у пользователя математиче- ское выражение в инфиксном виде, преобразующую его в постфиксную форму, выполняющую полученное выражение и выводящую на экран ре- зультат. Используйте при решении задачи свои наработки из упражнений 129, 130 и 131, а также алгоритм, приведенный выше. Примечание. В алгоритмах, предложенных для решения упражнений 131 и 132, не предусмотрена обработка возможных ошибок. В результате ваши программы могут выдавать ошибки или выполняться неправильно, если пользователь введет что-то неожиданное. Эти алгоритмы могут быть расширены и дополнены по желанию во избежание возникновения ошибок. Сами ошибки можно корректно обрабатывать и выводить соответствующие сообщения на экран. Если вам интересно попробовать это сделать, никто вас останавливать не будет. Упражнение 133. Содержит ли список подмножество элементов? (44 строки) Подмножеством элементов, или подсписком (sublist), мы будем называть список, являющийся составной частью большего списка. Подсписок мо- жет содержать один элемент, множество элементов, а также быть пустым. 110 Упражнения Например, [1], [2], [3] и [4] являются подсписками списка [1, 2, 3, 4]. Список [2, 3] также входит в состав [1, 2, 3, 4], но при этом список [2, 4] не является подсписком [1, 2, 3, 4], поскольку в исходном списке числа 2 и 4 не соседствуют друг с другом. Пустой список может быть рассмотрен как подсписок для любого списка. Таким образом, список [] является под- списком [1, 2, 3, 4]. Также список является подсписком самого себя, то есть [1, 2, 3, 4] – это подсписок для [1, 2, 3, 4]. В рамках данного упражнения вам необходимо написать функцию is- Sublist , определяющую, является ли один список подсписком другого. На вход функции должны поступать два списка – larger и smaller. Функция должна возвращать значение True только в том случае, если список smaller является подсписком списка larger. Напишите также основную програм- му для демонстрации работы функции. Упражнение 134. Все подсписки заданного списка (Решено. 41 строка) Используя определение подсписка из упражнения 133, напишите функ- цию, возвращающую список, содержащий все возможные подсписки за- данного. Например, в число подсписков списка [1, 2, 3] входят следую- щие: [], [1], [2], [3], [1, 2], [2, 3] и [1, 2, 3]. Заметьте, что ваша функция должна вернуть как минимум один пустой список, гарантированно явля- ющийся подсписком для любого списка. Напишите основную программу, демонстрирующую работу функции применительно к нескольким исход- ным спискам. Упражнение 135. Решето Эратосфена (Решено. 33 строки) Решето Эратосфена – алгоритм, изобретенный более 2000 лет назад и слу- жащий для нахождения всех простых чисел от 2 до некоторого целого числа n. Описание этого алгоритма приведено ниже. Выписываем все целые числа от 0 до заданной границы Вычеркиваем 0 и 1 как непростые числа Устанавливаем значение переменной p, равное 2 Пока p меньше указанного числа, делать Вычеркиваем все числа, кратные p, но не его само Устанавливаем значение p, равное следующему невычеркнутому числу Выводим все числа, оставшиеся незачеркнутыми Ценность данного алгоритма заключается в том, что на бумаге очень легко вычеркнуть все числа, кратные определенному. Для компьютера это также не самая сложная задача – с этим может прекрасно справиться Списки 111 инструкция for с третьим параметром, переданным функции range. Мы знаем, что вычеркнутые числа на листочке не являются простыми, но физически они никуда с листа не деваются и должны участвовать в даль- нейшем алгоритме. Так что и в компьютерной симуляции не стоит «вы- черкивать» элемент путем его удаления из списка – вместо этого лучше будет присвоить ему значение 0. После завершения алгоритма все нену- левые числа в списке и будут простыми. Напишите программу на Python, реализующую указанный выше алго- ритм для отображения простых чисел в интервале от двух до значения, введенного пользователем. Если алгоритм будет реализован правильно, ваша программа справится с выводом всех простых чисел от двух до мил- лиона всего за пару секунд. Примечание. Приведенный в данном упражнении алгоритм поиска простых чисел, названный в честь Эратосфена, был далеко не единственным вкладом греческого математика в науку. Ему также приписывают вычисление длины окружности Земли и градус наклона ее оси. Кроме того, с 235 г. до н. э. он служил хранителем знамени- той Александрийской библиотеки. |