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

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

 

writeln('Enter matrix ');

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

Begin

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

read(a[i, j]);

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

end;

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

Пример. Фрагмент программы по определению для заданной матрицы 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;

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);

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

<имя матрицы>:<тип>=((<элементы 1 строки>), . . , (<элементы последней строки>))

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

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

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

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:<тип1>; E,P:<тип2>;…)

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

3) Параметры-const (const A,B,C:<тип1>;…)

В качестве типа используется любой простой тип, 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;

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;

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;

end;

{main programm}

Begin

......

TAB(f2,0,1,0.1);

TAB(f1,5,7,0.1);

......

end.

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

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

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

Тем не менее, во многих случаях рекурсия предоствдяет возможность использовать естественное, простое решение задачи, которую иным способом решить было бы трудно. В силу сказанного, рекурсия – это важное и мощное средство для решения задач и программирования.

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

 

Пример2: составить программу печати цифр целого положительного числа в обратном порядке.

WhileN<>0 do

Begin

write(N mod10);

N:=N div10;

end;

{рекурсивная процедура}

procedureREVERS(N:word);

Begin

IfN<>0 then begin

write(n mod10);

REVERS()n div10);

end;

end;

пример3:

Дан текст, заканчивающийся точкой. Напечатать его в обратном порядке.

 

 

_______________________________________

 

 

Множество.

Ограничения: длина меньше или равна 256 символов. Любого порядкового типа. Вводится [1эл,2эл,…….n-эл].

Самая компактная структура данных.

Правила записи множеств:

1) Элементами могут быть const, переменные и выражения соответствующего типа.

2) Можно использовать диапазон значений.

По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:

Var

имя: set of тип;

В отличие от элементов массива, элементы множества не упорядочены и не имеют индексов.

Можно сначала объявить тип множества, а потом использовать его для объявления переменных:

Type

t_ch = set of char;

Var

ch1, ch2: t_ch;

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

Type

week_days = (Mon, Tue, Wed, Thu, Fri);

Var

work_days: set of week_days;

lett: set of 'A'..'Z';

Объявление переменной-множества не дает ей определенного значения.

A:=S

Множественная переменная присваивается множественное значение.

Множественное выражение состоит из множественных констант переменных, выражений соединенных знаками «+,-,*».

Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.

Var

chs1, chs2, chs3: set of char;

Begin

chs1 := ['a', 'b', 'd'];

chs2 := ['m', 'd', 'e'];

chs3 := chs1 + chs2 + ['k', 'n'];

end.

Результат: chs3 = ['a', 'b', 'd', 'm', 'e', 'k', 'n'].

Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.

chs3 := chs1 * chs2;

Результат: chs3 = ['d'].

Разность двух множеств A и B (A – B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.

chs1 := ['a', 'e', 't'];

chs2 := chs1 – ['e'] { ['a', 't'] }

chs3 := ['m', 'n', 't'] – chs2 { ['m', 'n'] }

 

Приоритет:

1)*

2)+ -

Добавление элемента в множество.

A: = A + [x]

Исключение элемента из множества.

A:= A – [x]

 

Над множествами можно выполнять четыре операции сравнения: =, <>, >=, <=.

Два множества A и B равны (A = B), если каждый элемент множества A является элементом множества B и наоборот.

Два множества A и B не равны (A <> B), если они отличаются хотя бы одним элементом.

Множество A является подмножеством множества B (A <= B, или B >= A), если каждый элемент из A присутствует в B.

Имеется также возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in. Пусть A – множество элементов некоторого базового типа, а x – переменная (константа, выражение) этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A.

Все операции сравнения множеств, а также операция in возвращают логическое значение true или false.

В сложных выражениях над множествами операции имеют следующие приоритеты:

1. *

2. +, -

3. =, <>, <=, >=, in

Ввод и вывод множественных значений.

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

Ввод:

A:=[ ];

A:=A+[x];

 

 

Построение множества

Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой — конструктор множества или некоторое выражение над множествами.

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

Type

week_days = (Mon, Tue, Wed, Thu, Fri);

Var

work_days: set of week_days;

lett: set of 'A'..'Z';

Begin

work_days := [Mon, Wed, Thu];

lett := ['C', 'E'..'M', 'Z']

end.

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

Множество, в котором нет элементов, называется пустым (или нуль-множеством). В языке программирования Паскаль обозначается квадратными скобками, между которыми нет элементов:

work_days := [ ];

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

const lett: set of ['а'..'я'] = ['а', 'е', 'и', 'о', 'у', 'ы', 'у', 'ю', 'я'];

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

Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 и ch2 имеют тип char, то допустима следующая последовательность операторов:

ch1 := 'A';

ch2 := 'K';

chs := [ch1, ch2, 'M'];

В результате получится множество ['A', 'K', 'M'].

Элементы множества нельзя вводить и выводить. Для организации ввода-вывода элементов множества следует использовать вспомогательные переменные. В то же время можно использовать множества как элементы типизированных файлов.

Модульное программирование.

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

Модуль – автономно компилированная программная единица которая включает компоненты раздела объявления процедур и функций. Код модуля размещается в отдельном сегменте данных, поэтому возможно уменьшение размера программ.(см. схема exe). Структура модуля:

1)

2)

3)раздел реализации

4)раздел инициализации

Объекты модуля:

· Видимые объекты – доступны вызывающей программе к которой подключен модуль и являются глобальными объектами.

· Скрытые объекты – собственные объекты модуля, локальные объекты.

Оформление модуля:

unit<name>;

 

Interface

<видимые объекты>

{Разздел Const,type, procedure-name,}

Implementation

<скрытые объекты>

{Const,type,переменные, метки,procedure и тело процедур и функций из 2 раздела}

Begin

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

end.

Все разделы кроме begin обязательны.

Использование модулей. Подключение модуля к программе выполняется по директиве uses <имя модуля>. Директива uses может использоваться во втором и третьем разделах.

Пример.

unitcompl;

 

Interface

Type

complex = record

re, im: real;

end;

 

procedurereadc(varc: complex);

procedureaddc(c1, c2: complex; vars: complex);

Implementation

procedurereadc(varc: complex);

Begin

writeln('enter realpart');

read(c.re);

writeln('enter image part');

read(c.im);

end;

procedureaddc(c1,c2:complex; vars:complex);

 

end.

 

Компиляция модуля.

Модуль необходимо записать в одноименный PAS файл. Необходимо установить опцию compile /destination disk. Используя опции осуществить компиляцию compile make build.

 

Дан файл F целых чисел, в котором количество отрицательных и положительных совпадает. Получить файл T. в котором числа идут в следующем порядке: 2 положительных, 2 отрицательных и т.д