Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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];
  }
}

Список задач

Задача 1: Художник
Задача 2: Проверка на симпатичность
Задача 3: Сапер
Задача 4: Морской бой - 2
Задача 5: Седловые точки
Задача 6: Теория игр
Задача 7: Табло
Задача 8: Судоку
Задача 9: Спираль
Задача 10: Змейка

Вернуться

 
     
Югорский НИИ ИТ, Югорский ФМЛ