close

Вход

Забыли?

вход по аккаунту

?

Kozenko Informatika ch2

код для вставкиСкачать
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ИНФОРМАТИКА
Часть 2
Лабораторный практикум
Санкт-Петербург
2007
УДК 007.5
ББК 32.81
К59
Рецензенты:
кандидат технических наук, доцент,
руководитель компьютерных классов
«Менеджер-центра» Санкт-Петербургского государственного
университета культуры и искусств Н. Н. Бондаренко;
кандидат технических наук, доцент С. В. Беззатеев
Утверждено редакционно-издательским советом университета
в качестве лабораторного практикума
Козенко С. Л.
К59Информатика: лабораторный практикум. Ч. 2 / С. Л. Козенко – СПб.: ГУАП, 2007. 55 с.: ил.
Рассмотрены типовые задачи обработки массивов данных и основные правила использования модульного принципа программирования. Приведено описание процедур и функций в языке высокого
уровня Паскаль. Даны примеры составления схем алгоритмов и программирования задач, а также описание лабораторных работ № 4
и 5.
Предназначен для студентов, обучающихся по специальностям
16040265 (181200), 16090365 (131000), 20010062 (551500), 20010265
(190200), 20010365 (190300), 20010765 (191000), 21020165 (220800),
21020265 (220500), 22010062 (553000), 28020265 (330200). Может
быть полезен студентам других специальностей, обучающимся по
дисциплинам с аналогичной тематикой.
УДК 007.5
ББК 32.81
© ГУАП, 2007
© С. Л. Козенко, 2007
Содержание
Предисловие...................................................................... 4
1. Процедуры и функции в Паскале....................................... 5
1.1. Процедуры............................................................... 5
1.2. Функции................................................................. 7
1.3. Рекурсивность процедур и функций............................ 8
2. Обработка массивов данных.............................................. 10
2.1. Общие положения..................................................... 10
2.2. Вычисление суммы (произведения) элементов массива.... 12
2.3. Поиск экстремальных элементов в массиве................... 15
2.4. Умножение матриц................................................... 18
2.5. Сортировка (упорядочение) массивов........................... 20
3. Обработка массивов данных с использованием модульного
принципа программирования............................................... 26
4. Методические указания к выполнению лабораторных работ..... 39
Лабораторная работа № 4. Обработка массивов данных............ 39
Лабораторная работа № 5. Обработка массивов данных с использованием модульного принципа программиррования .............. 48
Библиографический список.................................................. 54
ПРЕДИСЛОВИЕ
Предлагаемый вниманию методический материал является продолжением изложенных в работе [1] основных методов и приемов
решения типовых вычислительных задач. Целью лабораторного
практикума является обучение студента навыкам алгоритмизации
и программирования задач обработки массивов данных и использования при их решении модульного принципа программирования.
Лабораторный практикум содержит: описание процедур и функций языка высокого уровня Паскаль, описание задач обработки
массивов данных. Использование процедур и функций позволяет
осуществить блочный подход (применительно к языку Паскаль)
к решению задач или реализовать так называемый модульный принцип программирования.
Приведены примеры составления схем алгоритмов и программ
решения некоторых типовых вычислительных задач. Даны пояснения к лабораторным работам № 4 и 5. Представлены варианты заданий к указанным лабораторным работам.
Выполнение лабораторных работ, а также приведенные примеры
программ на языке Паскаль, рассчитаны на использование среды
программирования Borland Pascal 7.0 для ПК.
1. Процедуры и функции в Паскале
1.1. Процедуры
Часто одну и ту же последовательность операторов необходимо
выполнять несколько раз в разных местах программы. Для этой
цели используются процедуры и функции.
Описание процедуры состоит из заголовка и тела процедуры
(блока). Заголовок процедуры записывается следующим образом:
Procedure И ( <список формальных параметров> ); ,
где Procedure (процедура) – служебное слово; И – имя процедуры.
Список формальных параметров в общем случае может отсут­
ствовать. Перечисление формальных параметров в списке осуществляется с указанием их имен и типов. Назначение формальных параметров состоит в том, чтобы сообщить, какие подставить конкретные данные (фактические параметры) при обращении к этой
процедуре.
Пример заголовка:
Procedure Summa ( M : byte; R : Mas; var S : real );
Для передачи в процедуру входных данных обычно используются параметры-значения (в примере заголовка – это M и R). Соответствующие им фактические параметры могут быть константами, переменными или арифметическими выражениями того же типа. При
выходе из процедуры значения этих параметров остаются такими
же, какими они были до обращения к процедуре, независимо от
того, претерпевали они изменения в теле процедуры или нет.
Для передачи результатов из процедуры в блок программы, из
которого осуществлялся ее вызов, в список формальных параметров вводятся параметры-переменные, которым должно предшествовать служебное слово var (в примере заголовка – это переменная
S). Соответствующие им фактические параметры могут быть только переменными.
Обращение к процедуре осуществляется с помощью оператора
процедуры. Общий вид оператора процедуры:
И ( <список фактических параметров> ); ,
где И – имя вызываемой процедуры.
Список фактических параметров должен удовлетворять следующим требованиям: количество фактических параметров, их типы
и порядок следования должны быть те же, что и в списке формальных
параметров. Идентификаторы формальных и соответствующих им
фактических параметров могут совпадать или различаться. Например, к процедуре Summa можно обратиться следующим образом:
Summa ( 5, A, S );
Пример 1.1
Вычислить значения суммы и среднего арифметического элементов одномерного массива A, состоящего из 11 элементов вещественного типа.
Текст программы решения задачи приведен на рис. 1.1.
В общем случае описание процедуры может содержать три вида
идентификаторов.
1. Формальные параметры. Как уже отмечалось, среди этих параметров различают параметры-значения и параметры-переменные.
2. Локальные параметры. Эти параметры описываются в теле
процедуры (в примере 1.1 – i). Обратим внимание на то, что параметр i описан и в основном блоке. Согласно принципу локализации,
Program SUM ( input, output );
Uses Crt;
Type
Mas = array [ 1..11 ] of real;
Var
i : byte; Q, S : real; A : Mas;
Procedure Summa ( M : byte; R : Mas; var S : real );
Var
i : byte;
begin
S := 0;
for i := 1 to M do S := S + R [ i ];
Q := S/M
end;
Begin
ClrScr;
{ Ввод значений элементов массива A }
for i := 1 to11 do read ( A [ i ] );
Summa ( 11, A, S ); { Обращение к процедуре }
writeln;
writeln ( ‘Сумма элементов S=’, S : 7 : 3 );
write ( ‘Среднее арифметическое Q=’, Q : 7 : 3 )
End.
Рис. 1.1. Текст программы вычисления значений суммы и среднего арифметического элементов одномерного массива с использованием
процедуры
если какой-либо идентификатор описан в теле процедуры, то он
приобретает смысл в соответствии с этим описанием. Если такой же
идентификатор был описан вне процедуры (в объемлющем блоке),
то действие его внешнего описания временно (до выхода из процедуры) приостанавливается. При выходе из процедуры снова действует
внешнее описание.
3. Глобальные параметры. Эти параметры описываются в объемлющем процедуру блоке и имеют один и тот же смысл как в теле
процедуры, так и вне ее (в примере 1.1 таким параметром является
Q). Если связь процедуры с внешним блоком осуществляется только посредством глобальных параметров, то такая процедура называется процедурой без параметров.
1.2. Функции
В общем случае процедура служит для вычисления нескольких
выходных параметров. Если необходимо вычислить лишь один параметр, то вместо процедуры можно использовать другую структуру Паскаля – функцию. Описание функции также состоит из заголовка и тела функции. Заголовок функции выглядит следующим
образом:
Function И ( <список формальных параметров> ) : Т; ,
где Function (функция) – служебное слово; И – имя функции; Т –
тип функции. Список формальных параметров в общем случае может отсутствовать.
Например,
Function Summa ( M : byte; R : Mas ) : real;
В этом случае роль выходного параметра играет сам идентификатор функции Summa, поэтому в заголовке задается его тип. Другая отличительная особенность функции состоит в том, что в ее теле
должен присутствовать оператор, присваивающий выходное значение идентификатору функции.
Обращение к функции обычно состоит в упоминании ее имени
в выражениях соответствующего типа.
Пример 1.2
Составить программу решения примера 1.1 с использованием
функции. Текст программы решения задачи приведен на рис. 1.2.
Program Sum ( input, output );
Type
Mas = array [ 1..11 ] of real;
Var
i : byte; Q : real; A : Mas;
Function Summa ( M : byte; R : Mas ) : real;
Var
i : byte; S : real;
begin
S := 0;
for i := 1 to M do S := S + R [ i ];
Q := S/M;
Summa := S
end;
Begin
for i := 1 to 11 do read ( A [ i ] );
writeln;
writeln ( ‘Сумма элементов S=’, Summa ( 11, A ) : 7 : 3 );
write ( ‘Среднее арифметическое Q=’, Q : 7 : 3 )
End.
Рис. 1.2. Текст программы вычисления значений суммы и среднего арифметического элементов одномерного массива с использованием
функции
В приведенном тексте программы использован локальный параметр S для промежуточных вычислений суммы элементов массива.
Окончательный результат присваивается идентификатору функции Summa.
Если в функции, помимо вычисления основного результата, происходят изменения параметров, объявленных как глобальные
(в примере 1.2 – параметр Q), или параметров-переменных, а также
некоторые другие действия, то говорят о «побочном эффекте» функции. Опасность использования функции с побочным эффектом заключается в том, что все эти действия «скрыты» в теле самой функции и не «видны» из основной программы. Поэтому в больших программах действие такой функции может привести к ошибкам.
1.3. Рекурсивность процедур и функций
Функция или процедура может вызывать другую функцию или
процедуру, та в свою очередь третью и т. д. Допустимо также, чтобы
в функции или процедуре содержалось обращение к самой себе. Такой способ вызова носит название рекурсии. Чтобы рекурсивный
процесс не был бесконечным, необходимо правильно организовать
выход, то есть последний шаг должен представлять собой нерекурсивное решение. Так, в примере 1.2, при использовании рекурсии
в функции Summa, операция суммирования элементов массива может выглядеть следующим образом (фрагмент программы).
…
Summa := 0;
for i := 1 to 11 do Summa := Summa ( 11 - i, R ) + R [ i ];
…
Однако во избежании бесконечного процесса рекурсии, вычисление параметра Q следует перенести из функции в основной блок, например, перед последним оператором процедуры write вставить оператор присваивания следующего вида:
Q := Summa ( 11, A )/ 11;
Такие нетривиальные действия при использовании рекурсивных функций требуют большого внимания и осторожности.
Директива Forward. Две процедуры (функции) являются взаимно рекурсивными, если первая вызывает вторую и, в свою очередь,
вызывается второй при возврате. Эта первая процедура должна
быть определена с самого начала. Однако при вызове второй процедуры из первой, вторая еще не определена, так как ее описание располагается после первой процедуры. Для избежания конфликтной
ситуации используется служебное слово Forward (впереди), которое
записывается после полного заголовка второй процедуры и означает, что ее описание будет следовать ниже.
На рис. 1.3 приведен пример использования директивы Forward.
Для более детального изучения языка Паскаль можно воспользоваться работами [2, 3, 4] или приведенными в конце пособия ссылками на Интернет-ресурсы.
Program DemoForward;
Var i, j : real;
Procedure P2 ( i, j : real ); Forward;
Procedure P1 ( var i, j : real );
begin
read ( i, j ); P2 ( i, j )
end;
Procedure P2; { Список формальных параметров не повторяется }
Var S : real;
begin
S := i + j;
write ( S );
if S > 1.5 then P1 ( i, j )
end;
Begin
P1( i, j )
End.
Рис. 1.3. Использование директивы Forward
2. Обработка массивов данных
2.1. Общие положения
Под массивом будем понимать некоторым образом организованный набор данных (например, чисел), называемых элементами,
или компонентами, массива. Элементам массива приписывается
общее имя, при этом элементы имеют индексы, которые определяют местоположение каждого элемента в массиве. Количество индексов, используемых для указания координат (положения) элемента в массиве, зависит от размерности массива. Различают одномерные (векторы в математике), двумерные (матрицы в математике
или таблицы) и многомерные массивы. В дальнейшем будем рассматривать только одномерные и двумерные массивы.
Например,
A = { a1 , a2 , . . . , an } – одномерный массив (вектор) размерностью n;
 b11b12b13 ... b1n

 b b b ... b2n
B =  21 22 23
– двумерный массив (матрица) размерностью
...

m × n.
bm1bm2bm3 ... bmn
В общем случае массивы не упорядочены по значениям элементов, но в то же время упорядочены по индексам, что позволяет производить обработку массивов путем организации циклов по индексам.
К задачам обработки массивов числовых данных относятся задачи линейной алгебры, задачи поиска экстремальных элементов
и задачи сортировки.
Пусть задана некоторая матрица размерностью m × n, где m – количество строк; n – количество столбцов. При m = 1 говорят о матрице-строке, а при n = 1 – матрице-столбце, которые в дальнейшем
будем считать векторами.
Рассмотрим типовые задачи линейной алгебры по обработке матриц и векторов.
Транспонирование матриц. Матрица Qm×n называется транспонированной по отношению к матрице Rn×m, если элементы матриц Q
и R связаны следующим соотношением:
qij = rji , i = 1, ..., m; j = 1, ..., n.
10
Вычисление следа квадратной матрицы. След квадратной матрицы
A n×n есть сумма элементов главной диагонали:
n
Sp = ∑ aii .
i =1
Умножение матрицы на скаляр. Результатом умножения матрицы Qm×n на скаляр S является матрица Rm×n, элементы которой имеют вид
rij = S × qij , i = 1, ..., m; j = 1, ..., n.
При m = 1 (или n = 1) имеет место частный случай: умножение
вектора на скаляр. Например,
ri = S × qi , i = 1, ..., m.
Сложение матриц. Результатом сложения двух матриц Qm×n
и Rm×n является матрица Zm×n, элементы которой вычисляются по
формулам:
zij = qij + rij , i = 1, ..., m; j = 1, ..., n.
При m = 1 (или n = 1) имеет место частный случай: сложение векторов. Например,
zi = qi + ri , i = 1, ..., m.
Умножение матриц. Результатом произведения двух матриц
Qm×l и Rl×n является матрица Zm×n, элементы которой вычисляются
следующим образом:
l
zij = ∑ qik × rkj , i = 1, ..., m; j = 1, ..., n.
k=1
Заметим, что перемножить можно только те матрицы, у которых
число столбцов первой совпадает с числом строк второй (в данном
случае – это размерность l). Исходя из этого условия, допустимыми
являются следующие частные случаи:
а) при m = 1 – умножение матрицы-строки на матрицу. Результатом является матрица-строка, элементы которой вычисляются по
формуле:
l
zj = ∑ qk × rkj , j = 1, ..., n;
k=1
б) при n = 1 – умножение матрицы на матрицу-столбец. Результатом является матрица-столбец, элементы которой вычисляются
по формулам:
11
l
zi = ∑ qik × rk , i = 1, ..., m;
k=1
в) при m = 1 и n = 1 – умножение матрицы-строки на матрицустолбец. Результатом является скаляр, значение которого вычисляется по формуле:
l
z = ∑ qk × rk ;
k=1
г) при l = 1 – умножение матрицы-столбца на матрицу-строку.
Результатом является матрица, элементы которой вычисляются по
формуле:
zij = qi × rj , i = 1, ..., m, j = 1, ..., n.
Рассмотрим основные приемы алгоритмизации и программирования некоторых типовых задач обработки массивов данных.
2.2. Вычисление суммы (произведения) элементов массива
Вычисление суммы (произведения) элементов массива входит во
многие задачи обработки массивов, а также в задачи линейной алгебры. Значение суммы S (произведения Pr) элементов массива
ищется с использованием рекуррентной зависимости в виде последовательного накопления частичных сумм (произведений) элементов массива. Все рассуждения аналогичны приведенным в работе
[1]. Различие состоит лишь в том, что начальное значение суммы
задается равным 0 (для произведения начальное значение задается
равным 1).
Пример 2.1
Найти сумму положительных элементов матрицы A4×3. Схема алгоритма и текст программы решения задачи приведены на рис. 2.1.
Пример 2.2
Вычислить значение следа квадратной матрицы A5×5. Схема алгоритма и текст программы решения задачи приведены на рис. 2.2.
Пример 2.3
Найти произведение всех элементов одномерного массива A4.
Схема алгоритма и текст программы решения задачи приведены
на рис. 2.3.
12
¦¹Ð¹ÄÇ
J
K
›»Ç½"JK
K
J
4
J
K
¹
"JK
¦¾Ë
44"JK
K
J
Program Summa ( input, output );
Uses Crt;
Type
Mas = array [ 1..4, 1..3 ] of real;
Var
A : Mas; S : real; i, j : byte;
Begin
ClrScr;
{ Ввод исходных данных }
writeln ( ‘ Введите A 4x3 ‘ );
for i := 1 to 4 do
for j := 1 to 3 do
read ( A [ i, j ] );
{ Вычисление значения суммы
положительных элементов массива }
S := 0;
for i := 1 to 4 do
for j := 1 to 3 do
if A [ i, j ] > 0 then S := S + A [ i, j ];
{ Вывод результата }
writeln;
write ( ‘ Сумма S= ‘, S : 7 : 3 )
End.
›Ô»Ç½4
£ÇƾÏ
Рис. 2.1. Схема алгоритма и текст программы вычисления значения суммы положительных элементов массива
13
¦¹Ð¹ÄÇ
J
K
›»Ç½"JK
K
J
4M
J
4M4M"JJ
J
Program Sled ( input, output );
Uses Crt;
Type
Mas = array [ 1..5, 1..5 ] of real;
Var
A : Mas; Sl : real; i, j : byte;
Begin
ClrScr;
{ Ввод исходных данных }
writeln ( ‘ Введите A 5x5 ‘ );
for i := 1 to 5 do
for j := 1 to 5 do
read ( A [ i, j ] );
{ Вычисление значения следа матрицы }
Sl := 0;
for i := 1 to 5 do
Sl := Sl + A [ i, i ];
{ Вывод результата }
writeln;
write ( ‘ Sled= ‘, Sl : 7 : 3 );
ReadKey
End.
›Ô»Ç½4M
£ÇƾÏ
Рис. 2.2. Схема алгоритма и текст программы вычисления значения следа квадратной матрицы
14
¦¹Ð¹ÄÇ
J
›»Ç½"J
J
1S
J
1S1S"J
J
Program Mult ( input, output );
Uses Crt;
Type
Mas = array [ 1..4 ] of real;
Var
A : Mas; Pr : real; i, j : byte;
Begin
ClrScr;
{ Ввод исходных данных }
writeln ( ‘ Введите A 4 ‘ );
for i := 1 to 4 do
read ( A [ i ] );
{ Вычисление значения произведения }
Pr := 1;
for i := 1 to 4 do
Pr := Pr * A [ i ];
{ Вывод результата }
writeln;
write ( ‘ Произведение Pr= ‘, Pr : 7 : 3 )
End.
›Ô»Ç½1S
£ÇƾÏ
Рис. 2.3. Схема алгоритма и текст программы вычисления значения произведения элементов одномерного массива
2.3. Поиск экстремальных элементов в массиве
К подобным задачам относятся задачи поиска максимальных
и/или минимальных элементов, а также некоторых функций от
этих элементов (например, максимального по модулю элемента)
в массивах различной размерности с указанием или без указания
координат этих элементов в массиве.
15
Пример 2.4
Составить схему алгоритма поиска экстремальных по модулю
элементов в одномерном массиве A5. Схема алгоритма и текст программы решения задачи приведены на рис. 2.4.
Пример 2.5
Составить схему алгоритма поиска экстремальных элементов и их
координаты в двумерном массиве A3×6. Схема алгоритма и текст программы решения задачи приведены на рис. 2.5 и 2.6 соответственно.
¦¹Ð¹ÄÇ
Jc
›»Ç½"J
J
" NBY "
"NJO"
Jc
]"J]]"NBY]
¹
¦¾Ë
]"J] ]"NJO]
"NBY"J
¹
"NJO"J
J
Program Extrem ( input, output );
Uses Crt;
Type
Mas = array [ 1..5 ] of real;
Var
A : Mas; i : byte; Amax, Amin : real;
Begin
ClrScr;
{ Ввод исходных данных }
writeln ( ‘ Введите массив A 5 ‘ );
for i := 1 to 5 do
read ( A [ i ] );
{ Поиск экстремальных значений }
Amax := A [ 1 ];
Amin := A [ 1 ];
¦¾Ë
for i := 2 to 5 do
if abs ( A [ i ] ) > abs ( Amax )
then
Amax := a [ i ]
else
if abs ( A [ i ] ) < abs ( Amin )
then
Amin := A [ i ];
{ Вывод результатов }
writeln;
write ( ‘ |Amax| = ‘, Amax : 7 : 3,
‘ |Amin| = ‘, Amin : 7 : 3 )
End.
›Ô»Ç½"NBY"NJO
£ÇƾÏ
Рис. 2.4. Схема алгоритма и текст программы поиска экстремальных по
модулю элементов в одномерном массиве
16
¦¹Ð¹ÄÇ
J
K
α
β
›»Ç½"JK
"NBY"JK
"NJO"JK
K
*NBYJ
*NJOJ
J
+NBYK
+NJOK
χ
"NBY"
*NBY
K
+NBY
J
"NJO"
›Ô»Ç½"NBY*NBY
+NBY"NJO*NJO+NJO
*NJO
£ÇƾÏ
+NJO
J
Kc
"JK"NBY
¹
¦¾Ë
"JK"NJO
¦¾Ë
¹
α
β
χ
Рис. 2.5. Схема алгоритма поиска экстремальных элементов и их координат в двумерном массиве
17
Program Extrem1 ( input, output );
Uses Crt;
Type
Mas = array [ 1..3, 1..6 ] of real;
Var
A : Mas; Amax, Amin : real;
Imax, Jmax, Imin, Jmin, i, j, k : byte;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов матрицы A 3x6 : ’ );
for i := 1 to 3 do
for j := 1 to 6 do
read ( A[ i, j ] );
{ Поиск экстремальных элементов и их координат в матрице }
Amax := A [ 1, 1 ];
Imax := 1; Jmax := 1;
Amin := A [ 1, 1 ];
Imin := 1; Jmin := 1;
for i := 1 to 3 do
for j := 1 to 6 do
if A [ i, j ] > Amax
then
begin
Amax := A [ i, j ];
Imax := i; Jmax := j
end
else
if A [ i, j ] < Amin
then
begin
Amin := A [ i, j ];
Imin := i; Jmin := j
end;
{ Вывод результатов }
writeln;
writeln ( ‘Amax=’, Amax : 5 : 2, ’ Imax=’, Imax, ’ Jmax=’, Jmax );
writeln ( ‘Amin=’, Amin : 5 : 2, ’ Imin=’, Imin, ’ Jmin=’, Jmin);
ReadKey
End.
Рис. 2.6. Текст программы поиска экстремальных элементов и их координат в двумерном массиве
2.4. Умножение матриц
Как уже отмечалось, умножить можно две матрицы, для которых
справедливо следующее: число столбцов первой матрицы (левого операнда) должно совпадать с числом строк второй (правого операнда).
Пример 2.6
Составить схему алгоритма и программу нахождения значения
произведения двух матриц: A5×7 и B7×3 , состоящих из элементов вещественного типа.
18
Решение: результатом будет являться матрица C5×3 . Схема алгоритма и текст программы решения задачи приведены на рис. 2.7
и 2.8 соответственно.
¦¹Ð¹ÄÇ
J
K
›»Ç½"JK
K
J
J
K
›»Ç½#JK
K
J
J
α
K
J
J
K
›Ô»Ç½$JK
K
J
£ÇƾÏ
K
$JK
L
$JK$JK"JL#LK
L
α
Рис. 2.7. Схема алгоритма умножения матриц
19
Program Multi ( input, output );
Uses Crt;
Type
Mas1 = array [ 1..5, 1..7 ] of real;
Mas2 = array [ 1..7, 1..3 ] of real;
Mas3 = array [ 1..5, 1..3 ] of real;
Var
A : Mas1; B : Mas2; C : Mas3;
i, j, k : byte;
Begin
ClrScr;
{ Ввод значений элементов исходных матриц }
writeln ( ‘Введите значения элементов матрицы A 5x7 : ’ );
for i := 1 to 5 do
for j := 1 to 7 do
read ( A [ i, j ] );
writeln;
writeln ( ‘Введите значения элементов матрицы B 7x3 : ’ );
for i := 1 to 7 do
for j := 1 to 3 do
read ( B [ i, j ] );
{ Перемножение матриц }
for i := 1 to 5 do
for j := 1 to 3 do
begin
C [ i, j ] := 0;
for k := 1 to 7 do
C [ i, j ] := C [ i, j ] + A [ i, k ] * B [ k, j ]
end;
{ Вывод значений элементов результирующей матрицы }
writeln;
writeln ( ‘Матрица C:’ );
for i := 1 to 5 do
begin
for j := 1 to 3 do
write ( C [ i, j ] : 5 : 2, ’ ‘ );
writeln
end;
ReadKey
End.
Рис. 2.8. Текст программы умножения матриц
На примере умножения матриц можно легко реализовать следующие операции: умножение матрицы на вектор, умножение двух
векторов, умножение матрицы на скаляр.
2.5. Сортировка (упорядочение) массивов
Задача сортировки неупорядоченного массива данных (обычно
одномерного) заключается в перестановке элементов массива в заданном порядке, например, по возрастанию или убыванию значе20
ний элементов массива или значений функций от этих элементов.
Существуют несколько методов сортировки массивов. Рассмотрим
один из наиболее применимых на практике методов сортировки:
метод «пузырька».
Суть метода состоит в следующем. В ходе просмотра элементов
неупорядоченной последовательности сравниваются два соседних
числа. Если эти числа расположены в заданном порядке, то они остаются на своих местах, иначе их меняют местами. Затем переходят
к следующей паре, в которой одно число из предыдущей пары.
Обычно просмотр элементов начинается с последней пары. В этом
случае требуемые числа продвигаются с конца последовательности
в ее начало, что напоминает процесс обменного движения воздушных капель и жидкости в наклоненном пузырьке (отсюда и название метода). Сортировка считается законченной, если в ходе просмотра элементов последовательности не была произведена ни одна
перестановка, иначе процесс повторяется. Проверка на наличие или
отсутствие перестановок осуществляется посредством признака
окончания процесса сортировки, который показывает, были перестановки в парах или нет. Рассмотренный метод обеспечивает вполне приемлемую скорость сортировки [3].
Пример 2.7
Составить алгоритм и программу упорядочения одномерного
массива A11 в порядке возрастания значений его элементов методом
«пузырька».
Схема алгоритма и текст программы решения задачи приведены
на рис. 2.9.
К задачам сортировки относятся перестановка элементов массива и перестановка строк (столбцов) матрицы в соответствии с некоторым заданным критерием.
Пример 2.8
Переставить в одномерном массиве A9 элементы с четными и нечетными номерами.
Решение: перестановка четных и нечетных элементов в массиве
осуществляется в каждой из четырех соседних пар. Последний 9-й
элемент остается на своем месте.
Схема алгоритма и текст программы решения задачи приведены
на рис. 2.10.
Пример 2.9
Переставить в матрице A5×5 минимальный элемент каждой строки с соответствующим элементом главной диагонали. Схема алгоритма и текст программы решения задачи приведены на рис. 2.11.
21
¦¹Ð¹ÄÇ
J
›»Ç½"J
K
J
'MBH5SVF
KJ
"K"K
¦¾Ë
¹
3"K
"K"K
"K3
'MBH'BMTF
K
'MBH
¦¾Ë
J
J
¹
Program Sort ( input, output );
Uses Crt;
Type
Mas = array [ 1..11 ] of real;
Var
A : Mas; R : real; i, j : byte;
Flag : boolean;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов ‘,
‘ матрицы A11 : ’ );
for i := 1 to 11 do
read ( A [ i ] );
{ Сортировка }
for i := 2 to 11 do
begin
Flag := True;
for j := 11 downto i do
if A [ j-1 ] > A [ j ]
then
begin
R := A [ j-1 ];
A [ j-1 ] := A [ j ];
A [ j ] := R;
Flag := False
end;
if Flag
then
break
end;
{ Вывод результатов }
writeln;
writeln ( ‘Упорядоченный массив A:’ );
for i := 1 to 11 do
write (A [ i ] : 5 : 2, ’ ‘ );
ReadKey
End.
›Ô»Ç½"J
J
£ÇƾÏ
Рис. 2.9. Схема алгоритма и текст программы упорядочения массива
22
¦¹Ð¹ÄÇ
J
›»Ç½"J
K
J
3"J
"J"J
"J3
J
J
›Ô»Ç½"J
Program Sort1 ( input, output );
Uses Crt;
Type
Mas = array [ 1..9 ] of real;
Var
A : Mas; R : real; i : byte;
Begin
ClrScr;
{ Ввод значений элементов массива A }
writeln ( ‘Введите значения элементов ‘,
‘ массива A 9 : ’ );
for i := 1 to 9 do
read ( A [ i ] );
{ Перестановка }
for i := 1 to 4 do
begin
R := A [ 2 * i - 1 ];
A [ 2 * i - 1 ] := A [ 2 * i ];
A [ 2 * i ] := R
end;
{ Вывод результатов }
writeln;
writeln ( ‘Массив A после перестановки:’ );
for i := 1 to 9 do
write ( A [ i ] : 5 : 2, ’ ‘ );
ReadKey
End.
J
£ÇƾÏ
Рис. 2.10. Схема алгоритма и текст программы перестановки четных и нечетных элементов одномерного массива
23
¦¹Ð¹ÄÇ
α
J
J
K
K
›»Ç½"JK
›Ô»Ç½"JK
K
K
J
J
J
£ÇƾÏ
+N
K
"JK"J+N
¦¾Ë
¹
+NK
K
3"JJ
"JJ "J+N
"J+N3
J
Program Sort2 ( input, output );
Type Mas = array [ 1..5, 1..5 ] of real;
Var A : Mas; R : real; i, j, Jm : byte;
Begin
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения эл-ов A 5x5 : ’ );
for i := 1 to 5 do
for j := 1 to 5 do
read ( A [ i, j ] );
{ Перестановка }
for i := 1 to 5 do
begin
Jm := 1;
for j := 2 to 5 do
if A [ i, j ] < A[ i, Jm ] then Jm := j;
R := A [ i, i ];
A [ i, i ] := A [ i, Jm ];
A [ i, Jm ] := R
end;
writeln; { Вывод результатов }
writeln ( ‘Матрица A после перестановки:’ );
for i := 1 to 5 do
begin
for j := 1 to 5 do write (A [ i, j ] : 5 : 2, ’ ‘ );
writeln
end
End.
α
Рис. 2.11. Схема алгоритма и текст программы перестановки минимальных элементов строк матриц с элементами главной диагонали
24
Пример 2.10
Переставить местами в матрице A6×4 1 и 5-ю строки. Схема алгоритма и текст программы решения задачи приведены на рис. 2.12.
¦¹Ð¹ÄÇ
J
K
›»Ç½"JK
K
J
K
3"K
"K"K
"K3
J
J
K
›Ô»Ç½"JK
K
Program Sort3 ( input, output );
Uses Crt;
Type
Mas = array [ 1..6, 1..4 ] of real;
Var
A : Mas; R : real; i, j : byte;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения эл-ов A 6x4 : ’ );
for i := 1 to 6 do
for j := 1 to 4 do
read ( A [ i, j ] );
{ Перестановка строк }
for j := 1 to 4 do
begin
R := A [ 1, j ];
A [ 1, j ] := A [ 5, j ];
A [ 5, j ] := R
end;
{ Вывод результатов }
writeln;
writeln ( ‘Матрица A после перестановки:’ );
for i := 1 to 6 do
begin
for j := 1 to 4 do write (A [ i, j ] : 5 : 2, ’ ‘ );
writeln
end;
ReadKey
End.
J
£ÇƾÏ
Рис. 2.12. Схема алгоритма и текст программы решения примера 2.10
25
3. ОБРАБОТКА МАССИВОВ ДАННЫХ С ИСПОЛЬЗОВАНИЕМ
МОДУЛЬНОГО ПРИНЦИПА ПРОГРАММИРОВАНИЯ
Модульный принцип программирования позволяет при решении задачи использовать стандартные или разработанные пользователем программные фрагменты (процедуры, функции, библиотеки и т. п.) для реализации ряда типовых или иных подзадач, встречающихся обычно не один раз по ходу решения основной задачи.
Этот принцип в упрощенном виде уже применялся нами при составлении текста программ, в которых использовались, например, стандартные арифметические функции, а также процедуры и функции
модуля CRT, являющиеся подмножеством стандартных средств
языка Паскаль.
Рассмотрим на примере два подхода к решению одной и той же
задачи обработки массивов данных.
Пример 3.1
Ввести значения элементов одномерного массива A9. Элементы
массива B9 вычисляются по формуле: bi = 1 + sin(2i) i = 1, ..., 9.
Найти значения максимальных элементов в каждом из массивов.
Вывести промежуточные и окончательные результаты расчетов.
Решение:
В ариа н т 1. Составим схему алгоритма и программу решения
задачи, последовательно выполняя все указанные требования
(рис. 3.1 и 3.2).
В ариа н т 2. Перед алгоритмизацией задачи проведем ее анализ.
В задаче (основном процессе) можно выделить дважды встречающуюся подзадачу (подпроцесс) нахождения значения максимального
элемента в одномерном массиве. Решение этой подзадачи можно
оформить в виде функции, на которую необходимо организовать две
ссылки (отдельно для массива A и массива B) из основного блока
программы. Схема алгоритма и программа решения задачи приведены на рис. 3.3 и 3.4 соответственно.
На втором варианте решения следует остановиться подробнее.
Во-первых, о введенных обозначениях. Maximum – имя функции,
используемой для нахождения максимального элемента в одномерном массиве. Z и n – внутренние имена использующихся в функции
так называемых формальных параметров, причем Z – это одномерный массив размерностью n . Zmax – так называемый локальный
параметр, который определен внутри функции Maximum для исключения авторекурсии (см. подразд. 1.3). Во-вторых, действие *)
необходимо для правильной работы функции.
26
¦¹Ð¹ÄÇ
α
Jc
#NBY#
›»Ç½"J
Jc
J
#J#NBY
¦¾Ë
¹
#NBY#J
Jc
#JTJOJ
J
›Ô»Ç½#J
›Ô»Ç½#NBY
J
£ÇƾÏ
"NBY"
Jc
"J"NBY
¦¾Ë
¹
"NBY"J
J
›Ô»Ç½"NBY
α
Рис. 3.1. Схема алгоритма нахождения максимальных элементов массивов
27
Program Massiv1 ( input, output );
Uses Crt;
Type
Mas = array [ 1..9 ] of real;
Var
A, B : Mas;
i : byte; Amax, Bmax : real;
Begin
ClrScr;
{ Ввод значений элементов исходного массива }
writeln ( ‘Введите значения элементов массива A 9 : ’ );
for i := 1 to 9 do
read ( A [ i ] );
{ Вычисление и вывод значений элементов массива B}
writeln;
writeln ( ‘Массив B 9 : ’ );
for i := 1 to 9 do
begin
B [ i ] := 1+ sin ( 2 * i );
write ( B [ i ] : 5 : 2, ‘ ‘ )
end;
{ Нахождение Amax }
Amax := A [ 1 ];
for i := 2 to 9 do
if A [ i ] > Amax then Amax := A [ i ];
{ Вывод значения Amax }
writeln;
write ( ‘Amax=’, Amax : 5 : 2 );
{ Нахождение Bmax }
Bmax := B [ 1 ];
for i := 2 to 9 do
if B [ i ] > Bmax then Bmax := B [ i ];
{ Вывод значения Bmax }
write ( ‘ Bmax=’, Bmax : 5 : 2 );
ReadKey
End.
Рис. 3.2. Текст программы нахождения максимальных элементов массивов
Функция Maximum инициируется из основного блока программы посредством упоминания ее имени с указанием так называемых
фактических параметров (рис. 3.4, в операторе **) – A и 9, в операторе ***) – B и 9).
Как уже отмечалось, кроме функции, предназначенной для вычисления единственного скалярного значения, в языке Паскаль
предусмотрена возможность использования процедуры для получения множественных результатов (например, массивов данных).
Рассмотрим на примере два подхода к решению еще одной задачи обработки массивов данных.
Пример 3.2
Ввести значения элементов матрицы A9×11. Элементы матрицы
B9×11 вычисляются по формуле: bij = cos(i + j), i = 1, ..., 9, j = 1, ..., 11.
28
§ÊÆÇ»ÆǺÄÇÃ
­ÌÆÃÏÁØ.BYJNVN;O
¦¹Ð¹ÄÇ
¦¹Ð¹ÄÇ
Jc
;NBY;
›»Ç½"J
JcO
J
¦¾Ë
;J;NBY
Jc
¹
;NBY;J
#JTJOJ
›Ô»Ç½#J
J
J
.BYJNVN;NBY
£ÇƾÏ
"NBY.BYJNVN"
Вывод "NBY
#NBY.BYJNVN#
›Ô»Ç½#NBY
£ÇƾÏ
Рис. 3.3. Схемы алгоритмов основного блока и функции
29
Program Massiv2 ( input, output );
Uses Crt;
Type
Mas = array [ 1..9 ] of real;
Var
A, B : Mas;
i : byte; Amax, Bmax : real;
{ Функция Maximum }
Function Maximum ( Z : Mas; n : byte ) : real;
Var
Zmax : real; i : byte;
begin
Zmax := Z [ 1 ];
for i := 2 to n do
if Z [ i ] > Zmax then Zmax := Z [ i ];
Maximum := Zmax { * обязательное действие !!! }
end;
{ Основной блок }
Begin
ClrScr;
{ Ввод значений элементов исходного массива }
writeln ( ‘Введите значения элементов массива A 9 : ’ );
for i := 1 to 9 do
read ( A [ i ] );
{ Вычисление и вывод значений элементов массива B}
writeln;
writeln ( ‘Массив B 9 : ’ );
for i := 1 to 9 do
begin
B [ i ] := 1+ sin ( 2 * i );
write ( B [ i ] : 5 : 2, ‘ ‘ )
end;
{ Обращение к функции Maximum для нахождения Amax }
Amax := Maximum ( A, 9 );
{ ** }
{ Вывод значения Amax }
writeln;
write ( ‘Amax=’, Amax : 5 : 2 );
{ Обращение к функции Maximum для нахождения Bmax }
Bmax := Maximum ( B, 9 );
{ *** }
{ Вывод значения Bmax }
write ( ‘ Bmax=’, Bmax : 5 : 2 );
ReadKey
End.
Рис. 3.4. Текст программы с использованием функции
В каждой из матриц упорядочить по возрастанию модулей значений
элементов 5-ю строку (матрицы А1 и В1 соответственно). Вывести
промежуточные и окончательные результаты расчетов.
Решение.
В а р и а н т 1. Составим схему алгоритма и программу решения
задачи, последовательно выполняя все указанные требования (рис. 3.5
и 3.6).
30
¦¹Ð¹ÄÇ
α
Jc
3"K
Kc
"K" K
›»Ç½"JK
"K3
"JK"JK
'MBH'BMTF
β
K
K
J
'MBH
¹
¦¾Ë
Jc
J
Kc
#JKDPTJK
Jc
#JK#JK
Kc
›Ô»Ç½#JK
›Ô»Ç½"JK
K
K
J
J
Jc
Jc
'MBH5SVF
'MBH5SVF
KJ
KJ
¦¾Ë
]"K]]"K]
¹
α
¦¾Ë
]#K]]#K]
β
¹
γ
δ
Рис. 3.5. Схема алгоритма упорядочения строк матриц (начало)
31
γ
β
3#K
#K#K
#K3
'MBH'BMTF
K
¹
'MBH
¦¾Ë
J
Jc
Kc
›Ô»Ç½#JK
K
J
£ÇƾÏ
Рис. 3.5. Схема алгоритма упорядочения строк матриц (окончание)
32
Program Sort4 ( input, output );
Uses Crt;
Type
Mas = array [ 1..9, 1..11 ] of real;
Var
A, B, A1, B1 : Mas;
i, j : byte; R : real; Flag : boolean;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов матрицы A 9x11 : ’ );
for i := 1 to 9 do
for j := 1 to 11 do
begin
read ( A [ i, j ] );
A1 [ i, j ] := A [ i, j ]
end;
{ Вычисление и вывод значений элементов матрицы B}
writeln;
writeln ( ‘Матрица B 9x11 : ’ );
for i := 1 to 9 do
begin
for j := 1 to 11 do
begin
B [ i, j ] := cos ( i + j );
B1 [ i, j ] := B [ i, j ];
write ( B [ i, j ] : 5 : 2, ‘ ‘ )
end;
writeln
end;
{ Сортировка 5-й строки матрицы A1 ( копии A ) }
for i := 2 to 11 do
begin
Flag := True;
for j := 11 downto i do
if abs ( A1 [ 5, j-1 ] ) > abs ( A1 [ 5, j ] )
then
begin
R := A1 [ 5, j-1 ];
A1 [ 5, j-1 ] := A1 [ 5, j ];
A1 [ 5, j ] := R;
Flag := False
end;
if Flag then Break
end;
{ Вывод значений элементов матрицы A1 }
writeln
writeln ( ‘Матрица A1 9x11 : ’ );
for i := 1 to 9 do
begin
for j := 1 to 11 do
write ( A1 [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end;
{ Сортировка 5-й строки матрицы B1 ( копии B ) }
Рис. 3.6. Текст программы упорядочения строк матриц (начало)
33
for i := 2 to 11 do
begin
Flag := True;
for j := 11 downto i do
if abs ( B1 [ 5, j-1 ] ) > abs ( B1 [ 5, j ] )
then
begin
R := B1 [ 5, j-1 ];
B1 [ 5, j-1 ] := B1 [ 5, j ];
B1 [ 5, j ] := R;
Flag := False
end;
if Flag then Break
end;
writeln;
{ Вывод значений элементов матрицы B1 }
writeln ( ‘Матрица B1 9x11 : ’ );
for i := 1 to 9 do
begin
for j := 1 to 11 do
write ( B1 [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end
End.
Рис. 3.6. Текст программы упорядочения строк матриц (окончание)
В а р и а н т 2. Перед алгоритмизацией задачи проведем ее анализ. В задаче можно выделить дважды встречающуюся подзадачу
сортировки (упорядочения) строки матрицы по возрастанию модулей значений ее элементов. Решение этой подзадачи можно оформить в виде процедуры, на которую необходимо организовать две
ссылки (отдельно для матрицы A и матрицы B) из основного блока
программы. Схемы алгоритмов и программа решения задачи представлены на рис. 3.7, 3.8 и 3.9.
Прокомментируем некоторые используемые обозначения. В процедуре упорядочения строки матрицы Upor ( Z, k, m, n, Z1 ) определены следующие формальные параметры: Z – исходный массив
(матрица размером 9 × 11); k – номер строки матрицы, элементы которой подлежат сортировке; m и n – число строк и число столбцов
исходной и результирующей матриц; Z1 – результирующая матрица с упорядоченной k-й строкой.
Примечание. В тексте программы, приведенной на рис. 3.9, вме­
сто фрагмента { * } можно записать один оператор – Z1 := Z; . В этом
случае будет также произведено копирование элементов массива Z
в Z1, но без явного указания индексов. Это позволит сократить программный код и не передавать в процедуру Upor параметр m, задающий число строк матриц.
34
¦¹Ð¹ÄÇ
Jc
Kc
›»Ç½"JK
α
6QPS##
K
Jc
J
Kc
Jc
›Ô»Ç½#JK
Kc
K
#JKDPTJK
J
›Ô»Ç½#JK
£ÇƾÏ
K
J
6QPS""
Jc
Kc
›Ô»Ç½"JK
K
J
α
Рис. 3.7. Схема алгоритма основного блока решения задачи упорядочения
строк матриц
35
¦¹Ð¹ÄÇ
JcN
KcO
;JK;JK
K
J
JcO
'MBH5SVF
KOJ
];LK]];LK]
¦¾Ë
¹
3;LK
;LK;LK
;LK3
'MBH'BMTF
K
'MBH
¹
¦¾Ë
J
£ÇƾÏ
Рис. 3.8. Схема алгоритма процедуры упорядочения строки матрицы Upor
36
Program Sort5 ( input, output );
Uses Crt;
Type
Mas = array [ 1..9, 1..11 ] of real;
Var
A, B, A1, B1 : Mas;
i, j : byte;
{ Процедура упорядочения строки матрицы }
Procedure Upor ( Z : Mas; k, m, n : byte; var Z1 : Mas);
Var
R : real; Flag : boolean; i, j : byte;
begin
for i := 1 to m do
{*}
for j := 1 to n do
{*}
Z1 [ i, j ] := Z [ i, j ];
{*}
for i := 2 to n do
begin
Flag := True;
for j := n downto i do
if abs ( Z1 [ k, j-1 ] ) > abs ( Z1 [ k, j ] )
then
begin
R := Z1 [ k, j-1 ];
Z1 [ k, j-1 ] := Z1 [ k, j ];
Z1 [ k, j ] := R;
Flag := False
end;
if Flag then Break
end
end;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов матрицы A 9x11 : ’ );
for i := 1 to 9 do
for j := 1 to 11 do
read ( A [ i, j ] );
{ Вычисление и вывод значений элементов матрицы B}
writeln;
writeln ( ‘Матрица B 9x11 : ’ );
for i := 1 to 9 do
begin
for j := 1 to 11 do
begin
B [ i, j ] := cos ( i + j );
write ( B [ i, j ] : 5 : 2, ‘ ‘ )
end;
writeln
end;
{ Обращение к процедуре Upor }
Upor ( A, 5, 9, 11, A1);
{ Вывод значений элементов матрицы A1 }
writeln;
writeln ( ‘Матрица A1 9x11 : ’ );
for i := 1 to 9 do
Рис. 3.9. Текст программы упорядочения строк матриц (начало)
37
begin
for j := 1 to 11 do
write ( A1 [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end;
{ Обращение к процедуре Upor }
Upor ( B, 5, 9, 11, B1);
{ Вывод значений элементов матрицы B1 }
writeln;
writeln ( ‘Матрица B1 9x11 : ’ );
for i := 1 to 9 do
begin
for j := 1 to 11 do
write ( B1 [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end
End.
Рис. 3.9. Текст программы упорядочения строк матриц (окончание)
Для получения дополнительных сведений о методах и приемах,
используемых при решении задач обработки массивов данных,
можно воспользоваться следующими работами: этап алгоритмизации – [5, 6, 7]; этап программирования – [2, 3, 4] и приведенными
в конце методического материала ссылками на Интернет-ресурсы.
38
4. МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
Цель работ: 1) ознакомление с правилами и приемами обработки массивов данных; 2) применение возможностей модульного принципа программирования; 3) освоение приемов алгоритмизации
типовых вычислительных задач; 4) приобретение навыков программирования задач на языке Паскаль.
Содержание работ: а) математическое описание задачи; б) построение схемы алгоритма (схем алгоритмов) решения задачи в соответствии с заданием; в) составление программы, согласно алгоритму; г) отладка программы и получение результатов; д) составление
отчета о работе и его защита.
Содержание отчета: титульный лист установленного образца; задание на лабораторную работу; математическая часть (описание методов обработки массивов данных); схема алгоритма в соответствии
с ГОСТ и программа решения задачи; результаты, представленные
в соответствии с предлагаемой формой вывода. Отчет оформляется на
листах формата А4 (297 × 210). Подготовленный отчет защищается
и сдается преподавателю для получения зачета по работе. Защита отчета включает в себя ответы на вопросы по теме лабораторной работы.
Лабораторная работа № 4
Обработка массивов данных
Для пояснения хода выполнения лабораторной работы рассмотрим пример (табл. 4.1).
В соответствии с условием составим схему алгоритма и программу решения задачи на языке Паскаль (рис. 4.1 и 4.2 соответственно).
Таблица 4.1. Пример задания к лабораторной работе № 4
№
вари- Входной
анта массив
33
A4×4
Обработка массивов данных
Формируемый массив
Условие задачи
B4×4 , где
Найти след матрицы A (SpA)
и след матрицы B (SpB). Опреде0.5,
если
i
>
j

лить матрицу C, исходя из
bij = 
1 + sin(i − j), иначе условия: если SpA > SpB, то
C = SpA × B, иначе – C = SpB × A
i = 1,..., 4, j = 1,..., 4
Вывести: B, SpA, SpB, C
39
¦¹Ð¹ÄÇ
α
Jc
4Q##
Kc
Jc
›»Ç½"JK
4Q#4Q##JJ
J
J
Jc
›Ô»Ç½4Q#
Kc
4Q"4Q#
¹
JK
#JK
¦¾Ë
#JTJOJrK
Jc
¦¾Ë
Jc
Kc
$JK4Q#"JK
›Ô»Ç½#JK
K
K
J
J
4Q""
Jc
Jc
Kc
4Q"4Q""JJ
›Ô»Ç½$JK
J
K
›Ô»Ç½4Q"
J
α
£ÇƾÏ
Рис. 4.1. Схема алгоритма решения примера к ЛР № 4
40
¹
Kc
$JK4Q"#JK
K
J
{ $R+ }
Program LabRab4 ( input, output );
Uses Crt;
Type
Mas = array [ 1..4, 1..4 ] of real;
Var
A, B, C : Mas;
SpA, SpB : real; i, j : byte;
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов матрицы A 4x4 : ’ );
for i := 1 to 4 do
for j := 1 to 4 do
read ( A [ i, j ] );
{ Вычисление и вывод значений элементов матрицы B }
writeln;
writeln ( ‘Матрица B 4x4 : ’ );
for i := 1 to 4 do
begin
for j := 1 to 4 do
begin
if i > j
then
B [ i, j ] := 0.5
else
B [ i, j ] := 1 + sin ( i – j );
write ( B [ i, j ] : 5 : 2, ‘ ‘ )
end;
writeln
end;
{ Вычисление и вывод значения SpA }
SpA := A [ 1, 1 ];
for i := 2 to 4 do
SpA := SpA + A [ i, i ];
writeln;
write ( ‘SpA = ‘, SpA : 5 : 2, ‘ ‘ );
{ Вычисление и вывод значения SpB }
SpB := B [ 1, 1 ];
for i := 2 to 4 do
SpB := SpB + B [ i, i ];
writeln ( ‘SpB = ‘, SpB : 5 : 2 );
{ Проверка условия и выбор дальнейшего пути решения }
if SpA > SpB
then
for i := 1 to 4 do
for j := 1 to 4 do
C [ i, j ] := SpA * B [ i, j ]
else
for i := 1 to 4 do
for j := 1 to 4 do
C [ i, j ] := SpB * A [ i, j ];
{ Вывод значений элементов матрицы C }
writeln;
writeln ( ‘Матрица C 4x4 : ’ );
Рис. 4.2. Текст программы решения примера (начало) к ЛР № 4
41
for i := 1 to 4 do
begin
for j := 1 to 4 do
write ( C [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end;
ReadKey
End.
Рис. 4.2. Текст программы решения примера (окончание) к ЛР № 4
В тексте программы решения примера использована директива
компилятору { $R+ } для генерации кода проверки возможного выхода индексов массивов за диапазон допустимых значений, Например, в приведенном фрагменте программы
...
for i := 1 to 5 do { диапазон изменения индекса i – от 1 до 4 !!! }
begin
for j := 1 to 4 do
write ( C [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end;
...
в первой строке допущена ошибка. В этом случае программа будет
«аварийно» завершена, и выдано сообщение об ошибке – Error 201:
Range check error .
Использование указанной директивы может быть полезным при
написании и отладке программ обработки данных, типы которых
определяются диапазоном допустимых значений.
Учебные задания к лабораторной работе № 4 приведены в табл. 4.2.
1
42
Обработка массивов данных
Входной
массив
№ варианта
Таблица 4.2. Учебные задания к лабораторной работе № 4
Формируемый массив
A5×4 B ,
5×4
Условие задачи
Найти max элементы матриц A
(MaxA) и B (MaxB). Определить
cos(i + j), если i > j матрицу C, исходя из условия: если
bij = 
MaxA > MaxB, то C = A × MaxA,
sin(i − j), иначе
иначе – C = B × MaxB
i = 1, ..., 5, j = 1, ..., 4
Вывести: B, MaxA, MaxB, C
где
Продолжение табл. 4.2
№ варианта
Входной
массив
Обработка массивов данных
Формируемый массив
2
A5×5
B5, где
bi = sin(ln(i) + cos(i))
i = 1, ..., 5
3
A4×4
B4×4 , где
aij − aji , если i = j
bij = 
aij + aji , иначе
i = 1,..., 4, j = 1,..., 4
4
A4
B4 , где
bi = sin(ai ) − cos(ai )
i = 1,..., 4
5
A5×5
B5×5, где
1 + 2j, если i ≠ j
bij = 
1 − i, иначе
i = 1,...,5, j = 1,...,5
6
A4
Условие задачи
Определить номер столбца матрицы A, содержащего min элемент
(JM). Оформить этот столбец в виде
массива A1. Упорядочить массивы A1 и B в порядке убывания абсолютных значений элементов (массивы A2 и B1 соответственно)
Вывести: B, JM, A1, A2, B1
Определить номера строк матриц A
(IA) и B (IB), содержащих max
элементы. Если IA > IB, то поменять
местами 1 и IA-ю строки в матрице
A, иначе – 1 и IB-ю строки в матрице
B (матрица C )
Вывести: B, IA, IB, C
Упорядочить массивы A и B в порядке возрастания значений элементов
(массивы A1 и B1 соответственно).
Вычислить значение произведения
max элемента массива A1 на min
элемент массива B1 (С )
Вывести: B, A1, B1, C
Вычислить значения следа матрицы
A (SpA) и следа матрицы B (SpB).
Вычислить значения суммы положительных и суммы отрицательных элементов (SP, SN) матрицы A,
если SpA > SpB, или матрицы B –
иначе
Вывести: B, SpA, SpB, SP, SN
Сформировать массив B1 из элементов главной диагонали матрицы B.
sin(i + j), если i = j Упорядочить массивы A и B1 в поbij = 
1 − cos(i + j), иначе рядке убывания значений элементов
(массивы A1 и B2 соответственно).
i = 1,..., 4, j = 1,..., 4
Вычислить значение величины
C = A1 × B2T
Вывести: B, B1, A1, B2, C
B4×4 , где
43
Продолжение табл. 4.2
№ варианта
Входной
массив
Обработка массивов данных
7
A5×4
Формируемый массив
B4 , где
bi = sin(i) + cos(i)
i = 1,..., 4
8
A4×4
B4×4 , где
0, если i = j
bij = 
i + j, иначе
i = 1,..., 4, j = 1,..., 4
9
A7
B7 , где
bi = (−1)i × ln(i + 1.5)
i = 1,...,7
10 A6×6
B6×6 , где
bij = aij × sin(i + j)
i = 1,...,6, j = 1,...,6
11 A5×5
B5×5, где
bij = i × cos(i + j)
i = 1,...,5, j = 1,...,5
12 A4×4
B4×4 , где
bij = sin(i) − cos( j)
i = 1,..., 4, j = 1,..., 4
44
Условие задачи
Найти номер строки IM матрицы A,
содержащей max элемент. Выделить
эту строку в массив A1. Поменять
местами в массивах A1 и B элементы
с четными и нечетными номерами
(векторы A2 и B1 соответственно)
Вывести: IM, B, A1, A2, B1
Найти max элементы матриц A и B
(MaxA и MaxB соответственно). Если
MaxA > MaxB, то вычислить
C = A × B, иначе вычислить C = B × A
Вывести: MaxA, B, MaxB, C
Упорядочить массивы A и B в порядке убывания значений модулей
элементов (массивы A1 и B1 соответственно). Вычислить значение суммы
(S) 2-го элемента массива A1 и 5-го
элемента B1
Вывести: B, A1, B1, S
Определить номер столбца матрицы
B, содержащего min элемент (JB).
Если JB < 3, то вычислить
C = JB × A × B, иначе –
C = JB × B × A
Вывести: B, JB, C
Для каждой из матриц A и B найти
количество элементов, больших 2.5
(NA и NB соответственно). Переставить местами строки с четными
и нечетными номерами в матрице A,
если NA > NB, или в B – иначе
(матрица C)
Вывести: B, NA, NB, C
Построить матрицу B1 из матрицы B
путем перестановки min элемента
каждой строки с элементом главной
диагонали. Найти max элементы
главной диагонали матрицы A
(MDA) и главной диагонали матрицы
B1 (MDB1)
Вывести: B, B1, MDA, MDB1
Обработка массивов данных
Входной
массив
№ варианта
Продолжение табл. 4.2
Формируемый массив
Условие задачи
13 A5×3 B5×3, где
14
A4
15 A5×4
16
A5
17 A4×6
Определить номера столбцов матриц
A (JA) и B (JB), содержащих max
ln(i), если i > j
элементы. Оформить эти столбцы
bij = 
aij + ln(i + j), иначе в виде одномерных массивов (массивы A1 и B1 соответственно) и упоряi = 1,...,5, j = 1,...,3
дочить их в порядке возрастания
значений элементов (массивы A2
и B2 соответственно)
Вывести: JA, B, JB, A1, B1, A2, B2
Найти max элемент в матрице B
B4×4 , где
(MaxB). Если MaxB > 5.2, то выдеai − j, если i = j
лить в отдельный массив 2-ю строку
bij = 
матрицы B (массив B1) и поменять
i − aj , иначе
в нем местами крайние элементы
i = 1,..., 4, j = 1,..., 4
(массив B2), иначе поменять местами
крайние элементы в массиве A
(массив A1)
Вывести: B, MaxB, B1 (или A1)
Сформировать массив A1 из min
B5×4 , где
элементов строк матрицы A и массив
aij /2, если i ≤ j
B1 из min элементов строк матрицы
bij =  2
B. Найти max элементы массивов A1
aij , иначе
(MaxA1) и B1 (MaxB1)
i = 1,...,5, j = 1,..., 4
Вывести: B, A1, B1, MaxA1, MaxB1
Сформировать
массив C, состоящий
B5, где
из
элементов
c
ij = ai × aj, i = 1, …, 5;
bi = sin2 (i) + 0.5
j = 1, …, 5. Найти min элементы
массивов A и B (MinA и MinB соотi = 1,...,5
ветственно). Если MinA > MinB, то
сформировать матрицу C1 из матрицы C, заменив cij на ai, иначе – на bj
Вывести: B, C, MinA, MinB, C1
Определить номера строк матриц A
B4×6 , где
и B, содержащих min элементы (IA
i + 3, если i ≥ j
и IB соответственно). Если IA = IB,
bij = 
сформировать матрицу C из матрицы
 j − 2, иначе
A, в которой строка с номером IA
i = 1,..., 4, j = 1,...,6
упорядочена по убыванию значений
элементов. Иначе получить C из B,
упорядочив в B по убыванию значений элементов строку с номером IB
Вывести: B, IA, IB, C
45
Обработка массивов данных
Входной
массив
№ варианта
Продолжение табл. 4.2
18 A5×5
19
A5
Формируемый массив
Сформировать матрицы A1 = AT
и B1 = BT. Вычислить значения следа
aij + 2, если aij ≥ 0 матрицы A1 (SpA1) и следа матрицы
bij = 
B1 (SpB1). Если SpA1–SpB1 > 0, то
aij − 2, иначе
найти матрицу C = A1 × A, иначе –
i = 1,...,5, j = 1,...,5
C = B × B1
Вывести: B, A1, B1, SpA1, SpB1, C
B5×5, где
B5, где
bi = sin(ln(i))
i = 1,...,5
20
A4
B5×4 , где
bij = sin(i) × cos(aj )
i = 1,...,5, j = 1,..., 4
21 A3×6
B3×6 , где
3 × j, если i = j
bij = 
sin(2i), иначе
i = 1,...,3, j = 1,...,6
22 A4×9
B9, где
bi = sin(i − cos(i))
i = 1,..., 9
46
Условие задачи
Упорядочить массив A в порядке
убывания значений квадратов
элементов (A1). Найти сумму
элементов массива A (SA). Если
SA > 100, то упорядочить массив B
в том же порядке, что и A (B1), иначе
найти сумму элементов массива
B (SB)
Вывести: B, A1, SA, B1 или SB
Определить номер строки матрицы
B, содержащей min элемент (IM).
Оформить эту строку в виде массива
C. Если IM = 2, то вычислить
C1 = IM × A, иначе – C1 = IM × C
Вывести: B, IM, C, C1
Определить номера строк матриц A
(IA) и B (IB), содержащих max
элементы. Если IA < IB–1, то
сформировать матрицу C из A,
в которой в строке с номером IA
переставлены местами элементы
с четными и нечетными номерами.
Иначе получить C из B, проделав
такую же перестановку в строке
с номером IB
Вывести: B, IA, IB, C
Определить номер строки матрицы
A, содержащей min элемент (IM).
Оформить эту строку в виде массива
A1. Упорядочить массивы A1 и B
в порядке убывания значений
элементов с четными номерами
(массивы A2 и B1 соответственно)
Вывести: B, IM, A1, A2, B1
Обработка массивов данных
Входной
массив
№ варианта
Окончание табл. 4.2
23 A9×4
24 A4×4
25 A4×5
Формируемый массив
Условие задачи
Определить номер столбца матрицы
A, содержащего max элемент (JM).
bi = log(2i + cos(i))
Оформить этот столбец в виде
массива A1. Упорядочить массивы
i = 1,..., 9
A1 и B в порядке возрастания
значений элементов с нечетными
номерами (массивы A2 и B1 соответственно)
Вывести: B, JM, A1, A2, B1
Выделить главные диагонали матриц
B4×4 , где
A и B в одномерные массивы (A1 и B1
2i + j, если i > j
соответственно). Упорядочить
bij = 
массивы A1 и B1 в порядке убывания
i + 2j, иначе
значений элементов (массивы A2
i = 1,..., 4, j = 1,..., 4
и B2 соответственно). Найти среднее
арифметическое значение элементов
массива A2 (SrA2) и среднее арифметическое значение элементов массива
B1 (SrB2)
Вывести: B, A1, B1, A2, B2, SrA1,
SrB2
Сформировать вектор A1, состоящий
B5×4 , где
из max элементов строк матрицы A
cos(i), если i + j < 4 и вектор B1, состоящий из max
bij = 
элементов столбцов матрицы B.
sin(i + j), иначе
Вычислить значение величины
i = 1,...,5, j = 1,..., 4
C = B1 × A1T
Вывести: B, A1, B1, C
B9, где
47
Лабораторная работа № 5
Обработка массивов данных С ИСПОЛЬЗОВАНИЕМ
МОДУЛЬНОГО ПРИНЦИПА ПРОГРАММИРРОВАНИЯ
Для пояснения хода выполнения лабораторной работы рассмотрим пример задания, приведенного в табл. 4.1. В этом задании (основной задаче) выделим две подзадачи: а) нахождение следа матрицы; б) определение матрицы C. Будем считать, что одна из этих подзадач будет реализована с использованием процедуры (определение
матрицы C), а другая – с использованием функции (нахождение
следа матрицы). В конечном итоге задание к лабораторной работе
№ 5 будет выглядеть следующим образом (табл. 4.3).
В соответствии с условием составим схемы алгоритмов основного
блока, процедуры, функции и программу решения задачи на языке
Паскаль (рис. 4.3, 4.4, 4.5 и 4.6 соответственно).
Таблица 4.3. Пример задания к лабораторной работе № 5
Обработка массивов данных с использованием модульного
принципа программирования
Процедура
Функция
№ варианта
ЛР 4
33
Определение матрицы C
Нахождение следа матрицы
¦¹Ð¹ÄÇ
α
Jc
›Ô»Ç½ #
JK
Jc
K
›»Ç½"JK
J
J
4Q"4MFE"
Jc
›Ô»Ç½4Q"
Kc
JK
4Q#4MFE #
¹
#JK
¦¾Ë
#JTJOJrK
α
›Ô»Ç½4Q#
4Q"4Q#
¦¾Ë
β
Рис. 4.3. Схема алгоритма основного блока (начало)
48
¹
γ
γ
β
6NO 4Q"#$
6NO 4Q#"$
Jc
Kc
›Ô»Ç½$JK
K
J
£ÇƾÏ
Рис. 4.3. Схема алгоритма основного блока (окончание)
¦¹Ð¹ÄÇ
¦¹Ð¹ÄÇ
4Q;;
JcN
JcO
KcO
4Q;4Q;;JJ
$JK4Q;;JK
J
K
4MFE4Q;
J
£ÇƾÏ
£ÇƾÏ
Рис. 4.4. Схема алгоритма функции
Sled (Z, n)
Рис. 4.5. Схема алгоритма процедуры Umn (SpZ, Z, m, n, C)
49
{ $R+ }
Program LabRab5 ( input, output );
Uses Crt;
Type
Mas = array [ 1..4, 1..4 ] of real;
Var
A, B, C : Mas;
SpA, SpB : real; i, j : byte;
{ Функция вычисления значения следа матрицы }
Function Sled ( Z : Mas; n : byte ) : real;
Var
SpZ : real; i : byte;
begin
SpZ := Z [ 1, 1 ];
for i := 2 to n do
SpZ := SpZ + Z [ i, i ];
Sled := SpZ
end;
{ Процедура определения матрицы С }
Procedure Umn ( SpZ : real; Z : Mas; m, n : byte; var C : Mas );
Var
i, j : byte;
begin
for i := 1 to m do
for j := 1 to n do
C [ i, j ] := SpZ * Z [ i, j ];
end;
{ Основной блок }
Begin
ClrScr;
{ Ввод значений элементов матрицы A }
writeln ( ‘Введите значения элементов матрицы A 4x4 : ’ );
for i := 1 to 4 do
for j := 1 to 4 do
read ( A [ i, j ] );
{ Вычисление и вывод значений элементов матрицы B }
writeln;
writeln ( ‘Матрица B 4x4 : ’ );
for i := 1 to 4 do
begin
for j := 1 to 4 do
begin
if i > j
then
B [ i, j ] := 0.5
else
B [ i, j ] := 1 + sin ( i – j );
write ( B [ i, j ] : 5 : 2, ‘ ‘ )
end;
writeln
end;
{ Вычисление и вывод значения SpA }
SpA := Sled ( A, 4 );
writeln;
Рис. 4.6. Текст программы решения примера лабораторной работы № 5
(начало)
50
write ( ‘SpA = ‘, SpA : 5 : 2, ‘ ‘ );
{ Вычисление и вывод значения SpB }
SpB := Sled ( B, 4 );
writeln ( ‘SpB = ‘, SpB : 5 : 2 );
{ Проверка условия и выбор дальнейшего пути решения }
if SpA > SpB
then
Umn ( SpA, B, 4, 4, C )
else
Umn ( SpB, A, 4, 4, C );
{ Вывод значений элементов матрицы C }
writeln;
writeln ( ‘Матрица C 4x4 : ’ );
for i := 1 to 4 do
begin
for j := 1 to 4 do
write ( C [ i, j ] : 5 : 2, ‘ ‘ );
writeln
end;
ReadKey
End.
Рис. 4.6. Текст программы решения примера лабораторной работы № 5
(окончание)
Учебные задания к лабораторной работе № 5 формируются следующим образом. За основу берется соответствующее задание к лабораторной работе № 4. В нем выделяются подзадачи, которые
должны быть реализованы с использованием процедур и функций
языка Паскаль. Какие подзадачи и как их решение должно быть
реализовано, приведено в табл. 4.4.
№
варианта
ЛР 4
Таблица 4.4. Учебные задания к лабораторной работе № 5
Обработка массивов данных с использованием модульного принципа
программирования
Процедура
Функция
1
Умножение матрицы на скаляр
Поиск max элемента матрицы
2
Упорядочение массива в порядке убывания абсолютных
значений элементов
Перестановка строк в матрице
Определение номера столбца
матрицы, содержащего min
элемент
Определение номера строки
матрицы, содержащей max
элемент
Вычисление значения произведения двух скалярных величин
3
4
Упорядочение массива в порядке возрастания значений
элементов
51
№
варианта
ЛР 4
Продолжение табл. 4.4
5
6
7
8
9
10
Обработка массивов данных с использованием модульного принципа
программирования
Процедура
Вычисление значений суммы
положительных и суммы
отрицательных элементов
матрицы
Упорядочение массива в
порядке убывания значений
элементов
Перестановка в массиве элементов с четными и нечетными
номерами
Умножение матриц
Вычисление значения следа
матрицы
Упорядочение массива в порядке убывания значений модулей
элементов
Нахождение произведения
скаляра и двух матриц
Вычисление значения суммы
двух скалярных величин
11
Перестановка строк в матрице
12
Перестановка min элемента
каждой строки матрицы с
элементом главной диагонали
Упорядочение массива в порядке возрастания значений
элементов
Перестановка крайних элементов массива
13
14
Функция
Умножение векторов
Поиск номера строки матрицы,
содержащей max элемент
Поиск max элемента матрицы
Определение номера столбца
матрицы, содержащего min
элемент
Нахождение количества
элементов матрицы, больших
2.5
Поиск max элемента главной
диагонали матрицы
Определение номера столбца
матрицы, содержащего max
элемент
Поиск max элемента в матрице
15
Формирование массива из min
элементов строк матрицы
Поиск max элемента массива
16
Формирование матрицы C1
Поиск min элемента массива
17
Упорядочение строки матрицы
по убыванию значений элементов
1. Транспонирование матрицы
2. Умножение матриц
Определение номера строки
матрицы, содержащей min
элемент
Вычисление значения следа
матрицы
18
52
№
варианта
ЛР 4
Окончание табл. 4.4
19
20
21
22
23
24
25
Обработка массивов данных с использованием модульного принципа
программирования
Процедура
Упорядочение массива в порядке убывания значений квадратов элементов
Умножение скаляра на вектор
Функция
Нахождение суммы элементов
массива
Определение номера строки
матрицы, содержащей min
элемент
Перестановка в строке матрицы Определение номера строки
элементов с четными и нечетны- матрицы, содержащей max
ми номерами
элемент
Упорядочение массива в поряд- Определение номера строки
ке убывания значений элеменматрицы, содержащей min
тов с четными номерами
элемент
Упорядочение массива в поряд- Определение номера столбца
ке возрастания значений элематрицы, содержащего max
ментов с нечетными номерами
элемент
Упорядочение массива в поряд- Поиск среднего арифметическоке убывания значений элеменго значения элементов массива
тов
Формирование вектора, состоя- Умножение векторов
щего из max элементов строк
(столбцов) матрицы
Лабораторный практикум составлен в соответствии с рабочей
программой дисциплины «Информатика».
53
Библиографический список
1. Козенко С. Л. Информатика: лабораторный практикум / ГУАП.
СПб., 2007. Ч. 1. 68 с.
2. Немнюгин С. А. Turbo Pascal: практикум. СПб: Питер, 2004.
272 с.
3. Фаронов В. В. Turbo Pascal: учебное пособие. СПб: Питер, 2007.
367 с.
4. Фаронов В. В. Turbo Pascal 7.0. Практика программирования:
учебное пособие. ОМД ГРУПП, 2003. 432 с.
5. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: пер. с англ. М.: Мир, 1981. 368 с.
6. Кортмен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы.
Построение и анализ: пер. с англ. М.: Изд. дом «Вильямс», 2007.
1296 с.
7. Козенко С. Л. Алгоритмизация инженерных задач: методиче­
ские указания / ГУАП. СПб., 2005. 46 с.
Интернет-ресурсы
http://allprogramming.jino-net.ru/
http://fizmat.vspu.ru/pascal/
http://books.dore.ru/bs/f6sid54.html
http://mkskent.boom.ru/turbo/turbo.html
54
Учебное издание
Козенко Сергей Леонидович
ИНФОРМАТИКА
Часть 2
Лабораторный практикум
Редактор А. В. Семенчук
Верстальщик С. В. Барашкова
Сдано в набор 03.12.07. Подписано в печать 11.12.07. Формат 60 × 84 1/16.
Бумага офсетная. Печать офсетная. Усл.-печ. л. 3,25. Уч.-изд. л. 3,4.
Тираж 400 экз. Заказ №
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
853 Кб
Теги
kozenkov, informatika, ch2
1/--страниц
Пожаловаться на содержимое документа