П Р И М Е Р Ы О Б Р А Б О Т К И М Н О Ж Е С Т В

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

Пример 1. В строке записана последовательность цифр в заданной системе счисления с основанием 2 £ £ 10. В начале и в конце строки могут быть пробелы. Преобразовать цифровую последовательность в число.

Пусть задана последовательность цифр . Ее можно представить в виде полинома

или по схеме Горнера

.

Выполним два варианта решения задачи: без использования множеств и с их использованием.

Program ConVert1;

ConstDigits = '0123456789';

Var i,k,q : byte;

Number : longint;

S : string;

Begin

Ввод и печать S, q

Number:=0;

For i:=1 tolength(S) do

Begin

k:=Pos(S[i],Digits);

If k>0 then

Number:=Number*q+k-1;

End;

Печать Number

End.

Если выделенный из строки S символ - это пробел, то переменная Number не изменяется; в противном случае в ее состав поступает численное значение цифры, которое на 1 меньше позиции этой цифры в строке Digits и равно k-1.

Примечание. В программе предполагается, что значение числа не превышает MaxLongInt = 2³¹-1. Если для переменной Number указать тип real, то значение числа не должно превышать 10³⁸. В то же время, если во всех байтах строки S записать цифры 9, то значение числа составляет 10²⁵⁶-1. В этом случае нужно использовать тип double (максимальное значение 10³⁰⁸) или extended (максимальное значение 10⁴⁹³²).

Program ConVert2;

Vari,q : byte;

Number : longint;

S : string;

Digits : set of '0'..'9';

Begin

Ввод и печать S, q

Digits:=['0'..'9'];

Number:=0;

For i:=1 to length(S) do

If S[i] inDigits then

Number:=Number*q+ord(S[i])-ord('0');

Печать Number

End.

В программе Convert1 функция Pos определяет, является ли символ S[i] цифрой или нет, и при положительном ответе ( k > 0 ) указывает порядковый номер k этого символа в строке-константе Digits, который в данном случае равен численному значению цифры, увеличенному на 1.

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

В программе Convert2 проверка принадлежности символа S[i] к цифрам осуществляется операцией in, что на машинном уровне сводится к логическому умножению двух битовых строк. Численное значение цифры формируется как разность ord(S[i]) - ord('0') (эдесь используется тот факт, что в любой таблице символов, в том числе в таблице ASCII, цифры образуют непрерывную возрастающую последовательность элементов таблицы).

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

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

Program DelSymbols1;

Vari,k : byte;

S : string;

Begin

Ввод и печать S

i:=2;

While i<=length(S) do

Begin

k:=Pos(S[i],Copy(S,1,i-1));

If k>0 then

Delete(S,i,1)

Else

Inc(i);

End;

Печать S

End.

Program DelSymbols2;

Vari : byte;

S : string;

CharSet : set of char;

Begin

Ввод и печать S

CharSet:=[S[1]];

i:=2;

While i<=length(S) do

If S[i] inCharSet then

Delete(S,i,1)

Else

Begin

CharSet:=CharSet+[S[i]];

Inc(i);

End;

Печать S

End.

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

В программе DelSymbols2 формируется множество CharSet, в которое заносится i-ый символ, если он отсутствует в этом множестве. Если такой символ уже имеется в CharSet, то он удаляется из строки S. Поскольку операция inна машинном уровне сводится к логическому умножению, то такая проверка повторяемости символа осуществляется значительно быстрее, чем последовательный перебор байтов строки с помощью функции Pos.