Козенко С.Л. Алгоритмизация инженерных задач

Подождите немного. Документ загружается.

4. АЛГОРИТМИЗАЦИЯ ЗАДАЧ ЛИНЕЙНОЙ АЛГЕБРЫ

4.1. Общие положения

При решении прикладных задач часто возникает необходимость

производить вычисления, связанные с использованием основных

понятий линейной алгебры – матриц и векторов. Понятия «матри"

ца» и «вектор» хорошо известны, поэтому приводить их здесь не бу"

дем. Остановимся лишь на понятиях «матрица"строка» и «матрица"

столбец», которые встречаются в некоторых изданиях и употребля"

ются многими математиками.

Пусть задана некоторая матрица размерностью m´n, где m – коли"

чество строк, n – количество столбцов. Тогда, при m = 1 говорят о

матрице"строке, а при n = 1 – о матрице"столбце. Примеры обозначе"

ний: Q

1´n

– матрица"строка; Q

m´1

– матрица"столбец. В дальнейшем

размерность 1 в обозначении таких матриц будем опускать и считать

их векторами.

Как уже отмечалось в разд. 3, в языках программирования для

описания матриц используются двумерные массивы, а для описания

векторов – одномерные массивы. В связи с этим предлагаемый даль"

нейшему вниманию материал можно считать продолжением преды"

дущего раздела.

Рассмотрим типовые задачи линейной алгебры по обработке мат"

риц и векторов.

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

Матрица Q

m´n

называется транспонированной по отношению к

матрице R

n´m

, если элементы матриц Q и R связаны соотношениями

= r

, i = 1..m, j = 1..n.

Пример 4.1

Составить схему алгоритма поиска матрицы Q

m´n

, транспониро"

ванной по отношению к матрице R

n´m

Решение задачи показано на рис. 4.1.

4.3. Вычисление следа квадратной матрицы

След квадратной матрицы A

m´m

есть сумма элементов ее главной

диагонали:

Sp a1

Рис. 4.1. Схема алгоритма транспонирования матрицы (пример 4.1)

Пример 4.2

Составить схему алгоритма нахождения следа квадратной матри"

цы A

m´m

Решение. Для решения задачи можно снова воспользоваться

схемой алгоритма, приведенной на рис. 3.3. В этой схеме необходимо

произвести следующие изменения:

– удалить блоки 9, 10, 12;

– в блоке 3 вместо n написать m;

– в блоках 7, 11 и 14 вместо S написать Sp;

– в блоке 11 вместо A

написать A

ii.

4.4. Сложение матриц и векторов

Суммой двух матриц Q

m´n

и R

m´n

называется матрица Z

m´n

, эле"

менты которой вычисляются по формулам:

= q

+ r

, i = 1..m, j = 1..n.

При m = 1 (или n = 1) имеет место частный случай – сложение

векторов. Например,

= q

+ r

, i = 1..n.

Пример 4.3

Составить схему алгоритма нахождения матрицы Z

m´n

как суммы

двух матриц: Q

m´n

и R

m´n

Решение задачи показано на рис. 4.2.

Рис. 4.2. Схема алгоритма сложения двух матриц (пример 4.3)

Пример 4.4

Составить схему алгоритма нахождения вектора Z

как суммы

двух векторов: Q

и R

Решение. Для решения этой задачи можно воспользоваться схе"

мой алгоритма, приведенной на рис. 4.2. В этой схеме необходимо

произвести следующие изменения:

– удалить блоки 3, 5, 8, 11, 14 и 16;

– в блоках 4 и 10 вместо Q

записать Q

– в блоках 9 и 10 вместо R

записать R

– в блоках 10 и 15 вместо Z

записать Z

4.5. Умножение матриц и векторов

Произведением двух матриц Q

m´l

и R

l´n

называется матрица Z

m´n

элементы которой вычисляются следующим образом:

, 1.. , 1.. .

ij ik kj

zqrimjn1 21 1

Заметим, что перемножить можно только те матрицы, у которых

число столбцов первой совпадает с числом строк второй (в данном

случае – это размерность l ). Исходя из этого условия, допустимыми

являются следующие частные случаи:

а) при m = 1 – умножение матрицы(строки на матрицу. Резуль"

татом является матрица"строка, элементы которой вычисляются по

формуле:

,1...

jkkj

zqrjn12 1

б) при n = 1 – умножение матрицы на матрицу(столбец. Резуль"

татом является матрица"столбец, элементы которой вычисляются

по формуле

,1...

iikk

zqrim12 1

в) при m = 1 и n = 1 – умножение матрицы(строки на матрицу(

столбец. Результатом является скаляр, значение которого вычис"

ляется по формуле

zqr12

г) при l = 1 – умножение матрицы(столбца на матрицу(строку.

Результатом является матрица размерностью m´n, значения элемен"

тов которой вычисляются по формуле

= q

´ r

, i = 1..m, j = 1..n.

Пример 4.5

Составить схему алгоритма нахождения произведения двух мат"

риц: Q

m´l

и R

l´n

(матрица Z

m´n

Решение этой задачи приведено на рис. 4.3.

Нетрудно видеть, что все частные случаи, возникающие из задачи

умножения матриц, легко реализовать, опираясь на схему алгорит"

ма, приведенную на рис. 4.3. Внести изменения в эту схему с целью

Рис. 4.3. Схема алгоритма умножения двух матриц (пример 4.5)

представления соответствующих решений предлагается студенту са"

мостоятельно.

5. АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ ДАННЫХ

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

Понятие «подпроцесс» при решении инженерных задач встречается

очень часто и имеет различные трактовки. В нашем случае под терми"

ном «подпроцесс» будем понимать конечный набор действий (шагов),

направленных на решение подзадачи, выделенной из главной (основ"

ной) задачи. Алгоритмизация задач, в которых можно выделить одну

или несколько подзадач (встречающихся обычно не один раз по ходу

решения основной задачи), является полезным занятием для приобре"

тения навыков модульного принципа программирования.

Рассмотрим на примере два подхода к решению одной и той же

задачи обработки массивов данных.

Пример 5.1

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

. Элементы

массива B

вычисляются по формуле:

1sin(2*) 1...

biin12 1

Най"

ти значения максимальных элементов в каждом из массивов. Вывес"

ти промежуточные и окончательные результаты расчетов.

Решение

Вариант 1. Составим схему алгоритма решения задачи, последо"

вательно выполняя все указанные требования (рис. 5.1).

Вариант 2. Перед алгоритмизацией задачи проведем ее анализ. В

задаче (основном процессе) можно выделить дважды встречающуюся

подзадачу (подпроцесс) нахождения значения максимального элемен"

та в одномерном массиве. Решение этой подзадачи можно оформить в

виде отдельной схемы алгоритма, на которую необходимо организо"

вать две ссылки (отдельно для массива A и массива B) из схемы алго"

ритма решения основной задачи (рис. 5.2).

На втором варианте решения задачи следует остановиться под"

робнее.

Во"первых, о введенных обозначениях: Maximum – имя подпроцесса

нахождения значения максимального элемента в одномерном массиве;

Z и n – внутренние имена использующихся в подпроцессе так называе"

мых формальных параметров, причем Z – это одномерный массив

размерностью n. Подпроцесс Maximum инициируется из основного про"

цесса посредством упоминания имени подпроцесса с указанием так на"

зываемых фактических параметров (рис. 5.2, блок 9 – A и n, блок

11 – B и n). Z

max

– так называемый локальный параметр, который

может использоваться только внутри подпроцесса.

Во"вторых, подпроцесс Maximum можно с определенной степенью

условности отождествить с понятием «функция». Функция – это оп"

Рис. 5.1. Схема алгоритма решения примера 5.1 (вариант 1)

ределенная структура в языках программирования, имеющая харак"

терные свойства и использующаяся для реализации модульного прин"

ципа программирования.

В разных языках программирования свойства функций могут от"

личаться. Не вдаваясь в подробности (все"таки речь идет лишь об

алгоритмизации, а не о программировании), будем считать, что при

решении примера 5.1 (вариант 2) использована «функция» с возвра"

Рис. 5.2. Схемы алгоритмов решения примера 5.1 (вариант 2)

том значения посредством ее имени. В этом случае действие, отобра"

женное в блоке 7 рис. 5.2 (в схеме алгоритма подпроцесса Maximum),

является обязательным для корректной работы «функции».

Рассмотрим пример, иллюстрирующий другие возможности ис"

пользования подпроцессов.

Пример 5.2

Ввести значения элементов двумерного массива A

m´n

. Элементы

массива B

m´n

вычисляются по формуле:

sin( ) cos( ) , 1.. , 1.. .

bi jimjn12 1 1

Найти значения произведений элементов каждого из массивов на

скаляр 0,75 (массивы A1 и B1 соответственно). Вывести промежу"

точные и окончательные результаты расчетов.

Решение. Перед составлением схемы алгоритма решения зада"

чи произведем небольшой анализ. Во"первых, будем использовать

подпроцесс, осуществляющий умножение матрицы на скаляр. Во"

вторых, подпроцесс условно отождествим с понятием «процедура».

Под этим понятием будем понимать подпроцесс, возвращающий зна"

чения, указанные в списке формальных параметров подпроцесса. Имя

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

цесс. Схемы алгоритмов основного процесса и подпроцесса приведе"

ны на рис. 5.3 и 5.4 соответственно.

Рис. 5.3. Схема алгоритма основного процесса (пример 5.2)

На рис. 5.3 и 5.4 введены следующие обозна"

чения: Umn – имя подпроцесса умножения матри"

цы на скаляр. Z, m, n, S, Z1 – формальные пара"

метры, где Z – исходная матрица; m и n – размерно"

сти матриц; S – скаляр; Z1 – результирующая мат"

рица. На рис. 5.3 в блоках 13 и 19 показаны ини"

циации подпроцесса Umn с разными фактически"

ми параметрами.

Применение подпроцессов является наиболее

предпочтительным, так как позволяет, во"пер"

вых, исключить повторяющиеся однотипные дей"

ствия и, во"вторых, структурировать саму зада"

чу, что обеспечит в дальнейшем при программи"

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

как здания из готовых блоков.

6. МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ

В рамках данной дисциплины предусмотрено выполнение четы"

рех лабораторных работ:

· № 1 – «Ветвящийся вычислительный процесс».

· № 2 – «Обработка числовой последовательности».

· № 3 – «Обработка массивов данных».

· № 4 – «Обработка массивов данных с использованием подпро"

цессов».

Цель работ: а) ознакомление с приемами и методами составле"

ния схем алгоритмов решения типовых вычислительных задач;

б) приобретение практических навыков алгоритмизации предлагае"

мых к рассмотрению вычислительных задач.

Содержание работ: а) описание задачи; б) построение схемы

алгоритма (алгоритмов) решения задачи в соответствии с задани"

ем; в) составление отчета о работе и его защита.

Содержание отчетов: титульный лист установленного образца;

задание на лабораторную работу; схемы алгоритмов в соответствии

с ГОСТом. Отчет оформляется на листах формата А4 (297´210). Под"

готовленный отчет защищается и сдается преподавателю для полу"

чения зачета по работе. Защита отчета включает в себя ответы на

вопросы по теме лабораторной работы.

Задания к лабораторным работам № 1–4 приведены соответствен"

но в табл. 6.1–6.3.

Рис. 5.4. Схема

алгоритма

подпроцесса

Umn(Z,m,n,S,Z1)

(пример 5.2)