Массивы

главная диагональ;

побочная диагональ;

элементы, расположенные выше главной диагонали;

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

элементы, расположенные выше побочной диагонали;

элементы, расположенные ниже побочной диагонали;

Главная диагональ. Если значения индексов (i, j) элемента равны, то элементы расположены на главной диагонали.

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

if i=j then <инструкции>

Побочная диагональ. Если для значений индексов (i, j) элементов выполняется равенство: i+j=n+1, то элементы расположены на побочной диагонали.

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

if i+j=n+1 then <инструкции>

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

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=1 to n do

for j:=1 to n do

if i < j then <инструкции>

for i:=1 to n-1 do

for j:=i+1 to n do

<инструкции>

Если элементы расположены на главной диагонали и выше её необходимо использовать следующий фрагмент программы:

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=1 to n do

for j:=1 to n do

if i<=j then <инструкции>

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

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=1 to n do

for j:=1 to n do

if i>j then <инструкции>

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

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=1 to n do

for j:=1 to n do

if i>=j then <инструкции>

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

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=1 to n-1 do

for j:=1 to n-1 do

if i+j<=n then <инструкции>

Если элементы, расположены ниже побочной диагонали, то необходимо использовать следующий фрагмент программы:

А11              А12              А13              А14

A21              A22              A23              А24

A31              A32              A33              А34

A41              A42              A43              А44

for i:=2 to n do

for j:=2 to n-1 do

if i+j>n+1 then <инструкции>

Транспонирование матрицы

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

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

Исходная матрица

Транспонированная матрица

1

5

9

13

1

2

3

4

Фрагмент программы транспонирования матрицы:

for i:=1 to n do {Просмотр всех строк матрицы}

for j:=i+1 to n do {Просмотр всех элементов в строке, расположенных выше главной диагонали}

begin

k:=a[i,j];

a[i,j]:= a[j,i];

a[j,i]:= k;

end;

1.4 Пример задачи

Найти сумму всех элементов некоторого двумерного массива и сравнить их с произведением элементов некоторой строки.

program zadacha;

uses crt;

var

a: array[1..50,1..50] of integer; {массив}

i,j: integer; {переменные счетчики}

n,m: integer; {количество строк и столбцов массива}

s: integer; {сумма элементов массива}

p: integer; {произведение элементов некоторой строки}

q: integer; {некоторая строка}

begin

clrscr;

write('Введите количество строк: ');

readln(n);

write('Введите количество столбцов: ');

readln(m);

for i:=1 to n do

for j:=1 to m do

begin

write('a[',i,',',j,']=');

readln(a[i,j]);

end;

writeln('Матрица:');

for i:=1 to n do

begin

for j:=1 to m do

begin

write(a[i,j]:3);

end;

readln;

end;

for i:=1 to n do

for j:=1 to m do

begin

s:=s+a[i,j];

end;

write('Введите номер строки для работы: ');

readln(q);

p:=1;

for j:=1 to m do

begin

p:=p*a[q,j];

end;

writeln('Сумма элементов матрицы: ',s);

writeln('Произведение элементов строки ',q,' равна ',p);

if s>p then

begin

writeln('Сумма больше произведения');

end

else

begin

writeln('Произведение больше произведения');

end;

readln;

end.

2. Сортировка, параметры-массивы и параметры-строки

Сортировка

Задача сортировки (упорядочения) элементов массива в соответствии с их значениями относится к классу классических задач, которые решались еще на первых е- mail –ах.

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

Различают следующие типы сортировок:

1) по возрастанию

2) по убыванию

3) по не убыванию

4) по не возрастанию

При рассмотрении каждого метода будем сортировать элементы по неубыванию.

2.1 Метод простых обменов (Пузырьковая сортировка)

Идея метода: Весь массив рассматривается несколько раз, причем при каждом рассмотрении сравниваются значения 2-х соседних элементов. Если они стоят в неправильном порядке, то производится их перестановка. Так происходит до тех пор, пока не будет выполнено ни одной перестановки. Метод называют пузырьковой сортировкой потому что меньшие значения элементов постепенно "всплывают", как пузырьки воздуха в воде, перемещаясь в начало массива, а "тяжелые" элементы "оседают на дно".

7 0 -4 3 1 -2 5

-4 7 0 -2 3 1 5

-4 -2 7 0 1 3 5

-4 -2 0 7 1 3 5

-4 -2 0 1 7 3 5

-4 -2 0 1 3 7 5

-4 -2 0 1 3 5 5

Фрагмент:

For i:=2 to n do

For j:=n downto i do

if v[j] <v[j-1] then

begin

x:=v[j];

v[j]:=v[j-1];

v[j-1]:=x;

end;

2.2 Сортировка простым выбором

Идея метода: весь массив просматривается несколько раз и на каждом шаге ищется минимальный элемент и запоминается его порядковый номер. Затем найденный минимальный элемент меняется значением с первым, вторым, третьим и т.д. предпоследним элементом массива и исключается из рассмотрения

7 0 -4 3 1 -2 5

-4 0 7 3 1 -2 5

-4 -2 7 3 1 0 5

-4 -2 0 3 1 7 5

-4 -2 0 1 3 7 5

-4 -2 0 1 3 5 7

For i:= to n do

Begin

min:=v[i];

ind :=i;

for j:= i to n-1 do

if v[j]<min then

bedin

min:=v[j];

ind:=j;

end;

x:=v[i];

v[i]:=v[ind];

v[ind]:=x;

end;

2.3 Сортировка простым включением (Метод вставки и сдвига)

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

7 0 -4 3 1 -2 5

0 7 -4 3 1 -2 5

-4 0 7 3 1 -2 5

-4 0 3 7 1 -2 5

-4 0 1 3 7 -2 5

-4 -2 0 1 3 7 5

-4 -2 0 1 3 5 7

For i:=2 to n do

For j:=1 to i-1 do

if v[i]<v[j] then

begin

x:=v[i];

for h:=1 downto j+1 do

v[h]:=i[h-1];

v[j]:=x;

end.

2.4. Параметры - массивы и параметры – строки

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

Procedure S (a: array [1..10] of Real);

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

Если мы хотим передать какой-то элемент массива, то проблем, как правило, не возникает, но если в подпрограмму передается весь массив, то следует первоначально описать его тип. Например:

type

atype = array [1..10]of Real;

Procedure S (a: atype);

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

type

intype = String [15] ;

outype = String [30] ;

Function St (s : intype): outype;

Требование описать любой тип-массив или тип-строку перед объявлением подпрограммы на первый взгляд кажется несущественным. Действительно, в рамках простейших вычислительных задач обычно заранее известна структура всех используемых в программе данных, поэтому статическое описание массивов не вызывает проблем. Однако разработка программных средств универсального назначения связана со значительными трудностями. По существу, речь идет о том, что в Турбо Паскале невозможно использовать в подпрограммах массивы с "плавающими" границами изменения индексов. Например, если разработана программа, обрабатывающая матрицу 10х10 элементов, то для обработки матрицы 9x11 элементов необходимо переопределить тип, т.е. перекомпилировать всю программу (речь идет не о динамическом размещении массивов в куче, а о статическом описании массивов и передаче их как параметров в подпрограммы). Этот недостаток, как и отсутствие в языке средств обработки исключительных ситуаций (прерываний), унаследован из стандартного Паскаля и представляет собой объект постоянной и вполне заслуженной его критики. Разработчики Турбо Паскаля не рискнули кардинально изменить свойства базового языка, но, тем не менее, включили в него некоторые средства, позволяющие в известной степени смягчить отмеченные недостатки. Эти недостатки практически полностью устранены в языке Object Pascal, используемом в визуальной среде программирования Delphi.