Алгоритм построения, обработки и преобразования матриц

Автор: csaa ·

Пример 10Ж ввод вещественной матрицы A(n x m).

writeln(‘Enter matrix ‘);

forI := 1 ton do{перебор строк}

Begin

forj := 1 tom do{перебор элементов строк}

read(a[i, j]);

readln;{переход к следющей строке}

end;

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

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

{определение суммы элементов первого столбца}

S:=0;

fori:= 1 toN doS:=S+A[I,1]

Max:=S;{наибольшее значение из сумм элементов столбцов}

J_max:=1;{номер столбца с наибольшей суммой элементов}

forJ:=2 toM do{просмотр столбцов}

Begin

S:=0;{Сумма элементов J-столбца}

forI:=1 ton doS:=S+A[I,J];

Ifs max then

Begin

Max:=s:J_max:= j;

end;

writeln(‘Наибольшая сумма элементов’,max,’в столбце’,j_max);

Задачи:

1)построение матрицы по заданной формуле для элемента

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

3)Менять строки и столбцы местами, вычеркивать строки и столбцы.

4)Умножение матрицы на вектор, на матрицу, сумма матриц, транспонирование матрицы, получение обратной матрицы.

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

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

:=();

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

Пример: Задание в качестве типизированной константы одномерного массива их шести вещественных чисел.

Const

N=6;

Type

T_array = array[1..n] ofreal;

Const

A:T_array= (13.43,0.0,-1.0,10.0,-13.8,6.0);

Аналогично задаются типизированные константы для матриц:

:=((), . . , ())

Элементы строки перечисляются через запятую. В данном случае матрица интерпретируется как одномерный массив строк, т.е.

array[1..n] of array[1..M].

Пример: Задание в качестве типизированной константы единичной матрицы A(4×4).

array[1..n] of array[1..M].

Const

n=4;

Type

T_matr= array[1..n,1..n] ofbyte;

Const

a:t_matr=(…..)

особенности компилятора TP при обработке массивов

1)Работа с элементами массива идет медленнее, ччем с простой переменной

2)Если индекс задается Const, то местоположение элемента определяется один раз на этапе компиляции,

Если индекс задается выражением или переменной, то местоположение элемента определяется каждый раз.

3){$R+} – устанавливает проверку всех индексов на заданные границы(устанавливают на время отладки)

{$R-} – снимает проверку(устанавливают при счете).

Var A:array[0..9] of integer

B:=A[10] – ошибка на этапе компилирования не обнаружится

B:=A[i+1] – индекс на этапе компилирования не анализируется,если

I=10 – ошибка на этапе счета

B:A[11] – ошибка счета.

Обработка текстов.

Тип string.

Var

1)s:string;

2)s:string[n];

S[0]- фактическая длина строки в литерном виде.

Ord(S[0]) – числовое значение дл. Строки

1)сравнение S:=’ABCDEF’; s:’ABCDFG’;

2)Строки можно обрабатывать посимвольно: s[i]

3)S:=;

4)Операция + s:=s1+s2;

Var

s:string;

s1,s2: string[7];

Begin

s1:=’123456′;

s2:=’ABCDEF’;

s:=s1+s2;

(s:=’123456ABCD’)

При вводе строк с клавиатуры следует учитывать что длинна буфера ввода составляет 128 символов, поэтому при использовании оператора Readln(S),

В строку S может быть введено не более 127 символов.

1)k:=length(s); k:(byte)

2)s:=concat(s1,s2,s3….sn);

3)s1:=copy(s,n,m); {слияние нескольких строк в одну}

s:=’Turbo Pascal7′;

s1:=copy(s,7,6); s:=’Pascal’;

4)Функция определения строки S1 в строку S: pos(s1,s);

Процедуры обработки строк.

1) Удаление из строки S некоторой её части: delete(s,n,m)

2) Включениие строки S1 в строку s начиная с n позиции insert(s,n,m)

3) Процедура перевода числа x в строку S str(x,s)

4) Процедура перевода строки S в число x val(s,x,k) k – параметр целого типа фиксирует наличие ошибки k = 0 если нет ошибок k=номеру позиции то строка не может быть преобразована.

При работе со строками следует помнить, что если строка заполнена или преобразована по байтам (т.е. посимвольно) без использования специальных процедур и функций или операций «+», то содержимое нулевого байта строки не меняется , т.е. фактическая длина строки остается прежней.

Пример: Дана строка символов. Группы символов, разделенные пробелами, будем называть словами. Найти наибольшую длину слов палиндромов(перевертышей). Если палиндромов нет, то ответом должно быть число 0.

Процедуры.

1)Заголовок процедуры или функции с описанием формальных параметров.

2)назначение.

3)Спецификация.

Спецификация:

Имя	Тип	Назначение

Процедуры и функции. Модули.

В Паскале существуют подпрограммы двух типов: процедуры и функции.

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

Синтаксис описания процедур.

**Процедура. Может иметь несколько выходных параметров.

ОПИСАНИЕ

{Заголовок}

procedure();

{раздел описания локальных объектов}

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

Begin

end;

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

();

Понятие процедуры и основные определения.

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

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

**Алгоритм, непосредственно обрабатывающий конкретные данные и содержащий обращение к процедуре, или вызов, называется вызывающим, или главным.

**Исходные данные, или аргументы, и выходные данные, или результаты процедуры, при описании процедуры могут быть представлены в специфическом виде – в виде параметров – как описание и перечисление «мест», куда при выполнении процедуры должны быть подставлены фактические обрабатываемые данные.

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

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

Внутренние объекты процедуры, т.е. определяемые внутри процедуры, называются локальными (аналог промежуточных данных). Это – «собственные» объекты процедуры, не связанные с вызывающим модулем и недоступные в нем.

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

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

**Выполнение процедуры происходит так, как если бы вместо формальных параметров при вызове были подставлены фактические. А затем выполнялся бы алгоритм процедуры; таким образом, обрабатываются фактические параметры по алгоритму. Записанному для формальных параметров.

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

Связь между процедурой и основной программой.

1) С помощью механизма параметров. Там где возможно передавать результаты через фактические параметры-переменные.

2) С помощью глобальных переменных.

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

Виды формальных параметров.

1) Параметры значения (с авторской версии), (входные) (A,B,C:; E,P:;…)

2) Параметры-переменные (выходные) (var A,B,C: ;….)

3)Параметры-const (const A,B,C:;…)

В качестве типа используется любой простой тип, string, file.

Если тип структурированный – указывается имя типа, а сам тип объявляется в основной программе.

4) Без типовые параметры (var A,B,C..)

5) Открытые параметры массивы (для одномерных) (var A:array of ;….)

6)Открытые строки (var S:openstring;….)

7)Процедурные и функциональные параметры.

Распределение памяти.

Все глобальные переменные программы и типизированные константы всех уровней вложенности размещаются в одном сегменте данных(64кб).

Локальные переменные размещаются в памяти динамически при активизации подпрограммы их содержащей. После завершения подпрограммы память, отведенная под локальные переменные освобождается. Т.е. локальные переменные размещаются динамически в стеке. На стек по умолчанию отводится (65520 байт)

Пример: в массивах a(5,6)b(3,8) найти сумму положительных элементов каждой строки.

programex1;

Const

m = 8;

n = 5;

Type

matr = array[1..n, 1..m] ofreal;

vek = array[1..n] ofreal;

Var

a, b: matr;

va, vb: vek;

procedureenter(varc: matr; k, p: byte);

Var

i, j: byte;

Begin

writeln(‘enter array’);

fori := 1 tok do

Begin

forj := 1 top do

read(c[i, j]);

readln;

end;

proceduresum(varc: matr; k, p: byte; varvc: vek);

Var

i, j: byte;

s: real;

Begin

fori := 1 tok do

Begin

s := 0;

forj := 1 top do

ifc[i, j]0 thens := s + c[i, j];

vc[i] := s;

end;

procedure out(varvc: vek; k: byte);

Var

i: byte;

Begin

write(‘sum’);

fori := 1 tok do

write(vc[i],’ ‘);

end;

Begin

enter(a, 5, 6);

enter(b, 3, 8);

sum(a, 5, 6, va);

sum(b, 4, 8, vb);

out(va, 5);

out(vb, 3);

end.

Передача параметров – значений и парамметров – переменных

Механизмы передачи в процедуру параметров-переменных и параметров-значений принципиально отличается.

1) Если формальный параметр – параметр-переменная, то соответствующий ему фактический параметр – тоже переменная. Память отводится только под фактический параметр и процедуре предоставляется право работать с ним. При передаче параметров – переменных перед выполнением процедуры устанавливается ссылка на переменную – фактический параметр; иначе говоря, в процедуру передается адрес фактического параметра. Все действия процедуры, таким образом, выполняется над фактическим параметром. Если значение фактического параметра меняется , то это изменённое значение доступно в программе после завершения работы процедуры.

Поэтому выходные параметры процедуры необходимо специфицировать как параметры –переменные.

Следствие. Как var можно описывать входные массивы – параметры с целью экономии памяти (чтобы они не копировались во временную память) и времени на копирование.

2) Если формальный параметр – параметр-значение, то соответствующий ему фактический параметр может быть:

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

Обычно входные параметры процедуры делают переменными значениями.

programpp;

Var

x, y, z: real;

procedurep(vara: real; b: real);

Var

z: real;

Begin

z := a;

a := b;

b := z;

end;

procedureq(vara: real; b: real);

Begin

z := a;

a := b;

b := z;

end;

Begin

x := 1.1;

y := 2.2;

z := 3.3;

p(x, y);

writeln(x,’ ‘, y,’ ‘, z);

x := 1.1;

y := 2.2;

z := 3.3;

q(x, y);

writeln(x,’ ‘, y,’ ‘, z);

end.

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

Имена объектов описанных в некоторой подпрограмме считаются известными в пределах этой подпрограммы, включая все вложенные подпрограммы.

Функция. Вычисляет единственное значение.

Описание

{Заголовок}

Function():;

{раздел описания локальных объектов}

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

Begin

End;

Здесь ::=

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

::=()

programm1;

Const

n = 20;

Type

vek = array[1..n] ofinteger;

Var

x, y: vek;

u: integer;

procedurewwod(varc: vek);

Var

i: byte;

Begin

fori := 1 ton do

read(c[i]);

readln;

end;

functionspr(k, m: byte; varp, q: vek): integer;

Var

s: integer;

i: byte;

Begin

s := 0;

fori := k tom do

s := s + p[i] * q[i];

spr := s;

end;

Begin

wwod(x);

wwod(y);

ifspr(1, 15, x, y)0 thenu := spr(1, 20, x, y)

elseu := spr(10, 20, y, y);

writeln(‘u=’, u);

end.

Процедурный тип.

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

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

Определение такого типа аналогично заголовку подпрограммы, но без указания имени.

type{Процедурный тип}

PROC = procedure();

PP = Procedure;

{функциональный тип}

FUN = function():;

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

1)Элементами процедурного типа являются процедуры и функции, заголовки которых совпадают с заголовками в разделе type.

2)Допустимы операторы присваивания, в правых частях которых находятся идентификаторы подпрограмм.

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

Type

op=function(x,y:real):real;

Var

proces:op;

functionsum(a,b:real):real;

far;

Begin

sum:=a+b;

end;

functiondelen(a,b:real):real;

far;

Begin

delen:=a/b;

end;

begin….

ifvslov thenproces:=sum

elseproces:=delen;

write(proces(25.2,2.5+x));

….

end.

Конструкция proces(25.2,2.5+x) вызывает активизацию той функции, которая была присвоена переменной proces.

Переменные процедурных типов можно использовать в качестве параметров процедур и функций.

Пример.

Составить, универсальную процедуру печати значения для любых функций при х изменяющемся от a до b с шагом h. F1=x^4+x^2; f2=sinx*cosx;

programex1;

Type

fan= function(x:real):real;

{$F+} -//компиляция в режиме дальнего вызова.

functionf2(x:real):real; far

Begin

f2:=sin(x)+cos(x);

end;

functionf1(x:real):real; far;

Begin

f1:=sqr(sqr(x))+sqr(x);

end;

{$F-}

procedureTAB(f:fan; a,b,h:real);

Var

x:real;

l,n:word;

Begin

n:=round((a-b)/h);

x:=a;

fori:=0 ton do

Begin

writeln(x:12.f(x):14);

x:=x+h;

end;

{main programm}

Begin

……

TAB(f2,0,1,0.1);

TAB(f1,5,7,0.1);

……

end.

Рекурсивные алгоритмы.

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

Рекурсивной называется процедура или функция, которая вызывает себя сама. При каждом вызове, рекурсивной подпр�