Лабораторная работа №11. Функции и рекурсия

1 2 3 4 5 6 7

Методические указания по выполнению лабораторных работ на алгоритмическом языке Python

Рубежный контроль 2

Лабораторная работа №10. Списки. 1

Лабораторная работа №11. Функции и рекурсия. 8

Лабораторная работа №12. Двумерные массивы.. 14

Лабораторная работа №13. Циклы и массивы.. 20

Лабораторная работа №14. Множества. 28

Лабораторная работа №15. Работа со строками, файлами. 32

Лабораторная работа №16. Python, PythonXY. Работа с графикой. 36

Лабораторная работа №10. Списки

Цель: Приобретение практических навыков по работе со Списками:

– Списки

– Методы split и join

– Генераторы списков

– Срезы

– Операции со списками

Задание. Напишите программу, согласно варианту.

Содержание отчета:

– Постановка задание

– Описание входных/выходных данных

– Алгоритм работы программы

– Код программы с комментариями

– Файл с кодом программы на языке Python

Варианты заданий

Во всех задачах считывайте входные данные через input() и выводите ответ через print().

№	Задание
1.	Известно, что на доске 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Вам дана расстановка 8 ферзей на доске, определите, есть ли среди них пара бьющих друг друга. Программа получает на вход восемь пар чисел, каждое число от 1 до 8 – координаты 8 ферзей. Если ферзи не бьют друг друга, выведите слово NO, иначе выведите YES.
2.	N кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до N. Затем по этому ряду бросили K шаров, при этом i -й шар сбил все кегли с номерами от l_i до r_i включительно. Определите, какие кегли остались стоять на месте. Программа получает на вход количество кеглей N и количество бросков K. Далее идет K пар чисел l_i, r_i, при этом 1≤ l_i≤ r_i≤ N. Программа должна вывести последовательность из N символов, где j -й символ есть “I”, если j -я кегля осталась стоять, или “.”, если j -я кегля была сбита.
3.	Дан список. Выведите те его элементы, которые встречаются в списке только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в списке.
4.	Дан список чисел. Посчитайте, сколько в нем пар элементов, равных друг другу. Считается, что любые два элемента, равные друг другу образуют одну пару, которую необходимо посчитать.
5.	Дан список целых чисел, число k и значение C. Необходимо вставить в список на позицию с индексом k элемент, равный C, сдвинув все элементы, имевшие индекс не менее k, вправо. Поскольку при этом количество элементов в списке увеличивается, после считывания списка в его конец нужно будет добавить новый элемент, используя метод append. Вставку необходимо осуществлять уже в считанном списке, не делая этого при выводе и не создавая дополнительного списка.
6.	Дан список из чисел и индекс элемента в списке k. Удалите из списка элемент с индексом k, сдвинув влево все элементы, стоящие правее элемента с индексом k. Программа получает на вход список, затем число k. Программа сдвигает все элементы, а после этого удаляет последний элемент списка при помощи метода pop() без параметров. Программа должна осуществлять сдвиг непосредственно в списке, а не делать это при выводе элементов. Также нельзя использовать дополнительный список. Также не следует использовать метод pop(k) с параметром.
7.	В списке все элементы различны. Поменяйте местами минимальный и максимальный элемент этого списка.
8.	Переставьте соседние элементы списка (A[0] c A[1], A[2] c A[3] и т. д.). Если элементов нечетное число, то последний элемент остается на своем месте.
9.	Дан список, упорядоченный по неубыванию элементов в нем. Определите, сколько в нем различных элементов.
10.	Петя перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю. Помогите ему это сделать. Программа получает на вход невозрастающую последовательность натуральных чисел, означающих рост каждого человека в строю. После этого вводится число X – рост Пети. Все числа во входных данных натуральные и не превышают 200. Выведите номер, под которым Петя должен встать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то он должен встать после них.
11.	Дан список чисел. Выведите значение наибольшего элемента в списке, а затем индекс этого элемента в списке. Если наибольших элементов несколько, выведите индекс первого из них.
12.	Дан список чисел. Определите, сколько в этом списке элементов, которые больше двух своих соседей, и выведите количество таких элементов. Крайние элементы списка никогда не учитываются, поскольку у них недостаточно соседей.
13.	Дан список чисел. Если в нем есть два соседних элемента одного знака, выведите эти числа. Если соседних элементов одного знака нет — не выводите ничего. Если таких пар соседей несколько — выведите первую пару.
14.	Дан список чисел. Выведите все элементы списка, которые больше предыдущего элемента.
15.	Выведите все четные элементы списка. При этом используйте цикл for, перебирающий элементы списка, а не их индексы!
16.	Выведите все элементы списка с четными индексами (то есть A[0], A[2], A[4],...).

Методические указания

Списки

Большинство программ работает не с отдельными переменными, а с набором переменных. Например, программа может обрабатывать информацию об учащихся класса, считывая список учащихся с клавиатуры или из файла, при этом изменение количества учащихся в классе не должно требовать модификации исходного кода программы.

Раньше мы сталкивались с задачей обработки элементов последовательности, например, вычисляя наибольший элемент последовательности. Но при этом мы не сохраняли всю последовательность в памяти компьютера. Однако, во многих задачах нужно именно сохранять всю последовательность, например, если бы нам требовалось вывести все элементы последовательности в возрастающем порядке (“отсортировать последовательность”).

Для хранения таких данных можно использовать структуру данных, называемую в Питоне список (в большинстве же языков программирования используется другой термин “массив”). Список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, список можно задать так:

В списке Primes – 6 элементов, а именно: Primes[0] == 2, Primes[1] == 3, Primes[2] == 5, Primes[3] == 7, Primes[4] == 11, Primes[5] == 13. Список Rainbow состоит из 7 элементов, каждый из которых является строкой.

Также как и символы в строке, элементы списка можно индексировать отрицательными числами с конца, например, Primes[-1] == 13, Primes[-6] == 2.

Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len, например, len(Primes) == 6.

В отличие от строк, элементы списка можно изменять, присваивая им новые значения.

Рассмотрим несколько способов создания и считывания списков. Прежде всего, можно создать пустой список (не содержащий элементов, длины 0), а в конец списка можно добавлять элементы при помощи метода append. Например, пусть программа получает на вход количество элементов в списке n, а потом n элементов списка по одному в отдельной строке. Вот пример входных данных в таком формате:

В этом случае организовать считывание списка можно так:

В этом примере создается пустой список, далее считывается количество элементов в списке, затем по одному считываются элементы списка и добавляются в его конец. То же самое можно записать, сэкономив переменную n:

Для списков целиком определены следующие операции: конкатенация списков (сложение списков, т. е. приписывание к одному списку другого) и повторение списков (умножение списка на число). Например:

В результате список c будет равен [1, 2, 3, 4, 5], а список d будет равен [4, 5, 4, 5, 4, 5]. Это позволяет по-другому организовать процесс считывания списков: сначала считать размер списка и создать список из нужного числа элементов, затем организовать цикл по переменной i начиная с числа 0 и внутри цикла считывается i-й элемент списка:

Вывести элементы списка a можно одной инструкцией print(a), при этом будут выведены квадратные скобки вокруг элементов списка и запятые между элементами списка. Такой вывод неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному элементу в строке. Приведем два примера, также отличающиеся организацией цикла:

Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.

В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в цикле меняется не индекс элемента списка, а само значение переменной (например, в цикле for elem in ['red', 'green', 'blue'] переменная elem будет последовательно принимать значения 'red', 'green', 'blue'.

Обратите особое внимание на последний пример! Очень важная часть идеологии Питона — это цикл for, который предоставляет удобный способ перебрать все элементы некоторой последовательности. В этом отличие Питона от Паскаля, где вам обязательно надо перебирать именно индексы элементов, а не сами элементы.

Последовательностями в Питоне являются строки, списки, значения функции range() (это не списки), и ещё кое-какие другие объекты.

Приведем пример, демонстрирующий использование цикла for в ситуации, когда из строки надо выбрать все цифры и сложить их в массив как числа.

Методы split и join

Элементы списка могут вводиться по одному в строке, в этом случае строку целиком можно считать функцией input(). После этого можно использовать метод строки split(), возвращающий список строк, которые получатся, если исходную строку разрезать на части по пробелам. Пример:

Если при запуске этой программы ввести строку 1 2 3, то список a будет равен ['1', '2', '3']. Обратите внимание, что список будет состоять из строк, а не из чисел. Если хочется получить список именно из чисел, то можно затем элементы списка по одному преобразовать в числа:

Используя специальную магию Питона – генераторы – то же самое можно сделать в одну строку:

Объяснение того, как работает этот код, будет дано в следующем разделе. Если нужно считать список действительных чисел, то нужно заменить тип int на тип float.

У метода split() есть необязательный параметр, который определяет, какая строка будет использоваться в качестве разделителя между элементами списка. Например, вызов метода split('.') вернет список, полученный разрезанием исходной строки по символам '.':

В Питоне можно вывести список строк при помощи однострочной команды. Для этого используется метод строки join. У этого метода один параметр: список строк. В результате возвращается строка, полученная соединением элементов переданного списка в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Мы знаем, что вы не поняли предыдущее предложение с первого раза. Поэтому смотрите примеры:

Если же список состоит из чисел, то придется использовать еще тёмную магию генераторов. Вывести элементы списка чисел, разделяя их пробелами, можно так:

Впрочем, если вы не любитель тёмной магии, то вы можете достичь того же эффекта, используя цикл for.

Генераторы списков

Для создания списка, заполненного одинаковыми элементами, можно использовать оператор повторения списка, например:

Для создания списков, заполненных по более сложным формулам можно использовать генераторы: выражения, позволяющие заполнить список некоторой формулой. Общий вид генератора следующий:

где переменная — идентификатор некоторой переменной, последовательность — последовательность значений, который принимает данная переменная (это может быть список, строка или объект, полученный при помощи функции range), выражение — некоторое выражение, как правило, зависящее от использованной в генераторе переменной, которым будут заполнены элементы списка.

Вот несколько примеров использования генераторов.

Создать список, состоящий из n нулей можно и при помощи генератора:

Создать список, заполненный квадратами целых чисел можно так:

Если нужно заполнить список квадратами чисел от 1 до n, то можно изменить параметры функции range на range(1, n + 1):

Вот так можно получить список, заполненный случайными числами от 1 до 9 (используя функцию randrange из модуля random):

А в этом примере список будет состоять из строк, считанных со стандартного ввода: сначала нужно ввести число элементов списка (это значение будет использовано в качестве аргумента функции range), потом – заданное количество строк:

Срезы

Со списками, так же как и со строками, можно делать срезы. А именно:

A[i:j] срез из j-i элементов A[i], A[i+1],..., A[j-1].

A[i:j:-1] срез из i-j элементов A[i], A[i-1],..., A[j+1] (то есть меняется порядок элементов).

A[i:j:k] срез с шагом k: A[i], A[i+k], A[i+2*k],.... Если значение k<0, то элементы идут в противоположном порядке.

Каждое из чисел i или j может отсутствовать, что означает “начало строки” или “конец строки”

Списки, в отличии от строк, являются изменяемыми объектами: можно отдельному элементу списка присвоить новое значение. Но можно менять и целиком срезы. Например:

Получится список, у которого вместо двух элементов среза A[2:4] вставлен новый список уже из трех элементов. Теперь список стал равен [1, 2, 7, 8, 9, 5].

Получится список [40, 2, 30, 4, 20, 6, 10]. Здесь A[::-2] — это список из элементов A[-1], A[-3], A[-5], A[-7], которым присваиваются значения 10, 20, 30, 40 соответственно.

Если не непрерывному срезу (то есть срезу с шагом k, отличному от 1), присвоить новое значение, то количество элементов в старом и новом срезе обязательно должно совпадать, в противном случае произойдет ошибка ValueError.

Обратите внимание, A[i] — это элемент списка, а не срез!

Операции со списками

Со списками можно легко делать много разных операций.

x in A	Проверить, содержится ли элемент в списке. Возвращает True или False
x not in A	То же самое, что not(x in A)
min(A)	Наименьший элемент списка
max(A)	Наибольший элемент списка
A.index(x)	Индекс первого вхождения элемента x в список, при его отсутствии генерирует исключение ValueError
A.count(x)	Количество вхождений элемента x в список

Лабораторная работа №11. Функции и рекурсия

Цель: Приобретение практических навыков по работе с Функциями и рекурсиями:

– Функции

– Локальные и глобальные переменные

– Рекурсия

Задание. Напишите программу, согласно варианту.

Содержание отчета:

– Постановка задание

– Описание входных/выходных данных

– Алгоритм работы программы

– Код программы с комментариями

– Файл с кодом программы на языке Python

Варианты заданий

Во всех задачах считывайте входные данные через input() и выводите ответ через print().

№	Задание
1.	Даны четыре действительных числа: x1, y1, x2, y2. Напишите функцию distance(x1, y1, x2, y2), вычисляющая расстояние между точкой (x1,y1) и (x2,y2). Считайте четыре действительных числа и выведите результат работы этой функции. Если вы не знаете, как решить эту задачу, то вы, возможно, не изучали в школе теорему Пифагора. Попробуйте прочитать о ней на Википедии.
2.	Дано действительное положительное число a и целоe число n. Вычислите aⁿ. Решение оформите в виде функции power(a, n). Стандартной функцией возведения в степень пользоваться нельзя.
3.	Напишите функцию capitalize(), которая принимает слово из маленьких латинских букв и возвращает его же, меняя первую букву на большую. Например, print(capitalize('word')) должно печатать слово Word. На вход подаётся строка, состоящая из слов, разделённых одним пробелом. Слова состоят из маленьких латинских букв. Напечатайте исходную строку, сделав так, чтобы каждое слово начиналось с большой буквы. При этом используйте вашу функцию capitalize(). Напомним, что в Питоне есть функция ord(), которая по символу возвращает его код в таблице ASCII, и функция chr(), которая по коду символа возвращает сам символ. Например, ord('a') == 97, chr(97) == 'a'.
4.	Дано действительное положительное число a и целое неотрицательное число n. Вычислите aⁿ не используя циклы, возведение в степень через ** и функцию math.pow(), а используя рекуррентное соотношение aⁿ=a⋅a^n-1. Решение оформите в виде функции power(a, n).
5.	Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке. При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных. Рекурсия вам поможет.
6.	Напишите функцию fib(n), которая по данному целому неотрицательному n возвращает n -e число Фибоначчи. В этой задаче нельзя использовать циклы — используйте рекурсию.

Методические указания

Функции

Напомним, что в математике факториал числа n определяется как n! = 1 ⋅ 2 ⋅... ⋅ n. Например, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.

Однако, если мы ошибёмся один раз в начальном коде, то потом эта ошибка попадёт в код во все места, куда мы скопировали вычисление факториала. Да и вообще, код занимает больше места, чем мог бы. Чтобы избежать повторного написания одной и той же логики, в языках программирования существуют функции.

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение – факториал этого числа.

Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).

Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.

Встроенная функция max() в Питоне может принимать переменное число аргументов и возвращать максимум из них. Приведём пример того, как такая функция может быть написана.