3120

Множества и операции над ними

Лабораторная работа

Информатика, кибернетика и программирование

Множества и операции над ними Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции с помощью алгоритма типа слияния. Допустима организация множеств в виде списка или в виде массива...

Русский

2012-10-24

133 KB

116 чел.

Множества и операции над ними

Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции (È , Ç , Í , \) с помощью алгоритма типа слияния (по материалам главы 1, п.1.2). Допустима организация множеств в виде списка или в виде массива.

Работа программы должна происходить следующим образом:

  1.  На вход подаются два упорядоченных множества A и B (вводятся с клавиатуры, элементы множеств – буквы латинского алфавита).
  2.  После ввода множеств выбирается требуемая операция (посредством текстового меню, вводом определенного символа в ответ на запрос – выбор по желанию автора). Операции: вхождение AÍ B, AÈ B, AÇ B, A\B (дополнительно: B\A, AD B, BÍ A).
  3.  Программа посредством алгоритма типа слияния определяет результат выбранной операции и выдает его на экран с необходимыми пояснениями. Одновременно с результатом на экране должны присутствовать и исходные множества.
  4.  Возврат на п.2 (выбор операции).
  5.  Завершение работы программы – из п.2 (например, по ESC).

Дополнительно: предусмотреть возможность возврата не только к выбору операции (п.2), но и к вводу новых множеств (п.1). Выход в таком случае должен быть возможен из любого пункта (1 или 2).

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


Решение.

Множества будем хранить как массив с нумерацией элементов, начинающейся с единицы.

Объединение множеств.

Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество U, представляющее собой объединение множеств A и B. Через k обозначим мощность множества U. Также k будет и номером последнего добавленного элемента в U.

Алгоритм решения.

  1.  Положить i = j =1, k = 0.
  2.  Если ещё не просмотрены все элементы множеств A, B выполнить:
    1.  Если в A ещё есть элементы, и в B есть элементы и A[i] = B[j], то
      1.  Добавить A[i] в U, то есть k := k + 1 и U[k] := A[i]
      2.  Перейти к следующим элементам в A и B, то есть i := i + 1 и j := j + 1
    2.  Если в B уже все элементы были просмотрены или же A[i] < B[j] (при условии, что в A не все элементы были просмотрены) выполнить:
      1.  Добавить A[i] в U, то есть k := k + 1 и U[k] := A[i]
      2.  Перейти к следующему элементу множества A, то есть i := i + 1
    3.  Во всех остальных случаях (то есть когда в A уже все элементы просмотрены или же если A[i] > B[j]) выполнить:
      1.  Добавить B[j] в U, то есть k := k + 1 и U[k] := B[j];
      2.  Перейти к следующему элементу множества B, то есть j := j + 1
    4.  Перейти к пункту 2.

Как видно, на каждом шаге мы добавляем в U минимальный элемент из A[i] и B[j] и переходим к рассмотрению следующего элемента.

Пересечение множеств.

Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество P, представляющее собой пересечение множеств A и B. Через k обозначим мощность множества P. Также k будет и номером последнего добавленного элемента в P.

Алгоритм решения.

  1.  Положить i = j = 1 и k = 0.
  2.  Если в A и B (одновременно) есть ещё непросмотренные элементы, выполнить:
    1.  Если A[i] = B[j], то выполнить:
      1.  Добавить A[i] в U, то есть k := k + 1 и U[k] := A[i]
      2.  Перейти к следующим элементам множеств A, B, то есть i := i + 1 и j := j + 1
    2.  Если A[i] < B[j], то перейти к следующему элементу множества A, то есть i := i +1
    3.  В остальных случаях (то есть когда A[i] > B[j]) перейти к следующему элементу множества B, то есть j := j + 1
    4.  Перейти к пункту 2.

Разность множеств.

Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B. Будем получать множество D, представляющее собой множество A без элементов множества B. Через k обозначим мощность множества D. Также k будет и номером последнего добавленного элемента в D.

Алгоритм решения.

  1.  Положить i = j = 1 и k = 0.
  2.  Если в A и B (одновременно) ещё есть непросмотренные элементы, выполнить:
    1.  Если A[i] = B[j], то переходим к следующим элементам множеств A и B, так как равные элементы вычлись и в D ничего добавлять не надо. Выполняем i := i + 1 и j := j + 1
    2.  Если A[i] < B[j], то, в силу упорядоченности, в множестве B уже точно нет элемента, равного A[i], поэтому ничто не вычитается. Добавляем A[i] в D, то есть k := k + 1 и D[k] := A[i], и переходим к следующему элементу в A, то есть i := i + 1
    3.  Если A[i] > B[j], то берём следующий элемент из B (так как из A исключить элемент B[i] ввиду того, что в A нет такого элемента), то есть j := j + 1
    4.  Переходим к пункту 2.

Проверка вхождения A в B.

Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j – номер текущего рассматриваемого элемента множества B.

Алгоритм решения.

  1.  Если мощность A больше мощности B, то, очевидно, что A в B не входит. Завершить работу.
  2.  Положить i = j = 1.
  3.  Если в A и B (одновременно) есть ещё непросмотренные элементы, выполнить:
    1.  Если A[i] > B[i], то перейти к следующему элементу в B, то есть j := j + 1
    2.  Если A[i] = B[j], то перейти к следующим элементам в A и B, то есть i := i + 1 и j := j + 1
    3.  Перейти к пункту 3.
  4.  Если i - 1 равно N (то есть мы перебрали все элементы из A, а это в нашем алгоритме возможно лишь тогда, когда для каждого элемента из A имеется такой же элемент в B), то A входит в B, иначе не входит.


Исходный код на
Borland Pascal 7.

program lab1;

uses

 Crt;

const

 Nmax = 50;  { Макс. кол-во элементов множества }

type

 T = Char; { Тип элементов множества }

 TSet = Array[1..Nmax] of T; { Само множество }

{ Сортировка выбором по неубыванию }

procedure Sort(var A: TSet; const N: Integer);

var

 i, j, k: Integer;

 tmp: T;

begin

 for i := 1 to N - 1 do begin

   k := i;

   for j := i + 1 to N do

     if A[j] < A[k] then k := j;

   tmp := A[i];

   A[i] := A[k];

   A[k] := tmp;

 end;

end;

{ Ввод множества }

procedure Set_Input(var A: TSet; var N: Integer);

var

 i, j: Integer;

 tmp: T;

 F: Boolean;

begin

 Reset(Input);

 N := 0;

 while not SeekEoLn do begin

   Inc(N);

   Read(A[N]);

 end;

 Sort(A, N);

 F := False;

 i := 1;

 while i < N do begin

   if A[i] = A[i + 1] then begin

     F := True;

     Dec(N);

     for j := i + 1 to N do

       A[j] := A[j + 1];

   end

   else

     Inc(i);

 end;

 if F then WriteLn('Повторяющиеся элементы удалены.');

end;

{ Печать множества }

procedure Print(const A: TSet; const N: Integer);

var

 i: Integer;

begin

 for i := 1 to N do

   Write(A[i], ' ');

 if N = 0 then Write('Пустое множество.');

 WriteLn;

end;

{ Печать множеств A, B }

procedure Print_Sets(const A, B: TSet; const N, M: Integer);

var

 i: Integer;

begin

 WriteLn;

 Write('Множество A:  ');

 for i := 1 to N do

   Write(A[i], ' ');

 WriteLn;

 Write('Множество B:  ');

 for i := 1 to M do

   Write(B[i], ' ');

 WriteLn;

end;

{ Объединение множеств A и B методом слияния }

procedure Union(var U: TSet; var k: Integer; const A, B: TSet; const N, M: Integer);

var

 i, j: Integer;

begin

 i := 1;

 j := 1;

 k := 0;

 while (i <= N) or (j <= M) do

   if (j <= M) and (i <= N) and (A[i] = B[j]) then begin

     Inc(k);

     U[k] := A[i];

     Inc(i);

     Inc(j);

   end

   else if (j > M) or (i <= N) and (A[i] < B[j]) then begin

     Inc(k);

     U[k] := A[i];

     Inc(i);

   end

   else begin

     Inc(k);

     U[k] := B[j];

     Inc(j);

   end;

end;

{ Пересечение множеств A, B методом слияния }

procedure Product(var P: TSet; var k: Integer; const A, B: TSet; const N, M: Integer);

var

 i, j, W: Integer;

begin

 i := 1;

 j := 1;

 k := 0;

 while (i <= N) and (j <= M) do

   if (A[i] = B[j]) then begin

     Inc(k);

     P[k] := A[i];

     Inc(i);

     Inc(j);

   end

   else if A[i] < B[j] then

     Inc(i)

   else

     Inc(j);

end;

{ Разность множеств A, B методом слияния }

procedure Diff(var D: TSet; var k: Integer; const A, B: TSet; const N, M: Integer);

var

 i, j: Integer;

begin

 i := 1;

 j := 1;

 k := 0;

 while (i <= N) and (j <= M) do

   if A[i] = B[j] then begin

     Inc(i);

     Inc(j);

   end

   else if A[i] < B[j] then begin

     Inc(k);

     D[k] := A[i];

     Inc(i);

   end

   else if A[i] > B[j] then

     Inc(j);

 while (i <= N) and (j > M) do begin

   Inc(k);

   D[k] := A[i];

   Inc(i);

 end;

end;

{ Проверка на вхождение A в B }

function Incl(const A, B: TSet; const N, M: Integer): Boolean;

var

 i, j: Integer;

begin

 Incl := False;

 if N > M then Exit;

 i := 1;

 j := 1;

 while (i <= N) and (j <= M) and (A[i] >= B[j]) do

   if A[i] > B[j] then

     Inc(j)

   else if A[i] = B[j] then begin

     Inc(i);

     Inc(j);

   end;

 Incl := i - 1 = N;

end;

{ Вывод на экран клавиш управления }

procedure Keys;

begin

 ClrScr;

 WriteLn('Выберите действие:');

 WriteLn;

 WriteLn('1 - ввод множества A');

 WriteLn('2 - ввод множества B');

 WriteLn('3 - проверка вхождения A в B');

 WriteLn('4 - вывести объеденение множеств A и B');

 WriteLn('5 - вывести пересечение множеств A и B');

 WriteLn('6 - вывести разность A \ B');

 WriteLn('0 - очистка экрана');

 WriteLn('Esc - выход');

 WriteLn;

end;

var

 N, M, K: Integer;

 A, B, C: TSet;

 v: Char;

begin

 Keys;

 N := 0;

 M := 0;

 repeat

   v := ReadKey; { Получаем номер действия }

   if v in ['3'..'6'] then Print_Sets(A, B, N, M);

   case v of

     '1':

       begin

         WriteLn('Введите множество A:');

         Set_Input(A, N);

         WriteLn('Готово.');

         WriteLn;

       end;

     '2':

       begin

         WriteLn('Введите множество B:');

         Set_Input(B, M);

         WriteLn('Готово.');

         WriteLn;

       end;

     '3': if Incl(A, B, N, M) then WriteLn('A входит в B') else WriteLn('A не входит в B');

     '4':

       begin

         WriteLn('Объединение A и B:');

         Union(C, K, A, B, N, M);

         Print(C, K);

       end;

     '5':

       begin

         WriteLn('Пересечение A и B:');

         Product(C, K, A, B, N, M);

         Print(C, K);

       end;

     '6':

       begin

         WriteLn('Разность A \ B:');

         Diff(C, K, A, B, N, M);

         Print(C, K);

       end;

     '0': Keys;

   end;

 until v = #27;

end.
Результат работы программы.


 

А также другие работы, которые могут Вас заинтересовать

53391. Древняя Индия 41 KB
  Развивающая: Развивать умение пользоваться историко-географической картой, извлекать из неё знания, закрепить их с помощью работы по контурной карте. Умение переходить от одной формы работы к другой. Воспитательная: Закрепление представлений о том, что общечеловеческие достижения в культуре имеют конкретное происхождение. Представить культуру Индии как часть общемировой.
53392. США. Індіанці: пошуки вирішення проблеми. Контроль навичок - аудіювання 95.06 KB
  By the end of the lesson you should be able to reply and react appropriately to various statements. Beside, you will listen to some new information about the first Americans who came to Alaska from Asia crossing the Bering land bridge, which later became the Bering Strait. You will hear the text about American Indians and their problems.
53393. Методичні основи змісту навчання та виховання 143 KB
  В широкому плані особистість людини є інтегральною цілісністю біогенних соціогенних і психогенних елементів. Коменського великого чеського педагога чітко позначені положення про те що весь процес навчання і виховання дітей необхідно будувати з урахуванням їх вікових і індивідуальних особливостей і виявляти ці особливості шляхом систематичних спостережень. Він вважав що в процесі виховання і навчання необхідно орієнтуватися на позитивні якості...
53394. У НАС В ГОСТЯХ ІНДІЯ 99.5 KB
  Мета: забезпечити засвоєння учнями знань про характерні риси економіко географічного положення Індії особливості природних умов і ресурсів розміщення населення й господарства культурноісторичні особливості країни; розвивати творчі здібності учнів логічне мислення формувати культуру спілкування; продовжити розвивати інтерес до предмета; формувати вміння працювати самостійно та в групах виховувати почуття доброти й милосердя до людей інших...
53395. ІНДУКЦІЯ – МЕТОД ПІЗНАННЯ ІСТИНИ 59 KB
  Як виховати цілісне мислення як сформувати ставлення до математики як до цілісної системи яка забезпечує світопізнання розвиток інтелекту показати практичне застосування логічних методів для встановлення істини у житті людини Покажемо це на прикладі вивчення теми âІндукціяâ. У перекладі з латинської термін âіндукціяâ означає âнаведенняâ. Розрізняють кілька видів індуктивних міркувань: міркування за схемою âповна індукціяâ та міркування за схемою âнеповна індукціяâ. Це індукція шляхом переліку популярна індукція та...
53396. На шляху до сучасності: утвердження індустріального суспільства у провідних державах світу 91.5 KB
  Мета уроку: Систематизувати узагальнити та конкретизувати знання та уявлення учнів про розвиток провідних держав світу в 2 половині ХІХ ст. Тип уроку: урок узагальнення та систематизації знань умінь і навичок. Після цього уроку учні зможуть: Характеризувати процес завершення формування індустріального суспільства у провідних державах Європи та...
53397. Використання інформаційних технологій на уроках математики 1.49 MB
  Застосування компютерної техніки на уроках дозволяє зробити урок нетрадиційним яскравим насиченим наповнюючи його зміст знаннями з інших наочних областей що перетворюють математику з об'єкту вивчення в засіб отримання нових знань. Ефективність застосування нових інформаційних технологій на уроках математики обумовлена наступними факторами: 1 різноманітність форм представлення інформації; 2 висока степінь наочності; 3 можливість моделювання за допомогою компютера різноманітних обєктів і процесів; 4 звільнення від рутинної роботи...
53398. Засоби пошуку інформації в Інтернеті. Принципи функціонування веб-каталогів та пошукових систем. Стратегії пошуку інформації 1.56 MB
  Сьогодні на уроці продовжим вивчати сільське господарство, характеристику тваринництва, узагальнемо спеціалізацію сільського господарства, ознайомимось і оцінемо проблеми і перспективи розвитку сільського господарства, завершимо виконання практичної роботи №9, використовуючи знання з інформатики.
53399. Алгоритм 434 KB
  В цей час решта членів команд задіяні в перехресному опитуванні: задають один одному по 3 теоретичних питання за темою, які готували дома заздалегідь, причому, задають питання та дають відповіді різні члени команди. Оцінює команди журі, до складу якого входять 2 найбільш підготовлених студента (1 бал за кожну правильну відповідь). Вони ж здійснюють контроль часу.