Массивы. Задачи комбинированной обработки массивов

Массив — это структурированный тип данных, состоящий из фиксированного числа элементов одного типа. Тип элементов массива называется базовым. Число элементов массива фиксируется при описании и в процессе выполнения программы не меняется.

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

Определить массивы можно двумя способами:

1. Var

имя_массива: array [тип_индексов] of тип_элементов;

2. Type

имя_типа = array [тип_индекса] of тип_элементов;

Var

имя_массива: имя_типа;

Тип индекса (это тип-диапазон) определяет границы изменения значений индекса. Если задан один индекс, то массив называется одномерным, если два – двумерным, если n – n-мерным. Одномерные массивы используются для представления векторов, двумерные – для представления матриц.

Пример.

1-ый способ:

Var

A,B: array [1..10] of Real; {одномерные массивы}

С: array [1..5,1..10] of Integer; {двумерный массив}

2-ой способ:

Type

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

Mas2= array [1..5,1..10] of Integer;

Var

A,B:Mas1;

C:Mas2;

Диапазоны индексов можно задать константами, которые описаны в разделе описания констант:

Const

N=5;

M=10;

Var

C: array [1..N,1..M] of Integer;

Массив можно описать с помощью типизированных констант:

Const

Vect: array [1..5] of Byte=(1,6,3,8,5);

Matr: array [1..4,1..6] of Integer=

((1,6,3,5,2,4),

(7,2,5,4,3,2),

(3,1,6,3,8,5),

(5,2,8,5,5,4));

Элементы массива располагаются в памяти последовательно. Многомерные массивы располагаются таким образом, что самый правый индекс возрастает самым первым. Например, массив A[3,3] будем располагаться следующим образом: A[1,1], A[1,2], A[1,3], A[2,1], A[2,2], A[2,3], A[3,1], A[3,2], A[3,3].

Действия над массивами

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

1. A=B (проверить массивы на равенство);

2. А<>В (проверить массивы на неравенство);

3. А:=В.

Действия над элементами массива

1. Инициализация массива (заключается в присвоении каждому элементу массива одного и того же значения)

· одномерного

For i:=1 to N do

A[i]:=0;

· двумерного

For i:=1 to N do

For j:=1 to M do

B[i,j]:=0;

2. Ввод элементов массива

· одномерного

Write ('Введите размерность массива N=');

ReadLn (N);

WriteLn ('Введите элементы массива');

For i:=1 to N do

Begin

Write ('A[',i,']=');

ReadLn (A[i]);

end;

· двумерного

Write ('Введите размерность массива N, M');

ReadLn (N, M);

WriteLn ('Введите элементы массива');

For i:=1 to N do

For j:=1 to M do

Begin

Write ('B[',i,',',j,']=');

ReadLn (B[i,j]);

end;

3. Вывод элементов массива

· одномерного

WriteLn ('Вектор А:');

For i:=1 to N do

Write (A[i]:5);

WriteLn;

· двумерного

WriteLn ('Матрица В:');

For i:=1 to N do

Begin

For j:=1 to M do

Write (B[i,j]:5);

WriteLn;

end;

 

4. Поиск нулевых элементов в массиве

· одномерном

k:=0;

For i:=1 to N do

If A[i]=0 then k:=k+1;

· двумерном

k:=0;

For i:=1 to N do

For j:=1 to M do

If B[i,j]=0 then k:=k+1;

5. Нахождение минимального элемента массива и его места

· одномерного

min:=A[1];

i_min:=1;

For i:=1 to N do

If A[i]<min then

Begin

min:=A[i];

i_min:=i;

end;

· двумерного

min:=B[1,1];

i_min:=1;

j_min:=1;

For i:=1 to N do

For j:=1 to M do

If B[i,j]<min then

Begin

min:=B[i,j];

i_min:=i;

j_min:=j;

end;

 

6. Перестановка минимального и первого элементов в массиве

· одномерном

r:=A[1];

A[1]:=A[i_min];

A[i_min]:=r;

· двумерном

r:=B[1,1];

B[1,1]:=B[i_min,j_min];

B[i_min,j_min]:=r;

7. Нахождение суммы положительных элементов массива

· одномерного

sum:=0;

For i:=1 to N do

If A[i]>0 then sum:=sum+A[i];

· двумерного

sum:=0;

For i:=1 to N do

For j:=1 to M do

If B[i,j]>0 then sum:=sum+B[i,j];

8. Нахождение произведения нечетных элементов

· одномерного

prod:=1;

For i:=1 to N do

If (A[i] mod 2) <> 0 then

prod:=prod*A[i];

· двумерного (нахождение произведения нечетных элементов)

prod:=1;

For i:=1 to N do {Функция Odd(X) возвращает значение}

For j:=1 to M do {истина, если X нечетно }

If Odd(B[i,j]) then

prod:=prod*B[i,j];

9. Нахождение суммы положительных элементов выше главной диагонали (включая элементы диагоналей).

Элементы на главной диагонали характеризуются тем, что индексы этих элементов равны, т.е. i=j. Для элементов побочной диагонали для любого i индекс столбца j=n-i+1. Элементы областей выше, ниже главной или побочной диагоналей можно задать или порядком изменения индексов или условиями, накладываемыми на индексы:

i=1,2,…,n; j=1,2,…,i i=1,2,…,n; j=i,i+1,…,n

или i>=j или i<=j

i=1,2,…,n; j=1,2,… n-i+1; i=1,2,…,n;j=n-i+1,…,n

или n-i-j+1>=0 или n-i-j+1<=0

sum:=0;

For i:=1 to n do

For j:=i to n do

If B[i,j]>=0 then sum:=sum+B[i,j];

 

10. Поменять местами максимальный элемент на главной диагонали и минимальный элемент ниже побочной.

Max:=B[1,1];

I_max:=1;

For i:=1 to n do

If B[i,i]> max then

Begin

Max:=B[i,i];

I_max:=i;

end;

Min:=B[1,n];

I_min:=1;

J_min:=n;

For i:=1 to n do

For j:=n-i+1 to n do

If B[i,j]< Min then

Begin

Min:=B[i,j];

I_min:=i;

J_min:=j;

end;

R:=B[I_max,I_max];

B[I_max,I_max]:=B[I_min,J_min];

B[I_min,J_min]:=R;

 

11. Дана квадратная матрица В размерности nxn. Построить вектор А, где а_i – сумма положительных элементов i-ой строки матрицы.

For i:=1 to n do

Begin

S:=0;

For j:=1 to n do

If B[i,j]>0 then S:=S+B[i,j];

A[i]:=S;

End;

 

12. Дана квадратная матрица В размерности nxn. В каждом столбце оставить без изменения максимальный элемент столбца, остальные элементы заменить нулями.

For j:=1 to n do

Begin

Max:=B[1,j];

I_max:=1;

For i:=1 to n do

If B[i,j]> Max then

Begin

Max:=B[i,j]

I_max:=i;

end;

For i:=1 to n do

If i_max<>i then B[i,j]:=0;

end;

 

Пример: Дан целочисленный вектор A (n), поменять местами максимальный и минимальный элементы вектора. На печать выдавать исходный вектор, максимальный, минимальный элементы, полученный вектор.

Program Example_Vect;

Uses Crt;

Const

N_max=10;

Var

N,i,max,i_max,min,i_min,r:Integer;

A: array [1..N_max] of Integer;

Begin

Clrscr;

Write('Введите размерность массива N (<',N_max,')=');

ReadLn (N);

WriteLn ('Введите элементы массива');

For i:=1 to N do {ввод элементов вектора}

Begin

Write ('A[',i,']=');

ReadLn (A[i]);

end;

WriteLn ('Исходный вектор А:');

For i:=1 to N do { вывод вектора}

Write (A[i]:5);

WriteLn;

min:=A[1]; {нахождение минимального элемента}

i_min:=1; {и его индекса}

For i:=1 to N do

If A[i]<min then

Begin

min:=A[i];

i_min:=i;

end;

max:=A[1];

i_max:=1; {нахождение максимального элемента}

For i:=1 to N do {и его индекса}

If A[i]>max then

Begin

max:=A[i];

i_max:=i;

end;

WriteLn('Минимальный элемент A[',i_min,']=',min);

WriteLn('Максимальный элемент A[',i_max,']=',max);

r:=A[i_min]; {перестановка} {другой способ:}

A[i_min]:=A[i_max]; { A[i_min]:=A[i_max];}

A[i_max]:=r; { A[i_max]:=min;}

WriteLn ('Полученный вектор А:');

For i:=1 to N do {вывод полученного вектора}

Write (A[i]:5);

WriteLn;

End.

 

ИСПОЛЬЗОВАНИЕ ПОДПРОГРАММ

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

Все процедуры и функции языка Pascal подразделяются на две группы: встроенные и определенные пользователем.

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

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

Специальные процедуры

Delay (Time) – организует задержку выполнения программы на Time мс.

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

Halt – прекращает выполнение программы и передает управление системе программирования.

Специальные функции

KeyPressed – возвращает результат True, если на клавиатуре была нажата какая-либо клавиша, и False в противном случае.

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

 

Процедура пользователя представляет собой именованную группу операторов, реализующую определенную часть общей задачи и вызываемую при необходимости для выполнения по имени из любой позиции раздела операторов. Описание процедуры включает заголовок и тело процедуры. Заголовок состоит из зарезервированного слова Procedure, идентификатора (имени) процедуры и необязательного заключенного в скобки списка формальных параметров с указанием типа каждого параметра. Имя процедуры – идентификатор, уникальный в пределах программы. Тело процедуры представляет собой локальный блок, по структуре аналогичный программе:

Формат описания процедуры:

Procedure имя_процедуры (формальные_параметры); {заголовок}

раздел описаний

Begin {тело процедуры}

раздел операторов

End;

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

Формат обращения к процедуре:

имя_процедуры (фактические_параметры);

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

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

Формат описания функции пользователя:

Function имя (формальные_параметры): тип_результата;

разделы описаний

Begin {тело функции}

раздел операторов

End;

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

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

 

Директивы компилятора

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

Assembler – тело подпрограммы написано на ассемблере;

External – с помощью этой директивы объявляется внешняя подпрограмма;

Far – компилятор должен создать код подпрограммы, рассчитанный на дальнюю модель вызова;

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

Forward – используется при опережающем описании подпрограмм для сообщения компилятору, что описание подпрограммы следует дальше по тексту программы (но в пределах текущего программного модуля);

Inline – тело подпрограммы реализуется с помощью встроенных машинных инструкций;

Interrupt – используется при создании процедур обработки прерываний.

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