Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Двумерный массив

Двумерный массив - это одномерный массив, элементами которого являются одномерные массивы. Другими словами, это набор однотипных данных, имеющий общее имя, доступ к элементам которого осуществляется по двум индексам. Наглядно двумерный массив удобно представлять в виде таблицы, в которой n строк и m столбцов, а под ячейкой таблицы, стоящей в i-й строке и j-м столбце понимают некоторый элемент массива a[i][j].

Действительно, если разобраться с тем, что такое a[i] при фиксированном значении i, то увидим, что это одномерный массив, состоящий из m элементов, к которым можно обращаться по индексу: a[i][1], a[i][2], ... , a[i][m]. Схематически это вся i-я строка строка таблицы. Аналогично, если мы рассмотрим одномерный массив строк, то сможем заметить, что это так же двумерный массив, где каждый отдельный элемент - это символ типа char, а a[i] - это одномерный массив, представляющий отдельную строку исходного одномерного массива строк. Исходя из идеи определения думерного массива можно определить рекурентное понятие многомерного массива:

n-мерный массив - это одномерный массив, элементами которого являются (n-1)-мерные массивы.

Несложно догадаться, что 3-мерный массив визуально можно представить в виде куба с ячейками (похоже на кубик Рубика), где каждый элемент имеет вид a[i][j][k]. А вот с большими размерностями возникают сложности с визуальным представлением, но математическая модель ясна.

По-другому двумерный массив также называют матрицей, а в том случае, когда n=m (число строк равно числу столбцов) матрицу называют квадратной. В матрицах можно хранить любые табличные данные: содержание игрового поля (шашки, шахматы, Lines и т.д.), лабиринты, таблицу смежности графа, коэффициенты системы линейных уравнений и т.д. Матрицы часто используют для решения олимпиадных и математических задач.

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

3 5
7 8 2 3 1
5 3 2 6 3
9 3 5 2 0

В приведенном примере определена матрица, состоящая из трех строк и пяти столбцов. Рассмотрим пример чтения этих данных в матрицу и вывода матрицы в файл. Для этого удобно использовать двойной цикл, где внешний цикл по i будет пробегать по всем строкам, а внутренний цикл по j будет для текущей строки i перебирать все ее элементы. Алгоритмическая реализация этого процесса может выглядеть следующим образом:

int a[1..100][1..100];
//Чтение данных двумерного массива из файла
read(n,m);
for i=1..n{
  for j=1..m{
    read(a[i][j]);
  }
}
//Вывод матрицы в файл
for i=1..n{
  for j=1..m{
    write(a[i][j], ' ');
  }
  writeln; //новая строка
}

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

Транспонирование матрицы относительно главной диагонали
for i=2..n{
  for j=1..i-1{
    a[i][j] <---> a[j][i];
  }
}
Транспонирование матрицы относительно побочной диагонали
for i=1..n-1{
  for j=1..n-i{
    a[i][j] <---> a[n-j+1][n-i+1];
  }
}
 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Условный оператор
 Операторы цикла
 Строковые типы данных
 Массивы
 Функции
 Сортировка
 Двумерные массивы
 Рекурсия
 Базовые операции
 Символьные матрицы
 Целочисленные матрицы
 A. Двумерный массив
 B. Транспонирование - 1
 C. Транспонирование - 2
 D. Транспонирование - 3
 E. Транспонирование - 4
 F. Сумма матриц
 G. Произведение матриц

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483