Лекция 1.6 Массивы

Общий взгляд

Массив задает способ организации данных. Массивом называют упорядоченную совокупность элементов одного типа. Каждый элемент массива имеет индексы, определяющие порядок элементов. Число индексов характеризует размерность массива. Каждый индекс изменяется в некотором диапазоне [a,b]. В языке C#, как и во многих других языках, индексы задаются целочисленным типом. В других языках, например, в языке Паскаль, индексы могут принадлежать счетному конечному множеству, на котором определены функции, задающие следующий и предыдущий элемент. Диапазон [a,b] называется граничной парой, a – нижней границей, b – верхней границей индекса. При объявлении массива границы задаются выражениями. Если все границы заданы константными выражениями, то число элементов массива известно в момент его объявления и ему может быть выделена память еще на этапе трансляции. Такие массивы называются статическими. Если же выражения, задающие границы, зависят от переменных, то такие массивы называются динамическими, поскольку память им может быть отведена только динамически в процессе выполнения программы, когда становятся известными значения соответствующих переменных. Массиву, как правило, выделяется непрерывная область памяти.

В языке C# снято существенное ограничение языка C++ на статичность массивов. Массивы в языке C# являются динамическими. Как следствие этого, напомню, массивы относятся к ссылочным типам, память им отводится динамически в «куче». К сожалению, не снято ограничение 0-базируемости, означающее, что нижняя граница массивов C# фиксирована и равна нулю. Было бы гораздо удобнее во многих задачах иметь возможность работать с массивами, у которых нижняя граница изменения индекса не равна нулю.

В языке C++ «классических» многомерных массивов нет. Здесь введены одномерные массивы и массивы массивов. Последние являются более общей структурой данных и позволяют задать не только многомерный куб, но и изрезанную, ступенчатую структуру. Однако использование массива массивов менее удобно, и, например, классик и автор языка C++ Бьерн Страуструп в своей книге [Основы языка C++] пишет: «Встроенные массивы являются главным источником ошибок – особенно когда они используются для построения многомерных массивов. Для новичков они также являются главным источником смущения и непонимания. По возможности пользуйтесь шаблонами vector, valarray и т. п. ».

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

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

Объявление массивов

Рассмотрим, как объявляются одномерные массивы, массивы массивов и многомерные массивы.

Объявление одномерных массивов

Напомню общую структуру объявления:

[<атрибуты>] [<модификаторы>] <тип> <объявители>;

Забудем пока об атрибутах и модификаторах. Объявление одномерного массива выглядит следующим образом:

<тип>[] <объявители>;

Заметьте, в отличие от языка C++ квадратные скобки приписаны не к имени переменной, а к типу. Они являются неотъемлемой частью определения типа, так что запись T[] следует понимать как тип, задающий одномерный массив с элементами типа T.

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

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

int[] a, b, c;

Чаще всего при объявлении массива используется имя с инициализацией. И опять-таки, как и в случае простых переменных, могут быть два варианта инициализации. В первом случае инициализация является явной и задается константным массивом. Вот пример:

double[] x = {5.5, 6.6, 7.7};

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

Во втором случае создание и инициализация массива выполняется в объектном стиле с вызовом конструктора массива. И это наиболее распространенная практика объявления массивов. Приведу пример:

int[] d = new int[5];

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

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

public void TestDeclaration()

{

//объявляются три одномерных массива A,B,C

int[] A = new int[5], B= new int[5], C= new int[5];

//создание массивов статическим методом класса Arrs

Arrs.CreateOneDimAr(A);

Arrs.CreateOneDimAr(B);

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

C[i] = A[i] + B[i];

//объявление массива с явной инициализацией

int[] x ={5,5,6,6,7,7};

//объявление массивов с отложенной инициализацией

int[] u,v;

u = new int[3];

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

// v = {1,2,3}; //присваивание константного массива недопустимо

v = new int[4];

v = u; //допустимое присваивание

Arrs.PrintAr1(«A», A); Arrs.PrintAr1(«B», B);

Arrs.PrintAr1(«C», C); Arrs.PrintAr1(«X», x);

Arrs.PrintAr1(«U», u); Arrs.PrintAr1(«V», v);

}

На что следует обратить внимание, анализируя этот текст:

  • В процедуре показаны разные способы объявления массивов. Вначале объявляются одномерные массивы A, B и C, создаваемые конструктором. Значения элементов этих трех массивов имеют один и тот же тип int. То, что они имеют одинаковое число элементов, произошло по воле программиста, а не диктовалось требованиями языка. Заметьте, что после такого объявления с инициализацией конструктором, все элементы имеют значение, в данном случае – ноль, и могут участвовать в вычислениях.
  • Массив x объявлен с явной инициализацией. Число и значения его элементов определяется константным массивом.
  • Массивы u и v объявлены с отложенной инициализацией. В последующих операторах массив u инициализируется в объектном стиле, его элементы получают в цикле значения.
  • Обратите внимание на закомментированный оператор присваивания. В отличие от инициализации, использовать константный массив в правой части оператора присваивания недопустимо. Эта попытка приводит к ошибке, поскольку  v — это ссылка, которой можно присвоить ссылку, но нельзя присвоить константный массив. Ссылку присвоить можно.
    Что происходит в операторе присваивания v = u.? Это корректное  ссылочное присваивание: хотя u и v имеют разное число элементов, но они являются объектами одного класса. В результате присваивания память, отведенная массиву v, освободится, ей займется теперь сборщик мусора. Обе ссылки u и v будут теперь указывать на один и тот же массив, так что изменение элемента одного массива немедленно отражается на другом массиве.
  • Далее определяется двумерный массив w  и делается попытка выполнить оператор присваивания v = w. Это ссылочное присваивание некорректно, поскольку объекты w и v разных классов и для них не выполняется требуемое для присваивания согласование по типу.
  • Для поддержки работы с массивами создан специальный класс Arrs, статические методы которого выполняют различные операции над массивами. В частности, в примере использованы два метода этого класса, один из которых заполняет массив случайными числами, второй – выводит массив на печать. Вот текст первого из этих методов:

public static void CreateOneDimAr(int[] A)

{

for(int i = 0; i<A.GetLength(0);i++)

A[i] = rnd.Next(1,100);

}//CreateOneDimAr

Здесь rnd – это статическое поле класса Arrs, объявленное следующим образом:

private  static Random rnd = new Random();

Процедура печати массива с именем name выглядит так:

public static void PrintAr1(string name,int[] A)

{

Console.WriteLine(name);

for(int i = 0; i<A.GetLength(0);i++)

Console.Write(«\t» + name + «[{0}]={1}», i, A[i]);

Console.WriteLine();

}//PrintAr1

На рис. 6.1 показан консольный вывод результатов работы процедуры TestDeclarations:

Рис. 6.1. Результаты объявления и создания массивов

Особое внимание обратите на вывод, связанный с массивами u и v.

Динамические массивы

Во всех вышеприведенных примерах объявлялись статические массивы, поскольку нижняя граница равна нулю по определению, а верхняя всегда задавалась в этих примерах константой. Напомню, что в C# все массивы, независимо от того, каким выражением описывается граница, рассматриваются как динамические и память для них распределяется в «куче». Полагаю, что это отражение разумной точки зрения: ведь статические массивы скорее исключение, а правилом является использование динамических массивов. Действительно реальные потребности в размере массива, скорее всего, выясняются в процессе работы в диалоге с пользователем.

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

Приведу пример, в котором описана работа с динамическим массивом:

public void TestDynAr()

{

//объявление динамического массива A1

Console.WriteLine(«Введите число элементов массива A1″);

int size = int.Parse(Console.ReadLine());

int[] A1 = new int[size];

Arrs.CreateOneDimAr(A1);

Arrs.PrintAr1(«A1″,A1);

}//TestDynAr

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

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

Уже объяснялось, что разделение массивов на одномерные и многомерные носит исторический характер. Никакой принципиальной разницы между ними нет. Одномерные массивы — это частный случай многомерных. Можно говорить и по-другому: многомерные массивы являются естественным обобщением одномерных. Одномерные массивы позволяют задавать такие математические структуры, как векторы, двумерные – матрицы, трехмерные – кубы данных, массивы большей размерности — многомерные кубы данных.

Размерность массива это характеристика типа. Как синтаксически при объявлении типа  массива указать его размерность? Это делается достаточно просто, за счет использования запятых. Вот как выглядит объявление многомерного массива в общем случае:

<тип>[, … ,] <объявители>;

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

public void TestMultiArr()

{

int[,]matrix = {

{1,2},

{3,4}

};

Arrs.PrintAr2(«matrix», matrix);

}//TestMultiArr

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

public void TestMultiMatr()

{

int n1, m1, n2, m2,n3, m3;

Arrs.GetSizes(«MatrA»,out n1,out m1);

Arrs.GetSizes(«MatrB»,out n2,out m2);

Arrs.GetSizes(«MatrC»,out n3,out m3);

int[,]MatrA = new int[n1,m1], MatrB = new int[n2,m2];

int[,]MatrC = new int[n3,m3];

Arrs.CreateTwoDimAr(MatrA); Arrs.CreateTwoDimAr(MatrB);

Arrs.MultMatr(MatrA, MatrB, MatrC);

Arrs.PrintAr2(«MatrA»,MatrA); Arrs.PrintAr2(«MatrB»,MatrB);

Arrs.PrintAr2(«MatrC»,MatrC);

}//TestMultiMatr

Три матрицы MatrA, MatrB и MatrC имеют произвольные размеры, выясняемые в диалоге с пользователем, и использование для их описания динамических массивов представляется совершенно естественным. Метод CreateTwoDimAr заполняет случайными числами элементы матрицы, переданной ему в качестве аргумента, метод PrintAr2 выводит матрицу на печать. Я не буду приводить их код, похожий на код их одномерных аналогов.

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

public void MultMatr(int[,]A, int[,]B, int[,]C)

{

if (A.GetLength(1) != B.GetLength(0))

Console.WriteLine(«MultMatr: ошибка размерности!»);

else

for(int i = 0; i < A.GetLength(0); i++)

for(int j = 0; j < B.GetLength(1); j++)

{

int s=0;

for(int k = 0; k < A.GetLength(1); k++)

s+= A[i,k]*B[k,j];

C[i,j] = s;

}

}//MultMatr

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

Взгляните, как выглядят результаты консольного вывода на данном этапе работы:

Рис. 6.2. Умножение матриц

Массивы массивов

Еще одним видом массивов C# являются массивы массивов, называемые также изрезанными массивами (jagged arrays). Такой массив массивов можно рассматривать как одномерный массив, элементы которого являются массивами, элементы которых, в свою очередь снова могут быть массивами, и так может продолжаться до некоторого уровня вложенности.

В каких ситуациях может возникать необходимость в таких структурах данных? Эти массивы могут применяться для представления деревьев, у которых узлы могут иметь произвольное число потомков. Таковым может быть, например, генеалогическое дерево. Вершины первого уровня – Fathers, представляющие отцов, могут задаваться одномерным массивом, так что Fathers[i] – это i-й отец. Вершины второго уровня представляются массивом массивов – Children, так что Children[i] – это массив детей i-го отца, а Children[i][j] – это j-й ребенок i-го отца. Для представления внуков понадобится третий уровень, так что GrandChildren [i][j][k] будет представлять к-го внука j-го ребенка i-го отца.

Есть некоторые особенности в объявлении и инициализации таких массивов. Если при объявлении типа многомерных массивов для указания размерности использовались запятые, то для изрезанных массивов применяется более ясная символика – совокупности пар квадратных скобок; например, int[][] задает массив, элементы которого — одномерные массивы элементов типа int.

Сложнее с созданием самих массивов и их инициализацией. Здесь нельзя вызвать конструктор new int[3][5], поскольку он не задает изрезанный массив. Фактически нужно вызывать конструктор для каждого массива на самом нижнем уровне. В этом и состоит сложность объявления таких массивов. Начну с формального примера:

//массив массивов — формальный пример

//объявление и инициализация

int[][] jagger = new int[3][]

{

new int[] {5,7,9,11},

new int[] {2,8},

new int[] {6,12,4}

};

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

int[][] jagger1 = new int[3][]

{

new int[4],

new int[2],

new int[3]

};

В этом случае элементы массива получат при инициализации нулевые значения. Реальную инициализацию нужно будет выполнять программным путем. Стоит заметить, что в конструкторе верхнего уровня константу 3 можно опустить и писать просто new int[][]. Самое забавное, что вызов этого конструктора можно вообще опустить, он будет подразумеваться:

int[][] jagger2 =

{

new int[4],

new int[2],

new int[3]

};

Но вот конструкторы нижнего уровня необходимы. Еще одно важное замечание, – динамические массивы возможны и здесь. В общем случае, границы на любом уровне могут быть выражениями, зависящими от переменных. Более того, допустимо, чтобы массивы на нижнем уровне были многомерными. Но это уже «от лукавого», вряд ли стоит пользоваться такими сложными структурами данных, ведь с ними предстоит еще и работать.

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

/// <summary>

/// массив массивов -»Отцы и дети»

/// </summary>

public void GenTree()

{

int Fcount = 3;

string[] Fathers = new string[Fcount];

Fathers[0] = «Николай»; Fathers[1] = «Сергей»; Fathers[2] = «Петр»;

string[][] Children = new string[Fcount][];

Children[0] = new string[] {«Ольга», «Федор»};

Children[1] = new string[] {«Сергей», «Валентина», «Ира», «Дмитрий»};

Children[2] = new string[] {«Мария», «Ирина», «Надежда»};

Arrs.PrintAr3(Fathers, Children);

}

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

Я не буду демонстрировать работу с генеалогическим деревом, ограничусь лишь печатью этого массива. Здесь есть несколько поучительных моментов. В классе Arrs для печати массива создан специальный метод PrintAr3, которому в качестве аргументов передаются массивы Fathers и Children. Вот текст данной процедуры:

/// <summary>

/// Печать дерева «Отцы и дети»,

/// заданного массивами Fathers и Children

/// </summary>

/// <param name=»Fathers»>массив отцов</param>

/// <param name=»Children»> массив массивов детей</param>

public static void PrintAr3(string[] Fathers, string[][] Children)

{

for (int i = 0; i < Fathers.Length; i++)

{

Console.WriteLine(«Отец : {0}; Его дети:», Fathers[i]);

for (int j = 0; j < Children[i].Length; j++)

Console.Write(Children[i][j] + » «);

Console.WriteLine();

}

}//PrintAr3

Приведу некоторые комментарии к этой процедуре:

  • Внешний цикл по i организован по числу элементов массива Fathers. Заметьте, здесь используется свойство Length, в отличие от ранее применяемого метода GetLength.
  • В этом цикле с тем же успехом можно было бы использовать и имя массива Children. Свойство Length для него возвращает число элементов верхнего уровня, совпадающее, как уже говорилось, с числом элементов массива Fathers.
  • Во внутреннем цикле свойство Length вызывается для каждого элемента Children[i], который является массивом.
  • Остальные детали, надеюсь, понятны.

Приведу  вывод, полученный в результате работы процедуры PrintAr3:

Рис. 6.3. Дерево «Отцы и дети»

Процедуры и массивы

В наших примерах массивы неоднократно передавались процедурам в качестве входных аргументов и возвращались в качестве результатов. Остается подчеркнуть только некоторые детали:

  • В процедуру достаточно передавать только сам объект – массив. Все его характеристики (размерность, границы) можно определить, используя свойства и методы этого объекта.
  • Когда массив является выходным аргументом процедуры, как аргумент C в процедуре MultMatr, выходной аргумент совсем не обязательно снабжать ключевым словом ref или out (хотя и допустимо). Передача аргумента по значению в таких ситуациях так же хороша, как и передача по ссылке. В результате вычислений меняется сам массив в динамической памяти, а ссылка на него остается постоянной. Процедура и ее вызов без ключевых слов выглядит проще, поэтому обычно они опускаются. Заметьте, в процедуре GetSizes, где определялись границы массива, ключевое слово out, сопровождающее аргументы, совершенно необходимо.
  • Функция может возвращать массив в качестве результата.

Алгоритмы и задачи

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

Последовательность элементов – a1, a2, …. an – одна из любимых структур в математике. Последовательность можно рассматривать как функцию a(i), которая по заданному значению индекса элемента возвращает его значение. Эта функция задает отображение integer -> T, где T – это тип элементов последовательности. В программировании последовательности это одномерные массивы, но от этого они не перестают быть менее любимыми.

Определение: Массив – это упорядоченная последовательность элементов одного типа. Порядок элементов задается с помощью индексов.

В отличие от математики, где последовательность может быть бесконечной, массивы всегда имеют конечное число элементов. Для программистов важно то, как массивы хранятся в памяти. Массивы занимают непрерывную область памяти, поэтому, зная адрес начального элемента массива, зная, сколько байтов памяти требуется для хранения одного элемента, и, зная индекс (индексы) некоторого элемента, нетрудно вычислить его адрес, а значит и хранимое по этому адресу значение элемента. На этом основана адресная арифметика  в языках C, C++, где адрес элемента a(i) задается адресным выражением a+i, в котором имя массива a воспринимается как адрес первого элемента. При вычислении адреса i-го элемента индекс i умножается на длину слова, требуемого для хранения элементов типа T. Адресная арифметика использует 0-базируемость элементов массива, полагая индекс первого элемента равным нулю, поскольку первому элементу соответствует адресное выражение а+0.

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

Не менее важно понимать и то, что массивы C# относятся к ссылочным типам.

Ввод – вывод массивов

Как у массивов появляются значения, как они изменяются? Возможны три основных способа:

  • Вычисление значений в программе;
  • значения вводит пользователь;
  • связывание с источником данных.

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

Приведу некоторые рекомендации по вводу и выводу массивов, ориентированные на работу с конечным пользователем.

Для консольных приложений ввод массива обычно проходит несколько этапов:

  • ввод размеров массива;
  • создание массива;
  • организация цикла по числу элементов массива, в теле которого выполняется:
    • приглашение к вводу очередного элемента;
    • ввод элемента;
    • проверка корректности введенного значения.

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

При выводе массива на консоль, обычно вначале выводится имя массива, а затем его элементы в виде пары: <имя> = <значение> (например, f[5] = 77,7). Задача осложняется для многомерных массивов, когда для пользователя важно видеть не только значения, но и структуру массива, располагая строку массива в строке экрана.

Как организовать контроль ввода? Наиболее разумно использовать для этих целей конструкцию охраняемых блоков – try – catch блоков. Это общий подход, когда все опасные действия, связанные с работой пользователя, внешних устройств, внешних источников данных, размещаются в охраняемых блоках.

Как правило, для ввода — вывода массивов пишутся специальные процедуры, вызываемые в нужный момент.

Ввод — вывод массивов в Windows приложениях

Приложения Windows позволяют построить дружелюбный интерфейс пользователя, облегчающий работу по вводу и выводу массивов. И здесь, когда данные задаются пользователем, заполнение массива проходит через те же этапы, что рассматривались для консольных приложений. Но выглядит все это более красиво, наглядно и понятно. Пример подобного интерфейса, обеспечивающего работу по вводу и выводу одномерного массива, показан на рис. 6_4.

Рис. 6_4 Форма для ввода – вывода одномерного массива

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

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

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

На рис. 6_4 форма разделена на две части – для ввода и вывода массива. Крайне важно уметь организовать ввод массива, принимая данные от пользователя. Не менее важно уметь отображать существующий массив в форме, удобной для восприятия пользователя. На рисунке показаны три различных элемента управления, пригодные для этих целей – ListBox, CheckedListBox и ComboBox. Как только вводится очередной элемент, он немедленно отображается во всех трех списках.

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

Посмотрим, как это все организовано программно. Начну с полей формы OneDimArrayForm, показанной на рис. 6_4:

//fields

int n = 0;

double[] mas;

int currentindex = 0;

double ditem = 0;

const string SIZE = «Корректно задайте размер массива!»;

const string INVITE = «Введите число в формате m[,n]«;

const string EMPTY =  «Массив пуст!»;

const string ITEMB =  «mas[";

const string ITEME =  "] = «;

const string FULL =   «Ввод недоступен!»;

const string OK =     «Корректный ввод!»;

const string ERR =    «Ошибка ввода числа! Повторите ввод!»;

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

private void buttonCreateArray_Click(object sender, EventArgs e)

{

try

{

n = Convert.ToInt32(textBoxN.Text);

mas = new double[n];

labelInvite.Text = INVITE;

labelItem.Text = ITEMB + «0″ + ITEME;

labelResult.Text = EMPTY;

textBoxItem.ReadOnly = false;

listBox1.Items.Clear();

comboBox1.Items.Clear();

checkedListBox1.Items.Clear();

comboBox1.Items.Clear();

currentindex = 0;

}

catch (Exception)

{

labelResult.Text = SIZE;

}

}

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

private void buttonAddItem_Click(object sender, EventArgs e)

{

//Заполнение массива элементами

if (GetItem())

{

mas[currentindex] = ditem;

listBox1.Items.Add(mas[currentindex]);

checkedListBox1.Items.Add(mas[currentindex]);

comboBox1.Items.Add(mas[currentindex]);

currentindex++;

labelItem.Text = ITEMB + currentindex + ITEME;

textBoxItem.Text = «»;

labelResult.Text = OK;

if (currentindex == n)

{

labelInvite.Text = «»;

labelItem.Text = «»;

labelResult.Text = FULL;

textBoxItem.Text = «»;

textBoxItem.ReadOnly = true;

}

}

}

Функция GetItem вводит значение очередного элемента. Если пользователь корректно задал его значение, то элемент добавляется в массив, а заодно и в списки, отображающие текущее состояние массива. Создается подсказка для ввода следующего элемента массива, а если массив полностью определен, то форма переходит в состояние окончания ввода.

/// <summary>

/// Ввод с контролем текущего элемента массива

/// </summary>

/// <returns>true в случае корректного ввода значения</returns>

bool GetItem()

{

string item = textBoxItem.Text;

bool res = false;

if (item == «»)

labelResult.Text = INVITE;

else

{

try

{

ditem = Convert.ToDouble(item);

res = true;

}

catch(Exception)

{

labelResult.Text = ERR;

}

}

return res;

}

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

Организация ввода-вывода двумерных массивов

Ввод двумерного массива немногим отличается от ввода одномерного массива. Сложнее обстоит дело с выводом двумерного массива, если  при выводе пытаться отобразить структуру массива. К сожалению все три элемента управления, хорошо справляющиеся с отображением одномерного массива, плохо приспособлены для показа структуры двумерного массива. Хотя у того же элемента ListBox есть свойство MultiColumn, включение которого позволяет показывать массив в виде строк и столбцов, но это не вполне то, что нужно для наших целей – отображения структуры двумерного массива. Хотелось бы, чтобы элемент имел такие свойства, как Rows и Columns, а их у элемента ListBox нет. Нет их и у элементов ComboBox и CheckedListBox. Приходится обходиться тем, что есть.  На рис. 6_5 показан пример формы, поддерживающей работу по вводу и выводу двумерного массива.

Рис. 6_5 Форма, поддерживающая ввод и вывод двумерного массива

Интерфейс формы схож с тем, что использовался для организации работы с одномерным массивом. Схожа и программная организация ввода-вывода элементов массива. Поэтому я не буду приводить код, поддерживающий работу с формой TwoDimArrayForm, надеясь, что читатель при желании сможет его восстановить. Остановлюсь лишь на одном моменте, позволяющем отображать двумерный массив в элементе управления ListBox так, чтобы сохранялась структура строк и столбцов массива. Этого можно добиться за счет программной настройки размеров элемента управления ListBox:

listBox1.Height = n * HEIGHT_LINE;

listBox1.Width = m * 2 * HEIGHT_LINE;

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

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

Элемент управления DataGridView и отображение массивов

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

Рассмотрим классическую задачу умножения прямоугольных матриц C=A*B.             Построим интерфейс, позволяющий пользователю задавать размеры перемножаемых матриц, вводить данные для исходных матриц A и B, перемножать матрицы и видеть результаты этой операции.  На рис. 5 показан возможный вид формы, поддерживающей работу пользователя. Форма показана в тот момент, когда пользователь уже задал размеры и значения исходных матриц, выполнил умножение матриц и получил результат.

Рис. 5 Форма с элементами             DataGridView, поддерживающая работу с матрицами

На форме расположены три текстовых окна для задания размеров матриц, три элемента DataGridView для отображения матриц, три командные кнопки для выполнения операций, доступных пользователю. Кроме того, на форме присутствуют 9 меток (элементов управления label), семь из которых видимы на рис. 5. В них отображается информация, связанная с формой и отдельными элементами управления. Текст у невидимых на рисунке меток появляется тогда, когда обнаруживается, что пользователь некорректно задал значение какого-либо элемента исходных матриц.

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

//поля класса Form

int m, n, p;    //размеры матриц

double[,] A, B, C;  //сами матрицы

Рассмотрим теперь, как выглядит обработчик события «Click» командной кнопки «Создать DataGridView». Предполагается, что пользователь разумен и, прежде чем нажать эту кнопку, задает размеры матриц в соответствующих текстовых окнах. Напомню, что при перемножении матриц размеры матриц должны быть согласованы – число столбцов первого сомножителя должно совпадать с числом строк второго сомножителя, а размеры результирующей матрицы определяются размерами сомножителей. Поэтому для трех матриц в данном случае достаточно задать не шесть, а три параметра, определяющих размеры.

Обработчик события выполняет три задачи – создает сами матрицы, осуществляет чистку элементов управления DataGridView, удаляя предыдущее состояние, затем добавляет столбцы и строки в эти элементы в полном соответствии с заданными размерами матриц. Вот текст обработчика:

private void button1_Click(object sender, EventArgs e)

{

//создание матриц

m = Convert.ToInt32(textBox1.Text);

n = Convert.ToInt32(textBox2.Text);

p = Convert.ToInt32(textBox3.Text);

A = new double[m, n];

B = new double[n, p];

C = new double[m, p];

//Чистка DGView, если они не пусты

int k =0;

k = dataGridView1.ColumnCount;

if (k != 0)

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

dataGridView1.Columns.RemoveAt(0);

dataGridView2.Columns.Clear();

dataGridView3.Columns.Clear();

//Заполнение DGView столбцами

AddColumns(n, dataGridView1);

AddColumns(p, dataGridView2);

AddColumns(p, dataGridView3);

//Заполнение DGView строками

AddRows(m, dataGridView1);

AddRows(n, dataGridView2);

AddRows(m, dataGridView3);

}

Прокомментирую этот текст:

  • Прием размеров и создание матриц, надеюсь, не требует дополнительных комментариев;
  • Чистка предыдущего состояния элементов DataGridView сводится к удалению столбцов. Продемонстрированы два возможных способа выполнения этой операции. Для первого элемента показано, как можно работать с коллекцией столбцов. Организуется цикл по числу столбцов коллекции и в цикле выполняется метод RemoveAt, аргументом которого является индекс удаляемого столбца. Поскольку после удаления столбца происходит перенумерация столбцов, то на каждом шаге цикла удаляется первый столбец, индекс которого всегда равен нулю. Удаление столбцов коллекции можно выполнить одним махом, — вызывая метод Clear() коллекции, что и делается для остальных двух элементов DataGridView;
  • После чистки предыдущего состояния, можно задать новую конфигурацию элемента, добавив в него вначале нужное количество столбцов, а затем и строк. Эти задачи выполняют специально написанные процедуры AddColumns и AddRows. Вот их текст:

private void AddColumns(int n, DataGridView dgw)

{

//добавляет n столбцов в элемент управления dgw

//Заполнение DGView столбцами

DataGridViewColumn column;

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

{

column = new DataGridViewTextBoxColumn();

column.DataPropertyName = «Column» + i.ToString();

column.Name = «Column» + i.ToString();

dgw.Columns.Add(column);

}

}

private void AddRows(int m, DataGridView dgw)

{

//добавляет m строк в элемент управления dgw

//Заполнение DGView строками

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

{

dgw.Rows.Add();

dgw.Rows[i].HeaderCell.Value

= «row» + i.ToString();

}

}

Приведу краткий комментарий:

  • Создаются столбцы в коллекции Columns по одному.  В цикле по числу столбцов матрицы, которую должен отображать элемент управления DataGridView, вызывается метод Add этой коллекции, создающий очередной столбец. Одновременно в этом же цикле создается и имя столбца (свойство Name), отображаемое в форме. Показана возможность формирования еще одного имени (DataPropertyName), используемого при связывании со столбцом таблицы внешнего источника данных. В нашем примере это имя не используется.
  • Создав столбцы, нужно создать  еще и нужное количество строк у каждого из элементов DataGridView. Делается это аналогичным образом, вызывая метод Add коллекции Rows. Чуть по-другому задаются имена строк, — для этого используется специальный объект HeaderCell, имеющийся у каждой строки и задающий ячейку заголовка.
    • После того как сформированы строки и столбцы, элемент DataGridView готов к тому, чтобы пользователь или программа вводила значения в ячейки сформированной таблицы.

Рассмотрим теперь, как выглядит обработчик события «Click» следующей командной кнопки «Перенести данные в массив». Предполагается, что пользователь разумен и, прежде чем нажать эту кнопку, задает значения элементов перемножаемых матриц в соответствующих ячейках подготовленных таблиц первых двух элементов DataGridView. Обработчик события выполняет следующие задачи – в цикле читает элементы, записанные пользователем в таблицы DataGridView, проверяет их корректность и в случае успеха переписывает их  в матрицы. Вот текст обработчика:

private void button2_Click(object sender, EventArgs e)

{

string elem = «»;

bool correct = true;

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

for (int j = 0; j < n; j++)

{

try

{

elem=dataGridView1.Rows[i].Cells[j].Value.ToString();

A[i, j] = Convert.ToDouble(elem);

label8.Text = «»;

}

catch (Exception any)

{

label8.Text = «Значение элемента» +

«A[" + i.ToString() +", " + j.ToString() + " ]»

+ » не корректно. Повторите ввод!»;

dataGridView1.Rows[i].Cells[j].Selected= true;

return;

}

}

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

for (int j = 0; j < p; j++)

{

do

{

correct = true;

try

{

elem =

dataGridView2.Rows[i].Cells[j].Value.ToString();

B[i, j] = Convert.ToDouble(elem);

label9.Text = «»;

}

catch (Exception any)

{

label9.Text = «Значение элемента» +

«B[" + i.ToString() + ", " + j.ToString() + "]»

+ » не корректно. Повторите ввод!»;

dataGridView2.Rows[i].Cells[j].Selected=true;

Form3 frm = new Form3();

frm.label1.Text =

«B[" + i.ToString() + "," + j.ToString() + "]= «;

frm.ShowDialog();

dataGridView2.Rows[i].Cells[j].Value =

frm.textBox1.Text;

correct = false;

}

} while (!correct);

}

}

Этот программный код нуждается в подробных комментариях:

  • Основная задача переноса данных из таблицы элемента DataGridView в соответствующий массив не вызывает проблем. Конструкция Rows[i].Cells[j] позволяет добраться до нужного элемента таблицы, после чего остается присвоить его значение элементу массива.
  • Как всегда при вводе основной проблемой является обеспечение корректности вводимых данных. Схема, рассматриваемая нами ранее, нуждается в корректировке. Дело в том, что ранее проверка корректности осуществлялась сразу же после ввода пользователем значения элемента. Теперь проверка корректности выполняется, после того как пользователь полностью заполнил таблицы, при этом некоторые элементы он мог задать некорректно. Просматривая таблицу, необходимо обнаружить некорректно заданные значения и предоставить возможность их исправления. В программе предлагаются два различных подхода к решению этой проблемы.
  • Первый подход демонстрируется на примере ввода элементов матрицы A. Как обычно, преобразование данных, введенных пользователем, в значение, допустимое для элементов матрицы А, помещается в охраняемый блок. Если данные некорректны и возникает исключительная ситуация, то она перехватывается универсальным обработчиком catch(Exception). Заметьте, в данном варианте нет цикла, работающего до тех пор, пока не будет введено корректное значение.  Обработчик исключения просто прерывает работу по переносу данных, вызывая оператор return. Но предварительно он формирует информационное сообщение об ошибке и выводит его в форму. (Помните, специально для этих целей у формы были заготовлены две метки). В сообщении пользователю предлагается исправить некорректно заданный элемент и повторить ввод – повторно нажать командную кнопку «перенести данные в массив». Этот подход понятен и легко реализуем. Недостатком является его неэффективность, поскольку повторно будут переноситься в массив все элементы, в том числе и те, что были введены вполне корректно. У программиста такая ситуация может вызывать чувство неудовлетворенности своей работой.
  • На примере ввода элементов матрицы В продемонстрируем другой подход, когда исправляется только некорректно заданное значение. Прежде, чем читать дальше, попробуйте найти собственное решение этой задачи. Это оказывается не так просто, как может показаться с первого взгляда. Для организации диалога с пользователем пришлось организовать специальное диалоговое окно, представляющее обычную форму с двумя элементами управления – меткой для выдачи информационного сообщения и текстовым окном для  ввода пользователем корректного значения. При обнаружении ошибки ввода открывается диалоговое окно, в которое пользователь вводит корректное значение элемента и закрывает окно диалога. Введенное пользователем значение переносится в нужную ячейку таблицы DataGridView, а оттуда в матрицу.
  • При проектировании диалогового окна значение свойства формы FormBorderStyle, установленное по умолчанию как «sizeable» следует заменить значением «FixedDialog», что влияет на внешний вид и поведение формы. Важно отметить, что форма, представляющее диалоговое окно, должна вызываться не методом Show, а методом ShowDialog. Иначе произойдет зацикливание, начнут порождаться десятки диалоговых окон, прежде чем успеете нажать спасительную в таких случаях комбинацию Ctrl+ Alt + Del.

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

Рис. 6 Информационное сообщение о некорректных значенях матрицы А

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

На рис. 7 показана ситуация, когда некорректно заданное значение исправляется в открывшемся окне диалога.

Рис.7   Диалоговое окно для корректировки значений элементов матрицы В 

Обработчик события «Click» командной кнопки «Умножить матрицы» выполняет ответственные задачи – реализует умножение матриц и отображает полученный результат в таблице соответствующего элемента DataGridView. Но оба эти действия выполняются естественным образом, не требуя кроме циклов никаких специальных средств и программистских ухищрений. Я приведу программный код без дополнительных комментариев:

private void button3_Click(object sender, EventArgs e)

{

MultMatr(A, B, C);

FillDG();

}

void MultMatr(double[,] A, double[,] B, double[,] C)

{

int m = A.GetLength(0);

int n = A.GetLength(1);

int p = B.GetLength(1);

double S =0;

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

for (int j = 0; j < p; j++)

{

S = 0;

for (int k = 0; k < n; k++)

S += A[i, k] * B[k, j];

C[i, j] = S;

}

}

void FillDG()

{

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

for (int j = 0; j < p; j++)

dataGridView3.Rows[i].Cells[j].Value

= C[i, j].ToString();

}

Задачи (ввод, вывод и другие простые задачи с массивами)

2.1     Организуйте в консольном приложении ввод и вывод одномерного массива строкового типа.

2.2     Организуйте в Windows приложении ввод и вывод одномерного массива строкового типа.

2.3     Организуйте в консольном приложении ввод массива «Сотрудники», содержащего фамилии сотрудников. Введите массив «Заявка», элементы которого содержат фамилии сотрудников и, следовательно, должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных.

2.4     Организуйте в Windows приложении ввод массива «Сотрудники», содержащего фамилии сотрудников. Введите массив «Заявка», элементы которого содержат фамилии сотрудников и, следовательно, должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных.

2.5     Организуйте в Windows приложении ввод массива «Сотрудники», содержащего фамилии сотрудников. Создайте массив «Заявка», элементы которого должны содержаться в массиве сотрудников. Для создания массива «Заявка» постройте форму «Два списка», содержащую два элемента ListBox, источником данных для первого из них служит массив «Сотрудники». Пользователь переносит данные из первого списка во второй, формируя данные для массива «Заявка». После формирования данные переносятся в массив. Для построения формы используйте шаблон, описанный в лекции 24 учебника.

2.6     Организуйте в консольном приложении ввод и вывод двумерного массива строкового типа.

2.7     Организуйте в Windows приложении ввод и вывод двумерного массива строкового типа.

2.8     Организуйте в консольном приложении ввод массива «Сотрудники» из двух столбцов, содержащего фамилии и имена сотрудников. Введите массив «Заявка» той же структуры, элементы которого должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных. Организуйте вывод обоих массивов.

2.9     Организуйте в Windows приложении ввод массива «Сотрудники» из двух столбцов, содержащего фамилии и имена сотрудников. Введите массив «Заявка» той же структуры, элементы которого должны содержаться в массиве сотрудников. Обеспечьте контроль корректности ввода данных. Организуйте вывод обоих массивов.

2.10  (*) Организуйте в консольном приложении ввод и вывод массива «Машины», содержащего 4 столбца: «Владелец», «Марка», «Номер», «Год Выпуска». При вводе данных обеспечьте их корректность. Поле «Владелец» должно быть строкой в формате «фамилия имя», где фамилия и имя должны начинаться с большой буквы и состоять из букв алфавита кириллицы, включая дефис. Номер машины должен соответствовать формату, принятому для номеров машин. При выводе сохраняйте структуру массива.

2.11  (*) Организуйте в Windows приложении ввод и вывод массива «Машины», содержащего 4 столбца: «Владелец», «Марка», «Номер», «Год Выпуска». При вводе данных обеспечьте их корректность. Поле «Владелец» должно быть строкой в формате «фамилия имя», где фамилия и имя должны начинаться с большой буквы и состоять из букв алфавита кириллицы, включая дефис. Номер машины должен соответствовать формату, принятому для номеров машин.  При выводе сохраняйте структуру массива.

2.12  (*) В консольном приложении уже построен массив «Машины» (см. задача 3.9) . Построить массив «Цветные машины», в котором к столбцам массива «Машины» добавляется 5-й столбец «Цвет». Организуйте диалог с пользователем,  выясняя цвет для каждой машины из массива «Машины».

2.13    (*) В Windows приложении уже построен массив «Машины» (см. задача 3.10) . Построить массив «Цветные машины», в котором к столбцам массива «Машины» добавляется 5-й столбец «Цвет». Организуйте диалог с пользователем,  выясняя цвет для каждой машины из массива «Машины».

2.14     Организуйте в консольном приложении ввод и вывод одномерного массива арифметического типа (от byte до double).

2.15  Организуйте в Windows приложении ввод и вывод одномерного массива арифметического типа (от byte до double).

2.16  Организуйте в консольном приложении ввод массива «Сотрудники», содержащего фамилии сотрудников, и массива «Зарплата». Обеспечьте контроль корректности ввода данных о зарплате, проверяя диапазон возможных значений.

2.17  Организуйте в Windows приложении ввод массива «Сотрудники», содержащего фамилии сотрудников, и массива «Зарплата». Обеспечьте контроль корректности ввода данных о зарплате, проверяя диапазон возможных значений.

2.18  Организуйте в консольном приложении ввод и вывод матрицы — двумерного массива арифметического типа.

2.19  Организуйте в Windows приложении ввод и вывод матрицы — двумерного массива арифметического типа.

2.20  Организуйте в консольном приложении ввод массива декартовых координат n точек на плоскости. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

2.21  Организуйте в Windows приложении ввод массива декартовых координат n точек на плоскости. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

2.22  Организуйте в консольном приложении ввод массива полярных координат n точек на плоскости. Вычислите массив декартовых координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

2.23  Организуйте в Windows приложении ввод массива полярных координат n точек на плоскости. Вычислите массив декартовых координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

2.24  Организуйте в консольном приложении ввод массива декартовых координат n точек в трехмерном пространстве. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

2.25  Организуйте в Windows приложении ввод массива декартовых координат n точек в трехмерном пространстве. Вычислите массив полярных координат этих точек и организуйте вывод этого массива. Обеспечьте контроль вводимых значений.

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

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

Массивы и классические алгоритмы математики

Полиномы

Полиномом n-й степени Pn(x) называют функцию:

(1)

Если рассматривать график этой функции на плоскости, то x и Pn(x) – это декартовы координаты точек графика функции. Значения ak (k из интервала [0,n]) называются коэффициентами полинома. Все они принадлежат одному типу и при программной работе с полиномами представляются одномерным массивом с n+1 элементами.

Если задан массив коэффициентов полинома A, то вычислить значение полинома в точке x не представляет особой сложности. Но ни один уважающий себя программист не позволит себе вычислять значение полинома, буквально пользуясь схемой (1), требующей n-1 операций возведения в степень, n операций умножения и n операций сложения. Прекрасный пример того, как можно упростить алгоритм, дает схема Горнера, вообще не требующая возведения в степень. В этой схеме полином Pn(x) представляют в виде:

(2)

Удобнее представлять схему Горнера в рекуррентной форме:

 

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

Если Pn(x) – полином n-й степени с коэффициентами ai, Qn(x) – полином n-й степени с коэффициентами bi и Pn(x) = Qn(x), то из этого следует равенство соответствующих коэффициентов:

(3)

Многие задачи над полиномами связаны с определением их корней. Напомню, x0 является корнем полинома, если Pn(x0) = 0. У полинома n-й степени не более чем n действительных корней. Если n – нечетно, то полином имеет хотя бы один действительный корень. Все корни полинома принадлежат некоторому конечному интервалу [c, d]. Вне этого интервала поведение полинома определяется его старшим членом – anxn. Для полинома четной степени обе ветви уходят в +∞, если an>0 и в -∞, если an<0. Для полинома нечетной степени ветви полинома вне интервала [c, d] разнонаправлены. Если an>0, то правая ветвь уходит в +∞, а левая ветвь — в -∞. Если an<0, то левая ветвь уходит в +∞, а правая ветвь в -∞.

Когда по каким-либо физическим соображениям интервал [c, d] известен хотя бы приблизительно, то задача нахождения корней полинома облегчается, в противном случае она может быть довольно трудной, особенно для случая близко расположенных корней.

Исследование интервала

Рассмотрим один из простых алгоритмов, исследующих существует ли на заданном интервале [e, f] хотя бы один корень. Один корень заведомо существует, если полином на концах исследуемого интервала имеет разные знаки или один из концов интервала уже является корнем полинома. Это условие и будет характерным признаком поиска нужного интервала. Если исходный интервал [e, f] удовлетворяет характерному признаку, то задача решена и такой интервал найден. В противном случае в цикле по k вычислим h = L/2k, где L – длина исходного интервала (L= f-e). Затем организуем внутренний цикл, в котором проверим характерный признак на всех интервалах длины h. Если интервал будет найден, то вычисления завершаются, в противном случае переходим к следующему шагу цикла по k, производя очередное дробление h. Завершение цикла по k означает, что если исследуемый интервал [e, f] и содержит корни, то это близкие пары корней, отстоящие друг от друга на расстояние, меньшее h – заключительной длины интервала по завершении цикла по k.

Приведу несколько практических рекомендаций, полезных при реализации этой схемы. Внутренний цикл следует организовать так, чтобы не повторять вычисление полинома в тех точках, в которых это вычисление проводилось на предыдущих шагах цикла. Это означает, что когда шаг h = L/2k, то во внутреннем цикле достаточно вычислить значение полинома не более чем в 2k-1 точках. Внешний цикл достаточно ограничить числом в интервале от 10 до 20, поскольку уже при k=10 величина исходного интервала L уменьшится более чем в 1000 раз, что вполне достаточно в большинстве практических ситуаций. Хотя следует помнить, что в ряде ситуаций практики приходится иметь дело с резко осциллирующими функциями, где близкие корни являются правилом, а не исключением.

Алгоритмы нахождения корня полинома

Рассмотрим несколько простых схем нахождения корня полинома. Заметим, что все эти схемы применимы к нахождению корней любых функций, а не только полиномов. Как всегда в программировании речь идет не столько о точном нахождении корня, сколько о нахождении корня с заданной точностью ε. Так что, если x0 – это точное значение корня, то нам достаточно найти x* — такое что |x0 – x*| < ε.

Схема дихотомии отрезка (деление пополам):

Эта схема прекрасно подходит, когда предварительно проведено исследование интервала существования корня и найден такой интервал [e, f], на концах которого полином принимает разные знаки, так что существует корень внутри интервала. Если исходный интервал мал и сравним с заданной точностью ε, то в качестве корня можно выбрать середину этого интервала. Если же исходный интервал больше, чем значение ε, то интервал можно разделить пополам и из двух половинок выбрать ту, для которой выполняется характерный признак существования корня. Понятно, что если признак выполняется для всего интервала, то он обязательно будет выполняться для одной из его половинок. Деление отрезка пополам приводит к быстрому уменьшению длины отрезка, так что 10 — 20 делений достаточно, чтобы найти интервал длины, меньшей ε, а следовательно и корень полинома с заданной точностью.

Метод простой итерации:

Формально метод применим и в том случае, когда неизвестен интервал, в котором существует корень функции. Пусть x0 – некоторое заданное начальное приближение к корню полинома. Тогда можно построить следующий итерационный процесс:

 

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

Метод простой итерации обладает полезным свойством «неподвижной точки». Корни функции являются «неподвижными точками» метода. Нетрудно заметить, что если на некотором шаге xk-1 сошлось к  корню полинома x*, то xkи все последующие итерации будут равны x*, так что итерационный процесс из найденного корня не уходит.

Метод Ньютона

Этот метод чуть более сложен в реализации, но обладает лучшей сходимостью в сравнении с методом простой итерации, хотя и здесь сходимость во многом зависит от удачного выбора начального приближения x0. Для произвольной функции f итерационный процесс метода Ньютона выглядит так:

 

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

Понижение степени полинома

Если для полинома P(x) n-й степени найден корень x1, то можно понизить степень полинома, построив полином P1(x) степени n-1, у которого все корни совпадают с корнями полинома P(x) за исключением того, что у него нет корня x1.

Запишем соотношение, связывающее полиномы:

 

Учитывая соотношение (3) о равенстве двух полиномов одной степени, можно выписать n+1 соотношение, связывающее коэффициенты этих полиномов. Эти соотношения нетрудно разрешить относительно неизвестных коэффициентов bk. В результате получим:

(4)

Заметьте, неизвестных всего n,  а уравнений можно построить – n+1. Но последнее уравнение (a0 + b0x1= 0) является следствием предыдущих и используется для контроля вычислений.

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

Нахождение коэффициентов полинома по его корням

До сих пор рассматривалась задача отыскания корней полинома с заданными коэффициентами. Иногда приходится решать обратную задачу – найти коэффициенты полинома, если известны его корни – x1, x2, … xn. Полиномов с одинаковыми корнями существует бесчисленное множество. Однако среди них существует единственный полином с коэффициентом an, равным единице. Этот полином называется приведенным, его то и будем строить. Все остальные полиномы получаются из приведенного полинома умножением всех коэффициентов на произвольное число an, от которого требуется лишь, чтобы оно не было равно нулю. Поэтому для однозначного решения задачи требуется задать n корней и коэффициент при старшем члене полинома. Тогда можно записать следующее равенство:

 

Для нахождения коэффициентов полинома Pn(x) воспользуемся, как обычно соотношением (3). Но применить его напрямую сложно. Поэтому воспользуемся процессом, обратным к процессу понижения степени. Построим вначале P1(x) — полином первой степени, у которого x1 является единственным корнем. Затем повысим степень и построим полином второй степени – P2(x),  у которого появляется еще один корень – x2. Продолжая этот процесс, дойдем до искомого полинома Pn(x). При вычислении коэффициентов нового полинома будем использовать коэффициенты уже посчитанного полинома на единицу меньшей степени. Получающееся в результате соотношения близки к тому, что приведены для случая понижения степени полинома.

Коэффициенты полинома первой степени P1(x) выписываются явно:

 

Коэффициенты полинома k-й степени вычисляются через коэффициенты полинома степени k-1:

 

Переходя к коэффициентам, получим следующие уравнения:

(5)

В соотношении (5) через a’ обозначены коэффициенты полинома степени k-1. На самом деле схема безопасна и позволяет считать коэффициенты на том же месте, не требуя дополнительной памяти. Приведу алгоритм вычисления коэффициентов полинома по его корням в виде схемы, приближенной к языку C#.

Дано:

an – коэффициент при старшем члене полинома Pn(x);

n – степень полинома;

x – массив корней полинома (x[0], x[1], …x[n]);

Вычислить:

Массив a – массив коэффициентов полинома (a[0], a[1], …a[n]).

//Вычисляем коэффициенты полинома первой степени

a[1]= 1; a[0] = -x[0];

//цикл по числу полиномов

for(int k=2;k<=n; k++)

{

//Вычисляем коэффициенты полинома степени k

//Вначале старший коэффициент

a[k]= a[k-1];

//затем остальные коэффициенты, кроме последнего

for(int i=k-1;i>0; i—)

{

a[i] = a[i-1]- a[i]*x[k-1];

}

//теперь младший коэффициент

a[0]= -a[0]*x[k-1];

}

//Последний этап – умножение коэффициентов на an

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

a[i] = a[i]*an;

Полином Лагранжа

Пусть на плоскости заданы n+1 точка: R0(x0, y0), R1(x1, y1), R2(x2, y2),…, Rn(xn, yn). Полиномом Лагранжа PL(x) называется полином n-й степени, проходящий через все точки Rk. Если точки Rk не образуют возвратов, то такой полином существует и является единственным. Под возвратом понимается ситуация, когда существуют две точки Ri и Rj такие, что xi = xj.

Как построить такой полином? Лагранж предложил следующий алгоритм. Полином PL(x) строится как сумма n+1 полиномов n-й степени:

 

Каждый из полиномов Pk(x), входящих в сумму, строится следующим образом. Корнями полинома Pk(x) являются все точки Ri за исключением точки Rk. Единственность Pk(x) обеспечивается за счет того, что коэффициент при старшем члене an подбирается так, чтобы полином проходил через точку Rk.  В записи Лагранжа полином Pk(x) выглядит следующим образом:

(6)

 

В записи (6) в числителе находится приведенный полином, построенный по корням, а yk, деленное на знаменатель в формуле (6), задает an – старший коэффициент полинома.

Условия, накладываемые на полиномы Pk(x), обеспечивают выполнение требований к полиному Лагранжа – сумма полиномов Pk(x) будет полиномом, проходящим через все заданные точки.

Поскольку алгоритм построения приведенного полинома по его корням уже разобран, то схема построения полинома Лагранжа можно выглядеть так:

//Полином Лагранжа определяется как сумма из n+1

//полиномов Pk, для которых известны корни.

for(int k=0; k<=n; k++)

{

//Задание корней для полинома Pk

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

roots[i] = X[i];

for(int i =k+1; i<=n; i++)

roots[i-1] = X[i];

//Вычисление коэффициентов приведенного полинома по его корням

coefk = CalcCoefFromRoots(roots);

//вычисление An — старшего коэффициента полинома.

An = Y[k] / HornerP(coefk,X[k]);

//Добавление очередного полинома Pk к PL — сумме полиномов

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

{

coefL[i]= coefL[i]+An*coefk[i];

}

}

В этой схеме:

X и Y – массивы, задающие декартовы координаты точек, через которые проходит полином Лагранжа,

n – степень полинома,

roots – массив корней приведенного полинома Pk,

coefk — массив его коэффициентов,

An – старший коэффициент полинома, вычисляемый из условия прохождения полинома Pk через точку с координатами X[k], Y[k],

coefL —  массив коэффициентов полинома Лагранжа,

HornerP – метод, вычисляющий по схеме Горнера значение полинома по его коэффициентам и значению координаты x,

CalcCoefFromRoots – метод, вычисляющий массив коэффициентов приведенного полинома по его корням.

Сложение и умножение полиномов

При рассмотрении полинома Лагранжа возникала необходимость в нахождении суммы полиномов одинаковой степени, заданных своими коэффициентами. Пусть P(x) и Q(x) – полиномы степени n и m соответственно, заданные своими коэффициентами, и пусть для определенности n >= m. Тогда суммой полиномов называется полином R(x) степени n, коэффициенты которого вычисляются следующим образом:

 

Пусть полиномы P(x) и Q(x) заданы, подобно полиному Лагранжа, точками, через которые они проходят:

 

Тогда нетрудно найти подобное представление и для полинома R(x), представляющего сумму полиномов:

 

В этом случае понадобится вычислить значения полинома Q(x) в n точках.

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

Рассмотрим теперь операцию умножения полиномов:

 

Нетрудно понять, что полином S(x) является полиномом степени n+m и имеет n+m+1 коэффициент. Как вычисляется произведение, если заданы полиномы сомножители P(x) и Q(x)? Замечу, что произведение полиномов часто встречается на практике и имеет специальное имя – свертка полиномов.

В отличие от сложения полиномов проще всего найти свертку, если заданы корни обоих полиномов. В этом случае никаких вычислений не требуется, поскольку n корней P(x) и m корней Q(x)  будут n+m корнями S(x). Если у полиномов P(x) и Q(x) есть совпадающие корни, то у S(x) появятся кратные корни.

Если исходные полиномы P(x) и Q(x) заданы своими точками, то нетрудно получить набор точек для полинома произведения. Схема во многом похожа на ту, что имеет место при сложении полиномов, заданных точками:

 

Для получения множества точек, задающих представление полинома S(x), приходится вычислять значение полинома Q(x) в n точках и значение полинома P(x) в m точках,  а затем выполнять соответствующее умножение значений двух полиномов.

Если исходные полиномы P(x) и Q(x) заданы своими коэффициентами, то имеем:

 

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

 

Суммирование идет по всем наборам k и r, дающим в сумме значение i. Понятно, что для крайних значений (i=0 и i=n+m) сумма состоит из одного члена, поскольку подобные члены для x в нулевой степени  и степени n+m отсутствуют. Число членов суммирования увеличивается при приближении к середине интервала [0, n+m].

Итоги

Подводя некоторые итоги, отметим, что полином можно задать тремя разными способами – его коэффициентами, корнями, точками, через которые проходит полином. Если заданы коэффициенты полинома, то за время, пропорциональное n2, (T(n) = O(n2)) можно вычислить значения полинома в n+1 точках. Для вычисления значения полинома в одной точке применяется схема Горнера, выполняющая вычисления за линейное (пропорциональное n) время. Существует и обратное преобразование. Если заданы n+1 точки, через которые проходит полином, то алгоритм Лагранжа позволяет за время O(n2) вычислить коэффициенты полинома. Задача получения коэффициентов полинома по точкам называется задачей интерполяции, а полином Лагранжа называется интерполяционным полиномом.

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

Задание полинома его корнями является наиболее информативным. Если известны корни, то без труда выполняется свертка полиномов. Вычисление значения полинома в заданной точке, выполняется за n умножений, не требуя применения схемы Горнера. Несколько сложнее выполняется операция сложения полиномов. К сожалению, на практике редко встречается ситуация, когда известны корни полинома, но такое бывает – алгоритм Лагранжа тому пример.

Когда полиномы заданы своими коэффициентами, то вычисление значения полинома в заданной точке выполняется по схеме Горнера за линейное время. Сложение полиномов также является легкой операцией и выполняется за линейное время. Свертку полиномов в этом случае выполнить сложнее. Рассмотренный нами алгоритм требует уже квадратичного времени.

На практике полиномы чаще всего появляются при задании множества точек. Ситуация обычна такова. В результате экспериментов измеряются значения некоторой функции в ряде точек. Требуется предсказать, каково будет значение этой функции в других точках, в которых измерения не проводились. Если из теоретических соображений не известен вид функции, то чаще всего ее задают в виде полинома, проходящего через точки, полученные экспериментальным путем. В этой постановке задачу построения полинома и вычисления значений полинома в точках, не подлежащих измерениям, называют задачей интерполяции, а полином Лагранжа называют интерполяционным полиномом.  Задача интерполяции корректно решается, когда новые точки, в которых проводятся вычисления, лежат внутри интервала, заданного измеренными точками. Полиномы плохо приспособлены для решения задачи экстраполяции, когда точки лежат вне интервала измерений, из-за быстрого роста значения полинома вне этого интервала. Чем выше степень полинома, тем быстрее его рост.

 

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

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

Задачи

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

2.28  Полином P(x) задан своими коэффициентами. Дан массив координат X. Вычислить, используя схему Горнера, массив значений полинома в точках xi.

2.29   Полином P(x) задан своими корнями и старшим коэффициентом an. Дан массив координат X. Вычислить массив значений полинома в точках xi.

2.30  (задача интерполяции) Полином P(x) задан координатами n+1 точек, через которые он проходит. Дан массив координат X. Вычислить массив значений полинома в точках xi.

2.31  Полином P(x) задан своими корнями и старшим коэффициентом an. Вычислить коэффициенты полинома.

2.32  (задача построения интерполяционного полинома Лагранжа) Полином P(x) задан координатами n+1 точек, через которые он проходит. Вычислить коэффициенты полинома.

2.33  Полином P(x) задан своими коэффициентами. Дан массив чисел X. Построить полином Q(X), имеющий своими корнями числа из массива X и корни полинома P(x).

2.34   Полином P(x) задан своими коэффициентами. Для полинома известны два его корня – x0 и xn. Построить полином Q(x), корни которого совпадают с корнями полинома P(x) за исключением корней x0 и xn.

2.35  Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

2.36  Полиномы P(x) и Q(x) заданы своими корнями и старшими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

2.37  Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

2.38  Полиномы P(x) и Q(x) заданы своими коэффициентами. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

2.39  Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты суммы полиномов P(x) и Q(x).

2.40  Полиномы P(x) и Q(x) заданы точками, через которые они проходят. Вычислить коэффициенты произведения полиномов P(x) и Q(x).

2.41  Полином P(x) задан своими коэффициентами. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.

2.42  Полином P(x) задан точками, через которые он проходит. Определить интервал, если он существует, на котором полином имеет хотя бы один корень.

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

2.44  Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить схему исследования интервала и дихотомии.

2.45  Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод простой итерации.

2.46  Построить интерфейс пользователя, позволяющий ему находить корни полинома. В основу поиска положить метод Ньютона.

Проект

2.47  Построить проект, включающий построение класса Polinom и интерфейс пользователя. Методы класса должны реализовать все алгоритмы, рассмотренные в этом разделе. Интерфейс пользователя должен позволять пользователю решать основные задачи, возникающие при работе с полиномами.

Алгоритмы линейной алгебры

Матрицей называется набор чисел, состоящий из m строк и n столбцов. Для программиста матрица – это двумерный массив. Матрица называется квадратной, если m = n и прямоугольной в противном случае. Числа m и n определяют размерность матрицы. Над прямоугольными матрицами определены  операции транспонирования, сложения, умножения.

Пусть A – матрица размерности m*n (из m строк и n столбцов) с элементами ai,j. Транспонированной матрицей B = AT называют матрицу размерности n*m, элементы которой bi,j = aj,i. В транспонированной матрице строки исходной матрицы становятся столбцами.

 

Операция сложения определена над прямоугольными матрицами одинаковой размерности. Пусть A, B, C – прямоугольные матрицы размерности m*n. Тогда  сумма матриц определяется естественным образом:

 

Операция умножения определена над прямоугольными матрицами, у которых число столбцов первого сомножителя равно числу строк второго сомножителя. Матрица произведения имеет число строк, равное числу строк первого сомножителя, и число столбцов, равное числу столбцов второго сомножителя. Пусть A – матрица размерности m*p, B – размерности p*n, тогда матрица C= A*B имеет размерность m*n. Элементы матрицы произведения определяются как сумма попарных произведений элементов строки первого сомножителя на элементы столбца второго сомножителя.

(7)

Умножение всегда определено для прямой и транспонированной матрицы. Если A – прямоугольная матрица размерности m*n, то всегда определена квадратная матрица B размерности m*m

B = A*AT = BT = (A*AT)T = (AT)T*AT=A*AT

Результатом такого произведения является симметричная матрица. Квадратная матрица называется симметричной, если ai,j = aj,i для всех i и j, или, что тоже, если A = AT. Операции транспонирования, сложения и умножения обладают следующими свойствами:

(AT)T = A;       (A+B)T = AT + BT;     (A*B)T = BT * AT

Квадратные матрицы

Квадратная матрица называется диагональной, если все элементы, кроме диагональных, равны нулю, то есть ai,j = 0 при i /=j.

Квадратная матрица называется единичной, если все элементы, кроме диагональных, равны нулю, а диагональные элементы равны единице, то есть ai,j = 0 при i /=j и ai,j = 1 при i = j. Единичная матрица обозначается обычно буквой E, и она играет роль единицы при умножении матриц, поскольку для любой квадратной матрицы A и единичной матрицы E той же размерности имеют место соотношения:

A*E = E*A = A

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

 

Функция, задающая определитель, обладает рядом важных свойств:

  • Определитель диагональной матрицы равен произведению диагональных элементов. Отсюда следует, что определитель матрицы E равен 1;
  •  Определитель матрицы не меняется при выполнении над матрицей элементарных преобразований. Под элементарной операцией (преобразованием) понимается прибавление к любой строке матрицы линейной комбинации других ее строк. В частности, если к строке матрицы с номером j прибавить строку с номером k (k /= j), умноженную на некоторое число, то определитель матрицы не изменится;
  • Если все элементы одной строки матрицы умножить на некоторое число q, то определитель матрицы изменится в q раз (умножается на q);
  • Если переставить местами строки j и k, то модуль определителя не изменится, но изменится знак, если разность |k-j| является нечетным числом;
  • Определитель произведения матриц равен произведению определителей:
    D(A*B) = D(A)*D(B)

Не приводя общего формального определения,  рассмотрим ниже алгоритм вычисления определителя матрицы, основанный на его свойствах.

Если определитель квадратной матрицы A не равен нулю, то существует обратная матрица, обозначаемая как A-1. Прямая и обратная матрицы связаны соотношением:

A*A-1 = A-1*A = E

Операции транспонирования, умножения и обращения матриц связаны соотношениями:

(AT)-1 = (A-1)T;           (A*B)-1 = B-1*A-1

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

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

 

В круглых скобках для клеток заданы их размерности. Пусть теперь некоторые клетки нулевые, например, таковыми являются клетки D, F и G.  Тогда матрица M2 имеет вид:

 

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

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

 

Системы линейных уравнений

Рассмотрим систему из n линейных уравнений с n неизвестными:

(8)

В матричном виде эта система записывается намного элегантнее:

A*x=b             (9)

Здесь вектор неизвестных x рассматривается как столбец – прямоугольная матрица размерности n*1. Аналогичный вид имеет вектор правых частей b системы уравнений. В матричном виде условие существования решения системы линейных уравнений (8)  и нахождение самого решения формулируется совсем просто. Для существования решения необходимо и достаточно, чтобы определитель матрицы A был отличен от нуля. Тогда у матрицы A существует обратная матрица A-1. Для нахождения решения системы умножим обе части уравнения (9) на A-1. Тогда получим:

A-1*(A*x) = A-1*b        →  (A-1*A)*x = A-1*b         →  (E)*x = A-1*b  →  x = A-1*b            (10)

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

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

A*X = B

задается соотношением:

X = A-1*B

Здесь B – прямоугольная матрица размерности n*m, каждый столбец которой представляет вектор правых частей одной системы уравнений. Соответствующий столбец матрицы X дает решение этой системы. Что произойдет, если в качестве матрицы B рассмотреть единичную матрицу? Очевидно, что тогда матрица X будет представлять собой обратную матрицу A-1. Несмотря на кажущуюся очевидность соотношения A-1 = A-1*E, в нем есть определенный смысл, который постараюсь сейчас прояснить. Три задачи – вычисление определителя, решение системы линейных уравнений, нахождение обратной матрицы – имеют одинаковую вычислительную сложность и требуют, если не применять специальные алгоритмы, выполнения порядка n3 операций умножения и сложения. Если посмотреть на соотношение (10), то кажется, что решить систему уравнений несколько сложнее, чем вычислить обратную матрицу, поскольку нужно вначале найти обратную матрицу, а затем умножить ее на вектор правых частей b. Однако реальный алгоритм, рассматриваемый ниже, находящий решение системы, вычислительно проще, чем тот же алгоритм, находящий обратную матрицу. Для такого алгоритма найти обратную матрицу это все равно, что решить n систем линейных уравнений с одной и той же матрицей A в левой части, используя матрицу E в качестве правых частей.

Алгоритм Гаусса

Рассмотрим сейчас алгоритм Гаусса, позволяющий найти решение всех интересующих нас задач – вычислить определитель матрицы, решить m систем линейных уравнений, найти обратную матрицу. Построим вначале расширенную матрицу AB, состоящую из двух клеток:

AB = ||A   B||

Матрица B, дополняющая матрицу A, зависит от того, какую задачу предполагается решить. Если нужно вычислить только определитель матрицы A, то расширенная матрица совпадает с исходной и матрица B в этом случае отсутствует. Если нужно решить одну систему линейных уравнений, то матрица B состоит из одного столбца — правых частей системы уравнений. Если нужно решить m систем уравнений, то матрица B состоит из m векторов, каждый из которых задает правые части своей системы уравнений. Если нужно найти обратную матрицу, то матрица B задается единичной матрицей E.

После того, как построена расширенная матрица, вся специфика конкретной задачи теряется, — над расширенной матрицей выполняются одни и те же действия с параллельным вычислением определителя матрицы A. В чем суть этих действий? Над матрицей AB последовательно выполняются элементарные преобразования – деление элементов строки на число, что изменяет величину определителя, и вычитание из одной строки матрицы другой строки, умноженной на некоторое число. Цель наших действий состоит в том, чтобы в расширенной матрице AB клетку A преобразовать в единичную матрицу E. Поскольку каждое элементарное действие можно рассматривать, как умножение слева на некоторую матрицу, то совокупность преобразований, переводящая A в E, эквивалентна умножению слева на матрицу A-1. Но это означает также, что эти преобразования переводят клетку B в матрицу A-1*B, что и дает решение исходных задач. Поскольку в результате преобразования A переходит в единичную матрицу, определитель которой известен и равен 1, а для каждого преобразования известно как меняется величина определителя, то параллельно вычисляется и величина определителя исходной матрицы A.

Рассмотрим на простом примере матричный вид элементарных операций. Пусть элементарная операция состоит в том, что к первой строке прибавляется вторая строка, умноженная на число q.  Это действие эквивалентно умножению почти единичной матрицы на исходную матрицу:

 

Матрица, задающая элементарную операцию, отличается от единичной матрицы тем, что у нее в первой строке на втором месте стоит число q, а не ноль. Если бы к первой строке прибавлялась не вторая строка, а строка с номером j, то число q стояло бы не на втором месте, а в позиции j. Если строка j прибавляется не к первой строке, а к строке с номером i, то число q появлялось бы в i-ой строке матрицы.

Рассмотрим теперь возможную реализацию алгоритма Гаусса:

public void Gauss(double[,] M)

{

det = 1;

int n = M.GetLength(0);

int m = M.GetLength(1);

double d =0,r=0;

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

{

//Приведение столбца i  к единичному вектору

d = M[i, i]; det *= d;

//деление на диагональный элемент: M[i,i]теперь = 1;

for (int k = 0; k < m; k++)

M[i, k] /= d;

//Элементарная операция: сложение строк

for (int j=0; j<n; j++)

{

//К строке j прибавляется строка i, умноженная на r

//В результате M[j,i]=0

if(j!=i)

{

r=-M[j,i];

for (int k = 0; k < m; k++)

M[j, k] += r * M[i, k];

}

}

}

Аргументом метода является расширенная матрица M = ||A  B||. В результате работы метода матрица M приобретает вид: ||E  A-1*B||. В зависимости от того, как задана матрица B, находится решение одной системы уравнений, нескольких систем или вычисляется значение обратной матрицы. Параллельно в переменной det формируется значение определителя матрицы A.

На рис. 8 показан возможный интерфейс проекта, построенного для работы с линейными уравнениями.

Рис. 8 Интерфейс проекта, предназначенного для решения задач линейной алгебры

Алгоритм Гаусса в том виде, как он выше рассмотрен, не всегда обеспечивает получение результата. Действительно, пусть в матрице А элемент a[1,1] равен нулю. Тогда при выполнении элементарных операций в процессе преобразования матрицы А к единичной матрице Е возникнет ошибка уже на первом шаге при делении первой строки на элемент a[1,1]. Однако равенство нулю диагонального элемента вовсе не означает, что определитель матрицы равен нулю (если речь не идет о диагональной матрице), или что для нее не существует обратной матрицы.

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

В случае, когда а[i, i] равно нулю, алгоритм ищет первую строку ниже i-й, в которой элемент a[i, j] не равен нулю. Эта строка добавляется к строке i, что гарантирует возможность деления на а[i, i].

Алгоритм с выбором главного элемента в столбце

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

Алгоритм с выбором главного элемента во всей матрице

На каждом шаге приведения очередного столбца к диагональному виду в еще не приведенной матрице ищется максимальный элемент и меняются местами не только строки, но и столбцы матрицы, ставя максимальный элемент в позицию а[i, i]. Этот прием гарантирует отсутствие переполнения при выполнении операции деления. Гарантируется также, что при умножениях не будет получено слишком большое число, поскольку деление на максимальный элемент с последующим умножением на один из элементов приводит к тому, что элементы преобразованной матрицы не увеличиваются по модулю. Однако ничто не дается даром. Выбор главного элемента, перестановка строк и столбцов, необходимость обратной перестановки в конце вычислений, — все это усложняет алгоритм. Как правило, страдает и точность вычислений, особенно -1M[j, k] += r * M[i, k];для плохо обусловленных матриц. Все модификации алгоритма стоит применять тогда, когда в основной схеме возникла исключительная ситуация, требующая корректировки алгоритма. Обработчик исключительной ситуации при делении на ноль, возникновении переполнения, потери значащих цифр, может вызывать модифицированный вариант алгоритма в надежде получить решение, когда отказывается работать основная схема.

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

Интерполяционный полином, определитель  Вандермонда и обусловленность матриц

Вернемся к задаче построения интерполяционного полинома, проходящего через заданное множество точек. Напомню, заданы своими координатами (x0, y0), …(xn, yn) точки, через которые должен пройти полином степени n. Требуется найти коэффициенты a0, …an этого полинома. Ранее был рассмотрен алгоритм Лагранжа, позволяющий построить этот полином. Нетрудно понять, что существует прямое решение этой задачи, состоящее в построении системы линейных уравнений для нахождения неизвестных коэффициентов полинома. В матричном виде эта система уравнений имеет вид:

Матрица X называется матрицей Вандермонда, а ее определитель соответственно определителем Вандермонда. Этот определитель вычисляется достаточно просто:

 

Он равен произведению разностей координат точек, где произведение берется по всем j, большим i. Очевидно, что определитель будет отличен от нуля, если у точек нет совпадающих координат x. Этот факт отмечался и при рассмотрении полинома Лагранже, когда говорилось, что множество точек «не имеет возвратов».

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

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

Если матрица А плохо обусловлена, то и обратная к ней также является плохо обусловленной матрицей. Во сколько раз могут возрастать ошибки в элементах прямой матрицы при ее обращении? Примерный ответ на это дают «числа обусловленности» матрицы. Предлагаются различные количественные меры обусловленности матриц. Одной из таких мер является М-число обусловленности Тьюринга:

 

Матрица Вандермонда – потенциальный кандидат на плохую обусловленность. Если посмотреть на ее структуру, то видно, что для ее элементов во многих случаях характерен большой размах – отношение между максимальным и минимальным элементом велико. Действительно, пусть например максимальная по модулю координата xn  имеет значение 100, а степень полинома n равна 6. Это довольно скромные цифры, но уже в этом случае минимальный элемент матрицы равен 1, а максимальный — 1012 . Примерно такой же размах будет и у элементов обратной матрицы. Ее максимальный элемент будет примерно равен 1, а минимальный — (max ai,j)-1, так что число обусловленности M будет  примерно равно 1012. При наличии небольших ошибок в измерении координат, ошибки в определении значений полинома в точках, отличных от измеряемых, могут многократно возрастать. По этой причине интерполяционный полином еще можно применять внутри интервала измерений, но не рекомендуется использовать в задачах экстраполяции.

Скачать лекцию 1.6