Programming Taskbook


E-mail:

Пароль:

Регистрация пользователя   Восстановление пароля

 

ЮФУ

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет), 1998–2023

 

Решения | Python | Обработка последовательностей

PrevNext


Выполнение заданий на обработку последовательностей

Задания, связанные с обработкой числовых последовательностей, собраны, в основном, в группах Array и Matrix. В условиях этих заданий речь идет о массивах (одномерных и двумерных), поскольку во многих языках программирования именно массив является базовым (встроенным в язык) типом данных, предназначенным для хранения однотипных последовательностей элементов. В языке Python встроенная поддержка массивов отсутствует, однако имеются не менее мощные встроенные типы, связанные с наборами данных. Это, прежде всего, список (list), хотя во многих случаях бывает удобно использовать и другие встроенные типы: кортежи (tuple), словари (dict) и множества (set). При выполнении заданий из группы Array для хранения исходных и результирующих массивов следует, как правило, использовать списки, содержащие исходные данные. В заданиях из группы Matrix, посвященных обработке двумерных массивов, целесообразно использовать списки, элементами которых, в свою очередь, также являются списки, содержащие элементы соответствующей строки матрицы.

На данной странице приводится несколько примеров выполнения заданий из групп Array и Matrix.


Обработка одномерных списков: Array47, Array79

Array47°. Дан целочисленный массив размера N. Найти количество различных элементов в данном массиве.

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

a = []
for i in range(get_int()):
    a.append(get_int())

Можно поступить и по-другому: сразу создать список из требуемого количества элементов, после чего изменить их значения:

a = get_int() * [0]
for i in range(len(a)):
    a[i] = get_int()

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

Как определить количество различных элементов, содержащихся в последовательности? Стандартный алгоритм, не требующий использования никаких дополнительных возможностей, кроме доступа к элементу по индексу, может быть описан следующим образом: заводим счетчик n; для всех элементов a[i] последовательности проверяем, имеется ли в предшествующей части последовательности элемент, значение которого совпадает со значением элемента a[i]. Если таких элементов нет, значит, элемент a[i] содержит значение, появившееся в последовательности в первый раз, поэтому надо увеличить счетчик n на 1. Реализация алгоритма может выглядеть следующим образом:

n = 0;
for i in range(len(a)):
    isfound = False
    for j in range(i):
        if a[j] == a[i]:
            isfound = True
            break
    if not isfound:
        n += 1
put(n)

Решение можно упростить, если учесть, что у списка есть метод index(v), возвращающий индекс первого элемента списка, имеющего значение v. Заметим, что если требуемый элемент отсутствует, то генерируется ошибка ValueError. Чтобы проверить, имеется ли в предшествующей части последовательности элемент, равный a[i], достаточно вызвать метод a.index(a[i]). Этот метод гарантированно не приведет к ошибке: если его значение будет меньше, чем i, то это означает, что a[i] не является первым элементом последовательности, имеющим это значение. Получаем следующий вариант алгоритма:

n = 0;
for i in range(len(a)):
    if a.index(a[i]) == i:
        n += 1
put(n)

Если же воспользоваться еще одним стандартным типом данных языка Python — множеством (set), то алгоритм решения можно уменьшить до единственного оператора:

put(len(set(a)))

В данном операторе вначале исходный список преобразуется в множество; при этом из него автоматически удаляются все повторяющиеся элементы. Как и для любой последовательности, для множества можно использовать функцию len, возвращающую его размер. Результат этой функции сразу передается задачнику с помощью функции put.

Приведем полный текст функции solve для одного из вариантов решения:

def solve():
    task("Array47")
    a = get_int() * [0]
    for i in range(len(a)):
        a[i] = get_int()
    put(len(set(a)))

Примечание. Поскольку во всех заданиях, связанных с обработкой наборов данных, приходится выполнять практически одинаковые действия, обеспечивающие заполнение исходных списков, в задачник версии 4.19 были добавлены дополнительные функции get_list и get_matr, упрощающие выполнение подобных действий. В случае задания Array47 применение функции get_list позволяет получить решение, состоящее из единственного оператора:

def solve():
    task("Array47")
    put(len(set(get_list())))

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

Array79°. Дан массив размера N. Осуществить сдвиг элементов массива вправо на одну позицию (при этом A1 перейдет в A2, A2 — в A3, …, AN−1 — в AN, a исходное значение последнего элемента будет потеряно). Первый элемент полученного массива положить равным 0.

Для выполнения задания достаточно удалить последний элемент списка (с помощью инструкции del) и добавить в начало списка новый элемент с нулевым значением (с помощью метода списка insert(i, v), который добавляет элемент со значением v в позицию с индексом i):

del a[len(a) - 1]
a.insert(0, 0.0)
put(a)

Обратите внимание на то, что для вывода полученной последовательности достаточно использовать функцию put с единственным параметром — самой последовательностью. При этом задачнику будут последовательно переданы для проверки все элементы этой последовательности. Заметим также, что второй параметр метода insert обязательно должен быть вещественным нулем. Если дважды указать нуль целого типа (0), то первый элемент полученного списка также будет иметь целочисленный тип, что при проверке правильности решения приведет к сообщению об ошибке «Неверно указан тип при выводе результатов. Для вывода 1-го элемента (вещественного типа) использовано выражение целого типа».

Обработка матриц: Matrix7, Matrix24

Матрицы (прямоугольные таблицы чисел) могут быть представлены в виде списка своих строк, а каждая строка, в свою очередь, — в виде списка своих числовых элементов; таким образом, для хранения матрицы в языке Python можно использовать список списков.

Matrix7°. Дана матрица размера M × N и целое число K (1 ≤ K ≤ M). Вывести элементы K-й строки данной матрицы.

Приведем один из вариантов заполнения матрицы a:

a = get_int() * [0.0]
n = get_int()
for i in range(len(a)):
    a[i] = n * [0.0]
    for j in range(n):
        a[i][j] = get_float()

Для того чтобы вывести элементы строки с номером K, достаточно ввести этот номер и указать в функции put строку матрицы с этим номером (поскольку в заданиях предполагается, что строки нумеруются от 1, индекс соответствующей строки будет на 1 меньше введенного номера):

put(a[get_int() - 1])

Примечание 1. В данном примере основная часть решения приходилась на ввод элементов матрицы и их сохранение в соответствующих элементах списка списков. С использованием вспомогательной функции ввода get_matr, добавленной в версию 4.19 задачника, этот сложный фрагмент решения можно представить в виде одного оператора, получив, таким образом, решение, состоящее из двух строк:

a = get_matr()
put(a[get_int() - 1])

Заметив, что к переменной a после ее определения выполняется лишь одно обращение, мы можем сократить решение до единственного оператора (правда, разобраться в этом решении будет уже достаточно сложно):

put(get_matr()[get_int() - 1])
Примечание 2. В версии задачника 4.19 были добавлены варианты групп Series, Minmax, Array, Matrix с именами ZSeries, ZMinmax, ZArray, ZMatrix. Эти варианты отличаются тем, что в них применяется нумерация элементов от нуля, что соответствует способу индексирования в большинстве современных языков программирования. В частности, задача ZMatrix7 формулируется так:

ZMatrix7°. Дана матрица размера M × N и целое число K (0 ≤ K ≤ M–1). Вывести элементы K-й строки данной матрицы.

Решение этой задачи можно записать в виде единственного оператора следующим образом:

put(get_matr()[get_int()])

Рассмотрим еще одну задачу на анализ элементов матрицы.

Matrix24°. Дана матрица размера M × N. В каждом столбце матрицы найти максимальный элемент.

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

m = get_int()
n = get_int()
a = n * [0.0]
for j in range(len(a)):
    a[j] = m * [0.0]
for i in range(m):
    for j in range(n):
        a[j][i] = get_float()

Завершающая часть программы будет очень простой благодаря тому, что у любых числовых последовательностей имеются стандартные функции min и max, возвращающие их минимальное или, соответственно, максимальное значение:

for j in range(n):
    put(max(a[j]))

Заметим, что в этом решении не удастся использовать функцию get_matr для заполнения списка списков, так как функция get_matr заполняет список списков по строкам; таким образом, она возвращает список, который содержит списки, представляющие собой не столбцы исходной матрицы (как нам бы хотелось в данном случае), а ее строки. В то же время, функция get_matr позволяет существенно упростить решение аналогичного задания Matrix23, в котором требуется найти минимальный элемент в каждой строке исходной матрицы.


PrevNext

 

Рейтинг@Mail.ru

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2023