|
|
Примеры обработки одномерных массивовВ программировании существует ряд классических алгоритмов, которые можно рассматривать как основные операции. Комбинируя эти алгоритмы и видоизменяя их применительно к конкретным условиям, можно решать многие практические задачи. Ниже рассмотрены некоторые из этих алгоритмов. В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 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"); }
  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|