Programming Taskbook


E-mail:

Пароль:

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

 

ЮФУ

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

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

 

Решения | PascalABC.NET | Обработка массивов

PrevNext


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

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

Начиная с версии 4.19, в задачник, наряду с группами Array и Matrix, входят их варианты — группы ZArray и ZMatrix. Эти варианты отличаются от исходных тем, что в них с элементами массивов (а также со строками и столбцами матриц) связываются не порядковые номера, начинающиеся с 1, а индексы, начинающиеся с 0 (префикс Z в именах новых групп можно интерпретировать как «zero-indexed»). Группы ZArray и ZMatrix удобно использовать для языков, в которых элементы массивов и других коллекций всегда индексируются от 0, в частности, для языка PascalABC.NET, если при решении задач используются динамические массивы (одномерные или двумерные).

Если в заданиях не идет речь о номерах (или индексах) элементов, строк или столбцов, то их формулировки в группах Array и ZArray, а также в группах Matrix и ZMatrix совпадают.

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


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

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

Для чтения исходного массива достаточно использовать функцию задачника ReadArrInteger, которая вначале считывает размер массива, затем создает массив требуемого размер и, наконец, заполняет его исходными данными (здесь и далее в программах мы не будем указывать начальную директиву uses PT4):

begin
  Task('Array47');
  var a := ReadArrInteger;
end.

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

begin
  Task('Array47');
  var a := ReadArrInteger;
  Show(a);
end.

При запуске полученной программы окно задачника примет следующий вид:

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

begin
  Task('Array47');
  var a := new integer[ReadInteger];
  for var i := 0 to a.Length - 1 do
    a[i] := ReadInteger;
end.

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

begin
  Task('Array47');
  var a := ReadArrInteger;
  var n := 0;
  for var i := 0 to a.Length - 1 do
  begin
    var isfound := False;
    for var j := 0 to i - 1 do
      if a[j] = a[i] then
      begin
        isfound := True;
        break;
      end;
    if not isfound then
      n += 1;
  end;
  Print(n);
end.

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

begin
  Task('Array47');
  var a := ReadArrInteger;
  var n := 0;
  for var i := 0 to a.Length - 1 do
    if a.IndexOf(a[i]) = i then
      n += 1;
  Print(n);
end.

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

begin
  Task('Array47');
  ReadArrInteger.Distinct.Count.Print;
end.

В данном операторе вначале выполняется ввод исходного массива, затем к этому массиву применяется запрос Distinct, возвращающий последовательность, построенную по данному массиву и не содержащую одинаковых элементов, а к этой последовательности применяется метод Count, возвращающий ее размер. Для вывода полученного размера также применяется точечная нотация, с помощью которой вызывается метод Print.

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

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

«Традиционное» решение, использующее цикл, выглядит следующим образом:

begin
  Task('Array79');
  var a := ReadArrReal;
  for var i := a.Length - 2 downto 0 do
    a[i + 1] := a[i];
  a[0] := 0;
  a.Print;
end.

Если использовать срезы массивов и операцию + для массива и скалярного элемента, то решение можно представить в виде двух строк:

begin
  Task('Array79');
  var a := ReadArrReal;
  (0.0 + a[:a.Length-1]).Print;
end.

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

Более эффективное по памяти решение можно получить, если вместо массива использовать стандартную структуру List — «список на базе массива». Данная структура, в отличие от массива, имеет методы, позволяющие добавлять и удалять элементы в любой позиции; при этом размер структуры динамически изменяется. В частности, для выполнения задания Array79 достаточно удалить последний элемент списка (с помощью метода RemoveAt) и добавить в начало списка новый элемент с нулевым значением (с помощью метода Insert). Необходимо также учитывать, что текущий размер списка можно получить с помощью его свойства Count. Чтобы ввести исходные данные в структуру типа List достаточно воспользоваться соответствующей функцией ввода задачника, а для вывода — либо процедуру, либо метод Print:

begin
  Task('Array79');
  var a := ReadListReal;
  a.RemoveAt(a.Count - 1);
  a.Insert(0, 0.0);
  a.Print;
end.

Заметим, что в качестве второго параметра метода Insert можно было указать целочисленное значение 0, поскольку оно будет автоматически преобразовано к вещественному типу элементов списка.

Примечание 2. Приведем фрагмент программы для создания и заполнения исходного списка List, не использующий функцию ReadListReal:

begin
  Task('Array79');
  var a := new List<real>(ReadInteger);
  for var i := 0 to a.Capacity - 1 do
    a.Add(ReadReal);
end.

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

Матрицы (прямоугольные таблицы чисел) могут быть представлены в виде двумерного массива, первый индекс которого определяет номер строки, а второй — номер столбца.

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

Для ввода двумерных массивов-матриц с элементами типа integer, real и string в задачнике предусмотрены специальные функции, не требующие ни вызова конструктора, ни использования циклов. Каждая из таких функций вначале читает два числа, определяющие количество строк и столбцов, затем создает матрицу требуемого размера, а затем заполняет ее элементы, считывая их из набора исходных данных. Для того чтобы просмотреть содержимое полученной матрицы, достаточно вывести ее в раздел отладки с помощью процедуры Show:

begin
  Task('Matrix7');
  var a := ReadMatrReal;
  var k := ReadInteger;
  Show(a);
end.

При запуске полученной программы окно задачника примет следующий вид:

Следует обратить внимание на специальные средства форматирования, позволяющие отобразить матрицу в разделе отладки наиболее наглядным образом.

При традиционном решении задачи используется цикл. Следует, однако, иметь в виду, что в заданиях группы Array нумерация строк и столбцов начинается от 1, поэтому необходимо вывести элементы, первый индекс которых равен k–1. Для определения количества столбцов достаточно использовать свойство матрицы ColCount:

begin
  Task('Matrix7');
  var a := ReadMatrReal;
  var k := ReadInteger;
  for var j := 0 to a.ColCount - 1 do
    a[k - 1, j].Print;
end.

Решение можно существенно упростить, если воспользоваться стандартным методом двумерных массивов Row(i), который возвращает строку матрицы с индексом i в виде одномерного массива (имеется также парный метод Col(j), возвращающий столбец с индексом j). Используя данный метод, решение можно представить в виде единственного оператора, не использующего ни одной переменной:

begin
  Task('Matrix7');
  ReadMatrReal.Row(ReadInteger - 1).Print;
end.

Примечание 3. Решение соответствующей задачи из группы ZMatrix будет еще короче, поскольку в ней сразу дается индекс строки, которую требуется вывести:

begin
  Task('ZMatrix7');
  ReadMatrReal.Row(ReadInteger).Print;
end.

Примечание 4. Приведем фрагмент программы для создания и заполнения исходного двумерного массива-матрицы, не использующий функцию ReadMatrReal:

begin
  Task('Matrix7');
  var a := new real[ReadInteger, ReadInteger];
  for var i := 0 to a.RowCount - 1 do
    for var j := 0 to a.ColCount - 1 do
      a[i, j] := ReadReal;
end.

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

Вначале приведем «традиционное» решение, использующее двойной цикл:

begin
  Task('Matrix24');
  var a := ReadMatrReal;
  for var j := 0 to a.ColCount - 1 do
  begin
    var max := a[0, j];
    for var i := 1 to a.RowCount - 1 do
      if a[i, j] > max then
        max := a[i, j];
    Print(max);
  end;
end.

Если воспользоваться свойством Col(j), возвращающим соответствующий столбец в виде массива, и применить к нему запрос LINQ Max, возвращающий максимальный элемент последовательности (в частности, массива), то в решении можно избавиться от вложенного цикла:

begin
  Task('Matrix24');
  var a := ReadMatrReal;
  for var j := 0 to a.ColCount - 1 do
    a.Col(j).Max.Print;
end.

Еще более кратное решение можно получить, если воспользоваться методом Cols, который возвращает последовательность столбцов. В данном случае к самой этой последовательности можно применять запросы LINQ, в частности, запрос Select, позволяющий получить на основе последовательности столбцов последовательность их максимальных значений:

begin
  Task('Matrix24');
  ReadMatrReal.Cols.Select(e -> e.Max).Print;
end.

В данном решении функция Cols применяется непосредственно к результату, возвращенному функцией ввода ReadMatrReal, а метод Print применяется непосредственно к последовательности максимальных значений столбцов, возвращенной запросом Select.


PrevNext

 

Рейтинг@Mail.ru

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

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