Печатать книгуПечатать книгу

Теоретический материал (Паскаль)

Сайт: Информатикс
Курс: Массивы
Книга: Теоретический материал (Паскаль)
Напечатано:: Гость
Дата: Пятница, 27 Июнь 2025, 19:29

Оглавление

Понятие двумерного массива. Описание типа массива. Формирование значений элементов массива случайным образом

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

Мы уже рассматривали формирование и обработку одномерных массивов. Вспомним, что в массив мы объединяем конечную последовательность компонентов одного типа и даем им общее имя. Каждый отдельный компонент массива называется элементом. Количество элементов называется размером массива. Тип элементов определяет тип массива. Размер и тип массива указываются при его описании, причем размер может быть указан либо конкретным значением, либо ранее определенной константой. Номер элемента называется индексом. Индексы могут быть целыми положительными константами или целыми переменными. Чтобы обратиться к некоторому элементу массива, нужно рядом с идентификатором массива в скобках указать индекс элемента.

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

Размер двумерного массива задается парой чисел: M*N, где M - число строк, а N - число столбцов в таблице.

Пусть задан двумерный массив Matr, имеющий размер 10*20. Этот массив на языке Паскаль может быть описан следующим образом:

Var
  Matr : array [1..10,1..20] of integer;

тогда

  Matr[5,7] - элемент, расположенный в 5-ой строке и в 7-ом столбце.

Любая константа, переменная, значение функции или выражения в Турбо Паскале характеризуется своим типом. Тип любого из этих объектов определяет множество допустимых значений, которые может иметь объект, а также множество допустимых операций, которые применимы к объекту. Кроме того, тип определяет и формат внутреннего представления значения объекта.

Имя, которое программист присваивает своему определяемому типу, - произвольный идентификатор. Объявление типа должно быть сделано в разделе объявлений, и ему должно предшествовать кодовое слово Type.

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

Type
  Digit = array [0..9] of integer;
  Matrix = array [1..100, 0..9] of real;
Var
  m : Matrix;
  d : Digit;
  i : integer;

Описание типа массива задается следующим образом:

  <имя типа> = array [<сп. инд. типов>] of <тип>;

где:

<имя типа> - правильный идентификатор,
<сп. инд. типов> - список из одного или нескольких индексных типов, разделенных запятыми,
<тип> - любой тип Турбо Паскаля.

Примечание. Обычно в качестве индексного типа используется тип-диапазон, в котором задаются границы изменения индексов через две точки (..). Так как <тип>, идущий за кодовым словом of, - любой тип Турбо Паскаля, он может быть, в частности, другим массивом.

Рассмотрим примеры.

Пример 1. Массив можно описать как одномерный, элементами которого в свою очередь являются одномерные массивы.

Const
  n=2; m=3;
Type
  MyArray1 = array [1..m] of integer;
  MyArray2 = array [1..n] of MyArray1;
Var
  V : MyArray1;
  A : MyArray2;

В данном случае переменная V объявлена как одномерный массив из трех элементов целого типа, а переменная А описана как двумерный массив из двух строк, в каждую из которых включено по три элемента.

Пример 2. Описание массива можно сократить, исключив определение массива MyArray1.

Const
  n=2; m=3;
Type
  MyArray2 = array [1..n] of array [1..m] of integer;
Var
  A : MyArray2;

Пример 3. Еще более краткое описание массива А можно получить, указывая имя массива и диапазоны изменения индексов для каждой размерности массива (чем мы уже пользовались).

Const
  n=2; m=3;
Type
  MyArray2 = array [1..n, 1..m] of integer;
Var
  A : MyArray2;

Пример 4. Если же указанный тип используется для определения одного массива в программе, то удобно объявление массива в разделе описания переменных.

Const
  n=2; m=3;
Var
  A : array [1..n, 1..m] of integer;

Формирование значений элементов массива случайным образом и с клавиатуры и вывод их на экран

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

Очень часто значения элементов массива вводятся с клавиатуры. Этот способ задания информации слишком трудоемок при работе с массивами больших размеров. Для отладки широкого класса алгоритмов такой ввод информации должен быть заменен формированием элементов массива случайным образом. Для этого используют встроенные средства Турбо Паскаля: процедуру Randomize и функцию Random. Вы уже сталкивались с этими средствами. Сегодня же наша задача создать процедуру ввода элементов в массив и процедуру вывода элементов на экран.

Приведем пример заполнения массива случайными числами. Эта процедура должна принять в качестве входных параметров массив, количество строк и столбцов, заданные пользователем с клавиатуры в основном разделе операторов. Так как наша процедура будет воздействовать на пустой исходный массив, то его мы должны передать по ссылке. Количество строк и столбцов достаточно передать копиями по значению.

Procedure InsertMas1(Var X : MyArray; n, m: integer);
Var
  i, j : integer;
Begin
  Randomize;
  for i := 1 to n do {пробегая последовательно строки массива}
    for j := 1 to m do {просмотрим каждую ее ячейку текущего столбца}
      X[i, j]:= Random(50); {и запишем туда случайное число, которое сформирует компьютер в диапазоне [0..49]}
End;

Теперь, чтобы воспользоваться этой процедурой, достаточно вызвать ее в основном разделе программы, передав ей параметры.

Рассмотрим процедуру вывода элементов массива на экран. Для того, чтобы вывести наш массив на экран в виде таблицы, поставим при переходе к новой строке  оператор writeln и применим формат вывода элементов (:5).

Procedure PrintMas(X : MyArray; n, m: integer);
Var
  i, j : integer;
Begin
  for i := 1 to n do {пробегая последовательно строки и столбцы массива}
    begin
      for j := 1 to m do
        write(X[i, j]:5); {выведем элемент массива на экран, выделив ему 5 знакомест}
      writeln; {переход на новую строку}
    end;
End;

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

Рассмотрите процедуру, решающую следующую задачу.

Задача. Дана таблица действительных чисел. Сосчитайте сумму всех чисел в таблице.

Procedure Summa(A : MyArray; n, m: integer; Var S: real);
Var
  i, j : integer;

Begin
  S:= 0;
  for i := 1 to n do
    for j := 1 to m do
      S := S+A[i,j];
End.

Обратите внимание, что внутри цикла со счетчиком i организован цикл со счетчиком j. В результате суммируются в начале числа 1-й строки (i=1, при j=1, 2, ..., m), затем суммируются числа 2-й строки (i=2, при j=1, 2, ..., m) и т.д.

В данной программе в теле одного цикла содержится другой цикл. Такие циклы, как Вы уже знаете, называются вложенными. Причем цикл со счетчиком i является внешним, а цикл со счетчиком j - внутренним. Не забывайте основное правило при написании вложенных циклов: последний оператор внутреннего цикла должен либо предшествовать, либо совпадать с последним оператором внешнего цикла. Вложенные циклы напоминают матрешек, вложенных одна в другую.

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

Задание. Ниже приведен фрагмент решения некоторой задачи. Внимательно рассмотрев решение, сформулируйте решаемую задачу и оформите по всем правилам, применив знания текущего занятия.

. . .
  for i := 1 to N do
    Begin
      M := a[i,1];
      S := a[i, 1];
      for j := 2 to N do
        begin
          if M>a[i, j]
            Then
              M := a[i, j];
          S := S+a[i, j];
        end;
      writeln (i:7, M:6, S:6:3);
    End;
. . .

Работа с элементами массива

Для обработки двумерных массивов могут применяться методы решения задач, рассмотренные в теме "Одномерные массивы". Поскольку положение элемента в двумерном массиве описывается двумя индексами (первый - номер строки, второй - номер столбца), программы для решения большинства задач строятся на основе вложенных циклов. Рассмотрите предложенные ниже методы решения некоторых типов задач. Постарайтесь ответить на поставленные вопросы.

Нахождение количества элементов с данным свойством

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

Задача 1. Найти максимальный элемент массива и его индексы.

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

Procedure Maximum(X : MyArray2; n, m : integer; Var Max, Maxi, Maxj : integer);
Var
  i, j : integer;
Begin
  Max := X[1, 1]; {Предположим, что максимумом является первый элемент}
  Maxi := 1; {в этом случае запомним первую строку}
  Maxj := 1; {и первый столбец}
  for i := 1 to n do
    for j := 1 to m do
      if X[i, j] > Max {если среди элементов массива нашелся больший элемент, то}
        then
          begin
            Max := X[i, j];{внесем новое найденное значение в переменную Мах}
            Maxi := i; {и не забудем запомнить индексы строки} 
            Maxj := j;      {и столбца этого элемента}
          end;
End;

Задача 2. Найти количество отрицательных элементов в каждой строке.

Рассмотрим несколько способов решения этой задачи.

Способ 1 - количество элементов каждой строки хранить в одномерном массиве (Y) соответствующей размерности. Тогда можно описать такую процедуру:

Procedure KolOtr1(X : MyArray2; n, m : integer; Var Y : MyArray1);
Var
  i, j : integer;
Begin
  for i := 1 to n do
    begin
      Y[i] := 0; {записываем начальное значение количества элементов в соответствующую столбцу ячейку}
      for j := 1 to m do
        if X[i, j] < 0 {если отрицательный элемент найден}
          then
            Inc(Y[i]); {то увеличиваем текущее значение на единицу}
    end;
End;

Способ 2 - использовать счетчик, находить количество элементов строки и выводить значение на экран.

Procedure KolOtr2(X : MyArray2; n, m : integer);
Var
  i, j, k : integer;
Begin
  for i := 1 to n do
    begin
      k := 0;
      for j := 1 to m do
        if X[i, j] < 0
          then
            Inc(k);
      writeln(i,' - ', k);
    end;
End;

Вопрос. Сравните предложенные способы решения задачи. Какой способ Вам понравился больше и почему?

Определить, отвечает ли заданный массив некоторым требованиям

Задача. Определить, есть ли в заданном массиве элемент, равный 0.

Опишем логическую функцию, значение которой равно истине, если такой элемент есть, и ложно в противном случае. Самый простой способ - это просматривать элементы и, если найден искомый элемент, то присвоить функции значение True, иначе - False.

Function Check1(X : MyArray2; n, m : integer) : Boolean;
Var
  i, j : integer;
  Flag : Boolean;
Begin
  Flag := False; {Предполагаем, что искомого элемента в массиве нет}
  i := 1;
  while not(Flag) and (i<=n) do {элемент не найден и строки не закончились}
    begin
      j := 1;
      while (j<=m) and (X[i, j]<>0) do {перебираем все элементы текущей строки, пропуская ненулевые элементы}
        Inc(j);
      Flag := not(j=m+1);{если искомый элемент найден, то переменной Flag присваиваем значение True}
      Inc(i);
    end;
  Check1 := Flag;
End;

Задача. Определить, является ли данный квадратный массив симметричным относительно своей главной диагонали.

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

Заметим, что если массив является симметричным, то для него выполняется равенство A[i, j]=A[j, i] для всех i=1, ..., n и j=1, ..., n. Поэтому можно составить следующую функцию:

Function Check2(X : MyArray; n : integer) : Boolean;
Var
  i, j : integer;
  Flag : Boolean;
Begin
  Flag := True; {Предполагаем, что матрица симметрична}
  i := 2;
  while Flag and (i<n) do
    begin
      j := 1;
      while (j<i) and (X[i, j]=X[j, i]) do
        Inc(j);
      Flag := (j=i);
      Inc(i);
    end;
  Check2 := Flag;
End;

 Вопрос. Почему в функции употребляется условие i>j? Можно ли без него обойтись и что при этом изменится?

Изменение значений некоторых элементов, удовлетворяющих заданному свойству

Задача. В массиве размерностью NxM к элементам четных столбцов прибавить элемент первого столбца соответствующей строки.

Procedure Izmenenie1(Var X : MyArray2; n, m : integer);
Var
  i, j : integer;
Begin
  for i := 1 to n do
    for j := 1 to m div 2 do
      Inc(X[i, 2*j], X[i, 1]);
End;

Вопрос. Какой смысл вложен в оператор цикла for j := 1 to m div 2 do?

Задача. Заменить все отрицательные элементы на противоположные.

Procedure Izmenenie2(Var X : MyArray2; n, m : integer);
Var
  i, j : integer;
Begin
  for i := 1 to n do
    for j := 1 to m do
      X[i, j] := Abs(X[i, j]);
End;

Заполнение массива по правилу

Задача. Заполнить массив А размером NxM "змейкой" следующим образом:
  1   2   3   4   5   6   7
14 13 12 11 10   9   8
15 16 17 18 19 20 21
28 27 26 25 24 23 22

Для того, чтобы заполнить, надо определить правило заполнения, а оно в данном случае будет таким:
если ряд нечетный, то A[i, j]=(i-1)*m+j;
если ряд четный, то A[i, j]=i*m-j+1.

По этому правилу и составляем процедуру заполнения:

Procedure FillArray(Var X : MyArray2; n, m : integer);
Var
  i, j : integer;
Begin
  for i := 1 to n do
    for j := 1 to m do
      if i mod 2 =1
        then
          X[i, j] := (i-1)*m+j
        else
          X[i, j] := i*m-j+1;
End;

Задание. Вставьте в программу-шаблон рассмотренные подпрограммы и организуйте выбор одной из них через меню. Дополните подпрограммы, не содержащие пояснений, соответствующими комментариями. Сохраните файл на дискете.

Вставка и удаление строк и столбцов

Мы уже рассматривали такие действия для одномерных массивов. Обобщим для двумерных.

Вставка строк и столбцов

Для решения задачи вставки строки необходимо:

  1. Первые k строк оставить без изменения.


  2. Все строки после k-ой сдвинуть на одну назад, это лучше сделать, начиная с последней строки и идти до (k+1)-ой.


  3. Элементам строки k+1 присвоить заданное значение.


  4. Увеличить количество строк.


Кроме того, необходимо изменить размерность массива. Так как мы вставляем строку, то число строк будет на одну больше.

Задача. Вставить строку из нулей после строки с номером k.

Procedure Insert1(Var X : MyArray2; n, m : integer; k1 : integer);
Var
  i, j : integer;
Begin
  for i := n downto k1 +1 do
    for j := 1 to m do
      X[i+1, j] := X[i, j];{элементу столбца j присваиваем элемент этого же столбца, но из предыдущей строки}
  for j := 1 to m do
    X[k1+1, j] := 0;
  Inc(n);
End;

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

Задание. Напишите программу, содержащую процедуры вставки строки и столбца из заданного одномерного массива.

И еще несколько советов:

  1. Если необходимо выполнить вставку после строки, удовлетворяющей какому-либо условию, то надо найти лишь ее номер, и задача сводится к рассмотренной выше.


  2. Если вставка необходима после всех строк с заданным условием, то надо увеличить размерность по строкам, и если строка удовлетворяет условию, то к ней применять вставку. При этом надо заметить, что лучше просматривать строки, начиная с последней, и ввести счетчик вставленных строк.


  3. Вставка перед строкой с данным номером отличается лишь тем, что начинать сдвиг назад надо не с (k+1)-ой строки, а с k-ой.


Удаление строк и столбцов

Для решения задачи удаления строки необходимо:

  1. Сдвинуть все строки, начиная с данной на одну вверх.


  2. Последнюю строку обнулить.


  3. Уменьшить количество строк.


Процедура удаления строки приведена ниже.

Procedure Delete1(Var X : MyArray2; Var n, m : integer; k1 : integer);
Var
  i, j : integer;
Begin
  for i := k1 to n-1 do
    for j := 1 to m do
      X[i, j] := X[i+1, j];
  for j := 1 to m do
    X[n, j] := 0;
  Dec(n);
End;

Удаление столбца аналогично удалению строки.

И еще несколько советов:

  1. При выводе на экран полученного массива не выводите нулевые строки и столбцы.


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


Перестановка элементов массива

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

Задача. Поменять местами столбцы с номерами m1 и m2.

Эту задачу можно реализовать несколькими способами. Мы составим две процедуры, причем процедура обмена столбцами содержит в себе процедуру обмена значениями двух переданных ей ячеек массива. Рассмотрите их.

Procedure Swap2(Var X : MyArray2; n, m, m1, m2 : integer);
Var
  i : integer;
Procedure Swap1(Var elem1, elem2 : integer);
Var
  z : integer;
Begin
  z:=elem1;
  elem1:=elem2;
  elem2:=z;
End;
Begin
  if((m1<1) or (m1>m)) or ((m2<1) or (m2>m))
    then
      writeln('?')
    else
      for i := 1 to n do
        Swap1(X[i, m1], X[i, m2]);
End;

Вопрос. Какое сообщение должно быть выведено оператором writeln вместо знака вопроса и почему?