8. Множества

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

Появляется новая для вас операция In (проверка принадлежности элемента множеству), операции объединения множеств (+), пересечения множеств (*) и вычитания (-).

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

1. Множество символов в строке

Множество символов, принадлежащих строке легко получить по следующей программе:

Var M:set of char;

S:string;

i: integer;

Begin

S:='мама мыла раму';

For i:=1 to Length(S) do M:=M+[s[i]];

{просто символ нельзя добавит к множеству М}

{нужно построить из него множество []}

{и объединить его с множеством М}

End.

2. Вывод элементов множества на экран

Используем символьную переменную ch (Var ch: char;), перебираем все значения символов, начиная с пробела (код #32) и, если символ есть в множестве, выдаем его на экран.

For ch:=#32 to #255 do

If ch in M then write(ch);

3. Ввод множества символов

Множество можно задать в разделе констант.

Например, так

Const M: set of char = ['A'..'Z'];

R: set of char = ['0'..'9'];

Можно получить в результате присваивания, описав в разделе переменных (Var M:set of char;) и присвоив в программе

M:= ['0'..'9', '+', '-'];

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

4. Количество различных символов в строке

Все пояснения в тексте программы.

Var M:set of char;

S : string;

k, i: integer;

ch : char;

Begin

S:='мама мыла раму';

M:=[]; {пустое множество - обязательно}

к:=0; {обязательно обнуляем счетчик}

For i:=1 to Length(S) do

If Not (S[i] In M) then {символа еще нет мн-ве}

Begin

k:=k+1;

{добавляем символ к множеству,}

{чтобы не посчитать его повторно}

M:=M+[s[i]];

End;

Write(k);

Readln;

End.

9. Двухмерные массивы (матрицы)

   1. Описание матрицы.

Const n=4; m=5;

Type matrix=array[1..n, 1..n] of Real;

{или другой тип}

Var A:matrix;

На рис.2. показан вид описанной матрицы. Обратите внимание, что первый индекс – номер строки, второй - -номер столбца.

A11	A12	A13	A14	A15
A21	A22	A23	A24	A25
A31	A32	A33	A34	A35
A41	A42	A43	A44	A45

Рис. 2. Вид матрицы.

2. Ввод элементов матрицы.

Элементы вводятся последовательно по строкам, i – номер строки, j – номер столбца.

For i:=1 to n do

For j:=1 to m do Read(A[i, j]);

Если конкретный размер матрицы может меняться, то следует описать матрицу с запасом (максимальный размер по условию задачи), и вводить размеры матрицы, а затем ее элементы.

Const max=100;

Type matrix=array[1..max, 1..max] of Real;

{ или другой тип}

Var A: matrix;

Begin

Write ('Введите число строк'); Radln (n);

Write ('Введите число столбцов'); Radln (m);

Write ('Введите', m*n, 'элементов матрицы');

For i:=1 to n do

For j:=1 to m do Read (A[i, j]);

3. Вывод элементов матрицы.

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

For i:=1 to n do Begin

For j:=1 to m do Write (A[i, j], ' ');{ выдаем строку}

Writeln {переводим курсор на следующую строку}

End;

4. Основные алгоритмы работы с матрицами.

   1. Сумма элементов матрицы.

Простой алгоритм не требует дополнительных пояснений. Еще раз обращаем внимание на то, что переменная S должна быть обнулена.

S:=0;

For i := 1 to n do

For j := 1 to m do S:= S+ a[i, j];

2. Сумма главной диагонали квадратной матрицы.

Обращаем внимание на то, что элементы главной диагонали имеют равные номера строк (первый индекс) и номера столбцов (второй индекс).

S:=0;

For i:= 1 To n Do S:=S+a[i, i];

3. Сумма побочной диагонали квадратной матрицы.

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

S:=0;

For i:= 1 To n Do S:=S+a[i, n+1-i];

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

Строки исходной матрицы становятся столбцами транспонированной. Исходная матрица (а) имеет n строк и m столбцов. Транспонированная матрица (в) имеет m строк и n столбцов.

For i := 1 to n Do

For j := 1 to m Do b[j, i] := a [i, j];

5. Транспонирование матрицы в том же массиве (транспонирование квадратной матрицы).

Здесь без рабочей ячейки не обойтись.

For i := 1 To n-1 Do

For j := i To n Do

Begin

r := a[i, j]; a[i, j] := a[j, i]; a[j, i] := r;

End;

6. Умножение матриц.

Дана матрица A размерами n*m и матрица B – m*k. После умножения получим матрицу C размерами n*k.

Умножение ведем по формуле C_ij=  a_it*b_tj

For i := 1 To n Do

For j := 1 To k Do begin

S:=0;

For t := 1 To m Do S:= S+A[i, t]*B[t, j];

C[i, j] := S;

end;

7. Работа с фрагментами матриц

Рассмотрим квадратную матрицу. Решим четыре похожие задачи по одной простой схеме.

A11	A12	A13	A14
A21	A22	A23	A24
A31	A32	A33	A34
A41	A42	A43	A44

Рис.3. Квадратная матрица

Задачи:

1. сумма элементов на главной диагонали и выше нее.

2. сумма элементов на главной диагонали и ниже нее.

3. сумма элементов на побочной диагонали и выше нее.

4. сумма элементов на побочной диагонали и ниже нее.

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

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

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

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