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

Аналогичная ситуация имеет место и для языка R, в котором для работы с последовательностями предусмотрены такие типы, как вектор (vector) — одномерный набор однотипных данных матрица (matrix) — двумерный набор однотипных данных, а также более сложные типы, такие как список (list), и таблица (data frame), которые могут содержать наборы данных различных типов, и некоторые другие. При решении задач из групп Array и Matrix на языке R достаточно использовать типы vector и matrix.

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

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

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

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

[Python]

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

Аналогичный подход возможен и для языка R, если использовать структуру vector:

[R]

a <- integer()
for (i in 1:Get())
    a <- append(a, Get())

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

[Python]

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

[R]

a <- integer(Get())
for (i in 1:length(a))
    a[i] <- Get()

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

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

[Python]

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)

При реализации алгоритма на языке R необходимо учитывать, что в нем индексы начинаются не от 0, а от 1, а также что целочисленные константы во всех выражениях, кроме выражений диапазона «:», должны снабжаться суффиксом «L» (иначе эти константы будут считаться вещественными числами с нулевой дробной частью):

[R]

n <- 1L
for (i in 2:length(a)) {
    isfound <- FALSE
    for (j in 1:(i-1))
        if (a[j] == a[i]) {
            isfound <- TRUE
            break
    }
    if (!isfound)
        n <- n + 1L
}
Put(n)

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

[Python]

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

Аналогичный алгоритм можно реализовать для языка R, если воспользоваться функцией match(x, v) (данная функция возвращает индекс первого элемента вектора v, равного значению x, или особое значение NA, если требуемых элементов нет):

[R]

n <- 1L
for (i in 2:length(a))
    if (match(a[i], a) == i)
        n <- n + 1L
Put(n)

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

[Python]

put(len(set(a)))

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

Столь же краткое решение можно получить и для языка R, если использовать функцию unique(v), которая возвращает вектор, полученный из вектора v, путем удаления всех повторяющихся элементов (остаются только их первые вхождения):

[R]

Put(length(unique(a)))

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

[Python]

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

[R]

Solve <- function() {
    a <- integer(Get())
    for (i in 1:length(a))
        a[i] <- Get()
    Put(length(unique(a)))
}

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

[Python]

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

Примечание 2. Аналогичные возможности, упрощающие ввод исходных векторов и матриц, предусмотрены и для языка R. Эти возможности реализованы с помощью функций GetV и GetM. Приведем пример решения задачи Array47, в котором для ввода исходного набора данных используется функция GetV:

[R]

Solve <- function() {
    Put(length(unique(GetV())))
}

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

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

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

[Python]

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

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

В языке R для выполнения аналогичных действий рекомендуется использовать векторные операции (которые в данном языке выполняются гораздо эффективнее традиционных циклов):

[R]

a[2:length(a)] <- a[1:(length(a)-1)]
a[1] <- 0
Put(a)

Напомним, что константа 0 в языке R обозначает вещественное число (для обозначения целочисленного нуля надо использовать константу 0L). В указании диапазона 1:(length(a)-1) скобки являются обязательными, так как операция взятия диапазона «:» имеет более высокий приоритет, чем операция вычитания.

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

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

В языке R для работы с матрицами предусмотрен особый тип данных matrix.

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

Приведем один из вариантов заполнения матрицы a для языков Python и R, использующий только базовую функцию ввода get:

[Python]

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

[R]

a <- matrix(nrow = Get(), ncol = Get())
for (i in 1:nrow(a))
    for (j in 1:ncol(a))
        a[i,j] <- Get()

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

[Python]

put(a[get() - 1])

В языке R индексирование всегда выполняется от 1, поэтому дополнительное вычитание значения 1 не требуется:

[R]

Put(a[Get(),])

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

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

[Python]

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

В варианте задачника для языка R для быстрого ввода матриц предусмотрена функция GetM:

[R]

a <- GetM()
Put(a[Get(),])

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

[Python]

put(get_matr()[get() - 1])

[R]

Put(GetM()[Get(),])

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

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

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

[Python]

put(get_matr()[get()])

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

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

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

[Python]

m = get()
n = get()
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()

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

[Python]

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

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

В случая языка R отсутствует подобная «несимметричность» строк и столбцов матриц, поэтому в решении мы можем использовать функцию GetM для быстрого ввода матрицы и после этого применить функцию max ко всем ее столбцам:

[R]

a <- GetM()
for (j in (1:ncol(a)))
    Put(max(a[,j]))

Используя одну из функций семейства apply, очень полезных при работе со сложными данными в языке R, решение можно представить в виде единственного оператора:

[R]

Put(apply(GetM(), 2, max))

Первый параметр этой функции определяет обрабатываемую матрицу, второй — позицию обрабатываемых индексов (в данном случае 2, т. е. индексы, соответствующие столбцам), а третий — имя функции, применяемой ко всем получаемым частям матрицы (в данном случае ко всем столбцам). Результат возвращается в виде вектора, который можно сразу передать в функцию Put.

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

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