IPB

> Лекция №5.5: Символы и строки. Множества
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4 5

Содержание

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

Представление множеств битовыми массивами

В случае, если 65 000 элементов недостаточно для задания всех необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет означать наличие элемента в множестве, а нулевой бит — отсутствие.

Задавая битовый массив, начнём нумерацию его компонент с 0:

set_bit : array[0 .. N - 1] of Byte;

Тогда результатом операции <номер_элемента> div 8 будет номер той компоненты массива, в которой содержится информация об этом элементе. А вот номер бита, в котором содержится информация об этом элементе, придётся вычислять более сложным образом:

bit := <номер_элемента> mod 8;
if bit = 0 then
  bit := 8;

Эти вычисления потребуются нам ещё не раз, поэтому запишем их снова, более строго, а затем будем использовать по умолчанию (element — это «номер» обрабатываемого элемента в нашем множестве):

kmp := element div 8; {номер компоненты массива}
bit := element mod 8; {номер бита}
if bit = 0 then
  bit := 8;

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

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

    pusto := True;
    for i := 0 to N - 1 do
     if set_arr[i] <> 0 then
     begin
        pusto := False;
       Break
     end;
  2. Проверка элемента на принадлежность множеству потребует несколько большей изворотливости, ведь нам теперь нужно вычленить соответствующий бит:

    if set_arr[kmp] and (1 shl (bit - 1)) = 0 then
      is_in := False
    else
      is_in := True;

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

  3. Добавление элемента в множество теперь будет записано так:

    set_arr[kmp] := set_arr[kmp] or (1 shl (bit - 1));

    Здесь нельзя использовать обычную операцию сложения (+), так как если добавляемый компонент уже содержится в множестве (то есть, соответствующий бит уже имеет значение 1), то в результате сложения 1+1 получится 10: единица автоматически перенесётся в старший бит, а на нужном месте окажется 0.

  4. Удаление элемента из множества придётся записать более сложным образом:

    set_arr[kmp] := set_arr[kmp] and not (1 shl (bit - 1));

    Операция not превратит все 0 в 1 и наоборот, следовательно, теперь в качестве второго операнда для побитового and будет фигурировать число, состоящее из семи единиц и нуля на месте с номером bit. Единицы сохранят любые значения тех битов, которые должны остаться без изменения, и лишь 0 «уничтожит» значение единственного нужного бита.

  5. Пересечение множеств реализуется теперь при помощи операции «побитовое и»:

    for i := 0 to N - 1 do
      set_res[i] := set1[i] and set2[i];
  6. Объединение множеств реализуется при помощи операции «побитовое или»:

    for i := 0 to N - 1 do
      set_res[i] := set1[i] or set2[i];
  7. Разность двух множеств может быть построена так:

    for i := 0 to N - 1 do
      set_res[i] := set1[i] and not set2[i];
  8. Проверка двух множеств на равенство по–прежнему не требует особых пояснений:

    equal := True;
    for i := 0 to N - 1 do
     if set1[i] <> set2[i] then
     begin
        equal := False;
       Break
     end;
  9. Проверка двух множеств на включение (set1 < set2) будет производиться по схеме: «Если set1 - set2 = [], то set1 < set2», доказательство которой настолько очевидно, что мы не станем на нём задерживаться:

    subset := True;
    for i := 0 to N - 1 do
     if (set1[i] and not set2[i]) <> 0 then
     begin
        subset := False;
       Break
     end;

Замечание. Если предстоит многократно выполнять действия с элементами битовых массивов, то используемые для этого значения «единиц» удобнее всего сразу задать в специальном массиве:

{ed : array[1 .. 8] of Byte;}
ed[1] := 1;  
for k := 2 to 8 do
  ed[k] := ed[k - 1] shl 1;

И далее вместо громоздкой конструкции 1 shl (bit - 1) можно использовать просто ed[bit].

Примеры использования символов, строк и множеств

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

program z1;
var s : set of Char;
  inp, res : String;
  i : Byte;

begin
 Write('Введите исходную строку: ');
 ReadLn(inp);
  s := [];
  res := '';
 for i := 1 to Length(inp) do
   if not (inp[i] in s) then
   begin
      res := res + inp[i];
      s := s + [inp[i]];
   end;
 WriteLn('Результат: ', res);
end.

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

program z2;
var inp, res : String;
  i : Byte;

begin
 Write('Введите исходную строку: ');
 ReadLn(inp);
  res := '';
 for i := 1 to Length(inp) do
 begin
    k := Pos(inp[i], res);
   if k <> 0 then
     Delete(res, k, 1);
    res := res + inp[i];
 end;
 WriteLn('Результат: ', res);
end.

Задача 3. Выдать первые 100 000 натуральных чисел в случайном порядке без повторений.

program z3;
var bset : array[0 .. 12499] of Byte;   {множество, битовый массив}
    ed : array[1 .. 8] of Byte;
    el, k : LongInt;
    kmp, bin : Integer;
begin
  ed[1] := 1;  {генерация массива битовых единиц}
 for k := 2 to 8 do
    ed[k] := ed[k - 1] shl 1;
 {-------------------------------------------------------}
  k := 0;
 Randomize; {процедура активизации генератора случайных чисел}
 while k < 100000 do
 begin
    el := 1 + Random(99999);  {случайное число из диапазона 0 .. 99999}
    kmp := el div 8;
    bit := el mod 8;
   if bit = 0 then
      bit := 8;
   if bset[kmp] and ed[bit] = 0 then {проверка повторов}
   begin
     Inc(k);
     WriteLn(el);
      bset[kmp] := bset[kmp] or ed[bit]
   end;
 end
end.

страницы: 1 2 3 4 5

Примечания

  1. ^ Более простой вариант решения — повторить решение задачи 1 с заменой цикла for-to на for-downto. Приведённый же вариант решения можно использовать для обработки не только строк, но и файлов.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"