Обработка одномерных и двумерных массивов.

Цель: овладеть практическими навыками разработки алгоритмов и программ обработки одномерных и двумерных массивов

Теоретический материал

 

Массивы в Си/С++

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

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

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

Элементы массива объединены общим именем и занимают в компьютере определённую область памяти. Количество элементов в массиве всегда конечно. Эти элементы упорядочены таким образом, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого целого типа. Массив используют для хранения и обработки однородной информации, например таблиц и списков. Если за каждым элементом массива закреплен только один его порядковый номер, то такой массив называется линейным или одномерным.

 

Количество элементов массива может быть произвольным (в пределах доступной памяти) и зависит от решаемой задачи, т.е. задается программистом. Для размещения элементов массива в памяти требуется свободное место, определяемое произведением количества элементов на длину одного элемента. Например, для размещения 10 элементов типа double требуется 10 * 8 = 80 байт.

Размер массива зависит от решаемой задачи. При объявлении массива количество элементов в нем указывается в квадратных скобках после типа элементов данных и имени массива. Например,

 

int a[15],b,cp[10];

double x[25],y[25];

char st[100], ch;

В этом объявлении описаны массивы с элементами типа int с именами a (из 15 элементов) и cp (из 10 элементов); с элементами типа double с именами x и y (по 25 элементов каждый) и st с элементами типа char (из 100 элементов). Одновременно объявлены также скалярные переменные b типа int и ch типа char. Всего для размещения этих переменных требуется (если переменная типа int занимает 2 байта)

 

15 * 2 + 2 + 10 * 2 + 25 * 8 + 25 * 8 + 100 * 1 + 1 = 553 байт.

 

Тип каждого элемента массива совпадает с типом данных, объявленным для всего массива, и имеет некоторое конкретное значение. Например, элемент x[i], объявленного выше массива x, относится к типу double и может иметь значение, например, -1.536. Элементы массива могут иметь значение, не выходящее за пределы диапазона значений для этого типа данных. В качестве индекса массива указана переменная i, которая может иметь конкретное значение, например, 3. Имя переменной для индекса массива может быть любым, но лучше использовать имена, связанные с принятыми математическими обозначениями.

Для обращения к элементам массива используются индексы, которые записываются в квадратных скобках после имени массива. В качестве индексов и значений, используемых при объявлении массивов, могут использоваться целочисленные константы и выражения, которые при вычислении дают целые числа. Индексы изменяются от 0 до значения на 1 меньше объявленного количества элементов. Так, для упомянутого выше массива st из 100 элементов индексы изменяются от 0 до 99.

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

Если по какой-либо причине необходимо использовать индексы массива, начиная с 1, а не с 0, то можно объявить количество элементов массива на 1 больше, чем требуется, и не использовать элемент с индексом 0, либо этот элемент использовать для хранения информации, связанной со всеми элементами массива, например, масштабного коэффициента и т.п.

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

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

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

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

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

 

#define SIZE 20 /* Задание количества элементов массива */

...

double a[SIZE]; /* Объявление массива */

int i; /* Объявление индекса массива */

...

/* Оператор цикла, задающий изменение индекса */

for(i = 0; i < SIZE; i++) {

/* Выполнение действий с элементом массива, например

sum = sum + a[i]; */

}

В примере тип элементов массива объявлен как double, но могут быть указаны и любые другие, допустимые в языке Си типы данных.

В операторе цикла в проверке окончания цикла использовано строгое неравенство (i < SIZE), благодаря этому последнее значение переменной цикла i, как это и требуется, будет на 1 меньше заявленного количества элементов массива.

Если в программе начальное или конечное значение переменной цикла, являющейся индексом, задано с помощью переменной, которая в процессе выполнения программы может изменять свое значение, или не используется директива препроцессора #define, то программист может организовать в программе проверку на выход за пределы массива.

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

 

for(i = SIZE -1;i >= 0; i--)

 

Практически не отличается обработка элементов массива с шагом, отличным от 1, но при этом появляются две возможности:

1. Шаг обработки указывается в операторе цикла, например:

 

for(i = 0; i < SIZE; i = i + 2)

 

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

 

a[2 * i + 1]

 

Если нет достаточно веских оснований для использования способа 2, то лучше всегда использовать способ 1, поскольку он выполняется несколько быстрее способа 2, особенно если за один шаг цикла требуется вычислить более одного индекса.

 

Примеры обработки одномерных массивов

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

Пример 1. Задан одномерный массив, состоящий из SIZE элементов. Требуется подсчитать сумму этих элементов.

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

Для ввода элементов массива оформим цикл, который обеспечит последовательное изменение индекса от 0 до SIZE - 1. Тогда на каждом шаге цикла в массив a будет вводиться одно число, которое будет набрано с клавиатуры. Индекс элемента, в который будет записываться вводимое число, совпадает с текущим значением переменной цикла.

После ввода массива приравняем к нулю переменную sum, затем откроем цикл с переменной i, которая последовательно изменяется от 0 до SIZE - 1, и, прибавляя по очереди каждый последующий элемент массива к накапливаемой в переменной sum величине, получим требуемую сумму. После окончания цикла выведем полученный результат.

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

 

#include <stdio.h>

#include <conio.h>

#define SIZE 5

void main() {

/* Объявление пеpеменных */

double a[SIZE], sum;

int i;

/* Очистка экpана */

clrscr();

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Суммиpование элементов массива */

sum = 0;

for (i = 0; i < SIZE; i++)

sum = sum + a[i];

/* Вывод полученного pезультата */

printf("\nСумма равна %f", sum);

}

Программа работает следующим образом. Оператор double a[SIZE]; резервирует память для размещения SIZE (в данном случае 5) чисел с плавающей точкой. Этот оператор может только резервировать память, но никаких значений элементам не присваивает (точнее на выделенном участке памяти хранится информация, которая осталась от предыдущей программы и обычно совершенно бессмысленна).

Выполним статическое тестирование программы. Введем для массива а значения, например, такие: 1.7; 2.91; -0.8; 9.64; 3.4. Массив а вводится, как было отмечено выше. После присвоения sum значения нуль открывается цикл, т.е. переменной цикла i присваивается начальное значение 0 и выполняется собственно цикл. В данном случае тело цикла содержит один оператор, который к начальному значению переменной sum (которое равно 0) прибавляет значение первого элемента массива а, которое равно 1.7, и эту сумму присваивает переменной sum. На этом операторе проверяется условие выхода из цикла. Поскольку i меньше SIZE, то цикл повторяется, но i принимает значение 1. Снова к предыдущему значению sum (=1.7) прибавляется значение элемента а[1], равное 2.91. Результат (4.61) присваивается переменной sum. Поскольку i не достигло значения SIZE - 1, то процесс повторяется, и переменная sum далее последовательно получает значения

 

4.61 + (-0.8) = 3.81

3.81 + 9.64 = 13.45

13.45 + 3.4 = 16.85.

 

При суммировании последнего элемента массива переменная цикла i имеет значение 4 (т.е. SIZE - 1). В языке Си во время выполнения операторов цикла типа for значение переменной цикла как бы "запаздывает" на один шаг. Например, в операторе цикла переменной цикла было присвоено значение 0, но там же было записано и приращение этой переменной. Поэтому следовало бы ожидать, что выполнение цикла начнется со значения i = 1, но первый раз цикл выполняется при значении i = 0. Таким образом, хотя приращение переменной цикла и записано в заголовке операторов цикла после присвоения начального значения, но фактически это приращение выполняется после реализации всех операторов цикла непосредственно перед повторением цикла. Поэтому при попытке последующего повторения цикла переменная i принимает значение SIZE (равное 5), условие продолжения цикла оказывается ложным (теперь i не меньше SIZE), следовательно, цикл закончен, и выполнение программы продолжается с оператора, записанного сразу после "тела" цикла. Этим оператором осуществляется вывод значения переменной sum (равное 16.85), и выполнение программы заканчивается.

Пример 2. Подсчитать количество положительных элементов в массиве, состоящем из SIZE элементов.

Эта задача отличается от предыдущей тем, что суммируются не сами элементы, а подсчитывается их количество, причем не всех элементов (количество всех элементов известно заранее, оно равно SIZE), а только тех, которые больше нуля.

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

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

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

#include <stdio.h>

#include <conio.h>

#define SIZE 5

void main() {

/* Объявление пеpеменных */

double a[SIZE];

int i,n;

/* Очистка экpана */

clrscr();

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Подсчет количества положительных элементов */

n = 0;

for (i = 0; i < SIZE; i++)

if (a[i] > 0) n++;

printf("\nКоличество положительных чисел равно %d",n);

}

Пример 3. Задан одномерный массив, состоящий из SIZE элементов. Найти максимальный элемент.

Решение заключается в следующем. Выберем "кандидата" на максимальный элемент и назовем его аmах. Теперь будем последовательно сравнивать amaх c элементами массива. Если очередной элемент массива больше amaх, то заменим "кандидата" на максимальный элемент элементом массива и запомним его индекс. Если же очередной элемент массива меньше amaх, то никаких действий выполнять не будем, а перейдем к следующему элементу. Когда таким способом будут обработаны все элементы массива, amaх будет содержать значение максимального из элементов массива.

В этом решении есть неясности. Во-первых, каким образом первоначально выбрать "кандидата" на максимальный элемент. Для этого существуют два способа. Первый способ предусматривает выбор в качестве "кандидата" любого элемента массива, например, первого. Этот способ обычно применяется, когда перед началом поиска элементы массива уже существуют. Но задача поиска максимального (или минимального) элемента может быть решена и при одновременном формировании элементов массива и поиска среди них максимального (или минимального) элемента. В этом случае в качестве "кандидата" на максимальный элемент можно выбрать минимально возможное в данной ЭВМ число (при поиске минимума соответственно выбирают максимально возможное число), например, для чисел типа double таким значением является -1.7Е+308 (но можно выбрать число и меньшее по абсолютному значению, например -1.0E100, поскольку при решении реальных задач не может быть таких чисел). Во-вторых, как поступать, если "кандидат" на максимальный элемент и очередной элемент массива равны друг другу. В принципе это зависит от решаемой задачи. Если при равенстве мы будем пропускать обработку для текущего элемента, то обеспечим выбор первого из нескольких равных максимальных элементов. Если же при равенстве мы будем выполнять обработку (т.е. заменять значение "кандидата" значением текущего элемента массива и запоминать его индекс), то само значение при равенстве, естественно, одинаково, но индексы этих элементов разные. В этом случае будет обеспечен выбор последнего из нескольких равных максимальных элементов.

Для поиска минимального элемента в алгоритме требуется изменить на обратное условие проверки, и желательно изменить имя amax, например, на amin. И последнее, для "кандидата" на максимальный элемент в программе использовано специальное имя (amaх), что удобно для анализа работы программы. Иногда в программу не вводят такую дополнительную переменную, а вместо этого используют значение индекса текущего максимального элемента (в примере этот индекс имеет имя n). Принципиально, это также правильное решение, но менее наглядное. Кроме того, на реализацию алгоритма в этом случае будет затрачено чуть больше времени, поскольку время обращения к индексированной переменной больше времени обращения к обычной переменной на время вычисления адреса элемента по индексу.

Ниже приведен текст программы, решающей эту задачу.

 

#include <stdio.h>

#include <conio.h>

#define SIZE 5

void main() {

double a[SIZE], amax;

int i,n;

/* Очистка экpана */

clrscr();

/* Ввод элементов массива */

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Назначение "кандидата" на максимальный элемент */

amax = a[0];

n = 0;

/* Поиск максимального элемента массива */

for (i = 0; i < SIZE; i++)

if (a[i] > amax) {

amax = a[i];

n = i;

}

/* Вывод найденного максимального элемента массива */

printf("\nМаксимальное число равно %g, его индекс %d",amax,n);

}

Во всех рассмотренных выше программах операция ввода элементов массива выполнялась отдельно от операций по их обработке, но в этих примерах последовательность ввода элементов совпадает с порядком их обработки, поэтому эти операции можно совместить. Для этого достаточно функцию ввода элементов массива (scanf) записать перед операцией обработки, а цикл ввода исключить. Перед началом цикла в этом случае значение элемента a[0] неизвестно (поскольку этот элемент еще не введен), поэтому для назначения "кандидата" на максимальный элемент следует использовать минимально возможное число, т.е. для переменной amax присвоить значение, например, -1е100. Другими словами, вместо оператора

 

amax = a[0]; записать: amax = -1e100;

 

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

 

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

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

 

int n[4][3];

 

объявляет матрицу целочисленных элементов, состоящую из четырех строк и трех столбцов.

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

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

Пусть объявлена матрица

 

double a[4][4];

Ее элементы с математической точки зрения располагаются следующим образом:

 

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]

a[3][0] a[3][1] a[3][2] a[3][3].

 

Выберем, например, 4-ю строку (первый индекс равен 3) и будем последовательно изменять 2-й индекс, тогда изменение индексов (или порядок обращения к элементам матрицы) будет осуществляться в указанной ниже последовательности:

 

a[3][0] a[3][1] a[3][2] a[3][3],

 

т.е обработка выполняется по строкам.

Выберем теперь столбец, второй индекс у которого равен 3, и будем последовательно изменять 1-й индекс, тогда обращение к элементам матрицы будет выполняться в указанном ниже порядке:

 

a[0][3] a[1][3] a[2][3] a[3][3],

 

т.е обработка выполняется по столбцам.

Назначим для первого индекса матрицы переменную i, a для второго индекса матрицы переменную j (имена переменных для обозначения индексов могут быть и любыми другими). Тогда, если зафиксировать индекс i и изменять индекс j, матрица будет обрабатываться по строкам (быстрее изменяется второй индекс), если же зафиксировать индекс j и изменять индекс i, то матрица обрабатывается по столбцам.

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

Каждый циклический процесс часто требует подготовки (присвоения значения 0 для переменной, накапливающей сумму, выбора "кандидата" на максимальный элемент и т.д.). Если такая подготовка должна выполняться для каждого столбца или строки, то она выполняется перед внутренним оператором цикла. Обычно результаты обработки элементов матрицы по строкам или столбцам заносятся в массив, который объявляется вместе с матрицей и имеет соответственно размерность, равную количеству строк или столбцов.

С учетом изложенного, организация операторов цикла (с использованием директив препроцессора #define для задания размерностей матрицы по строкам и столбцам) имеет формы:

1)при обработке матрицы по столбцам

 

#define ROW <количество строк>

#define COL <количество столбцов>

...

<тип> <имя_матрицы>[ROW][COL],<имя_вектора>[COL];

int i,j; /* Объявление переменных для индексов матрицы */

for(j = 0; j < COL; j++) {

<операторы подготовки цикла обработки по столбцам>

for(i = 0; i < ROW; i++) {

<операторы обработки элементов>

}

}

2) при обработке матрицы по строкам

#define ROW <количество строк>

#define COL <количество столбцов>

...

<тип> <имя_матрицы>[ROW][COL],<имя_вектора>[ROW];

int i,j; /* Объявление переменных для индексов матрицы */

for(i = 0; i < ROW; i++) {

<операторы подготовки цикла обработки по строкам>

for(j = 0; j < COL; j++) {

<операторы обработки элементов>

}

}

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

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

 

#include <stdio.h>

#define ROW 2

#define COL 3

void main() {

int a[ROW][COL], b[ROW];

int i,j;

for(i = 0; i < ROW; i++) {

printf("\n Введите строку матрицы %d\n", i + 1);

for(j = 0; j < COL; j ++)

scanf("%d",&a[i][j]);

}

/* Суммирование по столбцам */

for(j = 0; j < COL; j ++) {

b[j] = 0;

for(i = 0; i < ROW; i++)

b[j] = b[j] + a[i][j];

}

printf("\n Суммы по столбцам матрицы\n");

for(j = 0; j < COL; j ++)

printf("%d\n ",b[j]);

}

Пример 5. Подсчитать количество нулей в строках матрицы.

#include <stdio.h>

#include <conio.h>

#define ROW 2

#define COL 3

void main(){

int a[ROW][COL], b[ROW];

int i, j, n;

clrscr();

for (i = 0; i< ROW; i++) {

printf("Введите строку матрицы %d\n", i + 1);

for (j = 0; j < COL; i++)

scanf("%d",&a[i][j]);

}

for (i = 0; i< ROW; i++) {

b[i] = 0;

n = 0;

for (j = 0; j < COL; i++)

if(a[i][j] == 0) n = n + 1;

b[i] = n;

}

printf("\nКоличество нулей по строкам мaтpицы\n");

for (i = 0; i< ROW; i++)

printf("%4d",b[i]);

}

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

Пусть имеется матрица, элементы которой имеют индексы:

 

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]

a[3][0] a[3][1] a[3][2] a[3][3].

 

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

Так, индексы у элементов, расположенных на главной диагонали, равны друг другу. Первый индекс элементов, расположенных на диагонали выше главной, меньше второго индекса и т.д.

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

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

Ниже приведены формулы для вычисления индексов на любых диагоналях матрицы. В этих формулах предполагается, что диагональ проходит через элемент, находящийся с края матрицы и имеющий индексы: k - номер строки, m - номер столбца. Через n обозначена размерность квадратной матрицы. Переменная i изменяется от 0 до count - 1, где count количество элементов на диагонали. Имя матрицы matrix.

а. Диагональ, параллельная главной, идущая сверху вниз.

Количество элементов на диагонали

count = n - (k + m);

Выражение для индексов

matrix[k + i][m + i]

Если k и m равны 0, то диагональ главная, и выражение для индексов упрощается до

matrix[i][i]

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

matrix[i][m + i]

количество элементов n - m.

Для элементов, расположенных ниже главной диагонали

matrix[i + k][i]

количество элементов n - k.

б. Диагональ, параллельная главной, идущая снизу вверх

Количество элементов на диагонали

count = k + m - (n - 2);

Выражение для индексов

matrix[k - i][m - i]

Если k и m равны n - 1, то диагональ главная, и выражение для индексов упрощается до

matrix[n - i - 1][n - i - 1]

в. Диагональ, перпендикулярная главной, идущая сверху вниз.

Количество элементов на диагонали

count = m - k + 1;

Выражение для индексов

matrix[k + i][m - i]

Если k равно 0, а m = n - 1, то это наибольшая диагональ, перпендикулярная главной.

Для диагоналей в левой верхней части матрицы k = 0, и формулы упрощаются.

matrix[i][m - i]

Количество элементов на диагонали

count = m + 1;

г. Диагональ, перпендикулярная главной, идущая снизу вверх.

Количество элементов на диагонали

count = k - m + 1;

Выражение для индексов

matrix[k - i][m + i]

Если m равно 0, а k = n - 1, то это наибольшая диагональ, перпендикулярная главной.

Для диагоналей в левой верхней части матрицы в этом случае

m = 0, и формулы упрощаются. Количество элементов на диагонали

count = k + 1;

matrix[k - i][i]

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

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

 

matrix[i][m + i],

 

где m - номер столбца, с которого начинается диагональ, а i - текущий индекс. Количество элементов на диагонали равно n - m (В примере программы размерность матрицы n равна ROW или COL, поскольку матрица квадратная).

Для решения задачи в программе открыты два цикла. В наружном цикле изменяется параметр m. Внутренний цикл задает текущий индекс. Количество элементов, обрабатываемых с помощью внутреннего цикла, т.е. диапазон изменения индексов переменный, задается выражением ROW - m в условии окончания цикла. Таким образом, наружный цикл задает смещение для второго индекса и границы его изменения, а внутренний цикл только изменяет значение переменной i, которая является первым индексом и входит в выражение для вычисления второго индекса элементов, расположенных выше главной диагонали. При таком оформлении операторов цикла обработка будет производиться от первой диагонали, расположенной выше главной, с последующим удалением от нее.

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

Для такой проверки определим в программе целочисленную переменную с именем flag, которую назовем флажком. Вначале флажку присваивается некоторое значение (в данном случае 1). Во внутреннем цикле проверяется значение очередного элемента. Если значение очередного элемента матрицы не равно 0, то проверяемое в операторе if условие оказывается истинным, а значит, будет выполнен оператор flag = 0;, т.е. будет сброшен флаг.

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

 

#include <stdio.h>

#define ROW 5

#define COL 5

void main() {

int a[ROW][COL];

int i, j, m, flag = 1;

for(i = 0; i < ROW; i++) {

printf("\n Введите строку матрицы %d\n",i + 1);

for(j = 0; j < COL; j++)

scanf("%d",&a[i][j]);

}

for(m = 1; m < COL; m++) {

for(i = 0; i < ROW - m; i++)

if(a[i][m + i]) flag = 0;

}

if(flag) printf("\n Матpица тpеугольная\n");

else printf("\n Матpица не тpеугольная\n");

}