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

Переменная типа «множество» занимает в памяти 32 байта или 256 бит. Поэтому ее эффективнее передавать по ссылке.

Создание множества на базе массива

const n=1000;
var s: array [1..n] of boolean;

s[i]=True – eсть элемент, False – нет элемента.

Такой способ хранения – в 8 раз менее компактный.

procedure Include(var s:MyIntSet; i: integer);
begin
s[i]:=True
end;

function Intersection(const s1,s2: MyIntSet): MyIntSet;
begin
for i:=1 to n do
Result[i]:=s1[i] and s2[i];
end;

Создание множества на базе битового массива.

type MyBitIntSet = array [0..n-1] of byte // n*8 элементов

Include(s,i)

1) найти нужный байт

2) установить в нем нужный бит:

by:=i div 8;
bi:=i mod 8;
s[by]:=s[by] or (1 shl bi)

Exclude(s,i)

s[by]:=s[by] and not (1 shl bi);

Пересечение

Побитовое or для всех элементов

Объединение

Побитовое and для всех элементов

Разность

Result[i]:=s1[i] and not s2[i]

Некоторые алгоритмы для двумерных массивов

const sz=10;
type IMatrix= array [1..sz,1..sz] of integer;
var A: IMatrix;

Заполнение матрицы случайными числами

read(m,n);
fillRandom(a,m,n); // fillRandom написать самостоятельно

Вывод матрицы

for i:=1 to n do
begin
for j:=1 to m do
write(A[i,j]:4);
writeln;
end;

Пример. Найти сумму элементов в каждом столбце матрицы A.

read(m,n);
fillRandom(A,m,n);
for j:=1 to n do
begin
s:=0;
for i:=1 to m do
s:s+A[i,j];
sum[j]:=s;
end;

Пример. Найти минимальные элементы в столбцах матрицы A.

for j:=1 to n do
begin
mn:=A[i,j];
for i:=2 to m do
if A[i,j]<mn then
mn:=A[i,j];
min[j]:=mn;
end;

Пример. Установить, есть ли в матрице элемент равный k.

label lbl;
begin
read(k);
flag:=False;
for i:=1 to n do
if A[i,j]=k then
begin
flag:=true;
goto lbl;
end;
lbl:
...

Использование goto оправдано - выход из двух вложенных циклов сразу.

Пример. Обнулить элементы матрицы ниже главной диагонали (сделав ее верхнетреугольной).

Алгоритм 1.

for i:=1 to n do
for j:=1 to n do
if i>j then
A[i,j]:=0;

Алгоритм 2.

for i:=2 to n do
for j:=1 to i-1 do
A[i,j]:=0;

Пример. Обнулить элементы

Алгоритм 1 (по строкам).

for i:=1 to (n+1) div 2 do
for j:=n-i+2 to n do
A[i,j]:=0;
for i:=(n+1) div 2+1 to n-1 do
for j:=i+1 to n do
A[i,j]:=0;

Алгоритм 2 (по столбцам).

for j:= n div 2+2 to n do
for i:=n-j+2 to j-1 do
A[i,j]:=0

Алгоритм умножения матриц

C=A*B

for i:=1 to m do
for j:=1 to n do
Begin
s:=0;
for k:=1 to n do
s:=s+A[i,k]*B[k,j];
C[i,j]:=s;
end;

Метод Гаусса

for k:=1 to m do
begin
akk:=A[k,k]; // если=0, то ошибка
for j:=1 to m+1 do
A[k,j]:=A[k,j]/akk;
for i:=1 to m do // A[i]:=A[i]-A[k]*A[i,k]
if i<>k then
begin
c:=A[i,k];
for j:=k+1 to m+1 do
A[i,j]:=A[i,j]-A[k,j]*c;
end;
end;
for i:=1 to m do
write(A[i,m+1],' ');

Строки

Символы

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

Для хранения символа используется 1 или 2 байта (соответствующие кодировки называются однобайтовыми или двухбайтовыми). Тип char занимает 1 байт, т.е. кодировка типа char - однобайтовая.

Кодовая таблица состоит из двух половин. В первой половине (коды 0..127) содержатся цифры, буквы латинского алфавита (большие и маленькие), знаки препинания и управляющие символы. Стандарт на первую половину кодовой таблицы называется ASCII (American Standard Code for Information Interchange – американский стандартный код для обмена информацией). Вторая половина с кодами от 128 до 255 содержит символы национального алфавита.

Символы с кодами от 0 до 31 считаются управляющими:

#10 - символ перехода на следующую строку
#13 - символ возврата "каретки"
#9 - символ табуляции

В России наиболее распространены следующие национальные (русские) кодировки:

• Dos
• Windows(CP-1251)
• KOI-8R

Стандартные подпрограммы для работы с символами

var
c: char;
x: byte;
ord(c) - функция, возвращающая код символа с (0..255)
chr(x) - функция, возвращающая символ с кодом x

Функции chr и ord- взаимно противоположные:

ord(chr(x))=x
chr(ord(c))=с

Если n - целое от 0 до 255, то вместо chr(n) можно использовать запись #n. Например, #32 - символ с кодом 32.

Другие подпрограммы:

succ(c) - функция, возвращающая следующий символ;
pred(c) - функция, возвращающая предыдущий символ;
Inc(c) - процедура увеличения кода символа на 1;
Dec(c) - процедура уменьшения кода символа на 1;
Inc(c,n) - процедура увеличения кода символа на n;
Dec(c,n) - процедура уменьшения кода символа на n.

Виды строк в Delphi

Cтроки shortstring

sizeof(shortstring)=256

Как строка shortstring хранится в памяти.

К символам строки можно обращаться по индексу: s[i] возвращает i-тый символ строки s.

Length(s) - функция, возвращающая длину строки s. Для shortstring возвращает содержимое нулевого байта - байта длины строки. Для shortstring Length(s)=ord(s[0]).

Можно также при описании указывать размер памяти под строку shortstring:

type str20=shortstring[20];

Такая строка будет занимать 20 байт памяти плюс 1 байт на длину строки.

Строки ansistring могут занимать до 2 Гб. Они растут динамически по мере заполнения. Переменные типа ansistring представляют собой указатели на реальные строки. Поэтому при их присваивании копируется лишь значение указателя.

var: s1,s: ansistring;
...
s1:=s; // копируется указатель

Однако, если после этого часть одной из строк меняется (например, меняется один символ), то происходит полное копирование строки и в копии происходит изменение. Такое отложенное копирование называется копированием при записи.

В Delphi есть также тип widestring строки, состоящей из widechar(2 байта - Unicode).