Разработка в среде Turbo Pascal программы сортировки элементов, находящихся на главной диагонали матрицы

" Разработка в среде Turbo Pascal программы сортировки элементов, находящихся на главной диагонали матрицы"

1. Постановка задачи

В курсовой работе «Разработка в среде Turbo Pascal программы сортировки элементов, находящихся на главной диагонали матрицы» ставятся несколько задач.

Исходными данными являются массивы :

Матрица, А — двумерный массив.

Матрицы B и Y — одномерные массивы.

Необходимо разработать алгоритмы, блок-схемы и программный код на языке Pascal для решения следующей задачи:

1) Решить линейное уравнение A^TAX=B

2) Отсортировать элементы, находящиеся на главной диагонали обратной матрицы (A^TA)^-1 по убыванию.

3) Вычислить значение матрицы Z=A^TB^TY

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

Для выполнения операций с матрицами будут использованы стандартные возможности и инструментарий языка Pascal, в частности это использование одномерных и двумерных массивов, циклов for… do, использование функций, оператора выбора, циклов if… then, объявление переменных разных типов и другие.

2. Описание алгоритма решения задачи графическим способом

2.1 Детализация схемы алгоритма

Блок схема основной программы Рис. 1. Блок схема основной программы Детализация укрупненной схемы алгоритма В алгоритме программы на рисунке 1 решаются несколько задач.

1) Реализация диалогового интерфейса меню для взаимодействия с пользователем. Выбор соответствующего пункта меню запрограммирован на клавиши F1… F4, это реализовано с помощью оператора выбора (селектора) case. Если значение селектора совпадает с каким-либо значением в операторе case, то выполняется ветка, относящаяся к данному случаю. При нажатии, например клавиши F1 происходит переход в процедуру zadacha1 и т. д.

2) Так как основная задача поделена на три основных части, то, соответственно, созданы три процедуры zadacha1, zadacha2, zadacha3. В каждой из них производятся итоговые вычисления матриц с выводом результатов на экран.

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

2.2 Блок-схемы алгоритмов

Рис. 2. Блок схема процедуры zadacha1

zadacha1 — процедура вычисления линейного уравнения A^T*A*X=B и вывод на экран результатов вычислений. На экран выводится значение матрицы Х.

i, j: integer — это переменные цикла.

M: Matrix44 — это двумерный массив, т. е. матрица 4х4

P: Matrix41 — это одномерный массив, т. е. матрица 4х1

Внутри процедуры zadacha1 находятся 4 вложенных цикла и 1 цикл вывода матрицы B на экран.

1 цикл: вычисление матрицы A^T. Перед началом цикла идет вызов процедуры Trans44(A, M).

2 цикл: вычисление матрицы A^T*A. Перед началом цикла идет вызов процедуры PMatrix44(M, A, M).

3 цикл: вычисление матрицы обратной (A^T*A). Перед началом цикла идет вызов процедуры Obrat (M, M).

4 цикл: вывод матрицы B на экран.

5 цикл: определение значения матрицы Х=((A^T*A)^(-1))*B. Перед началом цикла идет вызов процедуры PMatrix41(M, B, P).

Рис. 3. Блок схема процедуры zadacha2

Zadacha2 — процедура сортировки элементов главной диагонали матрицы, обратной (A^T*A) по убыванию. На экран выводится значение обратной матрицы (A^T*A), ее определителя и отсортированная главная диагональ матрицы обратной (A^T*A).

i, j, ni, nj: integer — это переменные цикла.

P: array[1.4] of Real — это одномерный массив для элементов главной диагонали.

max: real — это переменная массива P[i].

M: Matrix44 — это двумерный массив, т. е. матрица 4х4

Внутри процедуры zadacha2 находятся 3 вложенных цикла, 1 цикл присвоения массива, 1 цикл сортировки с условием и 1 цикл вывода отсортированных элементов на экран. Всего 6 циклов.

1 цикл: вычисление матрицы A^T. Перед началом цикла идет вызов процедуры Trans44(A, M).

2 цикл: вычисление матрицы A^T*A. Перед началом цикла идет вызов процедуры PMatrix44(M, A, M).

3 цикл: вычисление матрицы обратной (A^T*A). Перед началом цикла идет вызов процедуры Obrat (M, M).

4 цикл: присвоение элементов главной диагонали матрицы, обратной (A^T*A), в массив P.

5 цикл: цикл сортировки с условием, если элемент массива меньше следующего, то меняем их местами.

6 цикл: вывод на экран отсортированной главной диагонали матрицы M, обратной (A^T*A).

Рис. 4. Блок схема процедуры zadacha3

Zadacha3 — процедура вычисления значения матрицы Z=(B^T)*(A^T)*Y.

M: Matrix44 — это двумерный массив, т. е. матрица 4×4.

P: Matrix14 — это матрица 1×4.

i, j, nom: integer — это переменные цикла.

r: real — это искомая переменная, т. е. матрица Z.

Внутри процедуры zadacha3 находятся 3 основных цикла.

1) цикл вычисления матрицы B^T. Перед началом цикла идет вызов процедуры Trans41(B, P).

2) цикл вычисления матрицы A^T. Перед началом цикла идет вызов процедуры Trans44(A, M).

3) цикл вывода на экран матрицы Y и вычисление значения матрицы Z.

При вычислении значения матрицы Z идет вызов процедуры PMatrix14(P, M, P) и PMatrix (P, Y, r).

Рис. 5. Блок схема процедуры

PMatrix44(AMatrix, BMatrix: Matrix44; var Res: Matrix44)

PMatrix44 — это процедура умножения матрицы (4×4) на матрицу (4×4), результат — матрица (4×4).

var i, j, k: integer — это переменные цикла.

r: real; - это искомая переменная, результат вычислений.

AMatrix, BMatrix: Matrix44 — это присвоение массиву AMatrix и BMatrix значений двумерного массива Matrix44.

var Res: Matrix44 — это присвоение переменной Res значений двумерного массива Matrix44.

В конце процедуры Res[i, j] := r; означает, что искомой переменной r производится присвоение значения переменной Res.

Рис. 6. Блок схема процедуры

GetMatr (AMatr: Matrix44; var BMatr: Matrix33; i, j: integer)

GetMatr — это процедура вычеркивания из матрицы AMatr строки i и столбца j и формирование матрицы BMatr (3×3).

var ki, kj, di, dj: integer; - это переменные цикла.

var Res: Matrix44 — это присвоение переменной Res значений двумерного массива Matrix44.

Рис. 7. Блок схема функции GetDet (AMatrix: Matrix44): Real

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

var i: integer; - переменная цикла

Res: Real; - искомая переменная

M: Matrix33; - массив 3 на 3.

Рис. 8. Блок схема процедуры GetMatrDop (AMatr: Matrix44; var ResMatr: Matrix44);

pascal транспонированный матрица

GetMatrDop — эта процедура определяет значение элемента транспонированной матрицы дополнений.

Рис. 9. Блок схема функции znak (a, b: integer): integer;

Функция znak определяет, если четное число, результат = 1, иначе результат = -1.

Рис. 10. Блок схема функции DetMinor (AM: Matrix33): real;

Функция DetMinor определяет детерминанту матрицы 3×3.

Рис. 11. Блок схема процедуры

Obrat (AMatrix: Matrix44; var Res: Matrix44)

Процедура Obrat выполняет расчет обратной матрицы.

Рис. 12. Блок схема процедуры

PMatrix41(AMatrix: Matrix44; BMatrix: Matrix41; var Res: Matrix41);

PMatrix41- эта процедура выполняет умножение матрицы (4×4) на матрицу (4×1), результат — матрица (1×4).

Рис. 13. Блок схема процедуры

PMatrix14(AMatrix: Matrix14; BMatrix: Matrix44; var Res: Matrix14);

PMatrix14- эта процедура выполняет умножение матрицы (1×4) на матрицу (4×4), результат — матрица (1×4).

Рис. 14. Блок схема процедуры

PMatrix (AMatrix: Matrix14; BMatrix: Matrix41; var Res: Real);

PMatrix — это процедура умножения матрицы (1×4) на матрицу (4×1), результат — число.

3. Разработка программы на языке PASCAL

3.1 Краткое описание блоков программы

Программа начинается со служебного слова program, после которого следует заголовок программы laba1.

Далее включаем раздел uses для использования модуля CRT, который применяется для управления работой экрана в текстовом режиме.

После названия программы и идентификации используемых модулей следует раздел объявления типов (type), констант (const), переменных (var) и подпрограмм (procedure).

В данной программе в разделе типов задаются 4 статических массива (матрицы) вещественных чисел:

type Matrix44 = array[1.4, 1.4] of real;{матрица 4×4}

Matrix41 = array[1.4, 1.1] of real;{матрица 4×1}

Matrix14 = array[1.1, 1.4] of real;{матрица 1×4}

Matrix33 = array[1.3, 1.3] of real;{матрица 3×3}

В разделе констант объявлены 3 константы:

const A: Matrix44 = ((3, 3, 4, 5),(2, 6, 4, 6),(3, 4, 5, 5),(1, 9, 3, 6));

B: Matrix41 = ((1), (2), (1), (2));

Y: Matrix41 = ((1), (4), (0), (3));

В разделе переменных объявлена одна переменная символьного типа C: Char; и одна логического типа IsClose: Boolean.

Основная часть программы состоит из вспомогательных процедур и функций. Основные рабочие процедуры: zadacha1, zadacha2, zadacha3. Вспомогательные процедуры: PMatrix41, PMatrix14, PMatrix, PMatrix44, Trans41, Trans44, GetMatr, GetMatrDrop, Obrat. В каждой подпрограмме (процедуре) объявлены свои переменные и выполняются независимые циклы. Функции в программе объявлены как function DetMinor, znak, GetDet. Функция GetDet (возвращает значение определителя матрицы) используется в процедуре Obrat, функции DetMinor и znak используются в GetDet.

Такая структура программы объясняется множеством вычислений с матрицами, которые необходимо осуществить. Исходя из этого, все промежуточные вычисления реализованы во вспомогательных процедурах. А основные рабочие процедуры zadacha1, zadacha2, zadacha3 собирают в себе все промежуточные вычисления из других процедур и выводят вычисленные данные на экран.

Взаимодействие (интерфейс, простейшее меню) с пользователем организовано в программе в конце кода, начиная с BEGIN и до END. Запуск главных трех процедур zadacha1,2,3 выполняется через интерфейс пользователя.

Элементы ¦, L, -,, = это символы псевдографики, которые в dos-режиме используются для графического оформления таблицы.

3.2 Листинг программы

program laba1;

uses crt;

type Matrix44 = array[1.4, 1.4] of real;{матрица 4×4}

Matrix41 = array[1.4, 1.1] of real;{матрица 4×1}

Matrix14 = array[1.1, 1.4] of real;{матрица 1×4}

Matrix33 = array[1.3, 1.3] of real;{матрица 3×3}

const A: Matrix44 = ((3, 3, 4, 5),(2, 6, 4, 6),(3, 4, 5, 5),(1, 9, 3, 6));

B: Matrix41 = ((1), (2), (1), (2));

Y: Matrix41 = ((1), (4), (0), (3));

var C: Char;

IsClose: Boolean;

procedure PMatrix41(AMatrix: Matrix44; BMatrix: Matrix41; var Res: Matrix41);

var i, j, k: integer;

r: real;

begin

for i := 1 to 4 do

begin

for j := 1 to 1 do

begin

r := 0;

for k := 1 to 4 do

begin

r := r + AMatrix[i, k]*BMatrix[k, j];

end;

Res[i, j] := r;

end;

end;

end;

procedure PMatrix14(AMatrix: Matrix14; BMatrix: Matrix44; var Res: Matrix14);

var i, j, k: integer;

r: real;

begin

for i := 1 to 1 do

begin

for j := 1 to 4 do

begin

r := 0;

for k := 1 to 4 do

begin

r := r + AMatrix[i, k]*BMatrix[k, j];

end;

Res[i, j] := r;

end;

end;

end;

procedure PMatrix (AMatrix: Matrix14; BMatrix: Matrix41; var Res: Real);

var k: integer;

begin

Res := 0;

for k := 1 to 4 do

begin

Res := Res + AMatrix[1, k]*BMatrix[k, 1];

end;

end;

procedure PMatrix44(AMatrix, BMatrix: Matrix44; var Res: Matrix44);

var i, j, k: integer;

r: real;

begin

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

r := 0;

for k := 1 to 4 do

begin

r := r + AMatrix[i, k]*BMatrix[k, j];

end;

Res[i, j] := r;

end;

end;

end;

procedure Trans41(AMatrix: Matrix41; var Res: Matrix14);

var i: Integer;

begin

for i := 1 to 4 do

Res[1, i] := AMatrix[i, 1];

end;

procedure Trans44(AMatrix: Matrix44; var Res: Matrix44);

var i, j: Integer;

begin

for i := 1 to 4 do

for j := 1 to 4 do

Res[i, j] := AMatrix[j, i];

end;

procedure GetMatr (AMatr: Matrix44; var BMatr: Matrix33; i, j: integer);

var ki, kj, di, dj: integer;

begin

di := 0;

for ki := 1 to 3 do

begin

if (ki = i) then

di := 1;

dj:=0;

for kj := 1 to 3 do

begin

if (kj = j) then

dj := 1;

BMatr[ki, kj] := AMatr[ki + di, kj + dj];

end;

end;

end;

function DetMinor (AM: Matrix33): real;

var Res: real;

begin

Res := AM[1, 1]*AM[2, 2]*AM[3, 3] + AM[1, 2]*AM[2, 3]*AM[3, 1] + AM[2, 1]*AM[3, 2]*AM[1, 3];

Res := Res — (AM[1, 3]*AM[2, 2]*AM[3, 1] + AM[1, 1]*AM[2, 3]*AM[3, 2] + AM[2, 1]*AM[1, 2]*AM[3, 3]);

DetMinor := Res;

end;

function znak (a, b: integer): integer;

begin

if ((a+b) mod 2) = 0 then

znak := 1

else

znak := -1;

end;

function GetDet (AMatrix: Matrix44): Real;

var i: integer;

Res: Real;

M: Matrix33;

begin

Res := 0;

for i:=1 to 4 do

begin

GetMatr (AMatrix, M, 1, i);

Res := Res + znak (1, i) * AMatrix[1, i] * DetMinor (M);

end;

GetDet := Res;

end;

procedure GetMatrDop (AMatr: Matrix44; var ResMatr: Matrix44);

var M: Matrix33;

i, j: integer;

begin

for i := 1 to 4 do

for j := 1 to 4 do

begin

GetMatr (AMatr, M, i, j);

ResMatr[j, i] := znak (i, j) * DetMinor (M);

end;

end;

procedure Obrat (AMatrix: Matrix44; var Res: Matrix44);

var d: real;

i, j: integer;

M: Matrix44;

begin

d := GetDet (AMatrix);

writeln ('Определитель матрицы det|A^T*A| = ', d:10:2);

GetMatrDop (AMatrix, M);

for i := 1 to 4 do

for j := 1 to 4 do

Res[i, j] := M[i, j]/d;

end;

procedure zadacha1;

var M: Matrix44;

P: Matrix41;

i, j: integer;

begin

ClrScr;

writeln ('Решить линейное уравнение A^T*A*X=B');

writeln ('Вычислим матрицу A^T:');

Trans44(A, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

writeln ('Вычислим матрицу A^T*A:');

PMatrix44(M, A, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

writeln ('Вычислим матрицу обратную (A^T*A):');

Obrat (M, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

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

for i := 1 to 4 do

begin

write (B[i, 1]: 10:2);

writeln;

end;

writeln ('Определим значения матрицы Х=((A^T*A)^(-1))*B: ');

PMatrix41(M, B, P);

for i := 1 to 4 do

begin

for j := 1 to 1 do

begin

write (P[i, j]: 10:2);

write (' ');

end;

writeln;

end;

writeln ('Для продолжения нажмите любую клавишу…');

repeat

until KeyPressed;

end;

procedure zadacha2;

var M: Matrix44;

P: array[1.4] of Real;

i, j, ni, nj: integer;

max: real;

isExit: boolean;

begin

ClrScr;

writeln ('Сортировка элементов главной диагонали матрицы, обратной (A^T*A) по убыванию');

writeln ('Вычислим матрицу A^T:');

Trans44(A, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

writeln ('Вычислим матрицу A^T*A:');

PMatrix44(M, A, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

writeln ('Вычислим матрицу обратную (A^T*A):');

Obrat (M, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

for i := 1 to 4 do

P[i] := M[i, i];

repeat

isExit := false;

for i := 1 to 3 do

begin

if P[i] < P[i + 1] then

begin

max := P[i + 1];

P[i + 1] := P[i];

P[i] := max;

isExit := true;

end;

end;

until not isExit;

writeln ('Отсортированная главная диагональ матрицы M, обратной (A^T*A)');

for i := 1 to 4 do

begin

write (P[i]: 10:2);

write (' ');

end;

writeln;

writeln ('Для продолжения нажмите любую клавишу…');

repeat

until KeyPressed;

end;

procedure zadacha3;

var M: Matrix44;

P: Matrix14;

i, j, nom: integer;

r: real;

begin

ClrScr;

writeln ('Вычисление значения матрицы Z=(B^T)*(A^T)*Y');

writeln ('Вычислим матрицу B^T:');

Trans41(B, P);

for j := 1 to 4 do

begin

write (P[1, j]: 10:2);

write (' ');

end;

writeln;

writeln ('Вычислим матрицу A^T:');

Trans44(A, M);

for i := 1 to 4 do

begin

for j := 1 to 4 do

begin

write (M[i, j]: 10:2);

write (' ');

end;

writeln;

end;

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

for i := 1 to 4 do

begin

write (Y[i, 1]: 10:2);

write (' ');

end;

writeln;

PMatrix14(P, M, P);

PMatrix (P, Y, r);

writeln ('Значение матрицы Z: ', r:10:2);

writeln;

writeln ('Для продолжения нажмите любую клавишу…');

repeat

until KeyPressed;

end;

BEGIN

repeat

IsClose := false;

{очищаем экран}

ClrScr;

GotoXY (15, 8);

write ('г================================================');

GotoXY (15, 9);

write ('¦ Для выбора задания нажмите клавишу (F1.F4) ¦');

GotoXY (15, 10);

write ('¦====T===========================================¦');

GotoXY (15, 11);

write ('¦ F1 ¦ Решить линейное уравнение ¦');

GotoXY (15, 12);

write ('¦ F2 ¦ Сортировка элементов главной диагонали ¦');

GotoXY (15, 13);

write ('¦ F3 ¦ Вычислить значение матрицы ¦');

GotoXY (15, 14);

write ('¦ F4 ¦ Выйти из программы ¦');

GotoXY (15, 15);

write ('L====¦===========================================-');

repeat

C := ReadKey;

if C <> #59 then

if C <> #60 then

if C <> #61 then

if C <> #62 then

C := #0;

until C <> #0;

case C of

#59: zadacha1;

#60: zadacha2;

#61: zadacha3;

#62: IsClose := true;

end;

until IsClose;

END.

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

На рисунках ниже приведены скриншоты выполнения кода программы в программе FreePascal IDE.

Рис. 15. Главное окно программы при выполнении команды Run (Ctrl+F9)

Рис. 16. Выполнение первого задания (клавиша F1) согласно условиям задачи Рис. 17. Выполнение второго задания (клавиша F2) согласно условиям задачи Рис. 18. Выполнение третьего задания (клавиша F3) согласно условиям задачи

1. Долинский М. С. Алгоритмизация и программирование на Turbo Pascal: от простых до олимпиадных задач: Учебное пособие. — СПб.: Питер, 2005. — 237 с.: ил.

2. Потапова О. Н., Салихова Г. Л., Садриева Л. М., Миндиярова О. Г., Мохова О. М., Фахрутдинова Р. Р., Ханова И. А. Информатика: Методические указания по выполнению курсовой работы по дисциплине «Информатика» для бакалавров направления подготовки 131 000 «Нефтегазовое дело» всех форм обучения — Альметьевск: Альметьевский государственный нефтяной институт, 2013. -120 с.

3. Федоренко Ю. Алгоритмы и программы на Turbo Pascal. Учебный курс. — СПб: Питер, 2001. — 240 с.: ил.

4. Шпак Ю. А. Turbo Pascal 7.0 на примерах / Под ред. Ю. С. Ковтанюка — К.: Издательство Юниор, 2003. — 496 с., ил.

5.