Теоретический материал (С++)

Сайт: Информатикс
Курс: Массивы
Книга: Теоретический материал (С++)
Напечатано:: Гость
Дата: Пятница, 21 Январь 2022, 09:38

Многомерные массивы

Объявление, ввод и вывод двумерного массива

Объявление int A[n] создает в памяти одномерный массив: набор пронумерованных элементов, идущих в памяти последовательно. Но можно создать и массив массивов следующим образом: int A[n][m]. Данное объявление создает массив из n объектов, каждый из которых в свою очередь является массивом типа int [m]. Тогда A[i], где i принимает значения от 0 до n-1 будет в свою очередь одним из n созданных обычных массивов, и обратиться к элементу с номером j в этом массиве можно через A[i][j].

Подобные объекты (массивы массивов) также называют двумерными массивами. Двумерные массивы можно представлять в виде квадратной таблицы, в которой первый индекс элемента означает номер строки, а второй индекс – номер столбца. Например, массив A[3][4] будет состоять из 12 элементов и его можно записать в виде

    A[0][0]  A[0][1]  A[0][2]  A[0][3]
    A[1][0]  A[1][1]  A[1][2]  A[1][3]
    A[2][0]  A[2][1]  A[2][2]  A[2][3]

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

    int A[n][m];
    for(int i=0;i<n;++i)
    {  // Выводим на экран строку i
       for(int j=0;j<m;++j)
          cout<<A[i][j]<<" ";
       cout<<endl; // Строка завершается символом перехода на новую строку
    }

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

    for(i=0;i<n;++i)
       for(j=0;j<m;++j)
          cin>>A[i][j];

Обработка одномерного массива

Обработка массивов производится аналогичным образом. Например, если мы хотим записать в массив таблицу умножения, то есть присвоить элементу A[i][j] значение i*j, это можно сделать следующим образом:

    for(i=0;i<n;++i)
       for(j=0;j<m;++j)
          A[i][j]=i*j;

Рассмотрим более сложную задачу и несколько способов ее решения. Пусть дан квадратный двумерный массив int A[n][n]. Необходимо элементам, находящимся на главной диагонали проходящей из левого верхнего угла в правый нижний (то есть тем элементам A[i][j], для которых i==j) присвоить значение 1, элементам, находящимся выше главной диагонали – значение 0, элементам, нахощящимся ниже главной диагонали – значение 2. То есть получить такой массив (пример для n==4):

    1 0 0 0
    2 1 0 0
    2 2 1 0
    2 2 2 1

Рассмотрим несколько способов решения этой задачи. Элементы, которые лежат выше главной диагонали – это элементы A[i][j], для которых i<j, а для элементов ниже главной диагонали i>j. Таким образом, мы можем сравнивать значения i и j и по ним определять значение A[i][j]. Получаем следующий алгоритм:

    for(i=0;i<n;++i)
       for(j=0;j<n;++j)
       {
          if (i<j)
             A[i][j]=0;
          else if(i>j)
             A[i][j]=2;
          else
             A[i][j]=1;
       }

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

Сначала заполним главную диагональ, для чего нам понадобится один цикл:

    for(i=0;i<n;++i)
       A[i][i]=1;

Затем заполним значением 0 все элементы выше главной диагонали, для чего нам понадобится в каждой из строк с номером i присвоить значение элементам A[i][j] для j=i+1, ..., n-1. Здесь нам понадобятся вложенные циклы:

    for(i=0;i<n;++i)
       for(j=i+1;j<n;++j)
          A[i][j]=0;

Аналогично присваиваем значение 2 элементам A[i][j] для j=0, ..., i-1:

    for(i=0;i<n;++i)
       for(j=0;j<i;++j)
          A[i][j]=2;

Можно также внешние циклы объединить в один и получить еще одно, более компактное решение:

    for(i=0;i<n;++i)
    {   // Заполняем строку с номером i
       for(j=0;j<i;++j)
          A[i][j]=2;   // Сначала пишем 2 ниже диагонали
       A[i][j]=1;      // После завершения предыдущего цикла i==j, пишем 1
       for(++j;j<n;++j) // Цикл начинаем с увеличения j на 1
          A[i][j]=0;   // Записываем 0 выше диагонали
    }

Многомерные массивы

Можно объявлять не только двумерные массивы, но и массивы с большим количеством измерений. Например, объявление int A[n][m][l] создает трехмерный массив из n*m*l элементов. Для обращения к каждому элементу такого массива необходимо указать три индекса: A[i][j][k], при этом 0<=i, i<n, 0<=j, j<m, 0<=k, k<l. Количество измерений в массиве может быть практически бесконечным (т.е. достаточным для решения любых практических задач).

Форматирование чисел при выводе

Допустим, мы заполним массив таблицей умножения: A[i][j]=i*j как в примере в начале раздела. Если мы теперь попробуем вывести этот массив на экран, разделяя элементы в строке одним пробелом, то из-за того, что числа имеют различную длину столбцы таблицы окажутся неровными:

    0 0 0 0 0 0 0 0 0 0
    0 1 2 3 4 5 6 7 8 9
    0 2 4 6 8 10 12 14 16 18
    0 3 6 9 12 15 18 21 24 27

Для того, чтобы получить ровные столбцы, необходимо выводить числа так, чтобы на каждое выводимое число отводилось бы, например, ровно  3 позиции, причем "лишние" позиции были бы заполнены пробелами. Тогда получится следующая таблица:

      0  0  0  0  0  0  0  0  0  0
      0  1  2  3  4  5  6  7  8  9
      0  2  4  6  8 10 12 14 16 18
      0  3  6  9 12 15 18 21 24 27

Для того, чтобы выводимое число или строка имело в точности заданную ширину, необходимо перед выводом его на экран для потока cout вызвать метод width с соответствующим знаяением параметра (в нашем случае, 3). Данный метод устанавливает ширину поля для выводимого значения. Получим следующую программу для вывода:

    for(int i=0;i<n;++i)
    {
       for(int j=0;j<m;++j)
       {
          cout.width(3);
          cout<<A[i][j];
       }
       cout<<endl;
    }

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

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

Упражнения

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

  1. Дано число n. Создайте массив int A[n][n], и заполните его по следующему правилу:
       
    Числа на диагонали, идущей из правого верхнего в левый нижний угол равны 1.    
    Числа, стоящие выше этой диагонали, равны 0.    
    Числа, стоящие ниже этой диагонали, равны 2.    

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

            Вход                   Выход
            4                    0 0 0 1
                                 0 0 1 2
                                 0 1 2 2
                                 1 2 2 2

  2. Дано число n и квадратный массив int A[n][n]. Проверьте, является ли массив симметричным относительно главной диагонали. Программа должна выводить слово yes для симметричного массива и слово no для несимметричного. Пример

            Вход                   Выход
            3                     yes
            0 1 2
            1 2 3
            2 3 4

    Указание. Для элемента A[i][j] симметричным ему является элемент A[j][i].

  3. Состязания-1. В метании молота состязается n спортcменов. Каждый из них сделал m бросков. Победителем считается тот спортсмен, у которого сумма результатов по всем броскам максимальна.

    Если перенумеровать спортсменов числами от 0 до n-1, а попытки каждого из них – от 0 до m-1, то на вход программа получает массив int A[n][m], состоящий из неотрицательных чисел. Программа должна определить максимальную сумму чисел в одной строке и вывести на экран эту сумму и номер строки, для которой достигается эта сумма. Если таких строк несколько, то выводится номер наименьшей из них. Пример для n=4 спортсменов и m=3 попыток:

            Вход                   Выход
            4 3                    19
            5 6 7                  1
            6 6 7
            7 6 6
            4 3 5

    Не забудьте, что нумерация строк (спортсменов) начинается с 0.

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

            Вход                   Выход
            4 3                    5
            1 4 2                  1 0
            5 2 5
            5 1 4
            1 2 4

    Если в массиве несколько максимальных элементов, то нужно вывести минимальный номер строки, в которой встречается такой элемент, а если в этой строке таких элементов несколько, то нужно вывести минимальный номер столбца. Не забудьте, что все строки и столбцы нумеруются с 0.

  5. Состязания - 3. Будем считать, что побеждает спортсмен, у которого максимален наилучший бросок. Если таких несколько, то из них побеждает тот, у которого наилучшая сумма результатов по всем попыткам. Если и таких несколько, победителем считается спортсмен с минимальным номером. Определите номер победителя соревнований.

            Вход                   Выход
            4 3                    2
            8 8 8
            5 9 3
            9 4 7
            6 6 2

  6. Состязания - 4. Будем считать, что победитель определяется по лучшему результату. Определите количество участников состязаний, которые разделили первое место, то есть определите количество строк в массиве, которые содержат значение, равное наибольшему.

            Вход                   Выход
            4 3                    2
            1 2 3
            4 5 6
            6 2 5
            2 3 4

  7. Состязания - 5. Решите предыдущую задачу, но на экран выведите еще и номера спортсменов, разделивших первое место. Сначала программа выводит количество спортсменов, показавших наилучший результат, затем – их номера в порядке возрастания.

            Вход                   Выход
            4 3                    2
            1 2 3                  1 2
            4 5 6
            6 2 5
            2 3 4

  8. Даны два числа n и m. Создайте двумерный массив int A[n][m], заполните его таблицей умножения A[i][j]=i*j и выведите на экран. При этом нельзя использовать вложенные циклы, все заполнение массива должно производиться одним циклом, например, for(i=0;i<n*m;++i).
  9. Даны два числа n и m. Создайте двумерный массив int C[n][m] и заполните его по следующим правилам:

    Числа, стоящие в строке 0 или в столбце 0 равны 1 (A[0][j]=1, A[i][0]=1). Для всех остальных элементов массива A[i][j]=A[i-1][j]+A[i][j-1], то есть каждый элемент равен сумме двух элементов, стоящих слева и сверху от него. Выведите данный массив на экран, отводя на вывод каждого числа ровно 6 символов.

            Вход                   Выход
            4 6                    1     1     1     1     1     1
                                   1     2     3     4     5     6
                                   1     3     6    10    15    21
                                   1     4    10    20    35    56

    Что получилось в результате?

  10. Даны числа n и m. Создайте массив int A[n][m] и заполните его следующей змейкой (ниже приведен пример для n=4 и m=6):

              0   1   2   3   4   5
             11  10   9   8   7   6
             12  13  14  15  16  17
             23  22  21  20  19  18

    Выведите массив на экран, отводя на вывод каждого числа ровно 3 символа.

  11. Даны числа n и m. Создайте массив int A[n][m] и заполните его следующим образом (ниже приведен пример для n=4 и m=6):

              0   1   3   6  10  14
              2   4   7  11  15  18
              5   8  12  16  19  21
              9  13  17  20  22  23

    Выведите массив на экран, отводя на вывод каждого числа ровно 3 символа.

  12. Дано число n. Создайте массив int A[2*n+1][2*n+1] и заполните его по спирали начиная с числа 0 в центральной клетке A[n][n]. Спираль выходит вверх, далее закручивается против часовой стрелки. Выведите массив на экран, отводя на вывод каждого числа ровно 3 символа. Ниже приведен пример для n=2:

             12 11 10  9 24
             13  2  1  8 23
             14  3  0  7 22
             15  4  5  6 21
             16 17 18 19 20