3120
Множества и операции над ними
Лабораторная работа
Информатика, кибернетика и программирование
Множества и операции над ними Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции с помощью алгоритма типа слияния. Допустима организация множеств в виде списка или в виде массива...
Русский
2012-10-24
133 KB
127 чел.
Множества и операции над ними
Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции (È , Ç , Í , \) с помощью алгоритма типа слияния (по материалам главы 1, п.1.2). Допустима организация множеств в виде списка или в виде массива.
Работа программы должна происходить следующим образом:
Дополнительно: предусмотреть возможность возврата не только к выбору операции (п.2), но и к вводу новых множеств (п.1). Выход в таком случае должен быть возможен из любого пункта (1 или 2).
Замечание: Исходные множества не должны содержать повторяющихся элементов (при обработке входных данных такие элементы следует удалять). Если исходные множества не упорядочены, нужно отсортировать их по возрастанию. Только после такой обработки над множествами возможно выполнять требуемые операции.
Решение.
Множества будем хранить как массив с нумерацией элементов, начинающейся с единицы.
Объединение множеств.
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j номер текущего рассматриваемого элемента множества B. Будем получать множество U, представляющее собой объединение множеств A и B. Через k обозначим мощность множества U. Также k будет и номером последнего добавленного элемента в U.
Алгоритм решения.
Как видно, на каждом шаге мы добавляем в U минимальный элемент из A[i] и B[j] и переходим к рассмотрению следующего элемента.
Пересечение множеств.
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j номер текущего рассматриваемого элемента множества B. Будем получать множество P, представляющее собой пересечение множеств A и B. Через k обозначим мощность множества P. Также k будет и номером последнего добавленного элемента в P.
Алгоритм решения.
Разность множеств.
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j номер текущего рассматриваемого элемента множества B. Будем получать множество D, представляющее собой множество A без элементов множества B. Через k обозначим мощность множества D. Также k будет и номером последнего добавленного элемента в D.
Алгоритм решения.
Проверка вхождения A в B.
Обозначим через i номер текущего рассматриваемого элемента в множестве A, через j номер текущего рассматриваемого элемента множества 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.
Результат работы программы.
А также другие работы, которые могут Вас заинтересовать | |||
74455. | Система юридической науки | 29.74 KB | |
Система юридической науки. Правовая наука представляет собой сложную и развитую систему многообразных знаний о государстве и праве об их историческом развитии и современном состоянии разделенных на отдельные обособленные массивы отрасли правовой науки. Отрасль правовой науки это знания о закономерностях действующих в обособленной сфере политикоправовой практики которые характеризуются логической непротиворечивостью и целостностью как правило на уровне теории а также представляют устойчивый интерес для правовой науки и... | |||
74456. | Современная западноевропейская правовая наука | 18.77 KB | |
Современная западноевропейская правовая наука попрежнему находится в состоянии прогрессивного развития совершенствования чему во многом способствуют постоянно возрастающие потребности общества и государства в обеспечении устойчивого правопорядка и создании надежных гарантий реализации и защиты права и свобод личности. В числе ведущих направлений развития современной правовой науки можно выделить:... | |||
74457. | Современный этап развития российской правовой науки | 14.63 KB | |
Современный этап развития российской правовой науки. Современный период российской правовой науки берет начало с 1991 г. В современный период занятие научными исследованиями проблем правовой науки является практически частным делом ученогоправоведа. Интенсивно развивается наука конституционного права предметом исследований проводимых представителями этой науки выступают проблемы и закономерности формирования и функционирования системы федеральных органов государственной власти роль конституционного правосудия в деле защиты Конституции РФ... | |||
74458. | Стадии правового исследования | 43 KB | |
На стадии целеполагания решаются главные вопросы научного исследования: что подлежит исследованию; какие позитивные результаты можно ожидать по его завершении; с помощью каких методов могут быть получены ожидаемые результаты. С учетом результатов целепологания исследователь должен трезво оценить свой творческий потенциал и быть уверенным в том что его способностей знаний и навыков владения научными методами исследования вполне достаточно для успешного завершения планируемого исследования. Подготовительная стадия научного... | |||
74459. | Уровни и формы знаний юридической науки | 53.5 KB | |
Знания об объекте правовой науки образует ее эмпирический уровень а знания о предмете теоретический уровень. При этом эмпирический уровень знания об объекте правовой науки формируется на начальных этапах познания тогда как теоретические знания составляют конечную цель и наиболее высокий результат научного познания. Вся объективная реальность представленная в объекте правовой науки исследуется ученымиправоведами а результаты исследований составляют содержание эмпирического уровня науки. | |||
74460. | Философский как основа методологии правовой науки. Общие философские методы научного познания | 14.65 KB | |
Общие философские методы научного познания. Гносеология или теория познания это учение об условиях о сущности и границах познания. Основу теории составляют проблемы соотношения субъекта объекта и содержания познания. Логика учение о последовательном и упорядоченном мышлении его элементах и общих методах познания. | |||
74461. | Функции юридической науки | 50 KB | |
Основные направления воздействия правовой науки на другие сферы гражданского общества понимаются как функции. Теоретико-методологическая функция правовой науки характеризуется тем что теоретические знания о государстве и праве и методы их познания выступают основой последующих исследований проблем данной науки обеспечивают получение новых достоверных знаний о политикоправовых явлениях и процессах. Практическая функция выражается в глубоком научном обосновании правовой наукой политикоправовой практики формулировании... | |||
74463. | Понятия и их дефиниция. Правила определения понятий | 15.29 KB | |
Понятия и их дефиниция. Объективной основой понятия могут выступать конкретные явления процессы их отдельные свойства компоненты связи которые в логике обозначаются общим понятием предмет. Содержание понятия составляет совокупность признаков благодаря которой осуществляются обобщение и выделение предмета. Это понятия правонарушение правоотношение норма права. | |||