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

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

Как и в языке Паскаль, в С++и многомерные массивы конструируют, объявляя массив, элементы которого тоже массивы. Так:

– одномерный массив int A[10]; - это набор из 10 целых чисел;

– двумерный массив int A2[10][3]; - это массив из 10 элементов, а каждый элемент A2[i] массив из трех целых чисел;

– int A3[10][3][5]; это массив из 10 элементов, а каждый элемент A3[i] - двумерный массив размером 35;.

Двумерные массивы используются для работы с матрицами и другими прямоугольными таблицами. Для того, чтобы в программе на языке С++ объявить прямоугольную матрицу

t₀₀ t₀₁ t₀₂ t₀₃

T =t₁₀ t₁₁ t₁₃ t₁₂

t₂₀ t₂₁ t₂₂ t_23,

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

double T[3][4];

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

Чтобы задать конкретный элемент массива, надо указать номер строки, в которой находится этот элемент, и номер столбца. Так, элемент, который находится во второй строке и третьем столбце надо обозначать T[1][2]_. Можно рассуждать и иначе:

– выбираем элемент массива, указав его индекс - T[1];

– T[1] это массив из четырех чисел, выбираем элемент массива T[1], указав его индекс - T[1][2].

 В Паскале, чтобы увеличить сходство операторов программы с математической записью элементов матриц, разрешалось перечислять индексы массива через запятую. В С++ это недопустимо. Особенно неприятно, что компилятор, встретив обозначение M [1,2] будет считать, что это M[2] и при синтаксическом контроле может не выдать ошибку.

Объявление двумерного массива также можно совмещать с его инициализацией:

int Mas[3][4]= {{2, 7, 9,4},

{1,3},

{3,3,3,3}}

Правила инициализации вытекают из соответствующих правил для одномерных массивов.

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

В сделанном выше объявлении массива можно не указывать число строк:

int Mas[][4]= {{2,7… и т д.

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

– при размещении первым записывается в память элемент, у которого все индексы равны нулю;

– далее пробегаем последний (правый) индекс от нуля дот максимального значения;

– потом увеличиваем на единицу предпоследний индекс и заново изменяем последний от нуля до единицы;

– когда предпоследний индекс достигнет максимального значения, увеличиваем третий справа индекс и так далее.

Таким образом, в двумерном массиве целых чисел размером MN элемент с индексами i,j смещен на N*sizeof(int) i+ sizeof(int)*j байтов от начала массива.

Учитывая построчное расположение элементов в памяти, в языке разрешено перечислять при инициализации элементы одной строкой. Тот же массив, что показан выше, можно было объявить так:

int Mas[][4]= {2, 7, 9,4, 1,3,0,0, 3,3,3,3};, но оставлять незаполненными элементы второй строки уже нельзя. В этом случае тоже можно не указывать первую размерность. Последняя строка может быть не полной - при объявлении

int Mas[][4]={1,2,3,4, 1,3} компилятор будет отсчитывать по четыре числа в строке и создаст матрицу

1 2 3 4

1 3 0 0.

Вывести элементы двумерного массива на экран можно различными способами.

Удобно организовать цикл по строкам и вложить в него цикл по столбцам

for(int i=0; i<3;i=i+1)

for (j=0;j<4;j=j+1) printf (“%5d”,Mas[i][j]);.

Можно также учесть, что в массиве 12 чисел и сделать цикл от нуля до 12, но при этом придется использовать новую арифметическую операцию % (получение остатка от деления целых чисел)

for(int i=0; i<12;i=i+1) printf (“%5d”,Mas[i/4][i%4]);.

Оба приведенные выше цикла будут печатать элементы массива в одну строку.

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

for(int i=0; i<3;i=i+1)

{

for (j=0;j<4;j=j+1) printf (“%5d”,Mas[i][j]);.

printf(“\n”);

}

Объясните, как изменится работа программы, если в этом фрагменте удалить фигурные скобки.

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

Составим, для примера, программу решения систем уравнений методом Гаусса и решим систему:

1.7x₁ + 10.0x₂ - 1.3x₃ + 2.1x₄ = 3.1

3.1x₁ + 1.7x₂ - 2.1x₃ + 5.4x₄ = 2.1

3.3x₁ - 7.7x₂ + 4.4x₃ - 5.1x₄ = 1.9

10.0x₁ - 20.1x₂ + 20.4x₃ + 1.7x₄ = 1.8

При решении системы все ее числовые коэффициенты можно хранить в массиве, объявленном как double a[4][5]. Столбец свободных членов системы – это элементы a[I][4], где I=0,..., 3.

Методом Гаусса основано на последовательности преобразований системы, не изменяющих ее корней.

Если прибавить к левой и правой части уравнения одно и то же число, его корни не изменяются. (Когда x₁ x_{2 …} x_n– это корни уравнения, его левая и правая части равны. Поэтому к одном уравнению можно, не изменяя корней, прибавить другое, умноженное на числовой коэффициент).

В методе Гаусса решение системы из n уравнений получается за n шагов.

На шаге номер k:

уравнение номер k делится на коэффициент a[k][k] – диагональный элемент матрицы становится равным единице;

потом (для всех i ≠ k) к уравнению номер i прибавляется уравнение номер k умноженное на минус a[i][k]. В результате в столбце k все коэффициенты, кроме расположенного на диагонали, станут равными нулю (для ручного счета указанные на данном шаге действия выполняются только для значений i>k, но нам удобнее заменить нулями все коэффициенты столбца, кроме одного).

После того, как циклом, изменяющим k от нуля до n-1 выполнится n описанных выше шагов, в каждой строке коэффициенты при всех неизвестных, кроме одного, будут равны нулю – это и есть решение.

Проделаем описанные преобразования для заданного уравнения.

Разделим все коэффициенты первой строки на a[0][0]=1.7. Первое уравнение приобретет вид:

x₁ + 5.882x₂ - 0.7647x₃ + 1.235x₄ = 1.824

Теперь, чтобы в уравнении 2 получить нулевой коэффициент при x₁, все элементы первого уравнения умножаем на a[1][0]=3.1 и отнимаем от второго, получим

0x₁ - 16.54 x₂ + 0.2706 x₃ + 1.571 x₄ = 3.553

и так далее.

Программа, реализующая данный алгоритм, оказывается заметно короче его описания:

#include<stdio.h>

#include<conio.h>

double a[4][5]={{1.7, 10.0, -1.3, 2.1, 3.1}, //Записали систему уравнений

{1, 1.7, -2.1, 5.4, 2.1},

{3.3, -7.7, 4.4, -5.1, 1.9},

{10.0,-20.1, 20.4, 1.7, 1.8}};

void print (void) //Вывод таблицы коэффициентов оформили в виде функции.

{ for(int i=0;i<4;i++){for(int j=0;j<5;j++)

printf("%8.4lg ",a[i][j]);printf("\n");}

printf("\n");

}

void main (void)

{

clrscr();

print(); //Вывели исходную таблицу

for(int k=0;k<4;k++) //Цикл по числу уравнений

{ double Kf=a[k][k];

for(int j=0;j<5;j++) a[k][j]=a[k][j]/Kf; //Получаем единицу при x_k

for(int i=0;i<4;i++)

{ //Во всех уравнениях, кроме k-го делаем коэффициент при x_k равным нулю.

Kf=a[i][k];

if(i!=k) for(j=0;j<5;j++) a[i][j]=a[i][j]-a[k][j]*Kf;

}

print();//Вывели таблицу со столбцом из нулей.

}

getch();

}

В приведенной программе делитель a[k][k]; предварительно записывается в отдельную переменную: Kf=a[k][k];.

Объясните, почему нельзя отказаться от использования промежуточной переменной Kf, записав вместо оператора a[k][j]=a[k][j]/Kf; оператор a[k][j]=a[k][j]/ a[k][k];.

Далее показаны результаты вывода на экран.

Исходная таблица

1.7 10 -1.3 2.1 3.1

3.1 1.7 -2.1 5.4 2.1

3.3 -7.7 4.4 -5.1 1.9

10 -20.1 20.4 1.7 1.8

Результат обработки при k=0 (сравните с ручным счетом)

1 5.882 -0.7647 1.235 1.824

0 -16.54 0.2706 1.571 -3.553

0 -27.11 6.924 -9.176 -4.118

0 -78.92 28.05 -10.65 -16.44

Результат обработки при k=1

1 0 -0.6684 1.794 0.5596

-0 1 -0.01636 -0.09498 0.2149

0 0 6.48 -11.75 1.708

0 0 26.76 -18.15 0.523

Результат обработки при k=2

1 0 0 0.5818 0.7358

0 1 0 -0.1247 0.2192

0 0 1 -1.814 0.2636

0 0 0 30.37 -6.529

Результат обработки при k=3

1 0 0 0 0.8608

0 1 0 0 0.1924

0 0 1 0 -0.1263

0 0 0 1 -0.215

Проверьте, что подстановка в уравнения значений x₀=0.8608, x₁=0.1924,

x₂=-0.1263, x₃=-0. 215 дает тождества.

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

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

Чтобы этого не случилось можно переставить уравнения местами.

Пример программы, реализующей модификацию данного алгоритма нечувствительную к нулевым элементам (метод Жордана-Гаусса находится на диске в папке JrdGauss, в тексте учебника мы его разберем при знакомстве с оконным интерфейсом ОС Windows).

Похожие работы

Структурное программирование: предпосылки и назначение; основные критерии оценки качества программы для ЭВМ

Скачать

12975

0

3

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